终于弄的满意些了
不过好长,判断的分支太多了
/*
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;
}