在此記錄一些有關函數、遞歸和遞推的問題。所有題目均來自洛谷的題單能力提升綜合題單Part1 入門階段 - 題單 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)
（實際上都沒有用遞推做）

[NOIP2001 普及組] 數的計算

題目描述

給出正整數 $n$，要求按如下方式構造數列：

1. 只有一個數字 $n$ 的數列是一個合法的數列。
2. 在一個合法的數列的末尾加入一個正整數，但是這個正整數不能超過該數列最后一項的一半，可以得到一個新的合法數列。

請你求出，一共有多少個合法的數列。兩個合法數列 $a,b$ 不同當且僅當兩數列長度不同或存在一個正整數 $i\le |a|$，使得 $a_i\ne b_i$。

輸入格式

輸入只有一行一個整數，表示 $n$。

輸出格式

輸出一行一個整數，表示合法的數列個數。

樣例 #1

樣例輸入 #1

6

樣例輸出 #1

6

提示

樣例 1 解釋

滿足條件的數列為：

• $6$
• $6,1$
• $6,2$
• $6,3$
• $6,2,1$
• $6,3,1$

數據規模與約定

對于全部的測試點，保證 $1\le n\le 10^3$。

思路

注意到，對于任意一個數n，它構造數列的方式來源于它前面的數。例如，對于6來說，可以將它的數列分成下面幾個部分：

• 它本身
• 1
• 2
• 3

因此，我們可以得到
$$f[n]=1+\sum _{i=1}^{n/2}f[i]$$
得到這個表達式后，使用動態規劃或者遞歸解題均可。我在這里使用遞歸來解決。

代碼

#include<iostream>
#include<cstring>
using namespace std;const int N = 1e3 + 10;
int n;
int f[N];int get_nums(int u) {if(f[u] != -1) return f[u];int res = 1;for(int i = 1; i <= u /  2; i ++ ) {res += get_nums(i);}f[u] = res;return f[u];
}int main() {cin >> n;memset(f, -1, sizeof f);f[1] = 1;f[2] = 2;cout << get_nums(n) << endl;return 0;
}

[NOIP2002 普及組] 選數

題目描述

已知 $n$ 個整數 $x_1,x_2,?,x_n$，以及 $1$ 個整數 $k$（$k<n$）。從 $n$ 個整數中任選 $k$ 個整數相加，可分別得到一系列的和。例如當 $n=4$，$k=3$，$4$ 個整數分別為 $3,7,12,19$ 時，可得全部的組合與它們的和為：

$3+7+12=22$

$3+7+19=29$

$7+12+19=38$

$3+12+19=34$

現在，要求你計算出和為素數共有多少種。

例如上例，只有一種的和為素數：$3+7+19=29$。

輸入格式

第一行兩個空格隔開的整數 $n,k$（$1\le n\le 20$，$k<n$）。

第二行 $n$ 個整數，分別為 $x_1,x_2,?,x_n$（$1\le x_i\le 5\times 10^6$）。

輸出格式

輸出一個整數，表示種類數。

樣例 #1

樣例輸入 #1

4 3
3 7 12 19

樣例輸出 #1

1

思路

使用遞歸，函數dfs(int t, int sum, int d)的函數名中記錄已選的個數、已選數之和、已選的最后一個數在數組中的位置。我們要保證從小到大枚舉，這樣就可以避免算到重復的數。

代碼

#include<iostream>
using namespace std;const int M = 22;int n, k;
int a[M];
int ans;bool is_prime(int u) {for(int i = 2; i < u / i; i ++ ) {if(u % i == 0) return false;}return true;
}void dfs(int t, int sum, int d) {// t表示已選t個數// sum表示已選數之和// d 表示已選的最后一個數在數組中的位置//已選k個，判斷和是否是素數if(t == k) {if(is_prime(sum)) ans ++;return ;}//沒選到k個，從 d + 1開始枚舉for(int i = d + 1; i <= n; i ++ ) {dfs(t + 1, sum + a[i], i);}
}int main() {cin >> n >> k;for(int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);dfs(0, 0, 0);cout << ans << endl;return 0;
}

Function

題目描述

對于一個遞歸函數 $w(a,b,c)$

• 如果 $a\le 0$ 或 $b\le 0$ 或 $c\le 0$ 就返回值$ 1$。
• 如果 $a>20$ 或 $b>20$ 或 $c>20$ 就返回 $w(20,20,20)$
• 如果 $a<b$ 并且 $b<c$ 就返回$ w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)$。
• 其它的情況就返回 $w(a?1,b,c)+w(a?1,b?1,c)+w(a?1,b,c?1)?w(a?1,b?1,c?1)$

這是個簡單的遞歸函數，但實現起來可能會有些問題。當 $a,b,c$ 均為 $15$ 時，調用的次數將非常的多。你要想個辦法才行。

注意：例如 $w(30,?1,0)$ 又滿足條件 $1$ 又滿足條件 $2$，請按照最上面的條件來算，答案為 $1$。

輸入格式

會有若干行。

