I00024 出钱买羽

《九章算术》属于算经十书中的一部,是中国古典数学专著。这些经典数学专著中,有许多众所周知的问题。现在是计算机无所不在的时代,那些问题与其用数学方法来解,不如用计算机程序来解。这个时代是计算解决问题的时代。


《九章算术》卷第二 粟米的四十五题和四十六题如下:

〔四五〕今有出钱六百二十,买羽二千一百翭。欲其贵贱率之,问各几何?答曰:其一千一百四十翭,三翭一钱。其九百六十翭,四翭一钱。
〔四六〕今有出钱九百八十,买矢簳五千八百二十枚。欲其贵贱率之,问各几何?答曰:其三百枚,五枚一钱。其五千五百二十枚,六枚一钱。

仔细阅读可以知道,这两个问题几乎是同一类型的,可以用同一个程序来解。

这两个问题,已知的是钱多少,买了多少东西。所买的东西分贵和贱两种,需要求的是贵和贱的东西各买了多少,其价格各为多少。给2个数,需要求4个数。另外一点,需要假设古代的钱是比较值钱的,1钱可以买多个物品。再一点是,经过试算,钱如果太值钱则可行解就太多了,于是假定1钱最多买10个物品。

穷举法在这个问题中是非常适用的。贵的物品所用钱数从1钱(循环变量i)开始试算,那么贱的物品所用钱数=所有钱数-贵的物品钱数。贵的物品价格从1开始试到10(循环变量j),贱的物品价格从j+1开始试到10(循环变量k),满足j<k。

程序如下:

/*
 * 今有出钱六百二十,买羽二千一百翭。欲其贵贱率之,问各几何?答曰:其一千一百四十翭,三翭一钱。其九百六十翭,四翭一钱。
 *
 * 今有出钱九百八十,买矢簳五千八百二十枚。欲其贵贱率之,问各几何?答曰:其三百枚,五枚一钱。其五千五百二十枚,六枚一钱。
 *
 * 这两个问题出自《九章算术》卷第二粟米的四十五题和四十六题。
 */

#include <stdio.h>

#define MAX_PRICE 10

int main(void)
{
    int coin, goods, e_coin, c_coin;
    int i, j, k;

    while(scanf("%d%d", &coin, &goods) != EOF)
        for(i=1; i<= coin; i++) {
            e_coin = i;
            c_coin = coin - e_coin;

            for(j=1; j<=MAX_PRICE; j++) {
                for(k=j+1; k<=MAX_PRICE; k++) {
                    if(e_coin * j + c_coin * k == goods) {
                        printf("%5d %2d %5d %2d %d+%d=%d %d/%d+%d/%d=%d
",
                               e_coin * j, j, c_coin * k, k,
                               e_coin * j, c_coin * k, goods,
                               e_coin * j, j, c_coin * k, k, coin);
                        break;
                    }
                }
            }
        }

    return 0;
}

输入两组数据,一是620和2100,二是980和5820,程序运行结果如下:

620 2100
  380  2  1720  4 380+1720=2100 380/2+1720/4=620
  250  1  1850  5 250+1850=2100 250/1+1850/5=620
  324  1  1776  6 324+1776=2100 324/1+1776/6=620
 1140  3   960  4 1140+960=2100 1140/3+960/4=620
  810  2  1290  6 810+1290=2100 810/2+1290/6=620
  435  1  1665  9 435+1665=2100 435/1+1665/9=620
  896  2  1204  7 896+1204=2100 896/2+1204/7=620
 1500  3   600  5 1500+600=2100 1500/3+600/5=620
 1620  3   480  6 1620+480=2100 1620/3+480/6=620
 1680  3   420  7 1680+420=2100 1680/3+420/7=620
 1716  3   384  8 1716+384=2100 1716/3+384/8=620
 1740  3   360  9 1740+360=2100 1740/3+360/9=620
980 5820
   12  1  5808  6 12+5808=5820 12/1+5808/6=980
   30  2  5790  6 30+5790=5820 30/2+5790/6=980
   60  3  5760  6 60+5760=5820 60/3+5760/6=980
  120  4  5700  6 120+5700=5820 120/4+5700/6=980
  300  5  5520  6 300+5520=5820 300/5+5520/6=980
  416  2  5404  7 416+5404=5820 416/2+5404/7=980
  780  3  5040  7 780+5040=5820 780/3+5040/7=980
  375  1  5445  9 375+5445=5820 375/1+5445/9=980
 1212  3  4608  8 1212+4608=5820 1212/3+4608/8=980
 1500  3  4320  9 1500+4320=5820 1500/3+4320/9=980
 2020  4  3800  8 2020+3800=5820 2020/4+3800/8=980
 2600  5  3220  7 2600+3220=5820 2600/5+3220/7=980
 2400  4  3420  9 2400+3420=5820 2400/4+3420/9=980
 3750  5  2070  9 3750+2070=5820 3750/5+2070/9=980
 3980  5  1840 10 3980+1840=5820 3980/5+1840/10=980

《九章算术》卷第二 粟米的四十五题和四十六题给出的解也在上述结果中。

然而,程序计算出的可行解远多于1个,这是假定1钱最多买10个物品条件下得到的结果。


原文地址:https://www.cnblogs.com/tigerisland/p/7564766.html