算法经典问题系列1百钱买百鸡问题VIP专享VIP免费

算法经典问题系列1 百钱买百鸡问题 一说起唐朝，人们就会情不自禁地想起诗歌，绝对没有人会提到数学在数学上，虽说唐代并没有产生与其前的魏晋南北朝或其后的宋元相媲美的大师，却在数学教育制度的确立和数学典籍的整理方面有所建树.长达近三百年的唐代在数学方面最有意义的事情莫过于《算经十书》的整理和出版，这是高宗李治下令编撰的。除了《周牌算经》《九章算术》《海岛算经》和《缀术》以外，《算经十书》中至少还有三部值得一提，分别是《孙子算经》《张丘建算经》和《缉古算经》'这三部书的共同特点是，每一部都提出了一个非常有价值的问题，并以此传世。 《张丘建算经》成书于公元5 世纪，作者是北魏人.书中最后一道题堪称亮点，通常也被称为百钱买百鸡问题，民间则流传着县令考问神童的佳话书中原文如下： 今有鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一；百钱买鸡百只，问鸡翁、母、雏各几何? 题目的意思是，公鸡5 文钱1 只，母鸡3 文钱1 只，小鸡1 文钱买3 只，现在用 100 文钱共买了 100 只鸡，问：在这100 只鸡中，公鸡、母鸡和小鸡各是多少只?(设每种至少一只)算法分析： 此题很显然是用枚举法，我们以三种鸡的个数为枚举对象(设为x,y,z),以三种鸡的总数(x+y+z) 和买鸡用去的钱的总数(x*3+y*2+z) 为判定条件，穷举各种鸡的个数。 枚举法，常常称之为穷举法，是指从可能的集合中一一枚举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。 1.采用枚举算法解题的基本思路： 2.确定枚举对象、枚举范围和判定条件； 算 法 经 典 问 题 系 列 1百 钱 买 百 鸡 问 题 --第 1页算 法 经 典 问 题 系 列 1百 钱 买 百 鸡 问 题 --第 1页3.一一枚举可能的解，验证是否是问题的解下面是解这个百鸡问题的程序 var x,y,z：integer ； begin for x：=1 to 100 do for y：=1 to 100 do for z：=1 to 100 do if(x+y+z=100)and(x*5+y*3+z/3=100)then writeln('x=',x,'y=',y,'z=',z)；{验证可能的解，并输出符合题目要求的解} end. 这个算法学生容易想到，而重复是计算机的拿手好戏，算法可读性好。那么该算法执行工作量有多大呢?考虑到最耗费时间的是for 循环，故计算机执行语句次数大约是100*100*100=100 万次。这个问题规模 不大，所以程序在计算机上可以很快执行完。 上面的条件还有优化的空间，三种鸡...