圖說演算法使用JavaScript(一)

演算法特性內容與說明
輸入 Input0個或多個輸入資料,這些輸入必須有清楚的描述或定義。
輸出 Output至少會有一個輸出’結果,不可以沒有輸出結果。
明確性 Definiteness每一個指令會步驟必須是簡潔明確而不含糊的。
有限性 Finiteness在有限步驟後一定會結束,不會產生無窮迴路。
有效性 Effectiveness步驟清楚且可行,能讓使用者用紙筆計算而求出答案。
執行Node.js
再命令提示字元下輸入Node即可執行。

地球上最常見經典演算法

分治演算法

分治法Divide and conquer是一種很重要的演算法,我們可以應用分治法來逐一拆解複雜的問題,核心精神是將一個難以解決的大問題依照不同的概念,分割成兩個或更多的子問題,以便各個擊破,分而治之。
範例:  
如果有8張很難畫的圖,我們可以分成2組各四幅來完成,如果還是覺得太複雜,繼續再分成四組,每組各兩幅來完成,利用相同模式反覆切割問題,這就是最簡單的分治法核心精神。

遞迴演算法

遞迴是種很特殊的演算法,分治法和遞迴法很像,都是將一個複雜的演算法問題的規模變得越來越小,最終使子問題容易求解。
從程式語言的角度來說,遞迴的定義是,假如一個函數或副程式,是由自身所定義或呼叫,就稱為遞迴Recursion,它至少要定義2種條件,一個可以反覆執行的遞迴過程,與一個跳出執行過程的出口。
範例: recursion.js,recursion.php
我們知道階乘函數是數學上有名的函數,對遞迴式而言,也可以看成是很典型的範例,我們一般以符號"!"來表示階乘。如4階乘可寫為4!。
n!=n*(n-1)*(n-2).....*1

JS 範例    recursion.htm

let i=5;
		//var ans;
		function factorial(i) {
			var ans;
			if (i==0) return 1
			else ans=i*factorial(i-1);
			return ans;
		}


	console.log(`${i}階乘值為`+factorial(i));

PHP   範例        recursion.php

<?php
$count_num=5;

function factorial($i){

	if ($i==0) {
		$ans=1;
	}
	else{
		$ans=$i*factorial($i-1);
	}
    return $ans;
}

$result=factorial($count_num);
echo "count_num".$result;
?>

貪心法(給我最好,其餘免談)

貪心法Greed Method又稱為貪婪演算法,分法是從某一起點開始,在每一個解決問題步驟使用貪心原則,都採取在當前狀態下最有利或最優化的選擇,不斷的改進該解答,持續在每一步驟中選擇最佳的方法,並且逐步逼近給並的目標,當達到某一步驟不能再繼續前進時,演算法停止,以盡可能快的求得共好的解。

動態規劃演算表(分治法的麻吉兄弟)

動態規劃法Dynamic Programming Algorithm ,DPA 類似分治法,由20世紀50年代初美國數學家R.E.Bellman所發明,用來研究多階段決策過程的優化過程與求得一個問題的最佳解。動態規劃法主要的做法是如果一個問題答案與子問題
相關的話,就能將大問題拆解成各個小問題,其中與分治法最大不同的地方是可以讓每一個子問題的答案被儲存起來,以供下次求解時直接取用。這樣的作法不但能減少再次需要計算的時間,並將這些解組合成大問題的解答,故使用動態規劃則可以解決重複計算的缺點。

疊代演算法(不斷繞圈的演算法)

疊代法iterative method 是無法使用一次求解,而須反覆運算,例如用迴圈去循環重複程式碼的某些部份來得到答案。
fac.js;fac.php > 請利用for迴圈設計一個計算1!~n!的遞迴程式

fac.js => 不能執行因為我的環境沒有安裝prompt套件

PHP 範例       fac.php

<?
$fac = 1;
$my_n = 10;
for ($i=0; $i<=$my_n; $i++){

	for ($j=$i; $j>0; $j--){
		$fac *=$j;     // $fac=$fac*$j
	} 
	echo $i."!=".$fac."<br>";
	$fac = 1;   //$fac要歸1
}
?>

While迴圈  需要具備三個條件

1.變數初始值
2.迴圈條件式
3.調整變數增減值
<?php
$i = 1;                   //變數初始值
while ($i<10){            //迴圈條件式
	echo $i."<br>";
    	$i +=1;           //調整變數增減值
}   
?>

枚舉演算法(人人都有份的演算法) Enumerate

枚舉法(又稱窮舉法),是一種常見的數學方法,也是日常中使用到最多的一個演算法,它的核心思想就是:枚舉所有的可能。根據問題要求,一一枚舉問題的解答,或者為了解決問題而分為不重複、不遺漏的有限種情況,一一枚舉並加以解決,最終達到解決整個問題的目的。枚舉法這種分析問題、解決問題的方法,得到的結果總是正確,唯一的缺點就是速度太慢。
範例:
當某數1000,依次減去1,2,3...直到哪一數時,相減的結果開始為負數。

JS enumerate.js

<script type="text/javascript">
		x=1;
		num=1000;
		while (num >=0){
			num-=x;
			x=x+1;
		}

		console.log(x-1);
</script>

PHP       enumerate.php

$x=1;

$my_num=1000;
$j = $my_num;
while ($j >=0){

	$j -=$x;
	$x = $x+1;
}

$y=$x-1;
echo $my_num."減到數字".$y."會開始是負數";

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料