一个编程题目,求解题思路,不要求过程,当然有过程更好,望各位高手不吝赐教!
一个尾数前移问题，如：102564
它的尾数是4；
将尾数前移得：410256；
而刚好：410256能整除102564且为4；
现在的问题是：
我们将尾数记为：p;
将尾数前移后所得数去整除原数，所得结果记为： q;(前提p能被q整除）；
从键盘输入p和q;
从屏幕输出：与之对应的原数；
输入举例：
4 4
输出举例：
102564
我对这个程序是这样实现的：
# include<stdio.h>
void main()
{
long a[11],m,n,i,j,p,q,flag,flagf=0,k;
printf("Please enter two numbers 2<=q<=p<=9!\n");
scanf("%ld%ld",&p,&q);
a[1]=p;
for(a[10]=0;a[10]<=9;a[10]++)
for(a[9]=0;a[9]<=9;a[9]++)
for(a[8]=0;a[8]<=9;a[8]++)
for(a[7]=0;a[7]<=9;a[9]++)
for(a[6]=0;a[6]<=9;a[6]++)
for(a[5]=0;a[5]<=9;a[5]++)
for(a[4]=0;a[4]<=9;a[4]++)
for(a[3]=0;a[3]<=9;a[3]++)
for(a[2]=0;a[2]<=9;a[2]++)
{
for(j=10;j>=2;j--)
{
if(a[j]!=0)
{
flag=j;
break;}
}
m=n=0;
while(j>=2)
{
for(k=1;k<=j-1;k++)
a[j]=a[j]*10;
n=n+a[j];
}
n=n+a[1];
j=flag;
while(j>=2)
{
a[j]=a[j]/10;
m=m+a[j];}
for(k=1;k<=flag-1;k++)
a[1]=a[1]*10;
m=m+a[1];
if(m%n==0)
if(m/n==q)
{
printf("%ld",n);
flagf=1;
break;}
a[1]=p;
}
if(flagf!=1)
printf("NOt found!\n");
getch();
}
下面是我的问题：
我的着个程序陷入了死循环。
但我相信这个题目肯定还有其他解法，望各位高手指教一二；
只要告诉我基本思路就可一了。 [code]
/**************************************************************
利用穷举法求这道题，方法好象愚钝了些，但暂时也就
会这种方法了。
如有不对之处，还请大家不吝指教，谢谢。
**************************************************************/
#include<Stdio.h>
#define N 999999
float wei(float a,float b)
{
if(b>10&&b<100)
return a*=100;
else if(b>99&&b<1000)
return a*=1000;
else if(b>999&&b<10000)
return a*=10000;
else
return a*=100000;
}
int main(void)
{
float p,q,a,b;
printf("请输入两个整数,空格格开，enter结束输入：\n");
scanf("%f %f",&p,&q);
for(b=10;b<N;++b)
{
a=wei(p,b);
if((a+b)/(b*10+p)==q)
{
printf("这个数字为：%f\n",b*10+p);
break;
}
}
if(b>=N)
printf("没有您要找的数字。\n");
getch();
}
[/code] p和q的范围是什么？
[img]http://blog.programfan.com/upfile/200804/20080430094836.gif[/img][color=white] [quote][bo]以下是引用 [un]雨中飛燕[/un] 在 2008-5-11 23:30 的发言：[/bo]
p和q的范围是什么？
[/quote]
~~~~~~~~~~~~~`
实在是对不起，这道题我头回见到，所以对它很不了解，所以所用的例子就是用到LZ所用的4、4，结果也是用LZ提供的。我输入5、5，6、6全不行。
我想这题应该有很成熟的解法与算法，我的代码也算是抛砖引玉吧。 for(a[10]=0;a[10]<=9;a[10]++)
for(a[9]=0;a[9]<=9;a[9]++)
for(a[8]=0;a[8]<=9;a[8]++)
for(a[7]=0;a[7]<=9;a[9]++)
for(a[6]=0;a[6]<=9;a[6]++)
for(a[5]=0;a[5]<=9;a[5]++)
for(a[4]=0;a[4]<=9;a[4]++)
for(a[3]=0;a[3]<=9;a[3]++)
for(a[2]=0;a[2]<=9;a[2]++)
*********************************
是我愚昧还是你弄错，常数也能做“++” 运算？
回复 5# 的帖子
其实他用这么多的for本身就是错误的行为——我觉得。 我真服了楼上的这些兄弟姐妹们了
我根本就看不懂了! 这个题不错，我暂时保留一下我的答案
其中：
5 5 的结果是：
102040816326530612244897959183673469387755
而 6 6 的结果是：
1016949152542372881355932203389830508474576271186440677966
还有 7 5 的结果是：
142857
[img]http://blog.programfan.com/upfile/200804/20080430094836.gif[/img][color=white] 其实不必一定整除亦可
[img]http://blog.programfan.com/upfile/200804/20080430094836.gif[/img][color=white]
回复 8# 的帖子
你所求的数值太大了，我目前的知识无法将它求出来。 广陵兄，任何事情要认真分析以后才下结论。这道题其实很简单的。根据LZ的叙述，我们可以得出式子，其中n是m的位数。m是所求的数字。
p*10^n+m
---------=q
m*10+p
这个式子，p，q已知，n可以根据m算出来。似乎已经解决了：枚举m即可。但是从飞燕的结果来看，枚举m显然是不行的。因为位数太多。这时我们可以反其道而求之。我们先假设n已知，把m解出来：
p*10^n+m=10qm+pq
p*10^n=(10q-1)m+qp
m=(10^n-q)p/(10q-1)
这样，我们直接枚举n，然后就可以针对每个n求出一个m。但是除法不一定是整除。那么问题转变为：求最小的n，使上式得出的m为整数。同时m的位数为n。
枚举n的话，问题的复杂度就可以大大降低了。
这道题还需要大数运算的知识，大数除法，整除判断等我还没做过。查完了资料再来看这道题。 飞燕真的很强，一个小时可以写出算法并算出结果。要是我肯定做不到……基础啊………………欠缺基础…… 额……百度到两种大数除法的方法，一种是模拟手算，还有一种是用减法和移位实现……想想再说…… 楼上，你说的方法不好，还不是我所用的方法
还有，假如尾数不一定是一个位，比如是10，要是6的倍数，
那么结果是：
01669449081803005008347245409015025041736227045075125208681135225375626043405676126878130217028380634390651085141903171953255425709515859766277128547579298831385642737896494156928213689482470784641068447412353923205342237061769616026711185308848080133555926544240400667779632721202003338898163606010
（最高位的0必须要保留。。。）
[img]http://blog.programfan.com/upfile/200804/20080430094836.gif[/img][color=white] [quote][bo]以下是引用 [un]hjh10845[/un] 在 2008-5-12 00:03 的发言：[/bo]
for(a[10]=0;a[10] [/quote]
a[10]是变量 怎么会是常数呢？ 貌似不用那么复杂，我就说LZ的原始数据
最后一位（尾数）是4，并且把4挪走了以后新数变成原来的4倍，4*4=16，那么新数的个位必定是6还要往高位进一，也就是说原数的十位是6。然后6*4=24，那么新数十位（原数百位）就是24的那个4再加上刚才从后边进上来的1，也就是5，再往更高位进2（24的十位）......
往前递推就可以了。
我这么说不知道说清楚了没有？
假设p,q都是1位数：
[code]#include <stdio.h>
int main()
{
int a[1000]={0};
int p,q,jin,i;
scanf("%d%d",&p,&q);
a[0]=p;
i=1;
while(1)
{
jin=a[i-1]*q;
if(p==a[i]+jin)
{
i--;
break;
}
a[i]+=jin%10;
a[i+1]+=jin/10;
i++;
}
while(--i+1)
printf("%1d",a[i]);
printf("\n");
return 0;
}[/code]
[[it] 本帖最后由 forever74 于 2008-5-12 12:24 编辑 [/it]] 恩……递推复杂度的确比枚举低……Orz……
话说，枚举也不高吧？假设答案是m位，枚举也只需要枚举m次而已，每次一次减法，一次乘法，一次除法……
而且并不需要强制规定p是一位，可以稍微改改公式就够了。
前面的0我的方法也可以解决，如果n和m位数不同的话，前补0. 啊……递推其实不需要用到大数运算……Orz……我错了…… 16楼的代码要是输入 06896551724137931 2 呢？
注意最高位为0的情况（这时是有用的，占位）
[img]http://blog.programfan.com/upfile/200804/20080430094836.gif[/img][color=white] 飞燕，我的5 5的运行结果是：
10204081632653061224489795918367305
经验算也是正确的，但是比你的小……