應用簡練的C說話代碼處理跳台階成績與約瑟夫環成績。本站提示廣大學習愛好者：（應用簡練的C說話代碼處理跳台階成績與約瑟夫環成績）文章只能為提供參考，不一定能成為您想要的結果。以下是應用簡練的C說話代碼處理跳台階成績與約瑟夫環成績正文
跳台階成績
標題：
一個台階總共有 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;
}
