2005年5月2日第17期电脑报编程点将 题目：十个小孩围成一圈分糖果，老师分给第一个小孩10块，第二个小孩2块，第三个小孩8块，第四个小 孩22块，第五个小孩16块，第六个小孩4块，第七个小孩10块，第八个小孩6块，第九个小孩14块，第十个 小孩20块。然后所有的小孩同时将手中的糖分一半给右边的小孩；糖块数为奇数的人可向老师要一块。问 经过这样几次后大家手中的糖的块数一样多？每人各有多少块糖？ 我的程序：（这道题在我的c语言程序设计百例里面的第75题） /*这道题看起来简单，但是其实要一次完全做完整不不是很容易。 当然，这题目本身就有点歧义：起初我是这样理解的：第一个人把一半糖给第二个人， 然后第二个人检查一下糖是不是偶数，不是的话就再要一个糖， 然后再把总的糖分一半给第三个……后来发现这样做没有答案。 我的答案和获奖程序一基本上是一样的，主要的不同点在我的程序的注释的部分。 算法的思路比较简单就不分析了。 */ #include<iostream> using namespace std; void main() { const int n=10; int child[n]={10,2,8,22,16,4,10,6,14,20}; int temp,i,count=0; bool tag=true;//标志分配完后是否每个数值都是相等的，相等时为false，不等时为true while(tag) { count++; tag=false; temp=child[n-1];//获奖程序把这句放在这个循环的最外面， //我觉得这个就没有所谓的分配次数可言的,我把这个放在里层循环的外面 //在外层循环的里面是说明已经经过了一次分配，现在是另一次分配，这是重新初始化 for(i=0;i<n-1;i++) { child[i]=child[i]/2+temp/2; temp=(child[i]-temp/2)*2; if(child[i]%2==1)child[i]++; } for(i=0;i<n-1;i++) if(child[i]!=child[i+1]) { tag=true; break; } } cout<<"经过"<<count<<"次后大家手中的糖的块数一样多\n" <<"大家手中的糖的块数都是："<<child[0]<<endl; } 获奖程序一： #include <stdio.h> #include <conio.h> main() {int a[10]={10,2,8,22,16,4,10,6,14,20}; int i,flag=0,t=0,temp=20; while (flag==0) {for (i=0;i<=9;i++) {a[i]=a[i]/2+temp/2; temp=(a[i]-temp/2)*2; if (a[i]%2==1) a[i]++; } t++; flag=1; for (i=0;i<=8;i++) if (a[i]!=a[i+1]) {flag=0;break;}; } printf("%dtimes,number=%d\n",t,a[0]); getch(); } 获奖程序二： //数据结构： 十个小孩采用数组的存储结构 //算法描述： 对数组进行操作，将前驱节点的值的1/2与该节点的值的1/2相加，如果为奇数，就加1。依 次进行下去直到各节点值相等。 #include<iostream> using namespace std; struct node { int oldnum; //用来记录分糖前每个小朋友手中的糖果数 int newnum; //用来记录又一次分糖后每个小朋友手中的糖果数 }; void main() { node child[10]; int count=0; // 以下进行数组的初始化。 child[0].oldnum=10;child[0].newnum=0; child[1].oldnum=2;child[1].newnum=0; child[2].oldnum=8;child[2].newnum=0; child[3].oldnum=22;child[3].newnum=0; child[4].oldnum=16;child[4].newnum=0; child[5].oldnum=4;child[5].newnum=0; child[6].oldnum=10;child[6].newnum=0; child[7].oldnum=6;child[7].newnum=0; child[8].oldnum=14;child[8].newnum=0; child[9].oldnum=20;child[9].newnum=0; //以下是算法的实现 while (!(child[0].oldnum==child[1].oldnum&&child[1].oldnum==child[2].oldnum&&child [2].oldnum==child[3].oldnum&&child[3].oldnum==child[4].oldnum&&child[4].oldnum==child [5].oldnum&&child[5].oldnum==child[6].oldnum&&child[6].oldnum==child[7].oldnum)) { int i=1; while (i<11) { child[i%10].newnum=(child[i%10].oldnum+child[(i-1)%10].oldnum+1)/2; //进行重新分配，并进行从新赋值。 i++; } i=1; while (i<11) { child[i%10].oldnum=child[i%10].newnum; i++; } count++; } cout<<"分糖次数："<<count<<endl; cout<<"每个小朋友手中的糖果数:"<<child[0].oldnum; }
评论