整数因子团问题报告.docxVIP

数据结构课程设计报告设计题目:整数因子团问题院系：经济管理学院专业班级：电子商务2011-2 学生姓名：于晓静、侯金一、张庆振指导教师：周长红2013年7月5日指导教师评语指导教师：年月日成绩评定学号姓名任务分工成绩目录1.设计内容11.1问题描述11.2设计要求11.3开发环境11.4研究思路12.设计步骤32.1需求分析32.2概要设计32.3详细设计52.4调试分析102.5测试结果193.设计成果展示213.1用户手册213.2程序运行部分截图214.总结与心得体会24附录251.设计内容1.1问题描述①给定由n个连续自然数组成的序列1，…，n。②从当前序列中选择一整数，它在当前序列中至少有2个因子(该整数本身可以算作一个因子，例如，整数60的所有因子是：60，30，20，15，12，10，6，5，4，3，2，1。它们构成整数60在当前序列中的因子团 )。③从当前序列中删去所选整数的所有因子。④重复步骤②和③，直到空序列或当前序列中所有数字在序列中仅有一个因子。其中游戏中的得分是步骤②中所选择的数字的总和。1.2设计要求①．用户任意输入一个整数n，得到自然数序列1，…，n；②．输出该序列中依次选定的所有整数，并求出它们的和；③．删除选定整数时，将其所有因子一起删除得到新的序列；④．要求选定所有整数之和最大。1.3开发环境本程序采用C-Free开发环境。1.4研究思路①．要解决这个问题，第一件事情就是分析整数因子之间的关系。例如整数8，它的因子有4,2,1，而4的因子有2,1,用如下图形表示：那么当我们选定8时，4,2,1均被删除；当选定4时，2,1被删除而8会被留下。另外，在一个序列中，后1/2个数的因子都可以在前1/2中找到（如果序列中数字的个数为奇数个，那么将总个数的1/2取整。例如设n为7,那么[7/2]为3，所以后1/2数字为4,5,6,7），所以如果在后1/2数中还有非素数的情况下选定序列前1/2中的数，那么后1/2中会有选定数的倍数删不掉，导致不能得到最大分数。例如，n=8时,有1 2 3 4 || 5 6 7 8如果选4，那么1,2,4被删除，剩下 3 || 5 6 7 8，得分为4，8被留下删不掉；若选定8，那么1,2,4,8被删除，剩下 3 || 5 6 7，得分为8。综上所述，每次都要选定序列前1/2的数并删除其因子团得分才可能最大。 ②．因为程序要求的是最大和，所以首先选定的应为两个因子的整数。例如，在上面的1到8的序列中，7有两个因子，而8有四个因子。若第一次选定7，那么还剩下2 3 4 || 5 6 8 共六个数字；若选定8，则剩下3 || 5 6 7共四个数字。显然，第一次选8总的可删除次数将小于第一次选7的总次数，由此得到的和会小于第一次选两个因子的方法。综上，解决这个题目的关键为两个。一，只从序列前1/2的整数中选；二，首先选择因子为两个的整数，每删除一个数字就要判断新序列中是否有含两个因子的整数，有则继续删除，没有两个因子的则从小到大开始选择超过两个因子的整数。2.设计步骤2.1需求分析该程序主要设计整数因子团求最大和问题。①．以整形数据格式输入一个数，当输入其它非法字符（例如字母）时，程序将提示输入有误，需要用户重新输入正确的数据。输入正确数据后，按Enter键，不需要用户进行任何操作，删除的因子和最优解将自动呈现。计算完成后，用户按Enter键可退出程序。②．在程序上可以看到程序的说明和输入提示。③．用户将能看到每一次删除的数和最优解。④．当用户输入程序规定1到9999以外的数字或字母标点等时，程序将自动提示重新输入规定范围内的数字。2.2概要设计程序主要是利用循环来有哪些信誉好的足球投注网站最应该删除的数。删除的数应数越大，因子个数越小越好。从最大的数开始，从因子最少的数开始删除。每次删除后，由于其他数的因子个数也会减少，所以从最少因子个数重新开始有哪些信誉好的足球投注网站。程序中主函数实现程序的主要功能，CharToInt和Ten函数一起实现了将char型转化为int型的功能。2.3详细设计主程序n-s图：输入nj=1;j=n;j++ a[i]=j c=2;c=n/2;c++ i=1;ix/2;i++j=1 j=a[i-1];m++b[m]=ja[k]=j?YNa[i-1]%j=0? e++v=0;v=n;v++m0q=q+a[i-1]w++删除a[i-1]NYm=c?NYm1Yk=0Nj++k=0;k=n;k++m=0n=n-1z++a[z]=a[z+1]znz=vNYa[v]=b[m-1]接上页m--m=0c=2i=n+1