2663 Tri Tiling 完美覆盖,样例分析+详细题解-只需10行代码

2023-10-24 14:10

本文主要是介绍2663 Tri Tiling 完美覆盖,样例分析+详细题解-只需10行代码,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

描述

一张普通的国际象棋棋盘,它被分成 8 乘 8 (8 行 8 列) 的 64 个方格。设有形状一样的多米诺牌,每张牌恰好覆盖棋盘上相邻的两个方格,即一张多米诺牌是一张 1 行 2 列或者 2 行 1 列的牌。那么,是否能够把 32 张多米诺牌摆放到棋盘上,使得任何两张多米诺牌均不重叠,每张多米诺牌覆盖两个方格,并且棋盘上所有的方格都被覆盖住?我们把这样一种排列称为棋盘被多米诺牌完美覆盖。这是一个简单的排列问题,同学们能够很快构造出许多不同的完美覆盖。但是,计算不同的完美覆盖的总数就不是一件容易的事情了。不过,同学们 发挥自己的聪明才智,还是有可能做到的。
现在我们通过计算机编程对 3 乘 n 棋盘的不同的完美覆盖的总数进行计算。
在这里插入图片描述
任务
对 3 乘 n 棋盘的不同的完美覆盖的总数进行计算。

输入

一次输入可能包含多行,每一行分别给出不同的 n 值 ( 即 3 乘 n 棋盘的列数 )。当输入 -1 的时候结束。

n 的值最大不超过 30.

输出

针对每一行的 n 值,输出 3 乘 n 棋盘的不同的完美覆盖的总数。

思路

看着有点麻烦,其实不难,代码10行就够了。
首先对 n = 2 n=2 n=2时,对3*2的棋盘我们有三种(丑,勿怪)覆盖方式
在这里插入图片描述
对样例来说有12行,我们挑几种形式来分析一下
在这里插入图片描述

  • n n n是奇数,可以考虑一列,三列,5列的情形,你会发现,只要是奇数列,我们完全没有办法把他填充完整,因此我们可以考虑以两列为一个单位。
  • 记函数 f ( n ) f(n) f(n)为在 n n n列时的覆盖方案数目, f ( 0 ) = 1 f(0)=1 f(0)=1,为什么这么初始化?看 f ( 2 ) f(2) f(2)我们以两列为一个单位,那么他必定与 f ( 0 ) f(0) f(0)的排列总数有关,而 f ( 2 ) = 3 f(2)=3 f(2)=3是0号位置的排列数目之和*[1-2]位置的排列方法数目,因此初始化为1.
  • 再来看看 f ( 4 ) f(4) f(4),也就是下图红线框起来的部分。首先考虑他最右边两列有三种情况,承上之前的排列数即 f ( 2 ) ∗ 3 f(2)*3 f(2)3,不止如此,他的四列也可能长蓝线框起来这样,这种情况下有几种组合呢,答案是 f ( 0 ) ∗ 2 f(0)*2 f(0)2
    在这里插入图片描述
  • 最后我们看看 f ( n ) f(n) f(n),首先他的最后两列有三种情况 f ( n ) = 3 ∗ f ( n − 2 ) + . . . f(n)=3*f(n-2)+... f(n)=3f(n2)+...,然后他的最后四列单独拿出来有两种情况 f ( n ) = 3 ∗ f ( n − 2 ) + 2 ∗ f ( n − 4 ) + . . . f(n)=3*f(n-2)+2*f(n-4)+... f(n)=3f(n2)+2f(n4)+...,他的最后六列单独拿出来也只有两种情况:于是 f ( n ) = 3 ∗ f ( n − 2 ) + 2 ∗ f ( n − 4 ) + 2 ∗ f ( n − 6 ) + . . . f(n)=3*f(n-2)+2*f(n-4)+2*f(n-6)+... f(n)=3f(n2)+2f(n4)+2f(n6)+...,不断的向前递归我们得到
    在这里插入图片描述
    f ( n ) = 3 ∗ f ( n − 2 ) + 2 ∗ f ( n − 4 ) + 2 ∗ f ( n − 6 ) + . . . + 2 ∗ f ( 0 ) f(n)=3*f(n-2)+2*f(n-4)+2*f(n-6)+...+2*f(0) f(n)=3f(n2)+2f(n4)+2f(n6)+...+2f(0)
    f ( n − 2 ) = 3 ∗ f ( n − 4 ) + 2 ∗ f ( n − 6 ) + . . . + 2 ∗ f ( 0 ) ) f(n-2)=3*f(n-4)+2*f(n-6)+...+2*f(0)) f(n2)=3f(n4)+2f(n6)+...+2f(0))
    f ( n ) = 4 f ( n − 2 ) − f ( n − 4 ) f(n)=4f(n-2)-f(n-4) f(n)=4f(n2)f(n4)
