2017算法设计与应用作业

1、1有52张牌，使它们全部正面朝上，第一轮是从第2张开始，凡是2的倍数位置上的牌翻成正面朝下；第二轮从第3张牌开始，凡是3的倍数位置上的牌，正面朝上的翻成正面朝下的，正面朝下的翻成正面朝上的；以此类推，直到翻得牌超过104张为止。统计最后有几张牌正面朝上以及它们的位置号。问题分析：52张牌都有一个初始状态，即全部朝上。第一轮开始时，2的倍数位置改变，非2的倍数保持原样；第二轮开始时，3的奇数倍朝下，3的偶数倍朝上；第三轮开始时，4的倍数朝上，即2的偶数倍朝下，以此类推，直到牌数超过104,则进行状态统计。算法设计：根据题意，首先对第一轮进行记录，算法则应该是依次对位置进行改变，用循环求解翻转问题

2、。算法分析：这个算法使用循环对牌进行逐层比较，算法复杂度为O(n+1),使用了52个空间的一维数组。数据结构设计：用一维数组a52表示52张牌，设其初始状态为00计数小于104时，第一轮开始进行翻转，下一轮即n+1轮开始分情况进行翻转，用整型shang进行朝上个数的统计，位置则由i来确定。S1算法如下:#includeintmain()用一维数组表示52张牌，0表示正面朝上正面朝上的个数次数统计intn=1;while(count=104)if(n=1)for(i=n+1;i=52;+i)if(i%(n+1)=0)ai-1=1;/front-;+count;n+;elseWhile?S2S3(

3、inta52=0;/intshang=0;/inti=0;intcount=0;/for(i=n+1;i=52;+i)if(i%(n+1)=0)(if(ai-1=0)ai=1；+count;)else(ai=0;+count;)n+;)for(i=0;i52;+i)(if(ai=0)(shang+;)printf(正面朝上的扑克有：%dn,shang);printf(它们的位置号为：n);for(i=0;i52;+i)printf(%dt,i);printf(n);return0;运行结果如下:E；V所建文件夹(2)siJdnfaDebugsuianfa-exe*,ressanykeytoco

4、ntinue,ressanykeytocontinue1.键盘输入n个正整数，把它们看作一个“数圈”，求其中连续4个数之和最大者。问题分析： 用数1到n表示键盘输入的数， 把连续4个数之和同前后进行比较， 求出和最大，可利用二重循环把所有情况进行列举。算法设计：用1,2,3口代表输入的数，其存储的值代表连续4个数之和。第一层循环：范围从n到n+4;第二层循环：范围从1到n；最后对和进行比较，然后输出。算法分析：算法效率为O(4n),存储空间上有些浪费，可根据实际情况进行空间分配。数据结构设计：首先用一个一维数组表示键盘输入的数，定义一个最大数，设置其初始状态为0,把连续4个数的和用he表示，再

5、同max进行比较，输出内容就是问题的解。算法如下：#includeintmain(void)intch120,n,i,j,he=0,max=0,maxi;scanf(%d,&n);for(i=0;in;i+)scanf(%d,&chi);I=I回6 62 24 4有二克为邦号2 2田位1&1012141GIS1012141GIS3Q3Q3234343636bObOfor(i=n;in+4;i+)chi=chi-n;for(i=0;imax)max=he;maxi=i;i=maxi;printf(最大和=%d+%d+%d+%d=%dn,chi,ch(i+1)%n,ch(i+2)%n,ch(i+3

6、)%n,he);return0;运行结果如下：七新建文件夹(n nf fg,suanfa.g,suanfa.T T3579122235791222最大和=7+9412+22=7+9412+22-37-37PressantjlkePressantjlke toconi;Inuetoconi;Inue2.有一堆棋子，2枚2枚地数，最后余1枚；3枚3枚地数，最后余2枚；5枚5枚地数，最后余4枚；6枚6枚地数，最后余5枚；7枚7枚地数，最后正好数完，编程完成这堆棋子最少有多少枚棋子。问题分析：用n表示棋子数，要求可以7枚7枚的数，因此棋子数至少为7,问题可以用条件语句进行求解。算法设计：用7到n表示棋

7、子数，余数表示剩余的棋子数。设置棋子数的范围,因为不知道具体有多少，所以尽可能的大一点，然后进行情况判别。算法分析：算法比较简单，但由于预先不知道棋子数，因此效率比较差。数据结构分析：首先预确定一个棋子数的范围，分别对2、3、5、7进行取余，符合情况则输出棋子数n,不符合则加1,继续进行判断，输出结构符合问题要求。算法如下：#includeintmain(void)(intn=7;while(n1000)(if(n%2=1&n%3=2&n%5=4&n%6=5&n%7=0)(printf(%dn,n);break;elsen+;return0;运行结果如下：F F一t t*E*E：赍建文件夹 i

8、2)5uanfaDebugsuanfa.exei2)5uanfaDebugsuanfa.exe119Pressanptocontinue119Pressanptocontinue3.利用分治法求一组数据中最大的两个数和最小的两个数。问题分析：用n表示输入的数，最大的两个数和最小的两个数可用循环进行情况列举。算法设计：用分治法可以用较少的比较次数解决上述问题。问题可以简化为求最大值和最小值，再把这种情况除外，再求其最大值和最小值。算法分析：算法中需要n-1次比较，才能得到第一个最大最小值，需要n-2次比较得到第二个最大最小值。数据结构设计：把输入的数存入一维数组ch,首先对两个数进行比较，然后大

