gpt4 book ai didi

algorithm - 根据图案(展开)折叠一张纸并给出层的顺序

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:25:51 26 4
gpt4 key购买 nike

上周五,在一次法语编程比赛中,我们得到了一道折纸题,题目如下:

Given a square sheet of paper and a folding pattern, write a function "fold(pattern)" that will give the order of the layers that will result from the cumulative folding (in half) of the sheet in respect of the pattern."

这可能不是很清楚,所以让我解释一下(如果你愿意走那么远来帮助我,手头有一张方形纸可能有助于理解)。

假设我们有一张正方形的纸,我们在上面画了一个 N*N 的网格,然后给它内部的所有正方形编号。给定一个模式“LTRB”,我们会将这张纸垂直对折,然后将左边的部分放在右边的部分上。然后,我们将它水平折叠并将顶部放在底部。然后,我们将它再次垂直折叠并将右侧部分放在左侧部分上。最后,我们将它水平折叠并将底部放在顶部。这给我们留下了一张纸,大小为一个正方形和 N^2 层。预期的答案是每个原始方 block 的结果顺序。

例如,如果我们在一张正方形纸上画一个 2*2 的网格,然后将每个内部正方形从 1 到 4 编号(从左上到右下,水平方向),并给定图案“LT”,我们会发生这种情况:

fold("LT"):

1 | 2 L 1,2 T
---|--- ==> --- ==> 2,1,3,4
3 | 4 3,4

并带有“RB”模式,例如:

fold("RB"): 

1 | 2 R 2,1 B
---|--- ==> --- ==> 3,4,2,1
3 | 4 4,3

您可能已经猜到了,它基本上可以归结为 N*N 矩阵的递归变换。这是简单的部分,这是我的解决方案:

http://ideone.com/QaXGq

现在到了有趣的部分。

  • 编写一个函数 unfold(order) ,对于给定的结果层排序,给出产生这个排序的模式。注意展开(折叠(“LRTB”))=>“LRTB”

然后我的大脑停止工作了一段时间,我没有时间(总共 4 小时还剩下 2 小时)想出足够快的解决方案。

我最初的想法是:

  1. 尝试暴力破解它。因为我们知道输入的长度是 N^2,所以我们可以创建一个初始矩阵并尝试所有可能的折叠,直到达到与输入相同的顺序。 O(4^N) 复杂度,不可行。

  2. 暴力逆转。从输入开始,尝试所有展开的可能性,直到我们到达一个正确的初始状态。好一点了,但还是太慢了。

  3. ???

有人有想法吗?

最佳答案

在每一步中,您只需要知道列表的第一个元素和最后一个元素。如果第一个元素应该在最后一个元素的左边,那么折叠方向就是左(与右、上、下同上)。

关于algorithm - 根据图案(展开)折叠一张纸并给出层的顺序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10485309/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com