程序地带

用L型(包含三个小方格)覆盖缺一个小方格的2的n次方*2的n次方棋盘


找规律即可得出O(1)算法。假设n等于任意时空缺的都为右下方的小方格,先从n=1开始看,此时最大有1个L,然后n等于2,我们想象有4个一模一样的n1图形,经过组合发现需要多加一个L型使得新组合的图形仅有一个空缺,往后递推即可。


用第二数学归纳法描述,当n=1时,则缺一个小方格的22的正方形能被L型覆盖。 假设所有不超过n的2的n次方2n次方正方形都能被L型覆盖,则n=n+1时可以由四个2n次方2n次方的正方形构成,可以产生一个空缺一个方格的22正方形,这个正方形一定能被L覆盖,因此n+1可以被L覆盖。


#include <stdio.h>
int main()
{
int n,val=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
val=val*4+1;
}
printf("%d",val);
return 0;
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Haroldhyc/article/details/109757401

随机推荐

docker常见操作总结

一、原理1、Hypervisor是一种运行在物理服务器和操作系统之间的中间软件层,可允许多个操作系统和应用共享一套基础物理硬件,它能直接访问物理设备,会给每一台虚拟机分配内存、CPU、网络、磁盘等资源...

ImLiFeLong 阅读(706)

日志切割之Logrotate

关于日志切割日志文件包含了关于系统中发生的事件的有用信息,在排障过程中或者系统性能分析时经常被用到。对于忙碌的服务器,日志文件大小会增长极快,服务器会很快消耗磁盘空间,这成了个问题。除此之外,处理一个...

合衬-nfsnobody.com 阅读(731)

Nginx

Nginx

1.什么是Nginx?Nginx("enginex")是一款是由俄罗斯的程序设计师IgorSysoev所开发高性能的Web和反向代理服务器,也是一个IMAP/POP3/SMTP代理...

G丶影 阅读(579)

Win10 搭建java环境(图文)

目录一、JRE(JavaRuntimeEnvironment)二、JDK(JavaDevelopmentKit)三、JDK的下载四、JDK的安装五、环境变量的配置1.打开环境变量窗口<...

Amarao 阅读(410)