---
tags : C++
title : 遞迴與搜尋陣列
---
# 遞迴的運用-河內塔問題
### 規則
:::success
河內塔問題是將所有的盤子從木樁1搬移到木樁3，其搬動規則，如下所示：
每次只能移動一個盤子，而且只能從最上面的盤子搬動。
盤子可以搬到任何一根木樁。
維持盤子的尺寸是由上而下依序的遞增。
假設有三個盤子:
### 步驟:
:::
### 河內塔 ─ 遞迴特性解決的著名範例
:::success
#### 假設有 3 個塔，編號分別是 1、2、3
###### 現有 n 個半徑皆不相同的圓盤，依照半徑的大小，由小到大的依序疊好放在塔1上
#### 目標
###### 將這 n 個原盤，從塔 1 搬到塔 3但必須依照圓盤的半徑大小由小到大，由上到下依序疊好
#### 規則
###### 一次只能搬動一個圓盤，而且只能搬動柱子最上層的圓盤大圓盤不能疊在小圓盤上
:::
### 三階段的思考
::: 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);
#### 設定終止條件
當圓盤只有一個時，就是根據圓盤的位置，直接顯示搬動的過
:::
## 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)來比較陣列中的每個元素。
由於陣列中並沒有任何特別的順序，所以有可能在第一次比較就找到，也有可能要到最後一個元素才能找到。
平均上，程式需要一半的陣列元素來與搜尋鍵比較。
:::
:::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);
}
}
```
:::
Sign in with Wallet
Connect another wallet