9、的数或者小的数同下一个比较，直到输出最大的数maxi和最小的数mini；下一次继续进行循环比较，输出最大的数max2和最小的数min2o算法如下：#includeintmain(void)(intch20,n,i,max1=0,max2=0,min1=0,min2=0;scanf(%d,&n);for(i=0;in;i+)scanf(%d,&chi);for(i=0;in;i+)(if(chmax1chi)min1=i;)if(max1=0)max2=1;if(min1=0)min2=1;for(i=0;in;i+)(if(i=max1|i=min1)continue;if(chmax2chi

10、)min2=i;)printf(max1=%dmax2=%dmin1=%dmin2=%d,chmax1,chmax2,chmin1,chmin2);return0;)， E:E:第F*4*41 12 2：岸岸uauanfaDnfaDe enfa.exnfa.exe e 36?2112536?21125a.xl=23nax2=11ninl=lmxn2=2FreesdnyKeytocontinuea.xl=23nax2=11ninl=lmxn2=2FreesdnyKeytocontinue4.等分液体， 在一个瓶子中装有8N(N为偶数)升汽油， 要平均分成两份， 但只有一个装3(N/2-1)开的量

11、杯和装5(N/2+1)升的量杯(都没有刻度)。打印出所有把汽油分成两等份的操作过程。若无解打印“NO,否则打印操作过程。问题分析：将8升汽油平分装入两个不同容量的容器，在没有刻度的情况下，一次就平分是不行的，需要利用容器的差异性多次进行最后达到平分，可以通过分析具体情况达到目的。算法设计：利用深度优先算法进行搜索，不满足均分条件时则及时进行回溯，当满足问题的解则结束。算法分析：这个算法比较简单，利用条件分支进行判断，来保证不漏判。数据结构分析：将三个容器的容量定义为常量，在定义两个变量b和c来确定瓶中实际的重量。根据确定量的不同情况进行分配，最后达到均分的效果。算法如下：#includeintp=4;intmain()inta=8,y=3,z=5;voidfen(inta,inty,intz);fen(a,y,z);fen(a,z,y);return0;)voidfen(inta,inty,intz)(intb=0,c=0;printf(a:%db:%dc：%dn,a,y,z,a,b