资源描述：
《程序设计基础 Java语言 教学课件 作者 余先锋ch09.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Java系列教材《程序设计基础》第九章：算法与程序技巧本章要点穷举算法递推算法迭代算法递归算法查找算法排序算法算法综合与问题求解穷举法穷举法特点穷举法的思路是，列举出所有可能的情况，逐个判断有哪些是符合问题所要求的条件，从而得到问题的解答。穷举算法模式：（1）问题解的可能搜索的范围：用循环或循环嵌套结构实现；（2）写出符合问题解的条件；（3）对程序进行优化，缩小搜索范围，减少程序运行时间。穷举法穷举法示例求水仙花数：3位整数，该数等于该数各位的立方和。如：153=13+53+33inti,i0,i1,i2;for(i=100;i<1000;i++)
2、{i0=i%10;//个位i1=i/10%10;//十位i2=i/100;//百位if(i2*i2*i2+i1*i1*i1+i0*i0*i0==i){System.out.println(i);}}穷举法穷举法示例将一张面值为100元的人民币等值换成100张5元、1元和0.5元的零钞，要求每种零钞不少于1张，问有哪几种组合inty5,y1,y0;System.out.println("5元t1元t0.5元");for(y5=1;y5<20;y5++){for(y1=1;y1<100;y1++){y0=100-y5-y1;if(y5*5+y1+y
3、0*0.5==100){System.out.println(y5+"t"+y1+"t"+y0);}}}穷举法穷举法示例公元前5世纪，我国数学家张丘建在《算经》一书中提出了一个“百钱买百鸡问题”。问题如下：鸡翁一值钱5，鸡母一值钱3，鸡雏三值钱1。百钱买百鸡，问鸡翁、鸡母和鸡雏各几何？inty5,y3,y0;System.out.println(“鸡翁t鸡母t鸡雏");for(y5=0;y5<=20;y5++){for(y3=0;y3<=33;y3++){y0=100-y5–y3;if(y5*5+y3*+y0/3==100){System.
4、out.println(y5+"t"+y3+"t"+y0);}}}穷举法穷举法示例如果一个正整数的立方能够分解为另外3个正整数的立方和，那么我们把这个正整数称为“好数”。即若A、X、Y、Z都是正整数，且满足A3=X3+Y3+Z3，则称A为好数。例如，6是最小的好数(63＝33+43+53)。请求出最小的10个好数。穷举法求好数：inti=0,n=4,i1,i2,i3;while(i<=10){for(i1=n-1;i1>0;i1--)//分解后的三个数，只能比n小{for(i2=i1-1;i2>0;i2--){for(i3=i2-1;i3>0;
5、i3--){if(i3*i3*i3+i2*i2*i2+i1*i1*i1==n*n*n){System.out.println(""+n+":"+i3+","+i2+","+i1);i++;}}}}n++;}穷举法将1,2...9共9个数分成三组,分别组成三个三位数,且使这三个三位数构成1:2:3的比例intx,y,z;//x:y:z=1:2:3intn[]=newint[10];booleanflag;for(x=123;x<=321;x++){flag=true;y=2*x;z=3*x;for(inti=0;i<10;i++)n[i]=0;f(n
6、,x);统计每位数的个数f(n,y);f(n,z);for(inti=0;i<10;i++){if(n[i]>1){flag=false;break;}}if(flag)System.out.println(""+x+","+y+","+z);}穷举法publicstaticvoidf(int[]n,intx)//统计每位数的个数{inti;i=x/100;//百位n[i]++;i=x%100/10;//十位n[i]++;i=x%10;//个位n[i]++;}递推算法递推算法是一种简单的算法，即通过已知条件，利用特定关系得出中间推论，直至得到结果的
7、算法。递推算法分为顺推和逆推两种。顺推法所谓顺推法是从已知条件出发，逐步推算出要解决的问题的方法叫顺推。如Faibonacci数列，设它的函数为f(n),已知:f(1)=1，f(2)=1;f(n)=f(n-2)+f(n-1)(n>=3,n∈N)。则我们通过顺推可以知道:f(3)=f(1)+f(2)=2,f(4)=f(2)+f(3)=3……直至我们要求的解。逆推法所谓逆推法从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为逆推。递推算法递推算法(顺推)//计算自然数e//e=1/1!+1/2!+1/3!+...+1/
8、n!;doublee=1,t=1;ints=1,i=1;while(t>1E-10)//精确到小数点后10位{s*=i;t