并以 $?1,?1,?1$ 結束。

輸出格式

輸出若干行，每一行格式：

w(a, b, c) = ans

注意空格。

樣例 #1

樣例輸入 #1

1 1 1
2 2 2
-1 -1 -1

樣例輸出 #1

w(1, 1, 1) = 2
w(2, 2, 2) = 4

提示

數據規模與約定

保證輸入的數在 $[?9223372036854775808,9223372036854775807]$ 之間，并且是整數。

保證不包括 $?1,?1,?1$ 的輸入行數 $T$ 滿足 $1\le T\le 10^5$。

思路

我們注意到w實際上只需要計算0-20之間的數，因此我們可以用記憶化搜索把算到的w的值存儲起來。

代碼

#include<iostream>
#include<cstring>
using namespace std;typedef long long LL;
LL w[25][25][25];LL get_w(LL a, LL b, LL c) {if(a <= 0 || b <= 0 || c <= 0) return 1;if(a > 20 || b > 20 || c > 20 ) return get_w(20, 20, 20);if(w[a][b][c] != -1) return w[a][b][c];if (a < b && b < c) {w[a][b][c] =  get_w(a, b, c - 1) + get_w(a, b - 1, c - 1) - get_w(a, b - 1, c);}else w[a][b][c] = get_w(a - 1, b, c) + get_w(a - 1, b - 1, c) + get_w(a - 1, b, c - 1) - get_w(a - 1, b - 1, c - 1);return w[a][b][c];
}int main() {memset(w, -1, sizeof w);while(1) {LL a, b, c;scanf("%lld%lld%lld", &a, &b, &c);if(a == b && b == c && a == -1) break;printf("w(%lld, %lld, %lld) = %lld\n", a, b, c, get_w(a, b, c));}return 0;
}

【XR-3】等差數列

題目描述

小 X 給了你一個等差數列的前兩項以及項數，請你求出這個等差數列各項之和。

等差數列：對于一個 $n$ 項數列 $a$，如果滿足對于任意 $i\in [1,n)$，有 $a_{i+1}?a_i=d$，其中 $d$ 為定值，則稱這個數列為一個等差數列。

輸入格式

一行 $3$ 個整數 $a_1,a_2,n$，表示等差數列的第 $1,2$ 項以及項數。

數據范圍：

• $|a_1|,|a_2|\le 10^6$。
• $3\le n\le 10^6$。

輸出格式

一行一個整數，表示答案。

樣例 #1

樣例輸入 #1

1 2 3

樣例輸出 #1

6

樣例 #2

樣例輸入 #2

-5 -10 5

樣例輸出 #2

-75

提示

【樣例 $1$ 說明】

這個等差數列為 1 2 3，其各項之和為 $6$。

思路

這道題我沒用遞歸，直接用等差數列求和公式就可以了。要注意數據大小。

代碼

#include<iostream>
using namespace std;
typedef long long LL;int main() {LL a1, a2, n;cin >> a1 >> a2 >> n;LL d = a2 - a1;LL ans = ((a1 * 2 + (n - 1) * d) * n) / 2;cout << ans << endl;return 0;
}

臺階問題

題目描述

有 $N$ 級臺階，你一開始在底部，每次可以向上邁 $1～K$ 級臺階，問到達第 $N$ 級臺階有多少種不同方式。

輸入格式

兩個正整數 $N,K$。

輸出格式

一個正整數 $ans(\mathrm{mod}100003)$，為到達第 $N$ 級臺階的不同方式數。

樣例 #1

樣例輸入 #1

5 2

樣例輸出 #1

8

提示

• 對于 $20\%$ 的數據，$1\le N\le 10$，$1\le K\le 3$；
• 對于 $40\%$ 的數據，$1\le N\le 1000$；
• 對于 $100\%$ 的數據，$1\le N\le 100000$，$1\le K\le 100$。

思路

非常經典的問題。

注意到，對于第n級臺階，它來自于它前面的1~ k級臺階，因此第n級臺階的方案數應該等于前面n - k到n - 1級臺階的方案數之和。當然要注意邊界情況。

使用函數dfs(int u)表示u階臺階時的方案數，同時用一個數組把計算到的值全部存起來。

代碼

#include<iostream>
using namespace std;const int mod = 100003, N = 1e5 + 10;int n, k;int df[N];//表示u階臺階時的方案數 
int dfs(int u) {if(df[u] != 0) return df[u];int res = 0;for(int i = 1; i <= k && u - i >= 0; i ++ ) {res = (res + dfs(u - i)) % mod;}df[u] = res;return res;
}int main() {cin >> n >> k;if(k > n) k = n; df[0] = 1;cout << dfs(n) << endl;return 0;
}

[NOIP2001 提高組] 數的劃分

題目描述

將整數 $n$ 分成 $k$ 份，且每份不能為空，任意兩個方案不相同（不考慮順序）。

例如：$n=7$，$k=3$，下面三種分法被認為是相同的。

$1,1,5$;
$1,5,1$;
$5,1,1$.

問有多少種不同的分法。