#include<iostream>
using namespace std;
int f[35];
int main() {int n = 0; f[0] = 1, f[2] = 3;for (int i = 4; i < 35; i++)f[i] = 4 * f[i - 2] - f[i - 4];while (cin >> n && n != -1) {cout << f[n] << endl;}
}

这篇关于2663 Tri Tiling 完美覆盖,样例分析+详细题解-只需10行代码的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/275719

相关文章

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

如何为Yarn配置国内源的详细教程

《如何为Yarn配置国内源的详细教程》在使用Yarn进行项目开发时,由于网络原因,直接使用官方源可能会导致下载速度慢或连接失败,配置国内源可以显著提高包的下载速度和稳定性,本文将详细介绍如何为Yarn... 目录一、查询当前使用的镜像源二、设置国内源1. 设置为淘宝镜像源2. 设置为其他国内源三、还原为官方

最详细安装 PostgreSQL方法及常见问题解决

《最详细安装PostgreSQL方法及常见问题解决》:本文主要介绍最详细安装PostgreSQL方法及常见问题解决,介绍了在Windows系统上安装PostgreSQL及Linux系统上安装Po... 目录一、在 Windows 系统上安装 PostgreSQL1. 下载 PostgreSQL 安装包2.

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

Java程序进程起来了但是不打印日志的原因分析

《Java程序进程起来了但是不打印日志的原因分析》:本文主要介绍Java程序进程起来了但是不打印日志的原因分析,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java程序进程起来了但是不打印日志的原因1、日志配置问题2、日志文件权限问题3、日志文件路径问题4、程序

MySql match against工具详细用法

《MySqlmatchagainst工具详细用法》在MySQL中,MATCH……AGAINST是全文索引(Full-Textindex)的查询语法,它允许你对文本进行高效的全文搜素,支持自然语言搜... 目录一、全文索引的基本概念二、创建全文索引三、自然语言搜索四、布尔搜索五、相关性排序六、全文索引的限制七

python中各种常见文件的读写操作与类型转换详细指南

《python中各种常见文件的读写操作与类型转换详细指南》这篇文章主要为大家详细介绍了python中各种常见文件(txt,xls,csv,sql,二进制文件)的读写操作与类型转换,感兴趣的小伙伴可以跟... 目录1.文件txt读写标准用法1.1写入文件1.2读取文件2. 二进制文件读取3. 大文件读取3.1

Java字符串操作技巧之语法、示例与应用场景分析

《Java字符串操作技巧之语法、示例与应用场景分析》在Java算法题和日常开发中,字符串处理是必备的核心技能,本文全面梳理Java中字符串的常用操作语法,结合代码示例、应用场景和避坑指南,可快速掌握字... 目录引言1. 基础操作1.1 创建字符串1.2 获取长度1.3 访问字符2. 字符串处理2.1 子字

Linux内核参数配置与验证详细指南

《Linux内核参数配置与验证详细指南》在Linux系统运维和性能优化中,内核参数(sysctl)的配置至关重要,本文主要来聊聊如何配置与验证这些Linux内核参数,希望对大家有一定的帮助... 目录1. 引言2. 内核参数的作用3. 如何设置内核参数3.1 临时设置(重启失效)3.2 永久设置(重启仍生效

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析