data stucture第一章

Algorithm定義

須滿足下列五個criteria(標準要求)

• Input(至少提供>=0個輸入資料)
• Output(至少提供>=1個輸出結果)
• Definiteness明確性(每個指令敘述必須是clear且unambiguous)
• Finiteness有限性(Algorithm在執行有限steps後必須能夠終止)(program不具有限性)
• Effectiveness有效性(每個指令敘述夠基本，即可被人用紙、筆追蹤/執行)
  會考哪一個不是定義:
  ex correctness?

Recursion

• Direct Recursion直接(包含self-calling)
• Indirect recursion間接ex: A->B->C->A
• Tail recursion 尾端遞迴 (是Direct recursion的一種，即recursion call之下一個可執行敘述為return/end)
  ex return n*rec();//非尾端遞迴
return rec();//為尾端遞迴

Recursion vs. Iteration(Non-Recursion)

• 任何問題的解決必存在這兩種形式的演算法
• 遞迴->非遞迴(有標準SOP)
• 非遞迴->遞迴(無)

解題關鍵:記住數學上Recursion definition

輾轉相除法

gcd(A,B)=B,if(A %B)=0
gcd(A,B)=gcd(B,A %B),otherwise

Ackerman Function A(m,n)

很難算

快速冪!!!O(log(n))

數學rec:
x^n=1* x^(n/2)x^(n/2),if n=even
x^n=x x^(n/2)*x^(n/2),if n=odd
台大解:

1
2
3
4
5
6
7

int exp(int x,int n){
    int f;
    if(n%2==0)f=1;
    else f=x;
    if(n<2) return f;
    return f*exp(x*x,n/2);
}

自己寫比較好懂:

1
2
3
4
5

int exp(int x,int n){
    if(n==1) return x;
    if(n%2) return x*exp(x*x,n/2);
    return exp(x*x,n/2);
}

Hanoi河內塔

遞迴核心概念:把問題縮小
以這題為例 先拿n-1個disk然後再拿最後第n個
設有A,B,C柱
step1. n-1 disk到B柱
step2. 第n個disk放到C柱
step3. n-1 disk放到C柱
用程式實現:

1
2
3
4

Hanoi(n,from,to,Aux) // (最後面的是暫存)
step1. Hanoi(n-1,from,Aux,to); //先移動n-1個盤子
step2. move disk n from "from" to "to"
step3. Hanoi(n-1,Aux,to,from); //再把n-1個盤子移動到to

遞迴:T(n)=T(n-1)+1+T(n-1)從左至右就是step1~3
O(n)=2^n-1

Print all permutation of n data

觀念:
perm(a,b,c)=’a’+perm(b,c)+’b’+perm(a,c)+’c’+perm(a,b)
輪流作為head後面接剩下資料之perm

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
32
33

#include <iostream>

using namespace std;
void perm(char s[],int i,int n){
    for(int j=1;j<=n;j++){
        cout<<s[j]<<' ';
    }
    cout<<'\n';
    int j,temp;
    if(i==n){
        for(j=1;j<=n;j++){
            cout<<s[j];
        }
        cout<<'\n';
    }else{
        for(j=i;j<=n;j++){
            swap(s[i],s[j]);
            perm(s,i+1,n);
            swap(s[i],s[j]);
        }
    }
}
int main()
{
    char s[100];
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s[i];
    }
    perm(s,1,n);
    return 0;
}

缺點是資料並不會依輸入的字典序排列