猴子吃桃问题

    有一只猴子第一天摘下若干个桃子，当即吃掉了一半，有多吃了一个；第二天又将剩下的桃子吃掉一半，有多吃了一个；按照这样的吃饭每天都吃掉前一天剩下的一半又多一个。到了第10天，就剩下一个桃子。问题，这个桃子第一天摘了多少个桃子。

    看到这个题目，我们可以看出，这只猴子一共吃了9次，最后第九次吃过后，就剩下一个桃子，我们可以假设第8次吃过的桃子数为n.则我们可以列出如下的式子：

C8 / 2 - 1 = C9 = 1

也就是 

C(n-1) / 2 - 1 = C(n)

这个式子转化后，我们很容易得到下面的式子

C(n-1) = 2 * ( C(n) + 1 )

假设： x = n - 1 ,则 n = x + 1 

则上面的式子可以进行如下的转变：

C(x) = 2 * (C(x+1) + 1)

因此我们可以使用递归解决这个问题，代码如下：

#include <stdio.h>

int PeachCount(int n);

int main(int argc, char *argv[])
{
  int n = PeachCount(1);
  printf("the number of peach are %d\n",n);
  return 0;
}

int PeachCount(int n)
{
  if(n == 10)
    return 1;
  else
    return 2 * (PeachCount(n+1) + 1);
}

当然了，我也可以通过循环来进行问题的求解，代码如下：

#include <stdio.h>

int main(int argc, char *argv[])
{
  int i,sum = 1;
  for(i=1; i<10; i++)
    sum = (sum + 1) * 2;

  printf("the number of peach are %d\n",sum);

  return 0;
}

运行结果如下：

peng@ubuntu:~/src/test/c/suanfa/miaoqu$ ./a.out 

the number of peach are 1534