鱼C论坛

 找回密码
 立即注册
查看: 220|回复: 6

铺地毯(原题链接:http://noi.openjudge.cn/ch0405/9279/)

[复制链接]
发表于 2020-9-18 22:46:40 | 显示全部楼层 |阅读模式
10鱼币
题目在下图:

铺砖

铺砖

并不需要提供代码!!
主要是讲一下思路

题型:递归

屏幕截图(61).png
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2020-9-20 18:59:04 | 显示全部楼层
啥题目啊!砖的大小不一样,题目又没说多宽算一列,多宽算一行。两块1*2的可以拼成一块2*2的。问题是,2*2算一个格子,还是1*2算一个格子,甚至3*2算一个格子?或者1*3算一个格子?还有更多可能。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2020-9-20 21:43:21 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2020-9-21 11:20:13 | 显示全部楼层
3000是ms么。。ms的话递归好像跑不出来emm
我目前做出来的思路就是:
对于x,将其输入函数func:
if x==1:
    return 1#如果只剩下一层,只有一种情况
elif x==2:
    return 3 #如果剩下最后两层,返回3(即两种1*2+一种2*2)
else:
    return func(x-1)+2*func(x-2)#即:假定最后一层为1*2,递归,再假定最后一层为竖排的1*2 *2或2*2(此处横排的1*2 *2在前一种情况已经被计算过),递归

具体代码:
  1. def count_func(x):
  2.     count = 0
  3.     if x == 1:
  4.         return 1
  5.     elif x == 2:
  6.         return 3
  7.     else:
  8.         count += count_func(x - 1) + count_func(x - 2) * 2
  9.         return count


  10. def non_reverse_count(x):
  11.     list = []
  12.     for each in range(0, x):
  13.         if each == 0:
  14.             list.append(1)
  15.         elif each == 1:
  16.             list.append(3)
  17.         else:
  18.             list.append(list[each - 1] + 2 * list[each - 2])
  19.     return list[x-1]


  20. def main():
  21.     while True:
  22.         input_number = int(input('input\n'))
  23.         if input_number != -1:
  24.             print(non_reverse_count(input_number))
  25.         else:
  26.             break


  27. if __name__ == '__main__':
  28.     main()
复制代码

因为递归版本超时,所以附了一个非递归版本
   
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2020-9-21 11:21:09 | 显示全部楼层
Pliosauroidea 发表于 2020-9-21 11:20
3000是ms么。。ms的话递归好像跑不出来emm
我目前做出来的思路就是:
对于x,将其输入函数func:

递归那个词我不会拼,随手找个顺眼的写在函数名上了,无伤大雅23333
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2020-9-21 11:22:44 | 显示全部楼层
Pliosauroidea 发表于 2020-9-21 11:20
3000是ms么。。ms的话递归好像跑不出来emm
我目前做出来的思路就是:
对于x,将其输入函数func:

因为题目中只有1*2和2*2的tile,所以只存在单层1*2,双层竖排1*2和2*2三种情况,只要对这三种情况分别讨论后去掉对应tile,就变成了一个递归处理
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2020-9-21 16:22:34 | 显示全部楼层
你在标题中给的网站链接里面那个还考虑了更复杂的情况,那个题的意思是说如果你有一个左右不对称的布局,那么必然存在一个镜面对称的布局,这两种情况在那个题中是算为一个的,所以还要添加一个过程,算出你生成的形状中不对称的布局个数,然后在总生成数中将这一块的重复减掉
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1

GMT+8, 2020-10-29 13:34

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表