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

相关文章

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

Spring事务中@Transactional注解不生效的原因分析与解决

《Spring事务中@Transactional注解不生效的原因分析与解决》在Spring框架中,@Transactional注解是管理数据库事务的核心方式,本文将深入分析事务自调用的底层原理,解释为... 目录1. 引言2. 事务自调用问题重现2.1 示例代码2.2 问题现象3. 为什么事务自调用会失效3

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

找不到Anaconda prompt终端的原因分析及解决方案

《找不到Anacondaprompt终端的原因分析及解决方案》因为anaconda还没有初始化,在安装anaconda的过程中,有一行是否要添加anaconda到菜单目录中,由于没有勾选,导致没有菜... 目录问题原因问http://www.chinasem.cn题解决安装了 Anaconda 却找不到 An

Spring定时任务只执行一次的原因分析与解决方案

《Spring定时任务只执行一次的原因分析与解决方案》在使用Spring的@Scheduled定时任务时,你是否遇到过任务只执行一次,后续不再触发的情况?这种情况可能由多种原因导致,如未启用调度、线程... 目录1. 问题背景2. Spring定时任务的基本用法3. 为什么定时任务只执行一次?3.1 未启用

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

通过Docker Compose部署MySQL的详细教程

《通过DockerCompose部署MySQL的详细教程》DockerCompose作为Docker官方的容器编排工具,为MySQL数据库部署带来了显著优势,下面小编就来为大家详细介绍一... 目录一、docker Compose 部署 mysql 的优势二、环境准备与基础配置2.1 项目目录结构2.2 基