简单的c语言编程软件编程题

来源：蜘蛛抓取(WebSpider) 时间：2016-06-05 02:43 标签： c 简单编程
利用简洁的C语言代码解决跳台阶问题与约瑟夫环问题
作者：Zhang_H
字体：[ ] 类型：转载 时间：
这篇文章主要介绍了利用简洁的C语言代码解决跳台阶问题与约瑟夫环问题的方法,跳台阶问题与约瑟夫环问题是常见的基础算法题目,需要的朋友可以参考下
跳台阶问题
一个台阶总共有 n 级，如果一次可以跳 1 级，也可以跳 2 级。
求总共有多少总跳法，并分析算法的时间复杂度。
也是比较基础的题目，通过递归可以方便的求解
代码实现如下（GCC编译通过）：
#include "stdio.h"
#include "stdlib.h"
int function(int n);
int main(void)
tmp = function(5);
printf("%3d\n",tmp);
int function(int n)
if(n == 1)
else if(n == 2)
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-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 &= i ++)
last = (last + m) %
您可能感兴趣的文章:
大家感兴趣的内容
12345678910
最近更新的内容
常用在线小工具君，已阅读到文档的结尾了呢~~
最简单的C程序设计-顺序程..
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
最简单的C程序设计-顺序程序设计_习题四及参考答案
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口c语言基本编程题_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
c语言基本编程题
上传于||文档简介
&&c​语​言​经​典​题
阅读已结束，如果下载本文需要使用1下载券
想免费下载本文？
下载文档到电脑，查找使用更方便
还剩14页未读，继续阅读
你可能喜欢几个简单C语言编程题目,自己太笨做不来.速求1.计算1到100的连续整数和.2.输入3个整数.找其中最大值或最小值.3.输入一个3位的正整数,分解出它的个,十,百位数字.
1.#include&&stdio.h&int&main(){//求和int&i,sum=0;for(i=1;i&=100;i++)sum+=i;//sum就是最后的和printf(&1+2+3+...+100=%d&,sum);return&0;}2.#include&&stdio.h&int&main(){//最大最小值int&a,b,c;int&max,scanf(&%d,%d,%d&,&a,&b,&c);max=min=a;//最大值if(max&b)max=b;if(max&c)max=c;//最小值if(min&b)min=b;if(min&c)min=c;//此时min就是最小值,max就是最大值printf(&max=%d,min=%d&,max,min);return&0;}3.#include&&stdio.h&int&main(){int&a;int&ge,shi,scanf(&%d&,&a);ge=a%10;shi=(a/10)%10;bai=a/100;printf(&ge=%d,shi=%d,bai=%d&,ge,shi,bai);return&0;}
为您推荐：
其他类似问题
扫描下载二维码C语言简单的题目~~~_百度知道
C语言简单的题目~~~
从键盘输入输入一个三位正整数，将该数的个位与百位互换，则输出－1.如果输入的正整数为300，然后反向输出对应的数，则输出为3，如果输入的数不是三位正整数。【输入样例】356 【输出样例】653【样例说明】从键盘输入的正整数值为356。【输入形式】从键盘输入三位的正整数。【输出形式】输出交换后的正整数值，所得结果为653【问题描述】编写一程序
提问者采纳
include &%d&请输入一个数; scanf(&quot：&); } printf(&).h&%d\
100 == 0) {
printf(&-1&#92, &n);;; if (n / 100 + n % 10 * 100 + n % 100 - n % 10));n& printf(&quot, (n /n&void main(){ int n
来自团队：
其他类似问题
为您推荐：
c语言的相关知识
其他4条回答
ain(){int a,*p;=a&&a&p++,&a);p++,b;b+=&p*10;scanf(&b+=&p*100;if(100&;%d&quot,b);}你先试试这个;*p=a;b=0;-1&=999){b+=&p;);printf(&%d&}else print(&
#include &stdio.h&#include &stdlib.h&int main(){
scanf(&%d&,&value); if(value&100||value&999) {
printf(&-1\n&); } else {
value=(value%10)*100+(value/100)+((value/10)%10)*10;
printf(&%d\n&,value);
} system(&pause&); return 0;}
#include&stdio.h&void main(){ int num,a,b,c; printf(&In put number:&); scanf(&%d&,&num);
//三位数的输入 printf(&Change:&); if(num&100||num&999) printf(&-1\n&);
//小于100或大于999的处理，输出-1 else {
a=num/100;
//取百位数
b=num/10%10;
//取十位数
//取个位数
num=c*100+b*10+a;
//重新排列后的数
printf(&%d\n&,num); }}
main（）{float i,ans；int j,temp,ge,bai,scanf（&%f&,&i）;j=(int)i;//取i的整数部分ans=i-(float)j;if(ans==0)
//判断i小数点后面是否为0,即是否为正整数
printf(&-1&);
//输出个位
//输出百位
shi=i/10%10;
//输出十位temp=bai*100+shi*10+printf(&%d&,temp);
printf(&-1&);} 本程序包括可以判断输入的是负数，浮点数，整数。
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁

我要回帖

更多关于 c 简单编程 的文章

 

随机推荐