where {NEXT} is:

好吧，貌似不好玩，那找找原因

第一次 input 是 A=[1,2]


A(s)»B
A(b)»C
B(s)»C

交换的顺序是 1,2 -> 2,1
我们做的是先把 s 放在缓冲栈里，然后把 b 放到目标里，然后把 s 里的缓冲压入目标栈
这就是一次交换，归纳出来就是 src(smaller) » buf; src(bigger) » dst; buf(smaller) » dst

第二次 input 是 A=[1,2,3]
我们不得不再多考虑一个缓冲的顺序，也即更大意义上的顺序
因为缓冲是有限的，所以得弄出一套全新的理论解决这个问题
A(s) » C ; C=[] -> C=[1]
A(b) » B ; B=[] -> B=[2]
C(s) » B ; [1] » [2]

交换完出现一个非常令人 excited 🐸 的情况，C 直接为空栈了，而此时最大的 3 也被暴露在 A 栈顶了，我们可以开始实际解决问题了

A » C ; C=[3]

再做一次交换，因为此时 B 依然是顺序的，我们套用之前的 routine

def naive-swap(dst, buf, src) = src(smaller) » buf; src(bigger) » dst; buf(smaller) » dst

这里，我们定义（其实本质上是对问题的归纳）了一个函数，称它为 naive-swap，它需要输入三个参数

dst：汉诺塔 LIFO
src：至少有两个元素的汉诺塔 LIFO
buf：一个不存在大小比较问题的汉诺塔

它产生副作用，将 src（如 [1,2]）以反向压入到 dst 中（如最后 dst=[2,1]）
它还有一个要求要点，就是 src 的栈顶元素必须比 buf 的栈顶元素小，不然不能进行移动
对于 dst 也一样，src 栈顶后的下一个元素（比如 2）必须比 dst 的栈顶元素（正例，比如 3）小，不然也不能进行移动
（这些约束都是为了符合汉诺塔的定义，当然本来就有这些约束不过我特别指明这些）

上面那个 A » C; A » B; C » B
where A=[1,2,3]
我们其实也可以注意到了，它其实就是 naive-swap(A,C,B)

naive-swap(A,C,B) where A=[1,2,3] B=[] C=[] 的结果就是 A=[3] B=[1,2] C=[]

之后在这个结果上，我通过枚举组合和猜测的方式（<del>费曼算法</del>）得出了解法 A(3) » C; B(1) » A; B(2) » C; A(1) » C

其实，它也可以被归纳为使用 naive-swap 的版本，利用子程序可以使我们更好的抽象问题：

A » C; naive-swap(B, A, C)

其实，我们注意到，naive-swap 就是这个递归问题的『最本质，最小规模的子问题』

A=[] 时，无需任何操作
A=[1] 时，简单的 A » C 即可
A=[1,2] 时，执行 naive-swap(A,B,C)
A=[1,2,3] 时，执行 naive-swap(A, C, B); A » C; naive-swap(B, A, C)

我们来猜测一下，A=[1,2,3,4] 时该怎么样？

A=[1,2,3] 时
naive-swap(A, C, B) 后
A=[3], B=[1,2], C=[]

然后我们把『暴露』在 A 栈顶的 max value 送到 C 中（A » C）
最后从 B[1,2] 移动到 C[3]（naive-swap(B, A, C)），问题解决

...我好歹还是猜了一下...

A=[1,2,3] 时，首先处理 A=[2,3]
naive-swap(A, C, B)
A=[3], B=[1,2], C=[]
然后 A=[1]，A » C
naive-swap(B, A, C)

A=[1,2,3,4] 的时候，首先处理 A=[2,3,4]：

naive-swap(A, B, C)
[3,4] [] [1,2]

A » B
[4] [3] [1,2]

naive-swap(C,B,A)
[4] [1,2,3] []

A » C
** [] [1,2,3] [4]

终于，在我的一番胡乱猜测之后，回到了基线问题
至于『为什么』，我懒得追究了，来看看递归思路吧。

naive-swap(A,B,C);A»B;naive-swap(C,B,A);A»C 之后，A=[1,2,3,4] 变成了 A=[] B=[1,2,3] C=[4]

我们成功的让 A=[1,2,3,4] 变成了 A=[1,2,3] ！！！这是个大突破。

怎么办呢？我们定义

def naive-swap(dst, buf, src) = src(smaller) » buf; src(bigger) » dst; buf(smaller) » dst

def a123(SubA, SubB, SubC) = naive-swap(SubA, SubC, SubB); SubA » SubC; naive-swap(SubB, SubA, SubC)

这里，我们所谓的 『A』 是 B，『B』是 A，『C』依然是 C

然后我们调用 a123(B, A, C) 即可完成交换

