書籍筆記 – 頁面 6 – Bake

圖說演算法使用JavaScript(六)

3-14階梯狀圖形外觀 Staircase

對於給定數量的級別，請用$和符號空格打輸出類似「階梯狀」的圖形外觀。

JS staircase.js

const draw = no => {
	let pictures = "";
	for (let row=0; row<no; row++){
		str="";
		for (let column = 0; column<no; column++)
			str += column <= row? "$":" ";
		    pictures +=str + "\n";
	    }
		return pictures;
};
console.log(draw(15));

PHP staircase.php

$my_num = 15; 

function pictures($n){

	for($i=0; $i<$n; $i++){
		  
		  if($i!=0) echo "<br>";
		  
		  for ($j=0; $j<=$i; $j++){
		  echo "$";	
		  }
	}

}

$pictures = pictures($my_num);

3-15金字塔圖形外觀 Pyramid

對於給定數量的級別，請使用$和符號空格打輸出類似「金字塔」的圖形外觀。

課本的JS範例是錯的

我解的是對的↓

PHP pyramid.php

$my_num = 15; 

//function pictures($n){

	$layer = $my_num; //幾層
	$num = $my_num*2-1; //個數
	$mid = $layer ; //中間數

	for($h=1; $h<=$layer; $h++){
	   for($j=$mid-$h; $j>=1; $j--){
	   	echo "  ";
	   }
	   for($i=1; $i<=$h*2-1; $i++){
	   	echo "$";
	   }
	   echo "<br>";
	 }
echo "<br>".$layer."-".$num."-".$mid;

JavaScript 概念三明治(二)

物件型別

   「物件」指的就是物件。恩，但其實有很多東西本身也算是物件，例如陣列和函式，不相信嗎？讓我們繼續看下去。你可以在JavaScript裡面宣告一個陣列，然後用typeof去得到這個陣列的型別，就可以看出一些端倪：

JavaScript提供了Array這個所有地方都可以使用全域物件，而在這個Array.isArray的方法能夠讓我們使用，來知道某數值是不是一個陣列。

好，那麼剛剛說函式也是物件型別，是這樣嗎？你會發現，當你一樣用typeof去觀察一個function的型別時，所得到的結果不是object，而是function。

先別急著反駁，讓我先用一個最簡單的方式證明你看。前面應該提到過，一個物件型別的數值，可以用.或是[]來做存取。那麼首先我宣告一個函式，並把這個函式當作物件使用，在上面新增一個屬性之後，再取出這個屬性來看看，是不是得到同樣的值：

    函式真的是像物件一樣的東西，事實上，它真的就是。在JavaScript裡面，函式算是一個比較物件，稱為「函式物件」(Function Object)，它除了可以被當作函式來呼叫，也能夠當作物件使用。

一級函式 First-Class Function

    當我們說一個語言具有一級函式的特性時，代表這個語言把函式當作變數值一樣看待，也因此可以把函式當作參數一樣傳入另外一個函式裡面，也能夠以函式作為另一個函式的回傳值。在Function Programing 裡面，也是因為這個特性，才有辦法做到複合函式(Function Composition)。
    在JavaScript內，函式本身也是一個特殊的物件(就是函式物件)，所以才有辦法把函式當作參數傳給另外一個函式來做使用。

高階函式 High Order Function

    高階函式有人稱為HOF。只要是可以接收函式作為參數，或是回傳函式作為輸出的函式，我們就能夠把它稱為高階函式，例如，JavaScript裡面的陣列這個類別，上面有許多讓你很方便能夠對陣列做操作的方法，例如：map方法讓你能夠依序對每個陣列做一些修改、而filter則讓你能夠過濾掉不符合條件的元素。
     我們可以試著思考看看他們是怎麼被實做出來的，下面就以Array.map為例，一起來模擬這個方法、邊思考它的運作方式。

試著實作陣列上的map方法

map是在任何陣列上都可以取用的一個方法，它接收一個能夠修改陣列元素的函式。並在運算之後將每個元素被修改後的數值，以另外一個全新陣列最為回傳值。

   由於map其實就是對陣列元素個別巡訪，然後做某些操作之後回傳，所以可以推敲出可能的步驟如下：
1.將包含開發者修改的邏輯函式傳入map方法內。
2.先創造一個全新的陣列，用以存放運算之後的結果。
3.執行一個以陣列長度為執行次數的迴圈。
4.利用迴圈的計數值作為陣列的索引，來找到每個陣列元素。
5.取得陣列元素、逐個取得修改函式運算完的結果。
6.逐個放入運算結果值的陣列並待迴圈節結束後回傳。
有了這些運作的邏輯，我們也能夠嘗試自己實作類似map方法的邏輯，看起來可能會像是這樣：

function arrayMap(fn, array){
 let newArray = [];
  for (let i=0; i < array.length; i++){
   let result = fn(array[i]);
    newArray.push(result);
   }
   return newArray;
}
let array =[1,2,3];
let newArray = arrayMap(function(item){
   return item*2;
},array)
console.log(newArray);

試著實作陣列上的filter方法

    既然都講到這裡了，我們就來看看另一類似的filter方法。filter一樣接受一個函式來進行運算，只不過相對於map是變更陣列的個別元素，filter的目的是過濾不需要的元素，你應該也能從字面上看出來。
