第四届蓝桥杯 软件类省赛真题 第四题：第39级台阶

标题: 第39级台阶

    小明刚刚看完电影《第39级台阶》，离开电影院的时候，他数了数礼堂前的台阶数，恰好是39级!

    站在台阶前，他突然又想着一个问题：

    如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。
那么，上完39级台阶，有多少种不同的上法呢

    请你利用计算机的优势，帮助小明寻找答案。

要求提交的是一个整数。
注意：不要提交解答过程，或其它的辅助说明文字。
==========================================================
思路：
39级台阶 只能迈上1个或2个台阶 走偶数步
（隐含条件：迈的步数相同，顺序不同属于不同情况）
多少种不同的上法

题目大概可以理解成一个39的数，减去1或2，减的次数是偶数次，有多少种排序方法

我想到了鸡兔同笼的方法，根据那种方式，可以用穷举法
设2有0次，其他的是1（39-n），然后慢慢增加，一直增加到20为止
需要筛选的条件： 1.2的次数和1的次数相加为偶数【（2的次数/2+1的次数）%2==0】

但我后来发现之前这个想法过于天真，迈步不同于鸡兔同笼，不同顺序也属于不同的情况，有点像中学学习的数列插空，
可惜没好好学，想不起来，此时只好借助网络或者书本资料。

我想到用最低的开始来算，因为是填空题，所以就用手算加上电脑结合。
规律：
1.从最小开始：1个2步，37个1步，C38取1（总共偶数步）
2.第二步：3个2步，33个1步，C36取3
3.第三步：5个2布，29个1步，C34取5
……
步骤：
穷举：38-2-2-2-2…
定义始数：38，定义循环次数1

先做出3的情况，然后改成变量。

想法：
1.定义：a,b,
2.循环：while无限
3.计算：将数值变化，a+2，b-2
4.排除：if b 5.循环：从a到0，sum1=计数a*（计数a-1） 计数a–
sum2=计数b*（计数b-1） 计数b–
6.计算：double总值=计数1/计数b
7.sum总=总值+sum总
8.输出sum总

运用了这种方法后上面有缺陷，乘太大了变负数
public class Test {
/**
 * 
1.定义：b,a,
2.循环：while无限
3.计算：将数值变化，b+2，a-2
4.排除：if a 5.循环：从a到0，sum1=计数a*（计数a-1） 计数a–
sum2=计数b*（计数b-1） 计数b–
6.计算：double总值=计数1/计数b
7.sum总=总值+sum总
8.输出sum总
找出来规律做的代码：
错误代码：
 * @param args
 */

public static void main(String[] args) {
int a=38;
int b=1;
double zon=38;
while(true){    //循环记得清0
int sum1=1;  //记住每次循环要清0
int sum2=1;
double sum=0;
a=a-2;
b=b+2;
if(a break;
}
for(int i=b;i>0;i–){
sum1=sum1*i;
}
for(int i=a;i>a-b;i–){
sum2=sum2*i;
}
sum=sum2/sum1;
zon=zon+sum;
}
System.out.println(zon);
} 
}
我去网上寻找C语言的算法，进行改造，然后自己吸收

找到了递归的方式，感觉很好，每天有空看看，吸收这种思想：

文章已被收录至官方知识档案算法技能树蓝桥杯-搜索第39级台阶34686 人正在系统学习中

来源：Lee宇斌