穷举法习题课

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,穷举法习题课,不积跬步无以至千里,不积小流无以成江海,2010-4-8,1,第1棒：有从1到9共计9个号码球，请问，可以组成多少个三位数？编程打印出来。,123和213是两个不同的排列数。即对排列顺序有要求的，既属于“排列P”计算范畴。 上问题中，任何一个号码只能用一次，显然不会出现988,997之类的组合， 我们可以这么看，百位数有9种可能，十位数则应该有9-1种可能，个位数则应该只有9-1-1种可能，,2,第1棒：有从1到9共计9个号码球，请问，如果三个一组，代表“三国联盟”，可以组合成多少个“三国联盟”？编程打印出来。,213组合和312组合，代表同一个组合，只要有三个号码球在一起即可。即不要求顺序的，属于“组合C”计算范畴。,3,第2棒：编程找出三位数到五位数中的所有阿姆斯特朗数。它的定义是：一个N位自然数的各位数字的N次方之和等于它本身。例如153是三位阿姆斯特朗数（也叫水仙花数），8208则是一个四位数的阿姆斯特朗数。,4,第2棒：输入一根木棒的长度，将该木棒分成三段，每一段的长度为正整数；输出由这三段小木棒组成的不一样边长的三角形的个数。如输入10，则输出2，能组成的两个三角形边长为2、4、4 和3、3、4。,5,第3棒：用质量为1，3，9，27和81的五种砝码各1个（假如单位为克）称物体的质量，最大可称121，在实验室我们一般要求“物左砝右”。如果砝码允许放在天平的两边，编程输出称不同质量（1121）物体时，砝码应该怎样安排？,例如要称一个m=14克的物体，我们知道14=27-9-3-1，即14+9+3+1=27。所以我们可以把天平一端放置该和9、3、1的砝码，而另一端放27的砝码，这样即可称出。,被称物体的质量计算的数学原理：设被称物体m放在天平左边，根据天平平衡原理，左边质量应等于右边质量。问题关键在于算法中如何体现砝码放在天平左边、右边或没有参加称量。,这里可以用-1、1、0表示砝码放在天平左、右和没有参加称量，再没有其它数，所以称为三进制数，每个砝码都有这样的三种状态。,被称物体质量计算为： = a*81 + b*27 + c*9 + d*3 + e。这里a，b，c，d，e分别表示81，27，9，3，1克的砝码是放在天平的左边、右边或是没用。,6,第4棒：一元三次方程的解。设有一元三次方程ax3+bx2+cx+d=0,给出该方程中各项系数a、b、 c、d （均为实数），并假设该方程一定存在三个不同的实数解（范围在-100100之间），且解与解之间的绝对值大于等于1.请编程由小到大输出这三个解，精确到小数点后2位。,涉及到实数？ 如何穷举？,7,