（这里留点时间大家自己推导一下 A=[1,2,3,4,5] 的情况）

综上所述 #Learn #Haskell #FP #Algorithm

汉诺塔问题，问题的定义在这里 我对问题的抽象在这里

尝试使用递归算法求得可行解

我之前通过一̶长̶串̶失̶败̶的̶尝̶试̶总结出了规律

def naive-swap(dst, buf, src) = src(smaller) » buf; src(bigger) » dst; buf(smaller) » dst

这是一个较小规模的子问题

可以得知
+ A=[] 时无需进行任何操作
+ A=[1] 时进行 A » C
+ A=[1,2] 时直接 naive-swap(A, B, C)
+ A=[1,2,3] 时

  naive-swap(A, C, B)

[3] [1,2] []

  A » C

[] [1,2] [3]

  naive-swap(B, A, C)

[] [] [1,2,3]
+ A=[1,2,3,4] 时

  naive-swap(A, B, C)

[3,4] [] [1,2]

  A » B

[4] [3] [1,2]

  naive-swap(C, A, B)

[4] [1,2,3] []

  A » C

[] [1,2,3] [4]

我们可以依此推导出 A=[1,2,3,4,5] 时的数据转移情况
... 算了，因为今天有点晚了

See Also:
+ 各种语言的算法实现

+ 某博客的教程

+ Haskell 图解，并且使用了 Haskell 可视化包

+ 一个延伸的汉诺塔问题

+ Wikipedia Hanoi
+ Wikipedia 递归

== Haskell 的副作用版解法

hanoni n (a, b, c)
| n == 1 = putStr (a ++ "->" ++ c) >> putStrLn ";"
| otherwise
= do
hanoni (n - 1) (a, c, b)
hanoni 1 (a, b, c)
hanoni (n - 1) (b, a, c)

main = hanoni 5 ("A", "B", "C")


解法的基本思想是递归。假设有 A、B、C 三个塔，A 塔有 N 块盘，目标是把这些盘全部移到 C 塔。那么先把 A 塔顶部的 N − 1 块盘移动到 B 塔，再把 A 塔剩下的大盘移到 C，最后把 B 塔的 N − 1 块盘移到 C

A=[1,2]
[2] [1] []
[] [1] [2]
[] [] [1,2]

A=[1,2,3]
... (naive-swap(A,C,B))
[3] [1,2] []
[] [1,2] [3]
... (naive-swap(B,A,C))
[] [] [1,2,3]

A=[1,2,3,4]
...
[4] [1,2,3] []
[] [1,2,3] [4]
[] [] [1,2,3,4]

A=[1,2,3,4,5]

[5] [1,2,3,4] []
[] [1,2,3,4] [5]
[] [] [1,2,3,4,5]

......

所以总结一下，我最后还是没有递归成（我好像完全没有在最后的总结里打算使用递归定义，而是在按步骤枚举死推

我总结出来的简直就是抄袭 rev (rev xs) \equiv{xs} 归纳证明... 而这个版本稍微正常一点，逻辑很好理解

或者说它看到的是宏观递归，我看到的只是 naive-swap （就是从一个柱子利用另外一个柱子作为交换用柱，倒序移动两个圆盘到其他柱子的子程序）的组合，我是自底向上归纳手动造的解题递推式总结思路，它是自顶向下的分析问题得出步骤和递归答案，而我那个版本很费时间，离真正总结出什么递归移动之类的还有点距离（而且到底的结局我觉得还是突然根据数据流悟出问题的递归解法）

#Reveng #CoolApk 改天我把酷安的密钥生成算法提出来直接重新拿 JavaScript 模拟一下再加个 JQuery 写个 coolapk.js 网页版客户端...

https://www.coolapk.com/feed/9683397
#个人广播 #秀

（如果能在寒假开始前完成，显然不能耽误别的事）

你们就不要说我没能力弄这些东西了，我当然不是幼稚到只会发广播的水平

本来想先讲一下上次那个汉诺塔（Hanoni）的问题的：

其实就是有一个要点，上面 Haskell 例程的 A B C 塔不一定非得是 A B C
上面维基里的描述，其实涉及到了递归

假设有 A、B、C 三个塔，A 塔有 N 块盘，目标是把这些盘全部移到 C 塔。那么先把 A 塔顶部的 N − 1 块盘移动到 B 塔，再把 A 塔剩下的大盘移到 C，最后把 B 塔的 N − 1 块盘移到 C

A B C 不一定非得是我们『最开始』的 A B C，它还可以是『临时』子程序里的 A B C
而我之前分析归纳出的 naive-swap 其实就是一个『length(A) = 2 时的这种变换子程序思路』

def naive-swap(src, buf, dst) = src(smaller) » buf; src(greater) » dst; buf(smaller) » dst

