首页 > 编程语言 > 详细

C语言编程练习16:统计方案

时间:2021-01-22 22:47:12      阅读:66      评论:0      收藏:0      [点我收藏+]

题目描述

在一无限大的二维平面中,我们做如下假设:
1、每次只能移动一格;
2、不能向后走(假设你的目的地是“向上”,那么你可以向左走,可以向右走,也可以向上走,但是不可以向下走);
3、走过的格子立即塌陷无法再走第二次。
求走n步不同的方案数(2种走法只要有一步不一样,即被认为是不同的方案)。

输入

首先给出一个正整数C,表示有C组测试数据。
接下来的C行,每行包含一个整数n(n<=20),表示要走n步。

输出

请编程输出走n步的不同方案总数;
每组的输出占一行。

样例输入 Copy

2
1
2

样例输出 Copy

3
7
思路:我自己还是没找出来,画画图然后参考了其他大佬的博客
大佬解析1(感觉这个最好理解):因为n+1时都可以往两个方向或者三个方向;三个方向是为n时向上的状态;为n时有多少个向上的状态?当n-1有多少状态,n就有多少个向上的状态;所以递推公式为a[n]=2*a[n-1]+a[n-2];
大佬解析2:赤裸裸的递推问题,设第n步的走法为F(n),往上走的步数为a(n),往左或往右走的步数为b(n);

所以F(n)=a(n)+b(n);接下来分别找前一个状态。因为不能往下走,所以向上走的步数只有一种选择就是上一次的步数相加:a(n)=a(n-1)+b(n-1)(前(n-1)步内往上走的步数+前(n-1)步内往左或右的步数);又因为走过的不能返回,所以往左或右走只有一种方法,但向上走可以是左上和右上两种,因此b(n)=2*a(n-1)+b(n-1);化简得F(n)=2*F(n-1)+F(n-2);

#include <stdio.h>
#include <iostream>
#include <cstring>

using namespace std;

int f(int x)
{
	if(x==0)
	{
		return 1;
	}
	if(x==1)
	{
		return 3;
	}
	return 2*f(x-1)+f(x-2);
}
int main()
{
	int n;
	cin >> n;
	while(n--)
	{
		int m;
		cin >> m;
		cout << f(m) <<endl;
			
	}
    return 0;
}

 

C语言编程练习16:统计方案

原文:https://www.cnblogs.com/FantasticDoubleFish/p/14315485.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!