分页: 1 / 2

“百钱买鸡”最优解

发表于 : 2009-01-10 0:47
flyinflash
“百钱买鸡问题”出自公元前五世纪中国数学家张丘建的《算经》:公鸡每只五元,母鸡每只三元,而鸡仔每只一元。用一百元买一百只鸡,公鸡、母鸡和鸡仔(cocks, hens,chicks)各有多少只呢?

代码: 全选

# c
int cocks, hens, chicks;
for ( cocks = 1; cocks < 20; cocks ++ )
    for ( hens = 1; hens < 32; hens ++ )
        for ( chicks = 1; chicks < 92; chicks ++ )
            if (cocks * 5 + hens * 3 + chicks * 1 == 100)
                printf( "%2d, %2d, %3d \n", cocks, hens, chicks );

代码: 全选

# python
for cocks in range(1, 20):
    for hens in range(1, 32):
        for chicks in range(1, 92):
            if cocks * 5 + hens * 3 + chicks * 1 == 100:
                print "%2d, %2d, %3d" % (cocks, hens, chicks)
明显地,上面是最简单的方法,O(19*31*91)。现求最优解,请各位动手动脑 :em01

Re: “百钱买鸡”最优解

发表于 : 2009-01-10 1:51
stlxv
最优解是直接写出答案

Re: “百钱买鸡”最优解

发表于 : 2009-01-10 2:41
Tell360
stlxv 写了:最优解是直接写出答案
flyinflash, :em11 :em05 :em09 :em04

Re: “百钱买鸡”最优解

发表于 : 2009-01-10 4:20
ibear
call鸡场老板,¥100买100只鸡,大小、公母随便,可否?可,有解,O(¥100*统计时间);否,递归 :em05

中止条件?

Re: “百钱买鸡”最优解

发表于 : 2009-01-10 7:07
HuntXu
这题目写错了吧...
一百元怎么买也只能买到100只小鸡... :em20
用小鸡做贪心,第二次运算就可以结束了...

Re: “百钱买鸡”最优解

发表于 : 2009-01-10 9:37
firstddf
小鸡应该只0.5元

年底了不能随便涨价,小心物价局查你 :em04

Re: “百钱买鸡”最优解

发表于 : 2009-01-10 11:21
xhy
5x + 3y + z = 100

枚举x从 0到 20
枚举y从 0到 33

5x + 3y <= 100 就是解了

z不用枚举

Re: “百钱买鸡”最优解

发表于 : 2009-01-14 9:35
hyxuzhimin
楼上的才是最优啊。 :em02

Re: “百钱买鸡”最优解

发表于 : 2009-01-14 9:57
frogfrogfrog
xhy 写了:5x + 3y + z = 100

枚举x从 0到 20
枚举y从 0到 33

5x + 3y <= 100 就是解了

z不用枚举

赞~!

Re: “百钱买鸡”最优解

发表于 : 2009-02-09 15:14
vvvli
5x+3y+z=100
x+y+z=100

=> 2x+y=0

Re: “百钱买鸡”最优解

发表于 : 2009-02-09 15:40
flyinflash
7 楼的不错
:em01

Re: “百钱买鸡”最优解

发表于 : 2009-02-09 16:00
lerosua
学习七楼

Re: “百钱买鸡”最优解

发表于 : 2009-02-25 11:40
huxianhui
我知道了。这题我思考了也好久。一整本都是算这题的

最终算了出来。在C里的经典题目,
哦。原来是求最简单的算法啊,这就不清楚了。只能答。我的很烂

Re: “百钱买鸡”最优解

发表于 : 2009-02-28 18:08
delectate
单是貌似还是要for循环下……

Re: “百钱买鸡”最优解

发表于 : 2009-03-02 12:49
pypcjs
huxianhui 写了:我知道了。这题我思考了也好久。一整本都是算这题的

最终算了出来。在C里的经典题目,
哦。原来是求最简单的算法啊,这就不清楚了。只能答。我的很烂
这关C啥鸟事,不要有事没事就往C身上勾。