迭代法,遞歸,窮舉法

1、迭代法、遞歸、遞推、窮舉法、迭代法例：求兩個數(shù)的最大公約數(shù)輾轉相除法：如果不用較大的數(shù)對較小的數(shù)取余數(shù)，如果余數(shù)為0那么最大公約數(shù)就是小的那個數(shù)。 為0那么讓除數(shù)變?yōu)檩^大的數(shù)，余數(shù)變?yōu)檩^小的數(shù)，繼續(xù)這樣下去直到余數(shù)為0。var num0 =Number( prompt (” 輸入一個數(shù)");var numl =Number( prompt ("再輸入一個數(shù)")；var res =maxGCD (num0 ,num1 ); alert (res);function maxGCD (x,y)var max =Math .max(x,y);var min = Math

2、.min(x,y);while (max % min!=0)var temp =max %min;max =min;min = temp ;return min ;這個就叫迭代法：也叫輾轉法。規(guī)律：不斷的用舊的值去改變新的值，直到想要得到的結果。套路：(1) 找到迭代的變量(I日的值)被除數(shù)、除數(shù)和余數(shù)(2) 確定迭代的關系直接賦值(3) 迭代的條件余數(shù)不等于0作業(yè)：求一個數(shù)的算術平方根(牛頓法)var num =Number( prompt ("請輸入一個數(shù)");var k=1;while (Math .abs (k*k-num )>1e-9)k=(k+ num /

3、k)/2;document .write(k);5兔子產(chǎn)子問題：一般來說：兔子在出生 2個月后就能生崽 一對兔子每個月能生出一對兔子最開始有一對剛出生的兔子假設所有的兔子都不死，問一年后多少對兔子月份01234總和112358var arr =1,1;for (var i=2;i<12;i+)arr i=arr i-1 +arr i-2;alert(arr11);對于遞推，最重要的就是找到數(shù)學公式，從當前項或當前幾項推出下一項。猴子摘桃子：一個猴子，第一天摘了若干個桃子當即吃了一半不過癮有吃了一個。第二天又吃掉剩下的一半， 又多吃了 2個，第三天還是吃掉一半又多吃了 3個，到了第n天發(fā)現(xiàn)

4、 只剩下一個桃子。請問：第一天摘了多少個？var num =Number( prompt (” 請輸入天數(shù)");var sum =1;for (var days =num ;days >0;days -)sum =(sum +days )*2;alert(sum);關于存錢的問題：一個富豪，給它的兒子的四年大學生活存了一筆生活費，富二代每個月只能取3000作為下個月的生活費，年利率是1.71%，富豪一次性要存多少錢？var money =3000;for (var mon th =47;mo nth >0;m on th -)money =money /(1+0.0171

5、 /12)+3000;alert (money );三、窮舉法：百錢買百雞問題100元錢如何買100只雞公雞5兀一只，母雞 3兀一只，小雞1兀3只for (var x=0;x<20;x+)for (var y =0; y <33; y+)if (100 - x -y )=(100- 5 * x- 3 * y) * 3) varz = 100-x-y;document .write("雞翁:"+x + "&nbsp" +"雞母:"+y+ "&nbsp" +"雞雛: "+

6、z);document .write ("</br>");窮舉法：一般代碼比較簡單。但是計算量會很大，尤其沒有經(jīng)過人為的過濾。但是計算機的優(yōu)勢就是運算速度快，所以這個算法揚長避短。可以得到很好地效果，雖然計算機的計 算速度快但是有一定的局限。所以有的時候需要我們人為去優(yōu)化算法。減少計算的次數(shù)。案例：有一個三位數(shù)，個位數(shù)字比百位數(shù)字大，而百位數(shù)字比十位數(shù)字大，并且個位 數(shù)字之和等于個位數(shù)字相乘之積，求這個三位數(shù)。法一：for (var numO =1;numO <10 ;num0 +)for (var numl =1;numl <10;num1 +)f

7、or (var num2 =1;num2 <10;num2 +) if(num0 +num1 +num2 =num0 *num1 *num2 )if(num0 >num2 && num2 >num1 ) document .write (num0 +num1 *10+num2 *100);法二：for (var num =100;num <1000; num +)var a = Math .floor(num /100);百位var b = Math .floor(num /10) % 10;/十位var c = num % 10;/個位if (c &g

8、t; a&& a >b && (a + b +c) = a * b *c) var num = a *100 + b *10 + c;document .write(num);作業(yè)：蜘蛛有8條腿，蜻蜓有6條腿和2對翅膀，禪有6條腿和1對翅膀，三種蟲子 一共有18只，共有118條腿和20對翅膀。問每種蟲子各有多少只？for (var zz=0;zz<14 ;zz+)for (var qt=0;qt <10 ;qt+)for (var c=0;c<19;c+)if(zz+qt +c)=18 &&(zz*8+qt*6+c*6)=

9、118 && (qt*2+c)=20) document .write(”蜘蛛："+zz+"蜻蜓："+qt+"蟬："+c+"</br>");四、遞歸什么叫遞歸。函數(shù)內部調用本身。求階乘問題Function fact(n)If(1=n)Retur n 1;Return n*fact(n-1);遞歸算法如果按照常規(guī)思路去理解，非常復雜，函數(shù)調用的嵌套一層套一層，然后一層一層返回。使用遞歸的條件，必須要有一個已知的結果。遞歸實際上就是一個降階問題，將n階的問題轉化為 n-1階的問題，也就是去找 n和n-

10、1的關系。漢諾塔的遞歸算法：var n=Number( prompt(”請輸入柱子的數(shù)目")；var step =0;move( n);alert (step );fun cti on move (n)if(n=1)step +;returnelse move (n -1);step +;move (n -1);例:猴子選大王問題：一圈猴子，選大王報數(shù)，報的數(shù)為3就自動退出，直到最后一只猴子當選為大王。var num =Number( prompt ("輸入猴子的個數(shù)");var king =selectKing (num );alert (king );function selectKing (n)if(1=n)return 0;else return (selectKing (n-1)+3)%n;作業(yè)：青蛙跳臺階已知有n個臺階，青蛙一次可以一個臺階也可以跳兩個臺