c语言代码大全求解

来源：蜘蛛抓取(WebSpider) 时间：2019-12-17 17:33 标签： c语言代码大全

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

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

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

代码实现如下（GCC編译通过）：

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

现在我们知道了有n-1个数时last的位置，记为f(n-1,m)那么如何来求得f(n,m)关于f(n-1,m)之间的关系？用X,Y来表示如下：

所以y=(x+m)%n，最终关系如下：

根據关系可以很方便的得到代码

我要回帖

更多关于 c语言代码大全 的文章

 

随机推荐