基础强化报告新编范本.docx
《基础强化报告新编范本.docx》由会员分享,可在线阅读,更多相关《基础强化报告新编范本.docx(11页珍藏版)》请在冰点文库上搜索。
基础强化报告新编范本
基础强化报告新编范本
附件1:
学号:
0121210680529
课程设计
(基础强化训练)
题目
SmithNumbers
学院
计算机科学与技术
专业
软件工程
班级
Zy1202
姓名
胡小意
指导教师
段鹏飞
2014
年
7
月
11
日
课程设计任务书
学生姓名:
胡小意专业班级:
软件zy1202
指导教师:
段鹏飞工作单位:
计算机学院
题目:
SmithNumbers
初始条件:
输入:
Theinputfileconsistsofasequenceofpositiveintegers,oneintegerperline.Eachintegerwillhaveatmost8digits.Theinputisterminatedbyalinecontainingthenumber0.
输出:
Foreverynumbern>0intheinput,youaretocomputethesmallestSmithnumberwhichislargerthann,andprintitonalinebyitself.Youcanassumethatsuchanumberexists.
要求完成的主要任务:
(包括课程设计工作量及其技术要求,以及说明书撰写等具体要求)
1、完成算法分析
2、给出对应的程序流程图
3、给出能正确实现的程序源码
5、给出试算截屏图
6、课程设计工作的分析与总结
7、给出不少于5篇参考文献。
时间安排:
2014-7-7到2014-7-11
指导教师签名:
年月日
系主任(或责任教师)签名:
年月日
1注册资料
用户名:
huxiaoyi
密码:
123456789
选题题号:
1142
2选题描述
Description
Whileskimminghisphonedirectoryin1982,AlbertWilansky,amathematicianofLehighUniversity,noticedthatthetelephonenumberofhisbrother-in-lawH.Smithhadthefollowingpeculiarproperty:
Thesumofthedigitsofthatnumberwasequaltothesumofthedigitsoftheprimefactorsofthatnumber.Gotit?
Smith'stelephonenumberwas493-7775.Thisnumbercanbewrittenastheproductofitsprimefactorsinthefollowingway:
4937775=3*5*5*65837
Thesumofalldigitsofthetelephonenumberis4+9+3+7+7+7+5=42,andthesumofthedigitsofitsprimefactorsisequally3+5+5+6+5+8+3+7=42.Wilanskywassoamazedbyhisdiscoverythathenamedthiskindofnumbersafterhisbrother-in-law:
Smithnumbers.
Asthisobservationisalsotrueforeveryprimenumber,Wilanskydecidedlaterthata(simpleandunsophisticated)primenumberisnotworthbeingaSmithnumber,soheexcludedthemfromthedefinition.
WilanskypublishedanarticleaboutSmithnumbersintheTwoYearCollegeMathematicsJournalandwasabletopresentawholecollectionofdifferentSmithnumbers:
Forexample,9985isaSmithnumberandsois6036.However,WilanskywasnotabletofindaSmithnumberthatwaslargerthanthetelephonenumberofhisbrother-in-law.ItisyourtasktofindSmithnumbersthatarelargerthan4937775!
Input
Theinputfileconsistsofasequenceofpositiveintegers,oneintegerperline.Eachintegerwillhaveatmost8digits.Theinputisterminatedbyalinecontainingthenumber0.
Output
Foreverynumbern>0intheinput,youaretocomputethesmallestSmithnumberwhichislargerthann,andprintitonalinebyitself.Youcanassumethatsuchanumberexists.
SampleInput
4937774
0
SampleOutput
4937775
3算法分析
3.1构造逐位相加之和函数
要求大于n的最小的史密斯数,设此史密斯数为nn,由于史密斯数nn要满足质因数分解式每位相加之和等于其本身逐位相加之和,所以首先构建史密斯数每位相加的函数,其代码如下:
voidget_sum(longn,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);
}
elsem++;
}
get_sum(n,&sum2);
if(sum1==sum2&&cnt!
=0){
printf("%ld\n",nn);
break;
}
4程序流程图
N
图1get_sum函数的流程图
Y
N
图2主函数的流程图
5程序源码
voidget_sum(longn,int*sum){//逐位求和
while(n!
=0){
*sum+=n%10;
n/=10;
}
}
intmain(){
intsum1,sum2;
longceil,n,nn,m;
intcnt;
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);
}
elsem++;
}
get_sum(n,&sum2);
if(sum1==sum2&&cnt!
=0){
printf("%ld\n",nn);
break;
}
}
}
return0;
}
6试算截屏图
图3程序运行截图
7分析与总结
史密斯数是一个很有趣的问题,一开始也许有一点找不到思路,但是仔细观察,发现史密斯数所包含的一些规律,问题就会得到解决。
有了思路之后,画出程序流程图有助于以后代码的编写。
首先要保证思路是正确的,后期的程序编写才能准确无误。
在解题的过程中我也认识到我的一些不足,基础的c程序编写还是有一些小毛病,但是发现后及时改正就能够正确的运行了。
但是解决这个问题的算法我也许不是最优的,在今后会多加实践,完善解题思路。
8参考文献
[1]李文新、郭炜、余华山.程序设计导引及在线实践[M].北京:
清华大学出版社
[2]谭浩强.C程序设计[M].北京:
清华大学出版社,2005.
[3]严蔚敏,吴伟民.数据结构[M].北京:
清华大学出版社,1996.
[4]钟珞.计算机科学导论[M].武汉:
武汉理工大学出版社.
[5]张富.C及C++程序设计[M].北京:
人民邮电出版社.
本科生课程设计成绩评定表
班级:
软件zy1202 姓名:
胡小意 学号:
0121210680529
序号
评分项目
满分
实得分
1
学习态度认真、遵守纪律
10
2
设计分析合理性
10
3
设计方案正确性、可行性、创造性
20
4
设计结果正确性
40
5
设计报告的规范性
10
6
设计验收
10
总得分/等级
评语:
注:
最终成绩以五级分制记。
优(90-100分)、良(80-89分)、中(70-79分)、
及格(60-69分)、60分以下为不及格
指导教师签名:
20014年 月 日