当前位置: 代码迷 >> C语言 >> [求助]这是一个关于回数的程序,是我们的作业 ,可是却做不出来
  详细解决方案

[求助]这是一个关于回数的程序,是我们的作业 ,可是却做不出来

热度:147   发布时间:2007-11-09 17:37:56.0
以下是引用Eastsun在2007-11-8 21:57:18的发言:
可以证明: 除了11,不存在偶数位的素数回文数
so,qq95620412的代码还可以优化,另外,素数判断的代码还可以进一步优化.

可以证明给我看看吗?


----------------解决方案--------------------------------------------------------
以下是引用qq95620412在2007-11-9 17:37:56的发言:

可以证明给我看看吗?


偶数位的回文数都能被11除。
你可以把每个偶数为的回文数除以 11

101101 / 11 == 9191;

或你看看你的那个程序生成的回文数,素数偶数位回文只有 11 。


你的程序很好

[此贴子已经被作者于2007-11-9 18:00:51编辑过]


----------------解决方案--------------------------------------------------------

long int nexthuiwen(long int currenthuiwen)
//输入:一个回文数
//输出:比当前回文数大的最小回文数
{
long int i=currenthuiwen,m;
int weishu=0; //数字的位数
long int j=0;
// printf("当前回文数是:%ld\n",i);

while(i>0) //求出数值的位数
{
i=i/10;
weishu+=1;
}

if(weishu==1) //求出规整前的新数
{
currenthuiwen+=1;
}
else
{
currenthuiwen+=pow10(weishu/2);
currenthuiwen=currenthuiwen-currenthuiwen%pow10(weishu/2);
}
// printf("新数为:%ld\n",currenthuiwen);

i=currenthuiwen; //求出规整前数值的位数
weishu=0;
while(i>0)
{
i=i/10;
weishu+=1;
}

for(j=1;j<=weishu/2;j++) //规整新数
{
m=currenthuiwen/(long int)pow10(weishu-j)%10*(long int)pow10(j-1);
// printf("%ld\n",m);
currenthuiwen+=m;
}
// printf("新的回文数是: %ld\n",currenthuiwen);
return currenthuiwen;
}

有人能给出这个函数是如何计算下一个回文数的吗?
看不懂啊。


----------------解决方案--------------------------------------------------------

#include<stdio.h>
#include<math.h>
#include<time.h>

#define MAX 1000000000
#define MIN 101 //最小的3为回文数

long int pow10(int i)
{
long int result=1;
while(i>0)
{
result*=10;
i--;
}
return result;
}

long int nexthuiwen(long int currenthuiwen)
//输入:一个回文数
//输出:比当前回文数大的最小回文数
{
long int i=currenthuiwen,m;
int weishu=0; //数字的位数
long int j=0;
// printf("当前回文数是:%ld\n",i);

while(i>0) //求出数值的位数
{
i=i/10;
weishu+=1;
}

if(weishu==1) //求出规整前的新数
{
currenthuiwen+=1;
}
else
{
currenthuiwen+=pow10(weishu/2);
currenthuiwen=currenthuiwen-currenthuiwen%pow10(weishu/2);
}
// printf("新数为:%ld\n",currenthuiwen);

i=currenthuiwen; //求出规整前数值的位数
weishu=0;
while(i>0)
{
i=i/10;
weishu+=1;
}

for(j=1;j<=weishu/2;j++) //规整新数
{
m=currenthuiwen/(long int)pow10(weishu-j)%10*(long int)pow10(j-1);
// printf("%ld\n",m);
currenthuiwen+=m;
}
// printf("新的回文数是: %ld\n",currenthuiwen);
return currenthuiwen;
}


long int nexthuiwen_youhua(long int currenthuiwen)
//声明:按cosdos Eastsun版主的建议,将函数功能进行适当修改,以减少运行时间
//输入:一个位数为奇数的奇数回文数
//输出:比当前回文数大的位数为奇数的最小奇数回文数
//例如:19291 ->19391 39993->50005 99999->1000001
//编程思路: 1.先求出原回文数的位数 如:19291的位数为5
// 2.将回文数的最中间位数的数值加1 即 39993->40093,若新数为偶数位数,则乘以10 ,若首位为偶,则首位+1,得到规整前的新数
// 3.规整新数,将新数的右对称分支改为0 即 40093->40000
// 4.求出新数的右对称分支,加到该数上 即 40000->40004
// 5.返回新的回文值
{
long int i=currenthuiwen,m;
int weishu=0; //数字的位数
long int j=0;
// printf("当前回文数是:%ld\n",i);

while(i>0) //求出数值的位数
{
i=i/10;
weishu+=1;
}

if(weishu==1) //求出规整前的新数
{
currenthuiwen+=1;
}
else
{
currenthuiwen+=pow10(weishu/2);
currenthuiwen=currenthuiwen-currenthuiwen%pow10(weishu/2);
}

i=currenthuiwen; //求出规整前数值的位数
weishu=0;
while(i>0)
{
i=i/10;
weishu+=1;
}
if(weishu%2==0) //若位数为奇数,则 *10
{ currenthuiwen*=10;
weishu++;
}
if(currenthuiwen/pow10(weishu-1)%2==0) //若首位是偶数,则首位+1
{
currenthuiwen+=pow10(weishu-1);
}
// printf("规整前新数为:%ld\n",currenthuiwen);

for(j=1;j<=weishu/2;j++) //规整新数
{
m=currenthuiwen/(long int)pow10(weishu-j)%10*(long int)pow10(j-1);
// printf("%ld\n",m);
currenthuiwen+=m;
}
// printf("新的回文数是: %ld\n",currenthuiwen);
return currenthuiwen;
}


int sushu_youhua(long int data)
//声明:按cosdos Eastsun版主的意思,进行了优化
//输入:任意非偶长整数
//输出:若该整数为素数,则输出1,否则输出0

{
long int end=(long int)sqrt(data);
long int i;
for(i=3;i<=end;i+=2) //读者可以考虑以下为什么不写成 i++
{
if(data%i==0)return 0;
}
return 1;
}


int main(void)
{
long int data=MIN;
clock_t start,end;
start=clock();
printf("3\n5\n7\n11\n");
while(data<=MAX)
{
if(sushu_youhua(data))
{
printf("%ld\n",data);
}
data=nexthuiwen_youhua(data);
}
end=clock();
printf("%lf\n",(double)((end-start)/CLOCKS_PER_SEC));
getchar();
return 0;
}


[此贴子已经被作者于2007-11-10 20:13:19编辑过]


----------------解决方案--------------------------------------------------------
运行了一下

输出到屏幕时 2秒
输出到文件时 0秒
----------------解决方案--------------------------------------------------------
呵呵,不错~
----------------解决方案--------------------------------------------------------
  相关解决方案