假设 A=[1,2]，naive-swap(A,B,C) 即为 A»B;A»C;B»C

问题解决过程中，所谓的 A 塔可以被归纳抽象为『源塔』，B 塔可以被认为是『变序塔』，C 塔则可以认为是『目标塔』

Haskell 代码对应的自然语言就是这么说：

子程序 Hanoni （剩余步数，元组：源塔、倒序塔、目标塔）
  如果 『只需要一步即可完成（源塔）到（目标塔）的移动』
    则打印 “$（源塔） -> $（目标塔）”
  否则，
    Hanoni（剩余步数 - 1，（源塔、目标塔、倒序塔））
    Hanoni（1，（源塔、倒序塔、目标塔））
    Hanoni（剩余步数 - 1，（倒序塔、源塔、目标塔））
 

比如我之前的例子 A=[1,2,3]
因为我讲得很清楚了，所以就只看递归调用中塔们的变化

Hanoni n (src, buf, dst)

Hanoni 3 (A, B, C)
= Hanoni 2 (A, C, B)
  (1)
> Hanoni 1 (A, B, C)
* A -> C
> Hanoni 2 (B, A, C)
  (2)

(1) = Hanoni 2 (src=A, buf=C, dst=B)
= Hanoni 1 (src=A, buf=C, dst=B)
* A -> B
> Hanoni 1 (A, B, C)
* A -> C
> Hanoni 1 (B, A, C)
* B -> C

(2) = Hanoni 2 (src=B, buf=A, dst=C)
= Hanoni 1 (src=B, buf=C, dst=A)
* B -> A
> Hanoni 1 (A, B, C)
* B -> C
> Hanoni 1 (A, B, C)
* A -> C    

递归最好理解的方式就是弄清楚子程序的定义：它到底做什么？

如果你已经搞清楚了子程序的定义，诸如 reverse，每一步都把 reverse xs ++ [x]
那就不难分析了，需要递归的时候直接利用它的定义『reverse 一个 length >1 列表的顺序』即可


这里最重要的就是 Hanoni 本身的定义：它接受『源塔、倒序塔、目标塔』的名字，还有『我还要移动多少次』也即『要移动多少个盘子』（剩余步数）这个额外信息

Hanoni n (A, B, C) 执行的操作说到底是『从 A 上移动 n 个盘子到 C 上，利用 B 交换一下顺序』
在编写此子程序时，你只需要考虑到上面这个定义，然后是基线条件『n = 1 时只需要一步即可完成移动』，不难解决此问题，不过这里的确是有个额外的逆序限制，可以按照我昨天写了一晚上的做法推导出来递归时每一步的操作

之前可行的那个交换方法推广一下，使用这个抽象一弄就完成了（它只是加了一个 n 作为剩余步数计数，基线条件）

现在干脆临时从使用者的角度和大致的算法环境检查上分析一下 liba.so 算了

#sysadmin #life duangsuse 回来了！这次我更新了 Fedora 到 F29(Twenty Nine)

#yearPassed 新年新系统 release version！（Fedora 28 :> Fedora 29）

说个好笑的，Dnf（Dandified Yum，Fedora 28 的软件包管理器）离线更新的时候那个下载日志还是什么居然积累到了 18G，把我的 SSD 塞炸了... hhhhh #Haha

有能力又怎么样，没时间晚上手又冻住了不能动（ #Haha #dev #Coolapk #reveng

#archive #life #consumer 我买了一个 499 的 Wacom 数位板（指 18 年淘宝上最火的那个）（别喷我用淘宝，我爸的）

顺便又买了新墨盒... 又可以打印新 papper 们看了（指 HP 810（好吧，反正就是适配 HP DeskJet 1112 系列的

#School 这周马上就要放寒假了（还有一个月） 🤔

duangsuse 的安排嘛... 其他的都好了，本来每周就是讲东西为主，然后本周买了别的东西，画了几张画，最后书什么的基本没看。嗯嗯。

这周就是讲点东西，发点照片，没了。

顺便说一下，推荐有打印机又看过书的大家可以没事带几张 papper （比如之前那个代数程序逻辑的 fold.pdf，我在 USTC 中科大学生的分享里淘到的，当然论文基本都是公开的你们可以随便找个大学比如 Illinois 的 CS 系看...）到例如公交车的地方看看，因为我觉得吧，公交车之类的地方可能思维都比较开放一些，学习起来比较有效果，可惜就是很慢就是了

至于我上面提到的 papper A tutorial on the universality and expressiveness of fold 可以在 这里（Nottingham in UK 大学）下载 #papper #FP #CS
个人觉得... 虽然有些不常见的词，但是有一定函数式编程和程序分析变换、形式化证明基础的人虽然可能看很久但收获不错。

见好就收。