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

评论