Bake_WP空間 – 頁面 14

8-3內插搜尋法

內插搜尋法(Interpolation Search)又叫做插補循法，是二分搜尋法的改進版。它是依照資料的分布，利用公式預測資料的所在位置，再以二分法的方式漸漸逼近。使用內插法是假設資料平均分布在陣列中，而每一筆資料的差距是相當接近或有一定的距離比例。其內插搜尋法的公式為：

其中key是要尋找的鍵，data[high]、data[low]是剩餘待尋找記錄中的最大值及最小值，對資料筆數為n，其內插搜尋法的步驟如下：

JS interpolation.js

var Interpolation=(data, val)=> {
	low=0;
	high=49;
	console.log('搜尋處理中......');
	while (low<=high && val!=-1) {
		const rangeDelta=data[high]-data[low];
		const indexDelta=high-low;
		const valueDelta=val-data[low];
		if (valueDelta<0) {
			return -1;
		}
		if (!rangeDelta) {
			return data[low] === val ? low: -1;
		}
		const mid=low+Math.floor((valueDelta*indexDelta)/ rangeDelta);
		//內插法公式
		if (val==data[mid])
			return mid;
		else if (val < data[mid]) {
			console.log(val,'介於位置',low+1,'[',data[low],']及中間值'
						,mid+1,'[',data[mid],']，找左半邊"');
			high=mid+1;
		}
		else {
			console.log(val,'介於中間值位置',mid+1,'[',data[mid],']及'
						,(high+1),'[',data[high],']找右半邊');
			low=mid+1;
		}
	}
	return -1;
}

val=1;
var data=new Array();

for (i=0; i<50; i++) {
	data[i]=val;
	val=val+Math.floor(Math.random()*5)+1;
}

while (true) {
	num=0;
	const prompt=require('prompt-sync')();
	val = prompt('請輸入搜尋鍵值(1-150)，輸入-1離開：');
	if (val ==-1)  break;
	num=Interpolation(data, val);
	if (num==-1) console.log('##### 沒有找到[',val,']#####');
	else console.log('在第',num+1,'個位置找到 [',data[num],']');
}
console.log('資料內容：');
for (i=0; i<5; i++) {
	for (j=0; j<10; j++) {
		process.stdout.write((i*10+j+1)+'-'+data[i*10+j]+' ');
	}
	console.log();
}

PH P interpolation.php

$data=random_num_arr(1,150,50);
$data=sort_select($data); //排序
$_SESSION['data']=$data;  //存入
//print_arr($data);


if ($_POST['submit']!='送出' ){
echo "
    <center>
    <form method='post' action='{$_SERVER['[PHP_SELF]']}'>
     這是內插搜尋法(interpolation_serach)
     <br>請輸入欲搜索的數字(1-150)
     <input name='number' type='text'>
     <input type='submit' name='submit' value='送出''>
     </form>
    </center>
";
}
else
{
$number=$_POST['number'];
$val=$number;

//echo $number;
echo "您輸入的數字：".$number."<br><br>";
$data = $_SESSION['data']; //取出
$show=0;
  while (true) {
      $num=interpolation_serach($data, $val);
      //echo "<br>".$num."<br>";
      if ($num==-1){
        echo $val."<br>********沒有找到********";
        $show=1;
        break;
      }else{
        $num++;
        echo "<br>在{$num}位置找到".$val."OOOOOOOO找到了OOOOOOOO";
        $show=1;
        break;
      }
  }

  if($show==1){
    echo "[<a href=".$_SERVER['PHP_SELF'].">再找一次</a>]";
    echo "<br>亂數陣列為：<br>";
    print_arr($data);
    unset($_SESSION['data']); //刪除
  }

}


function interpolation_serach ($arr, $val) {
  $low=0;
  $high=count($arr)-1;
  
  echo "搜尋中......";
  while ($low<=$high) {
    $range_data=$arr[$high]-$arr[$low];
    $index_data=$high-$low;
    $value_data=$val-$arr[$low];
    if ($value_data<0) {
      return -1;
    }
    if (!$range_data) {
      return $data[$low] === $val ? $low:-1;
    }
    $mid=$low+intval(($value_data*$index_data)/$range_data);
      //內插法公式
    if ($val==$arr[$mid])
      return $mid;
    elseif ($val<$arr[$mid]) {
      echo "<br>值：{$val}介於位置：".$low."值：{$arr[$low]}及中間值 位置：".$mid."值：{$arr[$mid]}找左半邊";
      $high=$mid-1;
    }
    else {
      echo "<br>值：{$val}介於中間值 位置：".$mid."值：{$arr[$mid]}及 位置：".$high."
      值：{$arr[$high]}找右半邊";
      $low=$mid+1;
    }
  }
    return -1;
}


function random_num_arr($a, $b, $num) {

   //$a起始數字、$b結束數字、$num取出數字數量
   mt_srand((double)microtime()*1000000);
   $data =array();

   for ($i=0; $i<$num; $i++) {
    $randval=mt_rand(1,150);
    if (in_array($randval, $data)){
      $i--;
    }else{
      $data[]=$randval;
    }
  }
  return $data;
}

