《基础强化报告新编范本》由会员分享，可在线阅读，更多相关《基础强化报告新编范本（11页珍藏版）》请在金锄头文库上搜索。
1、附件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 di
2、gits. 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、应的程序流程图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,
4、 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 wa
5、s 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
6、 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 a
7、n 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 b
8、rother-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 th
9、e 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要满足质因数分解式每位相加之和等于其本身逐位相加之和，所以首先构建史密斯数每位相加的函数，其代码如下： voi
10、d 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值，
11、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从键盘上输入ceilCe
12、il等于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记录质因数个数，即标识了是否为素数
