首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Codingame本周谜题「折纸曲线」解

Codingame本周谜题「折纸曲线」解

作者头像
岂不美哉Frost
发布2019-11-30 21:00:03
4650
发布2019-11-30 21:00:03
举报
文章被收录于专栏:Frost's BlogFrost's Blog

Codingame.com Puzzle of the Week: Paper folding curve

题目简述

一张纸,一直保持向同一个方向对折,然后将折痕展成直角。从侧面看去,纸的折角会构成一个折线。 从纸的一端出发到另一端,每碰到一个折角,用1表示向左折,0表示向右折,则所有折角会构成一个1与0组成的序列,称为折叠序列。比如折一次是1,折两次是110,依次类推。 给定折叠次数,要求输出折叠序列中自s至e号元素(0-index,均包含)。

朴素解法

首先,不妨假定我们每次都向左对折,因为如果是向右,我们可以从另一侧观察,则还是向左对折。然后我们来研究下序列的特点。

  1. 对折$n$次将产生$2^n$小段的纸,$2^n-1$个折痕。也说是说序列长度为$2^n-1$,不妨在第1位补个1,序列变成1-index,共有$2^n$个元素。
  2. 考察对折点,对折点之前的纸和对折点之后的纸走向完全一致,即序列关于对折点对称,但由于先进方向相反,原来是向左的对称之后变成向右。所以准确说应该是序列关于对折点反向对称

  1. ** 序列与对折次数无关**。观察上图,折叠2次的折痕是①②③,而再折叠一次,序列①②③④⑤⑥⑦的前三项将与折叠两次的一致。就好像把纸延长了相同的长度,再把后续的折痕加在原序列后面。所以题目中「给定折叠次数」是用不上的。

由1及题设,第$2^n$个元素值恒为1。由1+2,序列的对折点所在是其实是第$2^{n-1}$个元素。又由2+3,序列关于$2^{n-1}$号元素对称,左半部分又关于$2^{n-2}$号元素对称,依次类推。转换成数学语言,用$f(i)$表示序列中第$i$号元素的值,则:

\begin{equation} \begin{split} f(2^n)&=1,,&n=0,1,\ldots \\ f(2^n+x)&=\sim f(2^n-x),,&0<x<2^n,,n>1 \end{split} \end{equation}

其中"~"表示将值取反。所以如果我们已经得到了序列前$2^n$项的值,我们就能根据对称性得到$2^{n+1}$项的值,写成伪代码如下:

// 写出前7项
result = '1101100'
while len(result) < e + 1
    result += '1' + reverse_and_flip(result)
end
print(result[s:e])

时间复杂度为$8+16+\cdots=O(N)$,其中$N=2^n$为全序列长度。提交运行,前面都能PASS,但当s, e都非常大时挂了,果然还是太朴素。

优化解法

我一直在思考:序列某个元素的值由前面的某个值得到,而前面的某个值又由更前面的某个值得到,最后的种子其实就是最开始的几个元素。我们浪费了很多时间在生成不需要输出的结果上。本能觉得,对某个特定元素,可能可以仅通过它的序号,在$O(1)$的复杂度上得到值。说干就干,继续找找规律。由上述的公式,我进一步发展,当$x\neq2^{n-1}$时, \begin{equation} \begin{split} f(2^n+x)&=\sim f(2^n-x) \\ &=\sim f(2^{n-1}+(2^{n-1}-x)) \\ &=f(2^{n-1}-(2^{n-1}-x))=f(x) \end{split} \end{equation}

当$x=2^{n-1}$时,

$$f(2^n+x)=\sim f(2^{n-1})=0$$

Exciting! 如果我们把元素序号用二进制表示的话,通过以上方法,我们就能使序号快速缩小(去掉首位的1)到一个很小的数,进而得到它的值。具体地:

  • 数字除去末尾的0后,如果是以连续的1结尾,则值为0
  • 否则,值为1

伪代码如下:

result = ''
// 修正0 - index到1 - index
for i in [s + 1:e + 1]
    // i是2的幂,快速返回
	if i & (i - 1) == 0
        result += '1'
            break
	end
    // 去掉末位的0
    while i & 1 == 0
        i >>= 1
    end
    if i & 3 == 3   // 11结尾
        result += '0'
	else            // 01结尾
        result += '1'
    end
end

print(result)

时间复杂度近似为$O(e-s)$。

一开始从一个实际问题出发,最后得出了一个简洁的数学表达,果然是代码令我愉快。完整代码(Python)见 https://github.com/frostming/Codingame/blob/master/Puzzle-of-the-Week/paper_folding_curve.py

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018-02-11T,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目简述
  • 朴素解法
  • 优化解法
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档