function sort_select ($arr) {
  //json_decode($arr);
  $count=count($arr);

  for ($i=0; $i<$count-1; $i++) {
    $smallest=$arr[$i];
    $index=$i;
      for ($j=$i+1; $j<$count; $j++) {
          //由i+1比較起
        if($smallest>$arr[$j]){
          //找出最小元素
        $smallest=$arr[$j];
        $index=$j;
        }
      }
  $tmp=$arr[$i];
  $arr[$i]=$arr[$index];
  //兩個交換
  $arr[$index]=$tmp;
  }
  return $arr;
}

function print_arr($arr){
  $i=0;
  foreach ($arr as $key =>$value){
    $key=$key+1;
    echo $key."[".$value."]";
    echo ($i%8==0 && $i!=0) ? "<br>":"   ";
    $i++;
  }

}

8-4費氏搜尋法

費氏搜尋法(Fibonacci Seach)又稱費伯那搜尋法，此法和二分搜尋法一樣都是以切割範圍來進行搜尋，不同的是費氏搜尋法不以對半切割，而是以費氏級數的方式切割。

費氏級數：0,1,1,2,3,5,8,13,21,34,55,89,….。也就是除了第0及第1個元素外，每個值都是前兩個值得加總。
費氏搜尋法的好處是只用到加減運算而不需用到乘法及除法，這是以電腦運算的過程來看效率會高於前兩種搜尋法。在尚未介紹費氏搜尋法之前，我們先來認識費氏搜尋樹。所謂費氏搜尋樹是以費氏級數的特性所建立的二元樹，其建立的原則如下：

1.費氏樹的左右子樹均亦為費氏樹。
2.當資料個數n決定，若想決定費氏樹的階層k值為何，我們必須找到一個最小的k值，使的費氏級數的Fib(k+1)>=n+1。
3.費氏樹的樹根為一費氏樹，且子節點與父節點的差值絕對值為費氏樹。
4.當K>=2時，費氏樹的樹根為Fib(k)，左子樹為(k-1)階費氏樹(其樹根為Fib(k-1))，右子樹為(k-2)階費氏樹(其樹根為Fib(k)+Fib(k-2))。
5.若n+1值不為費氏樹的值，則可以找出存在一個m使用Fib(k+)-m=n+1，m=Fib(k+1)-(n+1)，再依費氏樹的建立原則完成費氏樹的建立，最後費氏樹的各節點再減去差值m即可，並把小於1的節點去掉即可。

也就是說當資料個數為n，且我們找到一個最小的費氏數Fib(k+1)使得Fib(k+1)>=n+1。則Fib(k)就是這棵費氏樹的樹根，而Fib(k-2)則是與左右子樹開始的差值，左子樹用減的；右子樹用加的。以下來實際求取n=33的費氏樹：

由於n=33，且n+1=34為一費氏數，且我們知道費氏數列的三項特性：

Fib(0)=0
Fib(1)=1
Fib(k)=Fib(k-1)+Fib(k-2)

得知Fib(0)=0、Fib(1)=1、Fib(2)=1、Fib(3)=2、Fib(4)=3、Fib(5)=5、Fib(6)=8、Fib(7)=13、Fib(8)=21、Fib(9)=34
由上式可得知Fib(k+1)=34->k=8，建立二元樹的樹根為Fib(8)=21
左子樹樹根為Fib(8-1)=Fib(7)=13
右子樹樹根為Fib(8)+Fib(8-2)=21+8=29
依此原則我們可以建立如下的費氏樹：

費氏搜尋法是以費氏樹來找尋資料，如果資料的個數為n，而且n比某一費氏數小，且滿足如下的運算式：

Fib(k+1)>=n+1

此時Fib(k)就是這棵費氏樹的樹根，而Fib(k-2)則是與左右子樹開始的插值，若我們要尋找的鍵值為key，首先比較陣列索引Fib(k)和鍵值key，此時可以有下列三種比較情況：

1.當key值比較小，表示所找的鍵值key落在1到Fib(k)-1之間，故繼續尋找1到Fib(k)-1之間的資料。
2.如果鍵值與陣列索引Fib(k)的值相等，表示成功搜尋到所要的資料。
3.當key值比較大，表示所找的鍵值key落在Fib(k)+1到Fib(k+1)-1之間，故繼續尋找Fib(k)+1到Fib(k+1)-1之間的資料。

費氏搜尋法分析

1.平均而言，費氏搜尋法的比較次數會少於二元搜尋法，但在最壞的情況下則二元搜尋法較快。其平均時間複雜度為O(log2N)
2.費氏搜尋演算法較為複雜，需額外產生費氏樹。

JS fib_search.js

const MAX=20;

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

