---
# System prepended metadata

title: 遞迴與搜尋陣列
tags: [C++]

---

---
tags : C++
title : 遞迴與搜尋陣列
---
# 遞迴的運用-河內塔問題
![](https://i.imgur.com/O9hHQXV.jpg)
### 規則
:::success
河內塔問題是將所有的盤子從木樁1搬移到木樁3，其搬動規則，如下所示：
每次只能移動一個盤子，而且只能從最上面的盤子搬動。
盤子可以搬到任何一根木樁。
維持盤子的尺寸是由上而下依序的遞增。
假設有三個盤子:
![](https://i.imgur.com/7ZUWjo0.jpg)
### 步驟:
![](https://i.imgur.com/F4mTXrq.jpg)
![img](https://i.imgur.com/4DIM1ll.jpg)
![img](https://imgur.com/GxuUBvj.jpg)
![img](https://imgur.com/qXrSD28.jpg)
:::
### 河內塔 ─ 遞迴特性解決的著名範例
:::success

#### 假設有 3 個塔，編號分別是 1、2、3
###### 現有 n 個半徑皆不相同的圓盤，依照半徑的大小，由小到大的依序疊好放在塔1上
#### 目標
###### 將這 n 個原盤，從塔 1 搬到塔 3但必須依照圓盤的半徑大小由小到大，由上到下依序疊好
#### 規則
###### 一次只能搬動一個圓盤，而且只能搬動柱子最上層的圓盤大圓盤不能疊在小圓盤上
![img](https://imgur.com/LktpTvX.jpg)
:::
### 三階段的思考
::: success
#### 可以完成並顯示整個圓盤搬動過程的 Hanoi 函式已經存在這個函式不需要回傳值
需要四個 int 型別的引數，分別是：n、s、m、d
n：圓盤的個數，個數也對應於圓盤的編號，編號越小代表半徑越小
s ：為原盤一開始(start)放置所在塔的編號
m：為中繼(middle)塔的編號
d：為圓盤放置目的(destination)塔的編號
#### void Hanoi(int n, int s, int m, int d);
例如：
Hanoi(3,1,2,3) ：Hanoi 函式就會列出三個圓盤，從塔1搬到塔3的所有搬動過程
#### 問題簡化
將 n 個圓盤分成上面的 n-1 個與 1 個
先搬動上面的 n-1 個，從第一根柱子搬到第二根柱子上
Hanoi(n-1, s, d, m);
搬動最下面第 n 個圓盤從第一根柱子搬到第三根柱子
再將位於第二根柱子上的 n-1 個圓盤，搬到第三根柱子上
Hanoi(n-1, m, s, d);
![img](https://imgur.com/8SHIz4f.jpg)
#### 設定終止條件
當圓盤只有一個時，就是根據圓盤的位置，直接顯示搬動的過
:::

## Hanoi 的完整程式碼
:::info
```cpp=
#include <stdio.h>
#include <stdlib.h>
void Hanoi(int, int, int, int); //函式原型宣告
void Hanoi(int n, int s, int m, int d)
{
	if (n == 1) // 終止條件
		printf("將第%2d 個圓盤從塔%2d 搬到塔%2d\n", n, s, d);
	else {
		Hanoi(n - 1, s, d, m); // 將上面的 n-1 個從塔 s 搬到塔 m
		printf("將第%2d 個圓盤從塔%2d 搬到塔%2d\n", n, s, d);
		Hanoi(n - 1, m, s, d); // 將上面的 n-1 個從塔 m 搬到塔 d
	}
}
int main(void)
{
	int n;
	printf("有多少圓盤要搬: ");
	scanf("%d", &n);
	Hanoi(n, 1, 2, 3);
	system("pause"); return(0);
}
```
:::
# 遞迴呼叫轉換成陣列查表
費氏序列 f(n)=f(n-1)+f(n-2)
f(0)=0,f(1)=1;轉換成 f[n]=f[n-1]+f[n-2]
f[0]=0, f[1]=1則 f[0]=0; f[1]=1;
for(i=2;i<=n; i++)
f[i]=f[i-1]+f[i-2];
每個陣列格子內存相對陣列index的費氏序列值如f[5]內即費氏序列第五項的值
:::success
```cpp=
#include<stdio.h>

int main() {
	int s[100], n;
	scanf("%d", &n);
 	s[0] = 0; s[1] = 1;
 	for (int i = 2; i <= n; i++) 
 		s[i] = s[i - 1] + s[i - 2];
	 	printf("%d", s[n]);
}
```
:::
# 搜尋陣列
## 線性搜尋 (linear search) 
:::success
用搜尋關鍵值 (search key)來比較陣列中的每個元素。
由於陣列中並沒有任何特別的順序，所以有可能在第一次比較就找到，也有可能要到最後一個元素才能找到。
平均上，程式需要一半的陣列元素來與搜尋鍵比較。
:::
![img](https://imgur.com/eoQm6TO.jpg)
![](https://imgur.com/TULjHQR.jpg)
:::warning
對於小型的陣列或未排序過的陣列而言，線性搜尋可以表現的很好。
但是將線性搜尋用在大型陣列上，就很沒有效率了。
如果陣列已經排序過了，則我們可以用速度很快的二元搜尋法。
二元搜尋演算法在每次比較之後，就可以將已排序陣列中一半的元素刪去不考慮。
此演算法先找出陣列的中間元素，將之與搜尋關鍵值作比較。

:::
## 二元搜尋 (binary search)
:::success
搜尋的動作會一直持續到搜尋關鍵值等於子陣列的中間元素為止，或是子陣列只包含一個與搜尋關鍵值不相等的元素為止 (也就是沒有找到搜尋關鍵值)。
在最壞的情形之下，使用二元搜尋來搜尋1023個元素的陣列只需10次比較。
重複將1024除以2將會得到516, 256, 128,64, 32, 16, 8, 4, 2, 1等數值。
即1024(210)只要除以2十次，便可得到1。
除以2的動作相當於二元搜尋的比較動作。
:::
### 二分法-非遞迴做法
:::info
```cpp=
#include<stdio.h>

int serch(int a[], int key) {
int r = 5, l = 0, midden;
		for (int i = 0; i < 6; i++) {
	         midden = (r + l) / 2;
		 printf("\n%d", midden);
		if (a[midden] == key) {
			return 1;
		}
		else {
			if (key < a[midden])  r = midden - 1; 
			else if (key > a[midden]) l = midden + 1;
		}
			}
	return 0; 
}
int main()
    {
		int a[6] = { 5,4,9,10,7,99 }, key;
		scanf("%d", &key);
		for (int i = 0; i < 6; i++) {
			for (int n = i + 1; n < 6; n++) {
                 if (a[i] > a[n]) {
					int c;
					c = a[i];
					a[i] = a[n];
					a[n] = c;
				}
			}
			printf("%d\n", a[i]);
		}
		if (serch(a, key)==1)printf("\n有");
		else printf("\n沒有");
	}
   ```
:::
### 二分法-遞迴做法
:::info
``` cpp=
#include<stdio.h>


int foun(int a[], int key, int l, int r) {
	int middle;

	if (l >= r) return 2;
	middle = (l + r) / 2;
	if (a[middle] == key) return 1;
	else {

		if (key > middle) return foun(a, key, middle + 1, r);
		else return foun(a, key, l, middle - 1);

	}


}
int main() {
	int  a[10] = {1,2,5,6,8,9,7,15,123,1234}, key;
	
	for (int i = 0; i < 10; i++) {
		for (int n = i + 1; n < 10; n++) {
			if (a[i] > a[n]) {
				int c;
				c = a[i];
				a[i] = a[n];
				a[n] = c;
			}
		}
	}
	printf("key : ");
	scanf("%d", &key);
	if (foun(a, key, 0, 9) == 1) 
		printf("yes");
	else printf("no");
}
```
:::
### 已知兩個分別儲存10個整數的陣列A和B，請寫一程式利用binary search判斷是否陣列A中存在某個數值與B中另一個數值相等。
:::success
```cpp=
#include<stdio.h>

int foun(int a[], int key, int l, int r) {
	int middle;
	if (l >= r) return 2;
	middle = (l + r) / 2;
	if (a[middle] == key) return 1;
	else {
		if (key > middle) return foun(a, key, middle, r);
		else  return foun(a, key, l, middle);
	}
}


int main() {
	int  a[10] = { 1,2,3,4,5,6,7,8,9,10 }, b[10] = { 5,6,3,4,8,9,7,2,1,10 };
	for (int i = 0; i < 10; i++) {
		for (int n = i + 1; n < 10; n++) {
			if (a[i] > a[n]) {
				int c;
				c = a[i];
				a[i] = a[n];
				a[n] = c;
			}
		}
	}
	for (int i = 0; i < 10; i++) {
		if (foun(a, b[i] , 0, 10) == 1) printf("a與b[%d]有相同\n", i + 1);
		printf("t = %d\n", i);
	}
}
```
:::