利用简洁的C语言代码解决跳台阶问题与约瑟夫环问题
利用简洁的C语言代码解决跳台阶问题与约瑟夫环问题
发布时间:2016-12-28 来源:查字典编辑
摘要:跳台阶问题题目:一个台阶总共有n级,如果一次可以跳1级,也可以跳2级。求总共有多少总跳法,并分析算法的时间复杂度。分析:也是比较基础的题目,...

跳台阶问题

题目:

一个台阶总共有 n 级,如果一次可以跳 1 级,也可以跳 2 级。

求总共有多少总跳法,并分析算法的时间复杂度。

分析:

也是比较基础的题目,通过递归可以方便的求解

代码实现如下(GCC编译通过):

#include "stdio.h" #include "stdlib.h" int function(int n); int main(void) { int tmp; tmp = function(5); printf("%3dn",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; }

推荐文章
猜你喜欢
附近的人在看
推荐阅读
拓展阅读
相关阅读
网友关注
最新C语言学习
热门C语言学习
编程开发子分类