首頁 多元選修 (高中) 進階程式設計

# 遞迴

# 上課例題

# a623: 3. Combination

從 n 個物品取 m 個的組合是一個在數學及企業中常用的值。
本題的程式要讀入 n 和 m 的值，輸出從 n 個物品中取出 m 個的不同組合有幾種。

運用公式 Ckn=Ckn−1+Ck−1n−1C^n_k = C^{n-1}_k + C^{n-1}_{k-1} 做遞迴
在n=kn=k 或k=0k=0 時，就只會有 1 種

#include<iostream>
using namespace std;
int c(int n, int m){
    if (n==m||m==0)
        return 1;
    else
        return c(n-1,m)+c(n-1,m-1);
}
int main(){
    int n,m;
    while(cin >> n >> m)
        cout << c(n,m) << endl;
    return 0;
}
# 延伸練習
# e357: 遞迴函數練習
定義一個函數 F (x)，
若x=1x = 1, 則 F(x)=1F(x) = 1
若xx 為偶數，則 F(x)=F(x/2)F(x) = F(x/2)
其餘狀況，F(x)=F(x−1)+F(x+1)F(x) = F(x - 1) + F(x + 1)
就是照做遞迴函式即可！！！
#include <iostream>
using namespace std;
int F(long long int x){
    if(x==1) 
        return 1;
    if(x%2==0)
        return F(x/2);
    return F(x-1)+F(x+1);
}
int main(){
    long long int x;
    while(cin>>x)
        cout<<F(x)<<endl;
}
# c002: 10696 - f91
  • 如果 N <= 100, 那麼 f91(N)=f91(f91(N+11))f91(N) = f91( f91( N+11) )
  • 如果 N >= 101, 那麼 f91(N)=N−10f91(N) = N-10
照寫就對了！！！
#include<iostream>
using namespace std;
int f91(int n){
    if(n<=100)
        return f91(f91(n+11));
    if(n>=101)
        return n-10;
}
int main(){
    int n;
    while(cin>>n&&n)
        cout<<"f91("<<n<<") = "<<f91(n)<<endl;
}
# 分治法
# 概念
什麼是分而治之法？
  1. 針對一個有 n 筆輸入的問題，它的策略是把輸入分解成 k (1< k ≤ n) 個獨立的小集合，這導致原問題變成 k 個小問題。
  2. 小問題各自獨立地解決後產生各自的解，一共有 k 組解。
  3. 分而治之法最後必須將這 k 組解有系統地合併以產生原問題的解。
# 步驟
  1. 如果要處理的資料量已經夠少，那麼用直接的方式解決，否則，把輸入資料分解成兩個獨立的小集合
  2. 求出每一個小問題的解；並且
  3. 把這兩個小問題的解組合起來，成為原來的大問題的解。
