“百钱买鸡”最优解

软件和网站开发以及相关技术探讨
flyinflash
帖子: 2376
注册时间: 2006-09-21 14:28

“百钱买鸡”最优解

#1

帖子 flyinflash » 2009-01-10 0:47

“百钱买鸡问题”出自公元前五世纪中国数学家张丘建的《算经》:公鸡每只五元,母鸡每只三元,而鸡仔每只一元。用一百元买一百只鸡,公鸡、母鸡和鸡仔(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
头像
stlxv
论坛版主
帖子: 8275
注册时间: 2006-05-03 0:39
来自: المريخ

Re: “百钱买鸡”最优解

#2

帖子 stlxv » 2009-01-10 1:51

最优解是直接写出答案
PHP是最好的语言!不服来战!
Tell360
帖子: 6
注册时间: 2008-08-23 12:22

Re: “百钱买鸡”最优解

#3

帖子 Tell360 » 2009-01-10 2:41

stlxv 写了:最优解是直接写出答案
flyinflash, :em11 :em05 :em09 :em04
头像
ibear
帖子: 787
注册时间: 2006-10-19 8:43
来自: 长江口

Re: “百钱买鸡”最优解

#4

帖子 ibear » 2009-01-10 4:20

call鸡场老板,¥100买100只鸡,大小、公母随便,可否?可,有解,O(¥100*统计时间);否,递归 :em05

中止条件?
头像
HuntXu
帖子: 5776
注册时间: 2007-09-29 3:09

Re: “百钱买鸡”最优解

#5

帖子 HuntXu » 2009-01-10 7:07

这题目写错了吧...
一百元怎么买也只能买到100只小鸡... :em20
用小鸡做贪心,第二次运算就可以结束了...
HUNT Unfortunately No Talent...
firstddf
帖子: 36
注册时间: 2006-10-19 18:55

Re: “百钱买鸡”最优解

#6

帖子 firstddf » 2009-01-10 9:37

小鸡应该只0.5元

年底了不能随便涨价,小心物价局查你 :em04
头像
xhy
帖子: 3916
注册时间: 2005-12-28 1:16
系统: Ubuntu 12.10 X64
来自: 火星

Re: “百钱买鸡”最优解

#7

帖子 xhy » 2009-01-10 11:21

5x + 3y + z = 100

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

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

z不用枚举
目前负债150多万
头像
hyxuzhimin
帖子: 249
注册时间: 2008-05-09 14:14

Re: “百钱买鸡”最优解

#8

帖子 hyxuzhimin » 2009-01-14 9:35

楼上的才是最优啊。 :em02
头像
frogfrogfrog
帖子: 19
注册时间: 2008-07-13 23:19

Re: “百钱买鸡”最优解

#9

帖子 frogfrogfrog » 2009-01-14 9:57

xhy 写了:5x + 3y + z = 100

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

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

z不用枚举

赞~!
vvvli
帖子: 441
注册时间: 2006-10-26 7:02

Re: “百钱买鸡”最优解

#10

帖子 vvvli » 2009-02-09 15:14

5x+3y+z=100
x+y+z=100

=> 2x+y=0
flyinflash
帖子: 2376
注册时间: 2006-09-21 14:28

Re: “百钱买鸡”最优解

#11

帖子 flyinflash » 2009-02-09 15:40

7 楼的不错
:em01
头像
lerosua
论坛版主
帖子: 8455
注册时间: 2007-11-29 9:41
联系:

Re: “百钱买鸡”最优解

#12

帖子 lerosua » 2009-02-09 16:00

学习七楼
头像
huxianhui
帖子: 91
注册时间: 2007-12-21 22:36

Re: “百钱买鸡”最优解

#13

帖子 huxianhui » 2009-02-25 11:40

我知道了。这题我思考了也好久。一整本都是算这题的

最终算了出来。在C里的经典题目,
哦。原来是求最简单的算法啊,这就不清楚了。只能答。我的很烂
实践理想,多做自己怕的事



停止改变别人,开始改变自己

——————————————
我要变的更强!#¥#%#@!……%&!
delectate
帖子: 18311
注册时间: 2008-01-09 22:41

Re: “百钱买鸡”最优解

#14

帖子 delectate » 2009-02-28 18:08

单是貌似还是要for循环下……
pypcjs
帖子: 61
注册时间: 2005-11-15 23:10

Re: “百钱买鸡”最优解

#15

帖子 pypcjs » 2009-03-02 12:49

huxianhui 写了:我知道了。这题我思考了也好久。一整本都是算这题的

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