迭代算法-计算猴子一共摘了多少个桃子

时间：2010-07-23 来源：chengxiaopeng

迭代练习题：五只猴子一起摘了一堆桃子,因为太累了,它们商量决定,先睡一觉再分.一会其中的一只猴子来了,它见别的猴子没来,便将这堆桃子平均分成5份,结果多了一个,就将多的这个吃了,并拿走其中的一份.一会儿,第2只猴子来了,他不知道已经有一个同伴来过,还以为自己是第一个到的呢,于是将地上的桃子堆起来,再一次平均分成5份,发现也多了一个,同样吃了这1个,并拿走其中一份.接着来的第3,第4,第5只猴子都是这样做的.......,根据上面的条件,问这5只猴子至少摘了多少个桃子?第5只猴子走后还剩下多少个桃子? 看到这个练习题后，如果从前面往后面推，则很难。甚至能把你的思路弄的特别混乱，如果从往前推，我们可以列出如下数学式子。假设第五只猴子走后剩下x个桃子。即s6=x；假设第五只猴子没有分桃子之前的桃子数为s5。因为第五只猴子看到这堆桃子后，分了5份，发现多了一个把多余的一个吃了，拿走了其中的一份。我们可以这样理解，猴子吃了一个桃子，然后分了五份，自己拿走了一份。剩下的桃子个数为s6;因此我们可以很快的列出下面的一个数学式子： (s5 - 1)/5*4 = s6; A 因此是一个迭代的过程，因此。我们可以一直往上推，即可推出下面的式子。 (s4 - 1)/5*4 = s5; A (s3 - 1)/5*4 = s4; A (s2 - 1)/5*4 = s3; A (s1 - 1)/5*4 = s2; A 将上面的式子进行变化，我们很快可以可以得到下面的式子。 s6=x; s5=s6*5/4+1; B s4=s5*5/4+1; B s3=s4*5/4+1; B s2=s3*5/4+1; B s1=s2*5/4+1; B 从上面的式子，我们可以看到从s6到s1是一个迭代求解的过程。其迭代的表达式为: s=x
s=s*5/4+1
s=s*5/4+1
s=s*5/4+1
s=s*5/4+1
s=s*5/4+1 另外从上面标有 A 的表达式，进行简单等式变化： s6 = x; (s5-1)/5 = s6/4; (s4-1)/5 = s5/4; (s3-1)/5 = s4/4; (s2-1)/5 = s3/4; (s1-1)/5 = s2/4; 从上面的式子，我们可以很快的推理出s2,s3,s4,s5,s6都是4的倍数。当然了s1不一定是4的倍数。因为我们求解桃子的总个数是个未知数，从上面的分析可知桃子的个数是4的倍数，这样很容易让我们想到进行循环，初始值为0，每次循环，如果不是需要的数，就加上4。而跳出循环的判断条件即，进行5次分桃子都能成功(进行红色B运算)，即可跳出循环。代码如下：

#include <stdio.h>

int main(int argc,int *argv[])
{
    int i,j,number = 0,all;
    do
    {
      all = number;
      for (i = 1; i <= 5; i++)
      {
          all = all * 5 / 4 + 1;
          if (all % 4 )
          {
             break;
          }
      }

      if (i == 5)
      {
         break;
      }
      number += 4;
    } while (1);

    printf("all taozi count is : %d, the lost taozi count is :%d\n",all,number);

    system("pause");
    return 0;
}

程序运行结果：猴子一共摘了3121个桃子，第5只猴子走后还剩下1020个桃子。