# 上課例題
# d219: 00374 - Big Mod
計算 R=BPmodMR=B^P mod M
對相當大的 B、P、M 請寫一個有效率的演算法來。
運用分配律，將運算分開處理！！！
(A∗B)mod(M)=[(Amod(M))∗(Bmod(M))]mod(M)(A*B) mod (M)= [ (A mod (M))*(B mod (M)) ] mod (M)
BPmod(M)=[(BP/2mod(M))∗(BP/2mod(M))]mod(M)B^P mod (M) = [ (B ^{P/2} mod (M))*(B^{P/2} mod (M)) ] mod (M)
#include <bits/stdc++.h>
using namespace std;
#define int long long
int dc(int b,int p,int m){
    if (p==0) return 1;
    if (p==1) return b%m;
    int  half =dc ( b , p/2, m);
    if (p%2==0)
        return half * half % m;
    return  half * half  * b % m;
    
}
signed main(){
    int  b,p,m;
    while(cin >> b >> p >> m)
        cout << dc(b,p,m) << endl;
    return 0;
}
# d153: 六、智力测验
取一段序列的中位數 (序列尚未排序)
運用排序演算法，尋找中位數
這題我們用快速排序演算法演示！！！
#include <iostream>
using namespace std;
void quickSort(int a[],int L,int R){
    if(L>=R) return;
    int i=L,j=R,pivot=a[L];
    while(i!=j) {
        while (a[j]>=pivot&&i<j)  j--;
        while (a[i]<=pivot&&j>i)  i++;
        swap(a[i],a[j]);
    }
    a[L] = a[i];
    a[i] = pivot;
    quickSort(a, L, i-1);  // Left side
    quickSort(a, i+1,R);  // Right side
}
int main(){
    int t,n,a[40005];
    cin >> t;
    while(t--){
        cin >> n;
        for(int i=0;i<n;i++)
            cin >> a[i];
        quickSort(a,0,n-1);
        cout << a[(n-1)/2] << endl;
    }
    return 0;
}
# 延伸練習
# d636: 大爆炸 bomb
計算abmod(MOD)a^b mod (MOD) 的值
將冪次不斷的向下分割 (b/2)，直到冪次收斂到 0 或 1 為止。
若 p 等於 1，則回傳值為 a
若 p 等於 0，則回傳值為 0
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define MOD 10007
int dc(int b,int p){
    if(p==0) return 1;
    if(p==1) return b;
    int half= dc(b,p/2);
    if(p&1) return half*half*b%MOD;
    return half*half %MOD;
}
signed main(){
    int a,b;
    cin>>a>>b;
    cout<<dc(a,b);
}
# a227: 三龍杯 -> 河內之塔
輸出把 A 上 N 個環移動到 C 的方法
(剛開始 A 層最下方的 Ring 編號為 N 最上方的編號為 1)
運用遞迴函式，將問題向下切分，直至將 A 上的環接清空後，再反向運用相同的建構方式，將其復原於 C 上。
#include <bits/stdc++.h>
using namespace std;
void hanoi(int n, char A, char B, char C) {
    if(n > 0) {
        hanoi(n-1, A, C, B);
        printf("Move ring %d from %c to %c\n", n, A, C);
        hanoi(n-1, B, A, C);
    }
}
int main() {
    int n;
    while(scanf("%d", &n) == 1) {
        hanoi(n, 'A', 'B', 'C');
        puts("");
    }
    return 0;
}
# a638: Closest-pair problem
在二維座標平面上有 N 個點，
請找出最近兩點的距離。
  • 將所有點依 x 座標排序
  • 從中間切開，將所有點分成左右兩個集合 (設 line 為中線 x 座標)
  • 左右兩邊各求出任兩點最小值 a,b，設 d 為 min (a,b)
  • 那麼現在只要枚舉 [line-d,line+d] 這範圍內的點有沒有比 d 還更小的值即可
#include <bits/stdc++.h>
using namespace std;
struct point{
	double x,y;
	bool operator < (point other){
	    return x <other.x;
	}
};
int N;
double dis;
vector<point> V;
double ds(point& a, point& b){
	return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}
double Combine(int& a, int& b, int& mid, double& l, double& r) {
	double d = min(l, r);
	double line = (V[mid].x + V[mid + 1].x) / 2;
	double Min = d;
	for (int i = mid + 1; i <= b && V[i].x < line + d; ++i)
		for (int j = mid; j >= a && V[j].x > line - d; --j)
			Min = min(Min, ds(V[i], V[j]));
	return Min;
}
double Divide(int a, int b){
	if (a >= b) return 10000;
	int mid = (a + b) / 2;
	double l = Divide(a, mid);
	double r = Divide(mid + 1, b);
	return Combine(a, b, mid, l, r);
}
int main(){
	while (cin >> N && N){
		double a, b;
        V.clear();
        for (int i = 0; i < N; ++i) {
            cin >> a >> b;
            V.push_back({ a, b });
        }
		sort(V.begin(), V.end());
		dis = Divide(0, N - 1);
		if (dis < 10000)
            cout << setprecision(4) << fixed << dis << "\n";
        else
            cout << "INFINITY\n";
	}
}
int LIS(vector<int>& s)
{
    // 不得不判斷的特例
    if (s.size() == 0) return 0;
 
    // 先塞入一個數字，免得稍後 dp.back () 出錯。
    vector<int> dp;
    dp.push_back(s[0]);
 
    for (int i=1; i<s.size();i++) {
        int n = s[i];
        if (n > dp.back())
            dp.push_back(n);
        else
            *lower_bound(dp.begin(), dp.end(), n) = n;
    }
    return dp.size();
}
  
 更新於   閱讀次數  次
用實際行動犒賞爆肝的我😀
Zrn Ye LinePay
LinePay