PKU POJ 1142 Smith Numbers 一道简单的题

 

http://acm.pku.edu.cn/JudgeOnline/problem?id=1142 

以前就用pascal做过这道题，C再做一遍 

 1#include <stdio.h> 
 2#include <math.h> 
 3#include <memory.h> 
 4long int re(long int a)              //re函数功能：返回一个数各位数字相加的和 
 5{ 
 6long int s=a; 
 7int result=0; 
 8int wei=int (log(a)/log (10))+1; //换底公式 ，得到位数 
 9int r=0; 
10for (r=1;r<=wei;r++) 
11{ 
12  result=result+a%10;           //每一位相加 
13  a=a/10;                         
14} 
15return result;                    //返回结果 
16} 
17void tryx(long int r)                 //主过程 
18{ 
19int j,i=0,result=0; 
20long int w=r;                        //w用于保存原始的r值 
21long int number[32]; 
22memset (number,0,sizeof (number)); 
23long int e=2; 
24while (e<=int (sqrt(r)))            //分解出质因数，并存放到number[]中 
25{ 
26  if (r%e==0)                     //找到一个质因数 
27  { 
28   r=r/e; 
29   number[i]=e; 
30   e=2;                        //重新初始化e 
31   i++; 
32  } 
33  else 
34  { 
35   e++; 
36  } 
37} 
38number[i]=r;                         //r是最后一个数 
39
40for (j=0;j<=i;j++) 
41{ 
42  result=result+re(number[j]); 
43} 
44
45if ((result==re(w))&&(r!=w)) //如果质因数各位相加的结果等于w各位数字相加的结果，且质因数不等于w本身 ，输出 
46  printf("%d\n",w); 
47else 
48  tryx (w+1); 
49} 
50void main() 
51{ 
52long int snumber=0;                   
53scanf("%d",&snumber); 
54while (snumber!=0) 
55{ 
56  tryx (snumber+1); 
57        scanf("%d",&snumber);   
58} 
59} 
60



思考： 
    1.  用换底公式求位数 是一个不错的通用技巧。 
    2.  既然编译器是用的VC++6.0 ,那么完全可以使用纯C和C++的iostream混合编程。下次尝试一下。 
    3.  分解质因数这种最基本的“公式型”算法要熟练 ，，时间是宝贵的。

posted on 2007-09-14 02:08 流牛ζ木马 阅读(1750) 评论(5)  编辑 收藏 引用

评论

# re: PKU POJ 1142 Smith Numbers 一道简单的题 2008-01-17 10:12 anonymous

用换底公式求位数，有必要吗？

result=0;
while(a)
{
result+=a%10;
a/=10;
}

  回复  更多评论   

# re: PKU POJ 1142 Smith Numbers 一道简单的题 2008-05-09 16:21 Pho

貌似的确是多此一举  回复  更多评论   

# re: PKU POJ 1142 Smith Numbers 一道简单的题 2008-10-25 19:42 hz

我觉得会超时  回复  更多评论   

# re: PKU POJ 1142 Smith Numbers 一道简单的题 2009-08-25 08:35 wsk

e怎么没有验证是不是素数呢？  回复  更多评论   

# re: PKU POJ 1142 Smith Numbers 一道简单的题 2010-02-07 07:43 lolihunter

@wsk
if ((result==re(w))&&(r!=w))
r!=w就能剔除素数  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


<2011年8月>
日一二三四五六
31123456
78910111213
14151617181920
21222324252627
28293031123
45678910

导航

统计

公告

MY Email/MSN :mars1021@163.com QQ : 27402040 流牛ζ木马

常用链接

留言簿(6)

随笔档案

相册

搜索

最新随笔

最新评论

阅读排行榜

评论排行榜