2005年5月2日第17期电脑报编程点将(转载)

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;
}