- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
“假设你想用一排排 4×1 和 6×1 的乐高积木搭建一个实心面板。为了结构强度,积木之间的空间绝不能在相邻的行中排列。例如,所示的 18×3 面板下面是 Not Acceptable ,因为顶部两行中的块之间的空间对齐。
10×1面板有2种方式,10×2面板有2种方式,18×3面板有8种方式,36×5面板有7958种方式。
有多少种不同的方法来构建 64×10 面板?答案将适合 64 位有符号整数。编写一个程序来计算答案。您的程序应该运行得非常快——当然,即使在较旧的机器上,它也不应该超过一分钟。让我们知道您的程序计算的值、您的程序计算该值所需的时间以及您在何种机器上运行它。包括程序的源代码作为附件。
”
我最近收到了一个编程难题,并一直在绞尽脑汁试图解决它。我使用 c++ 编写了一些代码,我知道这个数字很大……我的程序运行了几个小时,然后我决定停止它,因为即使在慢速计算机上也需要 1 分钟的运行时间。有没有人见过类似的拼图?已经几个星期了,我不能再提交这个了,但这真的让我烦恼,我无法正确解决它。关于使用算法的任何建议?或者也许可能的解决方法是“开箱即用”。我采用的是制作一个程序,该程序构建了 4x1 和 6x1 块的每个可能的“层”以制作 64x1 层。结果证明大约有 3300 个不同的层。然后我让我的程序运行并将它们堆叠成所有可能的 10 层高的墙壁,这些墙壁没有排列的裂缝……正如你所看到的,这个解决方案需要很长很长很长的时间。所以很明显,在时间限制内,蛮力似乎并不能有效地解决这个问题。任何建议/见解将不胜感激。
最佳答案
主要见解是:在确定第 3 行中的内容时,您不关心第 1 行中的内容,只关心第 2 行中的内容。
因此,让我们将如何构建 64x1 层称为“行场景”。你说大约有3300行场景。那还不错。
让我们计算一个函数:
f(s, r) = 将行场景编号“s”放入“r”行并合法填充“r”上方的所有行的方法数。
(我在顶部的“1”行和底部的“10”行进行计数)
如果您想避免剧透,请立即停止阅读。
现在很清楚(将我们的行从 1 编号到 10):
f(s, 1) = 1
对于“s”的所有值。
此外,这就是洞察力的来源,(使用 Mathematica 符号)
f(s, r) = Sum[ f(i, r-1) * fits(s, i) , {i, 1, 3328} ]
Sum[ f(i, 10) , {i, 1, 3328} ]
关于language-agnostic - 有没有人见过类似的编程难题?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/913566/
我是一名优秀的程序员,十分优秀!