[求助]请点明下解题思路
对于整数 x ，现在有两种变换: f(x)= 3*x , g(x)= x / 2 ;（这里的 x / 2 ，同c语言里的 / 运算符，结果只取整数部分） 对于给定的两个正整数 N 和 M ,可以通过这两个变换的一系列组合来使 N 变成 M .而且这些变换中有一些变换是最优的,即所需的变换次数最少. 比如 15 变成 4 ，只需要 4 次变换。即：gfgg(15) = 4
注意:gfgg(15)表示g(f(g(g(15)))),变换顺序是从右到左的.
Input
输入数据第一行为正整数T 。表示下面有T 组测试数据。下面 2 到 T + 1 行 ，每行包括两个正整数 N，M ( 0 <= N , M <= 50).测试数据中的N M都是能变换的.
Output
输出数据每组包括三行:第一行为编号"Case #A:",A表示第几组数据.第二行为最优解的变换次数(即最少的变换次数).第三行为最优解的个数.
每组数据之间空一行。
----------------解决方案--------------------------------------------------------
我的想法是：temp = M;
if (temp > N）
{
g(temp);
}
if (temp < N)
{
f(temp);
}
直到 temp与N相等，不知道对不对？
----------------解决方案--------------------------------------------------------
脑筋转不动了，
----------------解决方案--------------------------------------------------------
貌似DP.晚上再想想.
----------------解决方案--------------------------------------------------------
/*
m,n<50
if(n>4*m) g(n)=n/2
if(9*n<m) f(n)=3*n
9 15
3*9= 27
27/2=13
13*3=39
39/2=19
19/2=9 又回到了9了 为了防止此现象发生，用s[Max]数组
s[Max] 存放1--1000的状态s[]=0表示没出现过 s[]=1表示对此数*3了 s[]=2表示对此数/2了
n如果比m大那么：如果它在m*pow(2,i)>=n && n<(m+1)*pow(2,i),那么它到m的最快步数是i
n如果比m小那么：如果它在
*/
#include <stdio.h>
#include <iostream.h>
#include <math.h>
#define Max 20000
long sum, m, min, s[Max][2]={0}, big, kk[50]; //sum=有多少个最优可能 m要转换成的数 min=最优步数
long pda(long a) //判断目前的n是否在m*pow(2,i)>=n && n<(m+1)*pow(2,i)之间
{
long i, b = m;
for(i = 1; b < a; i++)
b *= 2;
i -= 1;
if(a == b) //如果m*pow(2,i)==a，那么此时 a 到 m 的最短步数就是 i
return i;
else
{
i -= 1;
if(a < (m+1) * (int)pow(2, i))
return i; //在范围之内，那么 a 到 m 的最少步数就是 i
else
return 0; //不在范围之内，要考虑是/2 还是*3
}
return 0;
}
long js(long b, char a, long st) //a=f-->f(b) a=g-->g(b) st=steps
{
long t = b, i, j, temp;
if(t > big && min == 0) //判断上限这里还需要改进，基本方法已经确定了
big = t;
if(t > 1000 && min)
return t;
if(a == 'f') //f f() *3的操作
{
s[t-1][0] = 1;
if(st<=s[t-1][1] || s[t-1][1]==0)
s[t-1][1] = st;
else
{
return b;
}
st++;
t *= 3;
}
else if(a == 'g')
{
s[t-1][0] = 2;
if(st<=s[t-1][1] || s[t-1][1]==0)
s[t-1][1] = st;
else
{
return b;
}
st++;
t =(int)t/2;
}
kk[st] = t;
if(st <= min || min ==0) //如果当前的步数小于min或min==0 则继续
{
if(t > m)
{
i = pda(t); //判断 t 是否可以通过 /2 到 m
if(i > 0) //如果可以一直 /2 到 m
{
if(min == 0 || (st + i) <= min) //如果找到了
{
if(min > (st + i) || 0 == min)
{
min = st + i;
sum = 1;
}
else
sum++;
printf("\n");
for(temp = 0; temp < st+1; temp++)
printf("%d ", kk[temp]);
printf(" %d min = %d\n", sum,min);
}
else
return 0;
}
else //不能一直 /2 到 m 的话 继续优先g()
{
if(s[t-1][0] == 0)
{
js(t, 'g', st);
js(t, 'f', st);
}
else
return t;
}
}
else if(t < 2 && t != m)
{
js(t, 'f', st);
}
else if(t < m)
{
for(i = 1, j = t; j < m; i++)
j *= 3; //看看乘多少次 3 可以到 m
i--;
if(j == m)
{
if(0 == min || (st + i) <= min)
{
if(min > (st + i) || 0 == min)
{
min = st + i;
sum = 1;
}
else
sum++;
printf("\n");
for(temp = 0; temp < st+1; temp++)
printf("%d ", kk[temp]);
printf(" %d min = %d\n", sum,min);
}
else
{
return t;
}
}
else
{
if(s[t-1][0] == 0)
{
js(t, 'f', st);
js(t, 'g', st);
}
else
return t;
}
}
else //如果转换到了目标值
{
if(st < min || min == 0) //找到了更优的步数
{
min = st;
sum = 1;
cout << endl;
for(temp = 0; temp < min; temp++)
cout << kk[temp] << " ";
}
else if(st == min)
{
sum++; //
cout << "又找到一个" << endl;
for(temp = 0; temp < min; temp++)
cout << kk[temp] << " ";
}
}
}
else //发现此时的步数比纪录的大就放弃 返回
{
return b;
}
return t; //如果返回0的话就终止本次递归
}
long main()
{
long k[10][2], i, j, xh, temp, b;
scanf("%d", &i);
j = i;
while(i--)
{
scanf(" %d%d", &k[i][0], &k[i][1]);
if(k[i][1] > 50 || k[i][0] > 50)
i++;
}
for(i = j ; i--;)
{
sum = min = big =0;
for(xh = 0; xh < Max ;xh++)
s[xh][0] = s[xh][1] = 0;
m = k[i][1];
kk[0] = k[i][0];
if(k[i][0] > m)
{
temp = pda(k[i][0]);
if(temp > 0)
{
min = temp;
sum = 1;
}
else
{
temp = js(k[i][0], 'g', 0);
temp = js(k[i][0], 'f', 0);
}
}
else if(k[i][0] < m)
{
for(temp=0, b=k[i][0]; b < m; temp++)
b *= 3;
if(b == m)
{
min = temp;
sum = 1;
}
else
{
js(k[i][0], 'f', 0);
js(k[i][0], 'g', 0);
}
}
else
{
js(k[i][0], 'g', 0);
js(k[i][0], 'f', 0);
}
printf("Case #%d\n%d\n%d\n", j-i, min, sum);
}
return 0;
}
[此贴子已经被作者于2007-5-11 14:21:15编辑过]
----------------解决方案--------------------------------------------------------
把Max定义到1000，50以下的基本都可以算出来，这办法有点笨，期待更好的办法
----------------解决方案--------------------------------------------------------
终于弄的满意些了不过好长，判断的分支太多了
/*
m,n<50
9 15
3*9= 27
27/2=13
13*3=39
39/2=19
19/2=9 又回到了9了 为了防止此现象发生，用s[Max]数组
s[Max][3] 存放1000次转换过程中出现的数字状态s[max][0]=0表示没出现过 =2表示对此数/2了 =1表示对此数*3了
s[max][1] 代表到此数时用的步数 s[max][2] 代表转换过程中的数字
n如果比m大那么：如果它在m*pow(2,i)>=n && n<(m+1)*pow(2,i),那么它到m的最快步数是i
*/
#include <stdio.h>
#include <iostream.h>
#include <math.h>
#define Max 1000
unsigned long s[Max][3]={0}, kk[Max]; //kk[Max]里存放转换过程中的数字
int sum, m, min; //sum=有多少个最优可能 m要转换成的数 min=最优步数
int search(unsigned long a) //在数组里找a的位置
{
int i;
for(i = 0;(s[i][2] > 0) && (i < Max); i++)
{
if(s[i][2] == a)
break;
}
if(i < Max)
{
s[i][2] = a;
return i;
}
else
return -1;
}
int pda(unsigned long a) //判断目前的n是否在m*pow(2,i)>=n && n<(m+1)*pow(2,i)之间
{
int i;
unsigned long b = m;
for(i = 1; b < a; i++)
b *= 2;
i -= 1;
if(a == b) //如果m*pow(2,i)==a，那么此时 a 到 m 的最短步数就是 i
return i;
else
{
i -= 1;
if(a < (m+1) * (unsigned long)pow(2, i))
return i; //在范围之内，那么 a 到 m 的最少步数就是 i
else
return 0; //不在范围之内，要考虑是/2 还是*3
}
return 0;
}
void js(unsigned long b, char a, int st) //a=f-->f(b) a=g-->g(b) st=steps
{
unsigned long t = b;
int i, j, temp, wz; //wz=b在数组s[Max][2]里的位置
wz = search(t);
if(wz < 0 && 0 == min)
{
printf("Max定义的太小了,有些可能的组合被忽略！\n");
return;
}
if(a == 'f') //f f() *3的操作
{
s[wz][0] = 1;
if(st <= s[wz][1] || s[wz][1] == 0)
s[wz][1] = st;
else
{
return;
}
st++;
t *= 3;
}
else if(a == 'g')
{
s[wz][0] = 2;
if(st <= s[wz][1] || s[wz][1] == 0)
s[wz][1] = st;
else
{
return;
}
st++;
t =(int)t/2;
}
wz = search(t); //查找t在s[][]中的位置
if(wz < 0 && 0 == min)
{
printf("Max定义的太小了,有些可能的组合被忽略！\n");
return;
}
kk[st] = t;
if(st <= min || min ==0) //如果当前的步数小于min或min==0 则继续
{
if(t > m)
{
i = pda(t); //判断 t 是否可以通过 i 次 /2 到 m
if(i > 0) //如果可以一直 /2 到 m
{
if(min == 0 || (st + i) <= min) //如果找到了
{
if(min > (st + i) || 0 == min)
{
min = st + i;
sum = 1;
}
else
sum++;
/*///////////////////////////////////此段可以看到转换过程
printf("\n");
for(temp = 0; temp < st+1; temp++)
printf("%d ", kk[temp]);
printf(" %d min = %d\n", sum,min);
*////////////////////////////////////////////////////////
}
else
return;
}
else //不能一直 /2 到 m 的话 继续优先g()
{
if(s[wz][0] == 0)
{
js(t, 'g', st);
js(t, 'f', st);
}
else
return;
}
}
else if(t < 2 && t != m) //如果转化中出现1 1不能/2就只能 f()
{
js(t, 'f', st);
}
else if(t < m)
{
for(i = 1, j = t; j < m; i++)
j *= 3; //看看乘多少次 3 可以到 m
i--;
if(j == m)
{
if(0 == min || (st + i) <= min)
{
if(min > (st + i) || 0 == min)
{
min = st + i;
sum = 1;
}
else
sum++;
/*///////////////////////////////////此段可以看到转换过程
printf("\n");
for(temp = 0; temp < st+1; temp++)
printf("%d ", kk[temp]);
printf(" %d min = %d\n", sum,min);
*////////////////////////////////////////////////////////
}
else
{
return;
}
}
else
{
if(s[wz][0] == 0)
{
js(t, 'f', st);
js(t, 'g', st);
}
else
return;
}
}
else //如果转换到了目标值
{
if(st < min || min == 0) //找到了更优的步数
{
min = st;
sum = 1;
/*///////////////////////////////////此段可以看到转换过程
cout << endl;
for(temp = 0; temp < min; temp++)
cout << kk[temp] << " ";
*////////////////////////////////////////////////////////
}
else if(st == min)
{
sum++; //
/*///////////////////////////////////此段可以看到转换过程
cout << endl;
for(temp = 0; temp < min; temp++)
cout << kk[temp] << " ";
*////////////////////////////////////////////////////////
}
}
}
else //发现此时的步数比纪录的大就放弃 返回
{
return;
}
return; //返回终止本次递归
}
long main()
{
long k[10][2], i, j, xh, temp, b;
scanf("%d", &i);
j = i;
while(i--)
{
scanf(" %d%d", &k[i][0], &k[i][1]);
if(k[i][1] > 50 || k[i][0] > 50)
i++;
}
for(i = j ; i--;)
{
sum = min = 0;
for(xh = 0; xh < Max ;xh++)
s[xh][0] = s[xh][1] = s[xh][2] = 0;
m = k[i][1];
kk[0] = k[i][0];
if(k[i][0] > m)
{
temp = pda(k[i][0]);
if(temp > 0)
{
min = temp;
sum = 1;
}
else
{
js(k[i][0], 'g', 0);
js(k[i][0], 'f', 0);
}
}
else if(k[i][0] < m)
{
for(temp=0, b=k[i][0]; b < m; temp++)
b *= 3;
if(b == m)
{
min = temp;
sum = 1;
}
else
{
js(k[i][0], 'f', 0);
js(k[i][0], 'g', 0);
}
}
else
{
js(k[i][0], 'g', 0);
js(k[i][0], 'f', 0);
}
printf("Case #%d \n%d \n%d \n\n", j-i, min, sum);
}
return 0;
}
----------------解决方案--------------------------------------------------------