var fib_search=(data, SearchKey)=> {
	index=2;
	//費氏數列的搜尋
	while (fib(index)<=MAX) index+=1;
	index-=1;
	//index >=2
	//起始的費氏數
	RootNode=fib(index);
	//上一個費氏樹
	diff1=fib(index-1);
	//上二個費氏樹即diff2=fib(index-2)
	diff2=RootNode-diff1;
	RootNode -=1;
	//這列運算是配合陣列的索引是從0開始儲存資料
	while (true) {
		if (SearchKey==data[RootNode])
			return RootNode;
		else
			if (index==2)
				return MAX;
			    //沒有找到
			if (SearchKey<data[RootNode]) {
				RootNode=RootNode-diff2;
				//左子樹的新費氏數
				temp=diff1;
				diff1=diff2;
				//上一個費氏數
				diff2=temp-diff2;
				//上二個費氏數
				index=index-1;
			}
			else {
				if (index==3) return MAX;
				RootNode=RootNode+diff2;
				//右子樹的新費氏數
				diff1=diff1-diff2;
				//上一個費氏數
				diff2=diff2-diff1;
				//上二個費氏數
				index=index-2;
			}
	}
}

data =[5,7,23,37,48,54,68,77,91,99,102,110,118,120,130,136,150];
i=0;
j=0;
while (true) {
	const prompt=require('prompt-sync')();
	val=prompt('請輸入搜尋值(1-150)，輸入-1離開：');
	if (val==-1)
		break;
	RootNode=fib_search(data, val);
	if (RootNode==MAX)
		console.log('//////////沒有找到',val,'//////////');
	else {
		console.log('在第 ',RootNode+1,'個位置找到',data[RootNode]);
	}
}
console.log('資料內容：');
for (i=0; i<2; i++) {
	for (j=0; j<10; j++) {
		process.stdout.write((i*10+j+1)+'-'+data[i*10+j]+' ');
	}
	process.stdout.write('\n');
}

PHP fib_search.php

$num_arr=array();
$num_arr=random_num_arr(1,150,60);
$max=count($num_arr);
$num_arr=sort_select($num_arr);
//print_arr($num_arr);

$val=1; //起始值

if ($_POST['submit']!='送出' ){
echo "
    <center>
    <form method='post' action='{$_SERVER['[PHP_SELF]']}'>
     這是費氏搜尋法(fib_serach)
     <br>請輸入欲搜索的數字(1-150)
     <input name='number' type='text'>
		 <input type='submit' name='submit' value='送出''>
     </form>
    </center>
";
}
else
{
$number=$_POST['number'];
$val=$number;

	//echo "<br>輸入數值：{$number}<br>";
	while (true) {
		$rootnode=fib_search($num_arr,$val);
		if ($rootnode==$max){
			echo "<br>///////////沒有找到{$val}///////////<br>";
			break;
		}
		else {
			echo "<br>在第{$rootnode},個位置找到{$num_arr[$rootnode]}<br>";
			break;
		}	
	}
	echo "<br>數字陣列為：<br>";
	print_arr($num_arr);
}

function fib_search($data, $searchkey) {
	$index=2;
	$max=count($data);
	//費氏數列的搜尋
	while (fib($index)<=$max) $index++;
	$index--;
	$rootnode=fib($index);
	$diff1=fib($index-1);
	$diff2=$rootnode-$diff1;
	$rootnode--;
	while (true) {
		if ($searchkey==$data[$rootnode])
			return $rootnode;
		else {
			if ($index==2)
				return $max; //沒有找到
			if ($searchkey<$data[$rootnode]) {
				$rootnode=$rootnode-$diff2;
				//左子樹的新費氏數
				$temp=$diff1;
				$diff1=$diff2;
				//上一個費氏數
				$diff2=$temp-$diff2;
				//上二個費氏數
				//echo "<br>左子樹<br>";
				$index=$index-1;
			}
			else {
				if ($index==3) return $max;
				$rootnode=$rootnode+$diff2;
				//右子樹的新費氏數
				$diff1=$diff1-$diff2;
				//上一個費氏數
				$diff2=$diff2-$diff1;
				//上二個費氏數
				//echo "<br>右子樹<br>";
				$index=$index-2;
			}
		}
	}

}

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

function sort_select ($arr) {
	//select排序法
	$count=count($arr);

	for ($i=0; $i<$count-1; $i++) {
		$smallest=$arr[$i];
		$index=$i;
			for ($j=$i+1; $j<$count; $j++) {
					//由i+1比較起
				if($smallest>$arr[$j]){
					//找出最小元素
				$smallest=$arr[$j];
				$index=$j;
				}
			}
	$tmp=$arr[$i];
	$arr[$i]=$arr[$index];
	//兩個交換
	$arr[$index]=$tmp;
	}
	return $arr;
}

function random_num_arr($a, $b, $num) {

	 //$a起始數字、$b結束數字、$num取出數字數量
	 mt_srand((double)microtime()*1000000);
	 $data =array();

	 for ($i=0; $i<$num; $i++) {
		$randval=mt_rand(1,150);
		if (in_array($randval, $data)){
			$i--;
		}else{
			$data[]=$randval;
		}
	}
	return $data;
}


function print_arr($arr){
	$i=0;
	foreach ($arr as $key =>$value){
		$key=$key+1;
		echo $key."[".$value."]";
		echo ($i%8==0 && $i!=0) ? "<br>":"   ";
		$i++;
	}
}

七月 2025
一	二	三	四	五	六	日
« 六月
	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	31