Skip to main content

1.1 數學中的遞迴 vs 程式中的遞迴

數學中的遞迴

在高一數學課時，學習到使用遞迴解決數學上的問題，以下幾個是簡單的範例

  1. 有一位小朋友要走樓梯上樓，他一次可以往上走一階或一次走兩階，問你若要走 $n$ 階，共有幾種走法?

    • 在此我們可以藉由上一階、上兩階的特性，將問題轉換成，若我要走到第 $i$ 階，則他必是從 $i - 1$ 和 $i - 2$ 階走過來的，下一步，就可以列成遞迴關係式

    \[F(x)= \begin {cases} F(x-1)+F(x-2) & \text{if }x>1 \\ 1 & \text{if } x\leq 1\end{cases}\]

  2. 請將一個等差數列 $F(x)=3x+5$ 傳換成遞迴關係式

    • 很容易的第一項需要特別定義 $F(0)$，接下來的這一項就會式上一項再加3，列成關係式 \[F(x)= \begin {cases} F(x-1)+3 & \text{if }x>0 \\ 5 & \text{if }x=0\end{cases}\]

典型利用遞迴來找到解決問題的方法

  • 當遇到一個不易解決的問題時，試著找出分割這個問題的模式(建立遞迴關係式)
  • 找到之後藉由分割來將這個問題不斷地縮小
  • 當問題縮小到一定的大小時，我們可以直接解決該問題(決定終止條件)
  • 最後合併各個已解決小問題的答案即得到原問題的答案。(設計遞迴函式)

程式中的遞迴

　　在上面的一些例子中，都是使用學過的數學遞迴來解決一些數學上的問題，若是請你將上述問題變成程式問題，作法跟數學一模一樣，可以想像成$F(x)$就是程式當中的呼叫函數，換句話說，只需要藉由呼叫同一個函數的前幾項，就可以找到答案。接下來我們將上面兩個問題轉換成程式

  1. 小朋友上樓梯
    • 題目連結
    • 在此題中，唯一需要做的事就是將函數的回傳值設定為$F(x)=F(x-1)+F(x-2)$，再去注意中止條件即可
    • 程式碼

/* |----| |----| | | | | | ----| | | | | ----| | | | | | |----| |----|

*/ #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h> #define ll long long #define fastio ios::sync_with_stdio(0), cin.tie(0)

using namespace std;

struct TYPE { int ma, mi, ans; };

const int SIZE = 1 << 16; // 15:32678 16:65536 17:131072 18:2624144 19:524288 20:1048576 struct segment_tree { // start from 1 TYPE node[SIZE]; TYPE merge(TYPE a, TYPE b) { TYPE ret; ret.ma = max(a.ma, b.ma); ret.mi = min(a.mi, b.mi); ret.ans = ret.ma - ret.mi; return ret; } void pull(int idx) { node[idx] = merge(node[idx * 2], node[idx * 2 + 1]); } void init(int L, int R, int idx, vector<TYPE> &input) { if(L == R) { node[idx] = input[L]; return; } int now = (L + R) / 2; init(L, now, idx * 2, input); init(now + 1, R, idx * 2 + 1, input); pull(idx); } TYPE query(int L, int R, int idx, int l, int r) { if(L >= l && R <= r) return node[idx]; int now = (L + R) / 2; if(r <= now) return query(L, now, idx * 2, l, r); if(l > now) return query(now + 1, R, idx * 2 + 1, l, r); return merge(query(L, now, idx * 2, l, r), query(now + 1, R, idx * 2 + 1, l, r)); } void update(int L, int R, int idx, int p, TYPE v) { if(L == R) { node[idx] = v; return; } int now = (L + R) / 2; if(p <= now) update(L, now, idx * 2, p, v); else update(now + 1, R, idx * 2 + 1, p, v); pull(idx); } };

void solve() { int n, m, k; cin >> n >> m >> k; vector<TYPE> v(n + 1); for(int i = 1; i <= n; i++) { int in; cin >> in; v[i] = {in, in, in}; } segment_tree seg; seg.init(1, n, 1, v); for(int i = n; i >= m; i--) { // cerr << "-----\n"; int j = 1; vector<int> tmp; while(j <= n) { int a = j + i - 1; while(a <= n && seg.query(1, n, 1, j, a).ans <= k) { a++; } a--; if(seg.query(1, n, 1, j, a).ans <= k) { tmp.push_back(a - j + 1); j = a + 1; } else { break; } } int ans = 0; for(int aa : tmp) ans += aa; if(ans == n) { cout << tmp.size() << '\n'; for(int aa : tmp) { cout << aa << ' '; } cout << '\n'; return; } } cout << "-1\n"; return; }

int main() { ios::sync_with_stdio(false); cin.tie(nullptr);

int t = 1;
    // cin >> t;
    while(t--)
    {
      solve();
    }
    return 0;

}

```
Back to top