跳臺階問題
題目：
一個臺階總共有 n 級，如果一次可以跳 1 級，也可以跳 2 級。
求總共有多少總跳法，并分析算法的時間復雜度。
分析：
也是比較基礎的題目，通過遞歸可以方便的求解
代碼實現如下（GCC編譯通過）：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
#include "stdio.h"#include "stdlib.h" int function(int n); int main(void){ int tmp; tmp = function(5); printf("%3d\n",tmp); return 0;} int function(int n){ if(n == 1) return 1; else if(n == 2) return 2; else return function(n-1) + function(n-2);} |
約瑟夫環問題
題目：
n個數字（0,1,…,n-1）形成一個圓圈，從數字0開始，每次從這個圓圈中刪除第m個數字（第一個為當前數字本身，第二個為當前數字的下一個數字）。當一個數字刪除后，從被刪除數字的下一個繼續刪除第m個數字。求處在這個圓圈中剩下的最后一個數字。
（其實說了這么多就是約瑟夫環問題）
分析：
以前學習鏈表的時候也見過約瑟夫環問題，當時是拿循環鏈表模擬整個過程來解決的，今天在網上看到一種分析。記錄下來：
題目要求最后剩下的一個數(用last表示)，也就是這個數是第幾個，在（0,1,…,n-1）的位置是多少。明確了題目中的信息，所以我們要對這個數進行歸納。假設知道這個數在剩下的k個數中的位置，怎么來求得它在剩余K+1個數中的位置，這樣一步一步推導出它在有n個數中的位置，即為所求。為什么能這樣歸納，因為這個最后剩下的數在所有刪除過程中有幸存活下來，只不過每次刪除了一個數，它的位置就變了，知道最后，它的位置為0(只剩一個數了)。
現在來分析刪除第一個數后，last這個數的位置已之前有什么樣的關系。在這n個數字中，第一個被刪除的數字是(m-1)%n，為簡單起見記為k。那么刪除k之后的剩下n-1的數字為0,1,…,k-1,k+1,…,n-1，并且下一個開始計數的數字是k+1。相當于在剩下的序列中，k+1排到最前面，從而形成序列k+1,…,n-1,0,…k-1。
k+1 -> 0
k+2 -> 1
…
n-1 -> n-k-2
0 -> n-k-1
…
k-1 -> n-2
現在我們知道了有n-1個數時last的位置，記為f(n-1,m)，那么如何來求得f(n,m)關于f(n-1,m)之間的關系？用X,Y來表示，如下：
Y X
k+1 -> 0
k+2 -> 1
…
n-1 -> n-k-2
0 -> n-k-1
…
k-1 -> n-2
y=( x+k+1) %n
k = (m-1)%n
所以y=(x+m)%n，最終關系如下：
0 n=1
f(n,m)={
[f(n-1,m)+m]%n n>1
根據關系可以很方便的得到代碼
代碼實現如下：
|
1
2
3
4
5
6
7
8
9
10
11
|
int LastRemaining(int n, int m){ if(n < 1 || m < 1) return -1; int last = 0; for (int i = 2; i <= n; i ++) last = (last + m) % i; return last;} |