傳進filter的函式，會以回傳值的條件判斷，來作為陣列元素會不會被過濾掉的依據，若回傳值與布林值的true等價、可被轉型為true，那麼就保留這個元素，反之這個元素就不會出現在運算結果的陣列裡面。

而我們同樣的能夠推測filter的運作流程，預期上會與map相似：
1.將包含開發者判斷邏輯的函式傳入filter方法內。
2.先創造一個全新的陣列，用以存放運算的結果。
3.執行一個以陣列長度為執行次數的迴圈。
4.利用迴圈的計數值作為陣列的索引，來找到每個陣列元素。
5.取得陣列元素、並逐個取得判斷函式運算文成的結果。
6.依照判斷函式的結果決定是否要放入結果值的陣列，並待迴圈結束後回傳。

function arrayFilter(fn, array){
   let newArray=[];

   for (let i=0; i < array.length; i++){
      let arrayElement = array[i];
      let shouldkeep = fn(arrayElement);

      if (Boolean(shouldkeep)){
         newArray.push(arrayElement);
      }
   }

   return newArray;
}

let array = [1,2,3];
let resultArray = arrayFilter(function (element){
   return element > 1;
},array);

console.log(resultArray);

圖說演算法使用JavaScript(五)

3-11最大利潤 Max Profit

    給定一系列股票價格，找出產生最大利潤的最小買入價和最大賣出價。舉例以陣列的方式提供一系列的股票價格，例如[24,27,32,36,45]，這個函數會找出這一系列的股票價格的最低買入價及最高賣出價，再以陣列的方式回傳，如此一來可以計算出這支股票的最大利潤。

JS max_prifit.js

var maxProfit=(prices)=> {
	let low = prices[0] < prices[1]? prices[0]:prices[1];
	    high = prices[0] < prices[1] ? prices[1]:prices[2];
	let maxProfit = high - low;
	let temp = low;

	for (let index = 2; index < prices.length; index++){
		const sellPrice = prices[index];

		if (low > sellPrice) temp = prices[index];
		else{
			const  profit = sellPrice - low;
			if (profit > maxProfit)
				(maxProfit = profit),
				(high = sellPrice),
				(low = temp);
		}
	}
    return [low, high];
}
console.log("產生最大歷潤的最小買入價和最大賣出價分別為：");
console.log(maxProfit([24,27,32,36,45]));

PHP max_profit.php

$arr= array (24,27,32,36,45);
function get_max_profit($arr){

$low = ($arr[0] < $arr[1]) ? $arr[0] : $arr [1];
$high = ($arr[0] > $arr[1]) ? $arr[0] : $arr[1];
$maxProfit = $high - $low;
$temp = $low;
$len = count($arr);
$ans = array();
$i=1;
 while (  $i <= $len-1){
		$sellPrice = $arr[$i];

		if($low > $sellPrice) $temp = $arr[$i];

		else {
			$profit = $sellPrice -$low;
			if($profit > $maxProfit){
				$maxProfit = $profit;
				$high = $sellPrice;
				$low = $temp;
			}

		}
		$i++;
	}

	$ans[] =array($low,$high);
	return $ans;
}
$my_max_profix = get_max_profit($arr);
print_r($my_max_profix);

3-12費伯納序列 Fibonacci

JS fibonacci.js

var fib=(n)=>{
	if (n==0){
		return 0;
	} else if (n==1 || n==2){
		return 1;
	} else{
		return (fib(n-1)+fib(n-2));
	}
}

const num=10;

for(i=0; i<=num; i++){
	console.log("fib("+i+")=" + fib(i));
}

PHP fibonacci.php

$my_num = 30;  //超過38時，執行會超過30秒
function my_fibnacci ($n){

	switch ($n) {
		case ($n==0):
			return 0;
			break;
		case ($n==1 ||$n==2):
			return 1;
			break;
		default:
			return(my_fibnacci($n-1)+my_fibnacci($n-2));
			break;
	}
}
for ($i=0 ; $i<=$my_num; $i++){
	echo "fib(".$i.")=".my_fibnacci($i)."<br>";
}

3-13記憶式費伯納序列 Memoized Fibonacci

    這是一種具有記憶性質的費伯納序列的做法，它可以使得在求取費伯納序列能以較高的效率取得。也就是動態規劃法，它是一種具備記憶體功能的演算法。

JS momoized_fibonacci.js

output =[];   //宣告陣列
var fib=(n)=>{
	if (n==0)  return 0;
	
	if (n==1 ) return 1;
	else{
		output[0]=0;
		output[1]=1;
		for (t=2; t<=n; t++){
			output[t]=output[t-1]+output[t-2];
		}
		return output[n];
	}
}
const num=9;
for(i=0; i<=num; i++){
	console.log("fib("+i+")=" + fib(i));
}

PHP memoize_fibonacci.php

$my_num = 50; 

function my_fibnacci ($n){
   $ans=array();
	 
	 if($n==0) return 0;
	 if($n==1) return 1;
	 else{
	 	$ans[0]=0;
	 	$ans[1]=1;
	 	for ($j=2; $j<=$n; $j++){
	 		 $ans[$j]=$ans[$j-1]+$ans[$j-2];
	 	}
	 	return $ans[$n];
	 }
	}

for ($i=0 ; $i<=$my_num; $i++){
	echo "fib(".$i.")=".my_fibnacci($i)."<br>";
}

一	二	三	四	五	六	日
« 五月
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30