主题：第三十一次编程比赛第二题题目
boxertony [专家分：23030] 发布于 2006-06-15 20:33:00
整数变换问题。关于整数i的变换f和变换g的定义如下：f(i)=3i; g(i)=└i/2┘。试设计一个算法，对于给定的两个整数n和m，用最少的f和g变换次数将n变换为m。例如，可以将整数15用4次变换为整数4，即4=gfgg(15)。
具体变换如下：g(15)=7 g(7)=3 f(3)=9 g(9)=4
// f函数
inline int f(int i)
{
return 3*i;
}
// g函数
inline int g(int i)
{
return (i>>1);
}
// 函数接口
// [in]n -- 待转换正整数 (0<n<=1000)
// [in]m -- 目标正整数 (0<m<=1000)
// [out]fs -- 存放转换步骤，比如 15=>4 为 "gfgg" （请一定加上字符串结束标志符'\0'）
// [return]-- 转换的最少步数（当无解时，返回INT_MAX）
int transform(int n, int m, char *fs);
char *getid(char *id)
{
return strcpy(id, "boxertony"); // 请用自己的id替换掉"boxertony"
}
回复列表 （共16个回复）
11 楼
int0x080 [专家分：90] 发布于 2006-06-17 14:41:00
可能是最慢的了 *___*
[code]
char *
getid(char *id)
{
return strcpy(id, "int0x080");
}
[/code]
[code]
int
transform(int n, int m, char *fs)
{
const int MAX (INT_MAX / 3);
if (n == m) {
fs = '\0';
return 0;
}
list< pair<int,int> > l;
l.push_back( pair<int,int>( -1, n ) );
list< pair<int,int> >::const_iterator itb( l.begin()), ite(l.end() );
int step( 0 );
for(int b( 0 ); --ite,++step; ite=l.end() ){
bool flag(false);
set<int> filter;
do{
++b;
int temp( ((*itb).second<0)?-((*itb).second):(*itb).second );
if( temp && MAX > temp ){
int r( f(temp) );
if( 0 == filter.count( r ) ){
filter.insert( r );
l.push_back( pair<int,int>( l.size()+1-b,r ) );
if( r == m )goto ret;
flag = true;
}
r = g( temp );
if( 0 == filter.count( r ) ){
filter.insert( r );
l.push_back( pair<int,int>( l.size()+1-b,-r ) );
if( r == m )goto ret;
flag = true;
}
}
}while( itb++ != ite );
if (false == flag)return INT_MAX;
}
ret:
list< pair<int,int> >::const_iterator it(l.end());
for(--it; -1!=(*it).first; ){
int loop((*it).first);
*fs++ = (0>(*it).second)?'g':'f';
while(loop--)
--it;
}
*fs = '\0';
return step;
}
[/code]
12 楼
天国龙 [专家分：490] 发布于 2006-06-17 15:21:00
//自己增加两个逆向的函数
inline int g1(int i)
{
if (i)
return (i<<1);
else return 0;
}
inline int f1(int i)
{
if (i%3==0)
return i/3;
else return 0;
}
int transform(int n, int m, char *fs)
{
unsigned int *t;
unsigned int *t1;
unsigned int max(2147483647);
short int maxt(16383);
short int maxt1(19683);
t=new unsigned int[maxt];
if (!t)
{
cout<<"Can't using space!"<<endl;
return max;
}
int tij;
t[0]=n;
char str[24];
char str1[11];
int i(0),j(0),i1(0),tf(0);
while (*(t+i)!=m)
{
i++;
tij=(i-1)>>1;
if (i>=maxt)
break;
if (i%2==0)
*(t+i)=f(*(t+tij));
else *(t+i)=g(*(t+tij));
}
if (i>=maxt)
{
t1=new unsigned int[maxt1];
if (!t1)
{
cout<<"Can't using space!"<<endl;
return max;
}
*t1=m;
tf=1;
while (!(*(t1+j)==*(t+i) && *(t1+j)!=0))
{
j++;
tij=(j-1)/3;
if (j>=maxt1)
break;
if (j%3==0)
*(t1+j)=f1(*(t1+tij));
else if (j%3==1)
*(t1+j)=g1(*(t1+tij));
else *(t1+j)=*(t1+tij)?(g1(*(t1+tij))?g1(*(t1+tij))+1:0):0;
i=maxt>>1;
if (*(t1+j))
while (*(t1+j)!=*(t+i))
if (++i>=maxt)
break;
}
}
if (j<maxt1)
{
if (j)
for(;j;j=(j-1)/3)
*(str1+i1++)=j%3?'g':'f';
for (;i1;)
*(str+j++)=*(str1+(--i1));
for(;i;i=(i-1)>>1)
*(str+j++)=i%2?'g':'f';
str[j]='\0';
strcpy(fs,str);
}else return max;
delete t;
if (tf) delete t1;
return j;
}
char *getid(char *id)
{
return strcpy(id, "天国龙");
}
//说明：这段代码只要在22次及以内转换有解就能返回最少步数，
//超出22次才有解的视为无解，但是我用随机数测试100次用了7秒
//多,由于楼住没有说明怎么才算无解(理论上任意一个数都可以
//经过有限次g或f转换为另一个数)，当要求视为无解的次数越小
//这段代码的速度越快(每要求小一次可提高1.5-3倍的速度),
//例如设定超出21次即视为无解则我的代码测试100次用时为5秒
//多点，我的代码减少次数的方法:每用一次maxt/=2或maxt1/=3即
//可减少一次,当代码提示:Can't using space!表明无法开辟数组
//空间请楼主添上一次maxt/=2或maxt1/=3。
13 楼
bvor [专家分：0] 发布于 2006-06-17 22:36:00
#include<iostream>
#include<math.h>
using namespace std;
inline int f(int i)
{
return 3*i;
}
inline int g(int i)
{
return (i>>1);
};
void path(int i,int j,char *strpath)
{
if(i==0)return;
j%2==0?strpath[i-1]='f':strpath[i-1]='g';
path(i-1,j/2,strpath);
}
int transform(int n, int m, char *fs)
{
if(n<0||m<0){strcpy(fs,"n和m不能小于零\0");return -1;}
if(m==n){strcpy(fs,"不需要变换\0");return 0;}
for(int step=1;step>=0;step++)
{
char *strpath;
strpath=new char[step];
if(strpath==NULL){strcpy(fs,"内存分配失败\0");return -1;}
for(int j=0;j<(int)pow(2,step);j++)
{
int to=n;
path(step,j,strpath);
for(int length=0;length<step;length++)
{
strpath[length]=='f'?to=f(to):to=g(to);
}
if(to==m){
for(int every=0;every<step;every++)
fs[every]=strpath[step-every-1];
fs[every]='\0';
return step;
}
}
delete strpath;
}
strcpy(fs,"不存在\0");return -1;
}
int main()
{
int m,n,step;
char fs[1000]="\0";
n=1;
m=100;
step=transform(n,m,fs);
cout<<"最小步数为:"<<step<<"\n"<<"步骤为:"<<fs<<endl;
return 0;
}
14 楼
goal00001111 [专家分：4030] 发布于 2006-06-17 23:10:00
int transform(int n, int m, char *fs)
{
const int MAX = 50; //希望最大步数不要超过MAX，若步数较大，请修改MAX，但速度变慢
char *cfs;
if (!(cfs = new char[MAX+1]))
{
cout << "fail!\n";
exit(1);
}
int min = MAX;
Solve(n, m, fs, cfs, 0, min);
delete []cfs;
min = (min < MAX) ? min : INT_MAX;
return min;
}
void Solve(int n, int m, char fs[], char cfs[], int top, int & min)
{
if (n == m || top == min)
{
if (top < min)
{
min = top;
for (int i=0; i<top; i++)
fs[i] = cfs[top-i-1];
fs[top] = '\0';
}
return;
}
int cn = g(n);
if (cn > 0)
{
cfs[top] = 'g';
Solve(cn, m, fs, cfs, top+1, min);
}
cn = f(n);
if (cn > 0)
{
cfs[top] = 'f';
Solve(cn, m, fs, cfs, top+1, min);
}
}
char *getid(char *id)
{
return strcpy(id, "goal00001111"); // 请用自己的id替换掉"boxertony"
}
15 楼
pigeonoo [专家分：130] 发布于 2006-06-18 09:18:00
char *getid(char *id)
{
return strcpy(id, "pigeonoo"); // 请用自己的id替换掉"boxertony"
}
int transform(int n, int m, char *fs)
{
int max=0;
if(n==m) return max;
if (n>m)
{
max=transform(g(n),m,fs)+1;
int m=strlen(fs),i=0;
fs[m+1]='\0';
for (i=m;i>0;i--)
fs[i]=fs[i-1];
fs[0]='g';
}
else
{
max=transform(f(n),m,fs)+1;
int m=strlen(fs),j=0;
fs[m+1]='\0';
for (j=m;j>0;j--)
fs[j]=fs[j-1];
fs[0]='f';
}
return max;
}
16 楼
boxertony [专家分：23030] 发布于 2006-06-18 12:06:00
时间到。
我来回复
您所在位置：