您现在的位置是:首页 > 正文

C语言(CED)对于一个2行N列的走道。现在用1*2,2*2的砖去铺满。问有多少种不同的方式(递归求解)

2024-01-31 00:15:42阅读 0

又涉及到递归问题,这道题的大致内容是这样的:

(请用递推方式求解)对于一个2行N列的走道。现在用1*2,2*2的砖去铺满。问有多少种不同的方式。下图是一个2行17列的走道的某种铺法。

    提示:观察前n个结果,可以得到递推式子;如果N很大,需要高精度计算。

其实这道题,与之前的方格涂色问题很像,说它像不仅因为在思考方式上很像,在最后的代码上也很想像,听我一一道来。

题目提示,先观察前n个结果得到递推式。那我们就把前n个结果列出来。在列的同时,就有一种这样的感觉——就像是在高中化学中写同分异构式,“有序思考”。在这里我就不展示我在草稿纸上列举的了直接说思想。

一、主要思想

和讲解方格涂色问题一样,我先来讲一下我的思路:

每次铺砖时考虑的情况大致类似,所以可以用递归求解。根据最后剩余的列数,我们将本问题分成两种情况:

A:最后剩余一列,那么假设把这列去掉后,其铺砖情况与n-1时的情况一样,而加上后,也只有一种情况所以方法数位pave(n-1)

B:最后剩余两列,那么把这两列先去掉后和n-2的情况一样,加上这两列后一共有三种情况:1*2竖着放2列,1*2横着放,2*2直接填满。因为1*2竖着放和A情况重复,所以方法数为pave(n-2)*2

综上:方法总数=pave(n-1)+2*pave(n-2)

二、具体实现

思路有了,但是其中的pave()函数还没有,这就需要我们动手来操作了。以下是具体实现的代码,如果看过我之前那篇博文的同学可能就会知道,这不是一样的问题嘛!对的,代码几乎一样。

#include<iostream>
using namespace std;
long long pave(int n)
{
	long long c[3] = { 0 };//保存不使用2*2砖的方法次数
	c[0] = 1;//由数学逻辑推出
	c[1] = 3;//同上
	c[2] = 5;//同上
	if (n == 1)
		return 1;
	else if (n == 2)
		return 3;
	else if (n == 3)
		return 5;
	else
		return pave(n - 1) + 2 * pave(n - 2);//用递归求解
}
int main()
{
	int n;
	cout << "请输入走道的列数N" << endl;
	while (cin >> n)
	{
		if (n == 0)
		{
			cout << "输入有误,请重新输入!" << endl;
			continue;
		}
		cout << "对应的铺法有:" << endl;
		cout << pave(n) << endl;
		cout << "铺砖已完成" << endl;
		cout << "请输入下一走道的列数:(无其他输入请按EOF结束)" << endl;
	}
	return 0;
}

网站文章

  • JAVA WEB:西蒙购物网 实现页面 资源及代码

    JAVA WEB:西蒙购物网 实现页面 资源及代码

    一、准备资源1、图片在web目录里创建images目录,存放项目所需图片文件:2、css样式文件在web里创建css目录,在里面创建main.css文件:/* 样式 */body { margin: 0px; text-align: center; background: url("../images/frontBack.jpg") no-repeat;...

    2024-01-31 00:15:33
  • Mysql  ----------  安装

    Mysql ---------- 安装

    MySQL 是一个关系型数据库管理系统,由瑞典 MySQL AB 公司开发,目前属于 Oracle 公司。优点:关联数据库将数据保存在不同的表中,而不是将所有数据放在一个大仓库内,这样就增加了速度并提高了灵活性。可以在官网下载地址: https://dev.mysql.com/downloads/安装:同意选择完整安装...

    2024-01-31 00:15:04
  • Django ORM:数据库操作的Python化艺术

    Django的对象关系映射器(ORM)是其核心功能之一,允许开发者使用Python代码来定义、操作和查询数据库。

    2024-01-31 00:14:57
  • kubernetes env资源引用

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 @关于kubernetes env资源注入 前言 关于kubernetes env引用变量方式有configMap,DownwardA...

    2024-01-31 00:14:51
  • 蓝桥杯开发板CT107D使用 IAP15F2K61S2芯片时晶振频率的选择

    蓝桥杯开发板CT107D使用 IAP15F2K61S2芯片时晶振频率的选择

    蓝桥杯开发板CT107D上使用的晶振为12MHZ,在进行烧录和软件延时需要对晶振频率进行选择。而烧录软件一般默认为11.0592MHZ. 只需要将两个频率保持一致即可(一般在12和11.0592中选择一个),直接上图 选择 12MHZ 11.0592MHZ ...

    2024-01-31 00:14:45
  • Workerman ThinkPHP5 宝塔 安装Event拓展

    Workerman ThinkPHP5 宝塔 安装Event拓展

    Workerman 结合 TP5在宝塔环境下安装Event拓展操作系统是CentOS7先用workerman官方给的检查环境的脚本进行检查curl -Ss http://www.workerman.n...

    2024-01-31 00:14:18
  • selenium自动化-下拉列表

    selenium自动化-下拉列表

    selenium操作下拉列表select/option标签举个例子ul/li标签验证js是否能选中未显示的值结论python代码实现 selenium自动化获取对象时,肯定会涉及到下拉列表,项目中遇到...

    2024-01-31 00:14:10
  • Vue基础升级

    Vue基础升级

    生命周期函数面试题 1.什么是 vue 生命周期;2.vue生命周期的作用是什么 Vue每个组件都是独立的,每个组件都有一个属于它的生命周期,从一个组件创建、数据初始化、挂载、更新、销毁,这就是一个组...

    2024-01-31 00:14:03
  • Excel之单元格数字格式

    Excel之单元格数字格式

    文本与常规格式的正常转换 单元格格式一般分两种文本与常规 分列工具大部分是用于修改单元格的格式 文本数据不能正常的运算,像身份证号电话等等这些一般都是文本 常规的数据可以正常运算 文本如何转换成常规格...

    2024-01-31 00:13:33
  • Python进阶

    Python进阶

    Python

    2024-01-31 00:13:24