圖說演算法使用JavaScript(二)

3-1題目:字串反轉(String Reversal)
撰寫一個函數,傳入的引數為一個字串,其輸出結果會將該字串以反轉的方式輸出。

JS   String_Reversal.js

const reverse1 = str =>
	str
		.split("")
		.reverse()
		.join("")

const reverse2 = str =>{
	let result = "";
	for (let ch of str) result = ch +result;
		return result;
	};

console.log(reverse1("不要在你的智慧中夾雜著傲慢。不要使你的謙虛新缺乏智慧。"));
console.log(reverse2("一個人年輕的時候,不會思索,他將一事無成。"))

PHP    String_Reversal.php

$my_str="不要在你的智慧中夾雜著傲慢。不要使你的謙虛新缺乏智慧。";
echo "原來的字串:".$my_str."<br>";

function my_reverse ($str){

	$len = strlen($str);
	$str_ar = str_split($str);
	$str_ar = array_reverse($str_ar);
	$str_ar = join($str_ar);
	//echo $len;
	return $str_ar;

}

$my_len=my_reverse($my_str); 
$my_len = strrev($my_str);
//這兩個方法,中文反轉後都會出現亂碼。
使用函數
strlen($str) 傳回字串的長度
array_reverse($arr) 以相反的順序傳回陣列
join() 把陣列組合為一個字串
strrev 反轉字串

PHP 中文字串反轉會出現亂碼,需要做以下的判斷。


3-2題目:迴文Palindrome
所謂迴文是指由左唸到右或由又唸到左,字母排列順序都一樣的,例如以下的字串就是一個迴文:
"人人愛我!我愛人人"

JS   palindrome.js

const isPalindrome = str =>
	str
        .split("")
	.every((ch,index) => ch === str[str.length - 1 - index]);

console.log("[人人愛我!我愛人人] 這句話是否為迴文(palindrome)?",
             isPalindrome("人人愛我!我愛人人"));

PHP   palindrome.php

$my_str="不要在你的智慧中夾雜著傲慢。不要使你的謙虛新缺乏智慧。";
//$my_str="Hello World! 你好世界!";
//$my_str="我為人人,人人為我";
//$my_str="gooddoog";
echo "原來的字串:".$my_str."<br>";

function mb_str_split($str){
	//不分中英字串都可以切成陣列
	return preg_split('/(?<!^)(?!$)/u',$str);
}

$arr = mb_str_split($my_str);
print_r ($arr);
$len = count($arr);     //計算字串數
$mid_len=floor($len/2); //取中間整數
echo "<br>-----<br>";

for ($i=0; $i<=$mid_len-1; $i++){

	 if($i==0) 
	 	$last=$len-1;   //第一筆 頭-尾
	 else 
	   $last=$len-1-$i;
	//比對兩個字是否一樣,一樣就為0
	$check_f = strcmp($arr[$i],$arr[$last]); 
	echo $arr[$i]."-".$arr[$last]."<br>";
	if ($check_f ==0){
		$flag="true";
		continue;
	}else{
		$flag="false";
		//break;
	}
}

echo "<br>".$len."-".$mid_len."<br>";
echo "FLAG=".$flag;
?>
使用函數:
count() 傳回陣列中元素的數目
floor() 取中間整數
strcmp 比較兩個字串(對大小寫敏感)

3-3題目:整數反轉(Integer Reversal)
整數反轉的函數是只給定一個整數的引數,該函數會反轉該數字的順序。例如,原傳入字串為「12345」,則其輸入結果為「54321」。

JS      inter_reversal.js

const rev = integer =>
	Math.sign(integer)*parseInt(
		integer
		.toString()
		.split("")
		.reverse()
		.join("")
		);
console.log(rev(98754321));
console.log(rev(-987001200));

PHP    integer_reversal.php

$my_int=-987001200;
//$my_int=987654321;
//print_r(str_split($my_int));
echo "原始的數字=".$my_int;
function integer_reversal ($int){
    $minus=0;
	$arr=str_split(strval($int));
		
	$len = count($arr)-1;
    //echo "<br>".$len;
	for($i=$len; $i>=0; $i--){
		if($arr[$i]=="-")
		 $minus=1;  //偵測是否為負數
		else
      	 $re_arr[]=$arr[$i];
    }
	return [$re_arr,$minus]; //返回兩個數值
}

$my_re=integer_reversal($my_int);
echo "<br>";
$num=intval(join($my_re[0]));
if ($my_re[1]==1)
$num=$num*(-1);	
echo "<br>反轉後數字=".$num;
使用函數:
strval() 函數用於取得變數的字串值

圖說演算法使用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."會開始是負數";