资源描述
附件1：学 号： 9课 程 设 计（基本强化训练）题 目Smith Numbers学 院计算机科学与技术专 业软件工程班 级Zy1202姓 名胡小意指引教师段鹏飞年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篇参照文献。时间安排： -7-7到-7-11指引教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日目录1 注册资料42 选题描述43 算法分析53.1 构造逐位相加之和函数53.2 求史密斯数54 程序流程图65 程序源码86 试算截屏图97 分析与总结98 参照文献91 注册资料顾客名：huxiaoyi密码：选题题号：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. 北京：清华大学出版社，.3 严蔚敏，吴伟民. 数据构造M. 北京:清华大学出版社，1996.4 钟珞. 计算机科学导论M.武汉：武汉理工大学出版社.5 张富. C及C+程序设计M. 北京：人民邮电出版社.本科生课程设计成绩评估表班级：软件zy1202姓名：胡小意学号：9序号评分项目满分实得分1学习态度认真、遵守纪律102设计分析合理性103设计方案对的性、可行性、发明性204设计成果对的性405设计报告的规范性106设计验收10总得分/级别评语：注：最后成绩以五级分制记。优（90-100分）、良（80-89分）、中（70-79分）、及格（60-69分）、60分如下为不及格指引教师签名：4 年月日
展开阅读全文