百钱买百鸡问题

    我国古代数学家张丘建在《算经》一书中曾提出过著名的“百钱买百鸡”问题。该问题叙述如下：鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买百鸡，则翁，母，雏各几何？

    根据题目的意思，我们可以很快的列出数学式子：1) 5*x + 3 * y + z / 3 = 100; 2) x + y + z = 100;

从数学的角度我们可以看出，解此方程（三元一次方程），有多个解。由于数量在0-100之间，因此我们可以使用穷举法，解决此问题：

#include <stdio.h>

int accord(int i, int j, int k);

int main(int argc, char *argv[])
{
  int i,j,k;
  printf("the possible plans for buying 100 fowls with 100 yuan are:\n");
  for(i=0; i<21; i++)
    for(j=0; j<34; j++)
      for(k=0; k<101; k++)
        if(accord(i,j,k))
           printf("cock = %d, hen = %d, chicken = %d\n",i,j,k);

  return 0;
}

int accord(int i, int j, int k)
{
  if(5 * i + 3 * j + k / 3 == 100 && k % 3 == 0 && i + j + k == 100)
    return 1;
  else
    return 0;
}

    上面看到到循环的终止变量21，34，101.可能有些人不理解。其实书上的都是小于等于100的，但我们动脑筋想一下就可以明白了，拿100前最多可以买20鸡翁、买33鸡母，而题目的要求一共需要100，因此鸡雏最大值也就是100了。而因为我用的是小于，因此就在此基础上进行了加一操作。

    其实这道题，仔细想来还可以进行优化，我们细细想来。如果我们确定了可以根据每次穷举鸡翁的数量，可以确定鸡母的数量，当确定鸡母的数量时，我们也可以确定鸡雏的数量。根据此思想，编写代码如下：

#include <stdio.h>

int accord(int i, int j, int k);

int main(int argc, char *argv[])
{
  int i,j,k;
  int temp_0,temp_1,temp_2;
  printf("the possible plans for buying 100 fowls with 100 yuan are:\n");
  temp_0 = 100 / 5 + 1;
  for(i=0; i<temp_0; i++)
  {
    temp_1 = (100 - 5*i)/3 + 1;
    for(j=0; j<temp_1; j++)
    {
      temp_2 = 100 - i - j + 1;
      for(k=temp_2; k>=0; k--)
      {
        if(accord(i,j,k))
           printf("cock = %d, hen = %d, chicken = %d\n",i,j,k);
      }
    }
  }
  return 0;
}

int accord(int i, int j, int k)
{
  if(5 * i + 3 * j + k / 3 == 100 && k % 3 == 0 && i + j + k == 100)
    return 1;
  else
    return 0;
}

两个程序的运算结果都一样，执行结果如下:

peng@ubuntu:/media/XIAOPENG_U$ ./a.out 

the possible plans for buying 100 fowls with 100 yuan are:

cock = 0, hen = 25, chicken = 75

cock = 4, hen = 18, chicken = 78

cock = 8, hen = 11, chicken = 81

cock = 12, hen = 4, chicken = 84