晴天的魔法乐园——上楼

编辑:谯胜平      分类:程序与算法      标签:晴天的魔法乐园      发布时间:2019-09-02      浏览次数:638

题目链接:https://judger.net/problem/1054

Problem Description

我打算走楼梯上楼,共有n级台阶。
我身轻如燕,所以每次都可以选择上一级台阶或者两级台阶。
问有多少种上楼的方式。
例如当n=3时,共有三种方式上楼:

  1. 一级 -> 一级 -> 一级;

  2. 一级 -> 二级;

  3. 二级 -> 一级。

Input

每个输入文件一组数据。
一个正整数n(n<=45),表示台阶级数。

Output

一个正整数,表示上楼的方案数。

Sample Input 1

1

Sample Output 1

1

Sample Input 2

2

Sample Output 2

2

Sample Input 3

3

Sample Output 3

3

1、分析

这种题目看都不用看,想都不用想,绝对是找规律的题。

(1)、找规律。

考虑一下情形:

n = 1时:1种,①:1

n = 2时:2种,①:1 + 1

                        ②:2

n = 3时:3种,①:1 + 1 + 1

                        ②:1 + 2

                        ③:2 + 1

n = 4时:5种,①:1 + 1 + 1 + 1

                        ②:1 + 1 + 2

                        ③:1 + 2 + 1

                        ④:2 + 1 + 1

                        ⑤:2 + 2

n = 5时:8种,①:1 + 1 + 1 + 1 + 1

                        ②:1 + 1 + 1 + 2

                        ③:1 + 1 + 2 + 1

                        ④:1 + 2 + 1 + 1

                        ⑤:2 + 1 + 1 + 1

                        ⑥:1 + 2 + 2

                        ⑦:2 + 2 + 1

                        ⑧:2 + 1 + 2

...

看起来有点像组合数?没错,就是组合数。

总数=n个楼梯中选择0个2级楼梯的组合数 + (n - 1)个楼梯中选择1个2级楼梯的组合数 + (n - 2)个楼梯中选择2个两级楼梯的组合数 + ...

即:

ubang_image_20190902384387.png

注意奇数和偶数都是计算到n/2向下取整处哦。

知道了以上规律之后,就是计算组合数的问题了。

(2)求组合数。

由于int所能表示的最大正整数2 ^ 31 - 1 = 2147483647‬ ≈ 2 * 10 ^ 9 < 13!;

long long所能表示的正整数:2^64 - 1 = 9223372036854775807‬ ≈ 9 * 10 ^ 18 < 21!;

因此计算机中不能表示45!的整数。因此采用一下的最右边的公式进行计算。

image.png

有同学可能会考虑到整数相除会不会有问题,这里计算的时候,可以增加一个判断,如果(m - n + i) % i ==0的时候再相除即可。

2、代码

#include<stdio.h>

//计算组合数m为下标,n为上标 
int fac(int m, int n){
	if(n == 0){
		return 1;
	}else if(n == 1){
		return m;
	}else{
		int plus = 1;		//每一步计算临时保存的结果 
		for(int i = 1; i <= n; i++){
			plus = plus * (m - n + i);
			if(plus % i == 0){	//当可以进行整除的时候再进行除法操作 
				plus /= i;
			}
		}
		return plus;
	}
}

int main(){
	int n;
	scanf("%d", &n);
	int i = n, j = 0, sum = 0;
	while(i - j >= 0){	//当上标小于等于下标时才进行计算 
		sum += fac(i, j);
		i--;
		j++;
	}
	printf("%d\n", sum);
	return 0;
}




看不清?换一个