2016必威体育精装版java程序设计教程.ppt

11. 公安人员审问四个偷窃嫌疑犯A、B、C、D A: 是B偷的，不是D偷的 B: 我没有偷，是C偷的 C: A没有偷，是B偷的 D: 我没有偷，我用的是我家里的 已确切地知道，四个人中只有一个是偷窃者。还知道四人说的话中要么全是实话，要么全是假话。请根据四个人的答话，判断谁是偷窃者 三种基本算法 递推 递归 迭代 递推法 递推法：递推法实际上是一种递推关系，就是为了得到问题的解，把它推到比原问题简单的问题求解，可分为： 顺推法 倒推法 递推(顺推) 斐波那契兔子问题： 有一对小兔子，出生一个月后变大兔子开始怀孕;再过一个月生出一对小兔子，这时共有两对兔子；同时大兔子再次怀孕；第三个月，以前出生的小兔子变成大兔子，以前怀孕的大兔子又生出一对小兔子，这时共有三对兔子（两对大兔子，一对小兔子），所有大兔子又都全部怀孕；第四个月，以前出生的小兔子变成大兔子，以前怀孕的大兔子又各生出一对小兔子，这时共有五对兔子（三对大兔子，两对小兔子），所有大兔子又都怀孕….. 假设在兔子生养过程中没有死亡，编程序，计算n个月后，有多少对兔子 F1 = 1; F2 = 1; Fn = Fn-1+Fn-2 递推(顺推) 楼梯有24阶台阶，如果一步走1阶或2阶，试问有多少种走法？ u1 = 1, u2 = 2; un = un-1+un-2 递推 海盗分金块问题 10名海盗抢得了窖藏的100块金子，并打算瓜分这些战利品。他们的习惯是按下面的方式进行分配：最厉害的一名海盗提出分配方案，然后所有的海盗（包括提出方案者本人）就此方案进行表决。如果50%或更多的海盗赞同此方案，此方案就获得通过并据此分配战利品。否则提出方案的海盗将被扔到海里，然后下一名最厉害的海盗又重复上述过程。 他们是残忍的， 都乐于看到他们的一位同伙被扔进海里；他们是贪婪的，都千方百计多得一些金块然而他们是聪明的，而且知道其他的海盗也是聪明的。 这些金块不能再分，也不允许几名海盗共有金块，最凶的一名海盗应当提出什么样的分配方案才能使他获得最多的金子呢？  递推（逆推） 六个顾客买花。第一个买走全部的1/2加 1/2盆，第二个买走剩余的1/3加1/3盆 ,第三个买走剩下的1/4加1/4盆,第四个顾客买走剩余的1/5加1/5盆，第五个顾客买走剩余的1/6加1/6盆，第六个顾客一看还剩9盆，便全部买走。请问共有多少盆花？ un-1 = (un+1/n)÷(n-1)/n 一个猴子摘了一堆桃子，第一天吃了一半零一个，第二天吃了剩余的一半零一个，第三天又吃了剩余的一半零一个，如此下去，第十天吃完后剩余一个桃子。编程求猴子最初摘了几个桃子 递归 汉诺塔问题:一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔庙宇和众生也都将同归于尽。 考虑一下把64片金片由一根针上移到另一根针上，并且始终保持上小下大的顺序。这需要多少次移动呢? 这里需要递归的方法。假设有n片，移动次数是f(n).显然f⑴=1,f⑵=3,f⑶=7，且f(k+1）=2*f(k)+1。此后不难证明f(n)=2^n-1。n=64时， 　 　f（64）= 2^64-1=18446744073709551615 　　假如每秒钟一次，共需多长时间呢？一个平年365天有秒，闰年366天，平均每，计算一下， 　　18446744073709551615584554049253.855年 　　这表明移完这些金片需要5845亿年以上，而地球存在至今不过45亿年，太阳系的预期寿命据说也就是数百亿年。真的过了5845亿年，不说太阳系和银河系，至少地球上的一切生命，连同梵塔、庙宇等，都早已经灰飞烟灭。 多维数组 锯齿形数组 Java二维数组实际上数组的数组，作为数组基类型的数组可以是不同长度的 多维数组 二维数组的处理： 一般情况下使用二重for循环处理二维数组 for(int i=0;ia.length;++i) for(int j= 0; ja[i].length; ++j){