輸入格式

$n,k$ （$6<n\le 200$，$2\le k\le 6$）

輸出格式

$1$ 個整數，即不同的分法。

樣例 #1

樣例輸入 #1

7 3

樣例輸出 #1

4

提示

四種分法為：
$1,1,5$;
$1,2,4$;
$1,3,3$;
$2,2,3$.

【題目來源】

NOIP 2001 提高組第二題

思路

用遞歸來做。用一個函數dfs(int x, int sum, int d)來遞歸計算，其中上一個數為x，目前總和為sum，還需要遞歸的次數為d。當d = 0時，滿足sum == n時要加在總數中。

代碼

#include<iostream>
using namespace std;int n, k;
int ans;//表示上一個數為x，目前總和為sum，還需要遞歸的次數為d
void dfs(int x, int sum, int d) {if(d == 0) {if(sum == n) ans ++;return;}for(int i = x; i <= n && i + sum <= n; i ++ ) {dfs(i, sum + i, d - 1);}return;
}int main() {cin >> n >> k;dfs(1, 0, k); cout << ans << endl;return 0;
}

終于結束的起點

題目背景

終于結束的起點
終于寫下句點
終于我們告別
終于我們又回到原點
……

一個個 OIer 的競賽生涯總是從一場 NOIp 開始，大多也在一場 NOIp 中結束，好似一次次輪回在不斷上演。
如果這次 NOIp 是你的起點，那么祝你的 OI 生涯如同夏花般絢爛。
如果這次 NOIp 是你的終點，那么祝你的 OI 回憶宛若繁星般璀璨。
也許這是你最后一次在洛谷上打比賽，也許不是。
不過，無論如何，祝你在一周后的比賽里，好運。

當然，這道題也和輪回有關系。

題目描述

廣為人知的斐波拉契數列 $\mathrm{fib}(n)$ 是這么計算的

$$\mathrm{fib}(n)=?\begin{array}{ll}0,& n=0\\ 1,& n=1\\ \mathrm{fib}(n?1)+\mathrm{fib}(n?2),& n>1\end{array}$$

也就是 $0,1,1,2,3,5,8,13?$，每一項都是前兩項之和。

小 F 發現，如果把斐波拉契數列的每一項對任意大于 $1$ 的正整數 $M$ 取模的時候，數列都會產生循環。

當然，小 F 很快就明白了，因為 ($\mathrm{fib}(n?1)\mathrm{mod}M$) 和 ($\mathrm{fib}(n?2)\mathrm{mod}M)$ 最多只有 $M^2$ 種取值，所以在 $M^2$ 次計算后一定出現過循環。

甚至更一般地，我們可以證明，無論取什么模數 $M$，最終模 $M$ 下的斐波拉契數列都會是 $0,1,?,0,1,?$。

現在，給你一個模數 $M$，請你求出最小的 $n>0$，使得 $\mathrm{fib}(n)\mathrm{mod}M=0,\mathrm{fib}(n+1)\mathrm{mod}M=1$。

輸入格式

輸入一行一個正整數 $M$。

輸出格式

輸出一行一個正整數 $n$。

樣例 #1

樣例輸入 #1

2

樣例輸出 #1

3

樣例 #2

樣例輸入 #2

6

樣例輸出 #2

24

提示

樣例 1 解釋

斐波拉契數列為 $0,1,1,2,3,5,8,13,21,34,?$，在對 $2$ 取模后結果為 $0,1,1,0,1,1,0,1,1,0,?$。

我們可以發現，當 $n=3$ 時，$f(n)\mathrm{mod}2=0,f(n+1)\mathrm{mod}2=1$，也就是我們要求的 $n$ 的最小值。

數據范圍

對于 $30\%$ 的數據，$M\le 18$；

對于 $70\%$ 的數據，$M\le 2018$；

對于 $100\%$ 的數據，$2\le M\le 706150=\text{0xAC666}$。

提示

如果你還不知道什么是取模 $(\mathrm{mod})$，那我也很樂意告訴你，模運算是求整數除法得到的余數，也就是豎式除法最終「除不盡」的部分，也即
$$a\mathrm{mod}M=k?a=bM+k(M>0,0\le k<M)$$
其中 $a,b,k$ 都是非負整數。

如果你使用 C / C++，你可以使用 % 來進行模運算。

如果你使用 Pascal，你可以使用 mod 來進行模運算。

思路

使用記憶化搜索，存儲每個獲得的fib值。要注意數的范圍，都需要使用long long來存儲數。

代碼

#include<iostream>
using namespace std;typedef long long LL;
const int N = 1e7 + 10;LL f[N];
LL m;LL fib(LL u) {if(f[u]) return f[u];if(u == 1 || u == 2) return f[u] = 1 % m;f[u] = (fib(u - 1) + fib(u - 2)) % m;return f[u];
}int main () {scanf("%lld", &m);for(LL i = 2; ; i ++ ) {if(fib(i) % m == 0 && fib(i + 1) % m == 1) {printf("%lld", i);return 0;}}return 0;
}