跳臺階問題

題目：

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

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

分析：

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

代碼實現(xiàn)如下（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);
}

約瑟夫環(huán)問題
題目：

n個數(shù)字（0,1,…,n-1）形成一個圓圈，從數(shù)字0開始，每次從這個圓圈中刪除第m個數(shù)字（第一個為當前數(shù)字本身，第二個為當前數(shù)字的下一個數(shù)字）。當一個數(shù)字刪除后，從被刪除數(shù)字的下一個繼續(xù)刪除第m個數(shù)字。求處在這個圓圈中剩下的最后一個數(shù)字。

（其實說了這么多就是約瑟夫環(huán)問題）

分析：

以前學(xué)習(xí)鏈表的時候也見過約瑟夫環(huán)問題，當時是拿循環(huán)鏈表模擬整個過程來解決的，今天在網(wǎng)上看到一種分析。記錄下來：

    題目要求最后剩下的一個數(shù)(用last表示)，也就是這個數(shù)是第幾個，在（0,1,…,n-1）的位置是多少。明確了題目中的信息，所以我們要對這個數(shù)進行歸納。假設(shè)知道這個數(shù)在剩下的k個數(shù)中的位置，怎么來求得它在剩余K+1個數(shù)中的位置，這樣一步一步推導(dǎo)出它在有n個數(shù)中的位置，即為所求。為什么能這樣歸納，因為這個最后剩下的數(shù)在所有刪除過程中有幸存活下來，只不過每次刪除了一個數(shù)，它的位置就變了，知道最后，它的位置為0(只剩一個數(shù)了)。

現(xiàn)在來分析刪除第一個數(shù)后，last這個數(shù)的位置已之前有什么樣的關(guān)系。在這n個數(shù)字中，第一個被刪除的數(shù)字是(m-1)%n，為簡單起見記為k。那么刪除k之后的剩下n-1的數(shù)字為0,1,…,k-1,k+1,…,n-1，并且下一個開始計數(shù)的數(shù)字是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

現(xiàn)在我們知道了有n-1個數(shù)時last的位置，記為f(n-1,m)，那么如何來求得f(n,m)關(guān)于f(n-1,m)之間的關(guān)系？用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，最終關(guān)系如下：

                0                              n=1
f(n,m)={
                [f(n-1,m)+m]%n     n>1

根據(jù)關(guān)系可以很方便的得到代碼

代碼實現(xiàn)如下：

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

最新評論