跳臺階問題

題目：

一個臺階總共有 n 級，如果一次可以跳 1 級，也可以跳 2 級。

求總共有多少總跳法，并分析算法的時間復雜度。

分析：

也是比較基礎的題目，通過遞歸可以方便的求解

代碼實現如下（GCC編譯通過）：

#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

根據關系可以很方便的得到代碼

代碼實現如下：

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;}