基础强化报告新编范本.doc

附件1：学 号： 0121210680529课 程 设 计（基础强化训练）题 目Smith Numbers学 院计算机科学与技术专 业软件工程班 级Zy1202姓 名胡小意指导教师段鹏飞2014年7月11日课程设计任务书学生姓名： 胡小意 专业班级： 软件zy1202 指导教师： 段鹏飞 工作单位：计算机学院题 目: Smith Numbers 初始条件：输入： The input file consists of a sequence of positive integers, one integer per line. Each integer will have at most 8 digits. The input is terminated by a line containing the number 0.输出： For every number n 0 in the input, you are to compute the smallest Smith number which is larger than n,and print it on a line by itself. You can assume that such a number exists.要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、完成算法分析2、给出对应的程序流程图3、给出能正确实现的程序源码5、给出试算截屏图6、课程设计工作的分析与总结7、给出不少于5篇参考文献。时间安排： 2014-7-7到2014-7-11指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日目录1 注册资料42 选题描述43 算法分析53.1 构造逐位相加之和函数53.2 求史密斯数54 程序流程图65 程序源码86 试算截屏图97 分析与总结98 参考文献91 注册资料用户名：huxiaoyi密码：123456789选题题号：11422 选题描述 DescriptionWhile skimming his phone directory in 1982, Albert Wilansky, a mathematician of Lehigh University,noticed that the telephone number of his brother-in-law H. Smith had the following peculiar property: The sum of the digits of that number was equal to the sum of the digits of the prime factors of that number. Got it? Smiths telephone number was 493-7775. This number can be written as the product of its prime factors in the following way:4937775= 3*5*5*65837The sum of all digits of the telephone number is 4+9+3+7+7+7+5= 42,and the sum of the digits of its prime factors is equally 3+5+5+6+5+8+3+7=42. Wilansky was so amazed by his discovery that he named this kind of numbers after his brother-in-law: Smith numbers.As this observation is also true for every prime number, Wilansky decided later that a (simple and unsophisticated) prime number is not worth being a Smith number, so he excluded them from the definition.Wilansky published an article about Smith numbers in the Two Year College Mathematics Journal and was able to present a whole collection of different Smith numbers: For example, 9985 is a Smith number and so is 6036. However,Wilansky was not able to find a Smith number that was larger than the telephone number of his brother-in-law. It is your task to find Smith numbers that are larger than 4937775!InputThe input file consists of a sequence of positive integers, one integer per line. Each integer will have at most 8 digits. The input is terminated by a line containing the number 0.OutputFor every number n 0 in the input, you are to compute the smallest Smith number which is larger than n,and print it on a line by itself. You can assume that such a number exists.Sample Input49377740Sample Output49377753 算法分析3.1 构造逐位相加之和函数 要求大于n的最小的史密斯数，设此史密斯数为nn，由于史密斯数nn要满足质因数分解式每位相加之和等于其本身逐位相加之和，所以首先构建史密斯数每位相加的函数，其代码如下： void get_sum(long n, int * sum) /逐位求和 while(n != 0) *sum += n%10; n /= 10; 3.2 求史密斯数首先我们了解到任意合数都可以分解为几个质因数的乘积并且给定合数的质因数分解表达式是唯一的。根据上述性质，我们的质因数分解思路如下：设被分解合数为N，则分解步骤如下： 初始状态，M = 2 用M试除N，若能整除，说明M为N的质因数，则更新N = N / M，M不变；若不能整除，则N不变，M+本题中，算法描述如下： sum1 = sum2 = cnt = 0; get_sum(nn, &sum1); n = nn; /nn固定保存原N值，n用于整除后更新N值 m = 2; while(m = sqrt(n) if(n%m = 0) cnt+; /cnt记录质因数个数，即标识了是否为素数 n = n/m; get_sum(m, &sum2); else m+; get_sum(n, &sum2); if(sum1 = sum2 & cnt != 0) printf(%ldn, nn); break; 输入任意合数n 4 程序流程图 输出结果*sum n=0? N*sum += n%10; n /= 10; 图1 get_sum函数的流程图 输入sum1，sum2，ceil，n，nn，m，cnt 是否为1Y从键盘上输入ceilCeil等于0用M试除N，若能整除，说明M为N的质因数，则更新N = N / M，M不变；若不能整除，则N不变，M+,并求sum1和sum2的值Nsum1=sum2&cnt!=0输出所求出的满足要求的史密斯数nn 程序结束 图2 主函数的流程图5 程序源码void get_sum(long n, int * sum) /逐位求和 while(n != 0) *sum += n%10; n /= 10; int main() int sum1, sum2; long ceil, n, nn, m; int cnt; while(1) scanf(%ld, &ceil); if(ceil = 0) break; for(nn = ceil+1; ; nn+) sum1 = sum2 = cnt = 0; get_sum(nn, &sum1); n = nn; /nn固定保存原N值，n用于整除后更新N值 m = 2; while(m = sqrt(n) if(n%m = 0) cnt+; /cnt记录质因数个数，即标识了是否为素数 n = n/m; get_sum(m, &sum2); else m+; get_sum(n, &sum2); if(sum1 = sum2 & cnt != 0) printf(%ldn, nn); break; return 0; 6 试算截屏图图3 程序运行截图7 分析与总结史密斯数是一个很有趣的问题，一开始也许有一点找不到思路，但是仔细观察，发现史密斯数所包含的一些规律，问题就会得到解决。有了思路之后，画出程序流程图有助于以后代码的编写。首先要保证思路是正确的，后期的程序编写才能准确无误。在解题的过程中我也认识到我的一些不足，基础的c程序编写还是有一些小毛病，但是发现后及时改正就能够正确的运行了。但是解决这个问题的算法我也许不是最优的，在今后会多加实践，完善解题思路。8 参考文献1 李文新、郭炜、余华山. 程序设计导引及在线实践M. 北京：清华大学出版社2 谭浩强. C程序设计M. 北京：清华大学出版社，2005.3 严蔚敏，吴伟民. 数据结构M. 北京:清华大学出版社，1996.4 钟珞. 计算机科学导论M.武汉：武汉理工大学出版社.5 张富. C及C+程序设计M. 北京