跳臺(tái)階問題

題目：

一個(gè)臺(tái)階總共有 n 級(jí)，如果一次可以跳 1 級(jí)，也可以跳 2 級(jí)。

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

分析：

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

代碼實(shí)現(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個(gè)數(shù)字（0,1,…,n-1）形成一個(gè)圓圈，從數(shù)字0開始，每次從這個(gè)圓圈中刪除第m個(gè)數(shù)字（第一個(gè)為當(dāng)前數(shù)字本身，第二個(gè)為當(dāng)前數(shù)字的下一個(gè)數(shù)字）。當(dāng)一個(gè)數(shù)字刪除后，從被刪除數(shù)字的下一個(gè)繼續(xù)刪除第m個(gè)數(shù)字。求處在這個(gè)圓圈中剩下的最后一個(gè)數(shù)字。

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

分析：

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

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

現(xiàn)在來分析刪除第一個(gè)數(shù)后，last這個(gè)數(shù)的位置已之前有什么樣的關(guān)系。在這n個(gè)數(shù)字中，第一個(gè)被刪除的數(shù)字是(m-1)%n，為簡單起見記為k。那么刪除k之后的剩下n-1的數(shù)字為0,1,…,k-1,k+1,…,n-1，并且下一個(gè)開始計(jì)數(shù)的數(shù)字是k+1。相當(dāng)于在剩下的序列中，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個(gè)數(shù)時(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)系可以很方便的得到代碼

代碼實(shí)現(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;
}

最新評(píng)論