经典算法之不定方程问题

所谓不定方程,是指未知数个数多于方程个数,且对解都有一定的限制。

首先,来看一道经典的数学问题“百钱买鸡”问题。

中国古代数学家张丘建在他的《算经》中提出了著名的“百钱买鸡”问题:鸡翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱一,百钱买鸡,问翁、母、雏各几何?

意思是:公鸡5文钱1只,母鸡3文钱1只,小鸡3只1文钱,要求100文钱买100只鸡,求公鸡、母鸡和小鸡应该各买多少只?

其实这是一道不定方程问题,有两个条件:一是用的钱数正好是100文;二是买鸡的数量正好是100只。设买公鸡、母鸡和小鸡分别为x、y、z只,则可列出一下方程:

x+y+z = 100

5x+3y+z/3 = 100

根据这两个公式,通过计算机的穷举算法即可求得结果。

代码一:

[cpp][/cpp] view plaincopyprint?

  1. void BuyChicken()
  2. {
  3.     int x,y,z;
  4.     for(x = 0; x <= 20; x++)
  5.     {
  6.         for(y = 0; y <= 33; y++)
  7.         {
  8.             z = 100 – x – y;
  9.             if(z % 3 == 0 && x*5 + y*3 + z/3 == 100)
  10.             {
  11.                 printf(“公鸡:%d,母鸡:%d,小鸡:%d\n”,x,y,z);
  12.             }
  13.         }
  14.     }
  15. }

 

以上的算法并不是最佳的,深入分析,4只公鸡值20文钱,3只小鸡值1文钱,合起来鸡数是7,钱数是21;而7只母鸡的钱数也正好是21.如果少买7只鸡,就可以用这笔钱多买4值公鸡和3只小鸡。这样,百钱还是百钱,百鸡还是百鸡。所以,只要求出一个答案,根据这个规则,马上就可以求出其他的答案出来。

设一个参数看,则有:

x = 4k;

y = 25 – 7k;

z = 75 + 3k;

因为鸡的数量x、y、z都只能是正数,所以满足式子的k值只能是0、1、2、3.

代码二:

[cpp][/cpp] view plaincopyprint?

  1. <span style=”font-size:18px”>void BuyChicken2()
  2. {
  3.     int x,y,z,k;
  4.     for(k = 0; k <= 3; k++)
  5.     {
  6.         x = 4*k;
  7.         y = 25 – 7*k;
  8.         z = 100 – x – y;
  9.         printf(“公鸡:%d,母鸡:%d,小鸡:%d\n”,x,y,z);
  10.     }
  11. }</span>

其次,还有大家都非常熟悉的趣味数学题“鸡兔同笼”问题。

问题的描述是:有若干只鸡兔同在一个笼子里,从上面数,有35个头;从下面数,有94只脚。求笼子中有多少只鸡和多少只兔?

这个问题用穷举法可以解决,设有鸡x只,兔y只,则有方程:

x + y = 35;

2x + 4y = 94;

代码三:

[cpp][/cpp] view plaincopyprint?

  1. <span style=”font-size:18px”>void Chook_Rabbit()
  2. {
  3.     int chook,rabbit,head,foot;
  4.     printf(“请输入头数和脚数:”);
  5.     scanf(“%d%d”,&head,&foot);
  6.     for(chook = 0; chook <= head; chook++)
  7.     {
  8.         rabbit = head -chook;
  9.         if(chook * 2 + rabbit * 4 == foot)
  10.         {
  11.             printf(“鸡有:%d只,兔子有:%d只。”,chook,rabbit);
  12.         }
  13.     }
  14. }</span>

仔细分析,还有更简单的方法,用奥数中的知识:

将每个头都按2只算(则认为都是鸡),则剩下的足就是兔子的另两只,则只需要将剩下的足除以2即可得到兔子的数量。

代码四:

[cpp][/cpp] view plaincopyprint?

  1. <span style=”font-size:18px”>void Chook_Rabbit1()
  2. {
  3.     int chook,rabbit,head,foot;
  4.     printf(“请输入头数和脚数:”);
  5.     scanf(“%d%d”,&head,&foot);
  6.     rabbit = (foot – 2*head)/2;
  7.     chook = head – rabbit;
  8.     printf(“鸡有:%d只,兔子有:%d只。”,chook,rabbit);
  9. }</span>

最后再来看一道著名的“五家共井”问题。

问题的描述:今有五家共井,甲二绠不足如乙一绠,乙三绠不足如丙一绠,丙四绠不足如丁一绠,丁五绠不足如戊一绠,戊六绠不足如甲一绠。如各得所不足一绠,皆逮。问井深、绠长几何?(题中:“绠”是汲水桶上的绳索,“逮”是到达井底水面的意思。)

意思是:现在有5家共用一口井,甲、乙、丙、丁、戊5家各有一条绳子打水,设各家绳子的长度分别为len1,len2,len3,len4,len5,井深len,则以上条件可以表示为下面的方程:

len1*2+len2 = len;

len2*3+len3 = len;

len3*4+len4 = len;

len4*5+len5 = len;

len5*6+len1 = len;

求井的深度和各家打水所用绳子的长度。

根据上面的方程可得到一下算式:

len1*2 + len2 = len2*3+len3 = len3*4+len4 = len4*5 +len5 = len5*6+len1

由以上算式可以推出:

len1 = len2 + len3/2

len2 = len3 + len4/3

len3 = len4 + len5/4

len4 = len5 + len1/4

根据以上列出的这些算式,可枚举各种情况,最后得出结果。

代码五:

[cpp][/cpp] view plaincopyprint?

  1. <span style=”font-size:18px”>void Length()
  2. {
  3.     int len1,len2,len3,len4,len5,len,flag;
  4.     flag = 1;
  5.     len5 = 0;
  6.     while(flag)
  7.     {
  8.         len5 += 4;  //len5为4的倍数
  9.         len1 = 0;
  10.         while(flag)
  11.         {
  12.             len1 += 5;                   //len1为5的倍数
  13.             len4 = len5 + len1/5;        //丁家井绳长
  14.             len3 = len4 + len5/4;        //丙家井绳长
  15.             if(len3 % 2)                 //若不能被2整除
  16.                 continue;
  17.             if(len4 % 3)                 //若不能被3整除
  18.                 continue;
  19.             len2 = len3 + len4/3;
  20.             if(len2 + len3 / 2 < len1)   //不符合条件
  21.                 break;
  22.             if(len2 +len3 / 2 == len1)   //符合条件
  23.                 flag = 0;
  24.         }
  25.     }
  26.     len = 2*len1 + len2;
  27.     printf(“各家井绳长度分别为:\n”);
  28.     printf(“甲:%d\n”,len1);
  29.     printf(“乙:%d\n”,len2);
  30.     printf(“丙:%d\n”,len3);
  31.     printf(“丁:%d\n”,len4);
  32.     printf(“戊:%d\n”,len5);
  33.     printf(“井深:%d\n”,len);
  34. }</span>

标签