北京大学Julia语言入门讲义第23章: Julia编程示例–递归趣例

23.1 汉诺塔问题

设有三根柱子A, B, C,
有大小依次为1,2,…,𝑛𝑛个空心圆盘,
在A柱子上依次从低向上穿了𝑛,𝑛−1,…,1大小的圆盘。
任务是要把这𝑛个圆盘移动到C柱子上,
仍按照从低向上越来越小的次序。
移动的要求为:

  • 每次仅移动一个圆盘到另一个柱子上;
  • 每次的移动,都不能使得增加一个圆盘的柱子上的大圆盘压在小圆盘上。

这个问题是典型的递归问题:

  • 如果仅有一个圆盘(𝑛=1),
    就直接将A柱子的圆盘放到C柱子,问题解决;
  • 如果有𝑛>1个圆盘,分为三个步骤:
    • 将A柱子上面的𝑛−1个圆盘以C柱为缓存转移到B柱子;
    • 将A柱子最下面的𝑛号圆盘转移到C柱子;
    • 将B柱子的𝑛−1个圆盘以A柱子为缓存转移到C柱子,问题解决。

其中,在将B柱子的𝑛−1个圆盘转移到𝐶时,
会将最上面的𝑛−2个先转移到A柱子,
所以递归过程中三个柱子的地位是可以互相改变的。

用三个数组表示A, B, C三个柱子,
数组第一个元素记录柱子编号,
数组第二个元素表示放在最下面的圆盘编号(1号最小,𝑛号最大),
后续元素依次表示上面的圆盘。

function demo_hanoi(n=3)
    # 用第一个元素保存柱子编号,
    # 后续元素保存圆盘大小
    a = [1; collect(n:-1:1)]
    b = Int[2]
    c = Int[3]
    labels = ("A", "B", "C")

    function solve!(a, b, c, n)
        if n == 1
            plate = pop!(a)
            push!(c, plate)
            println("$(plate): $(labels[a[1]]) ==> $(labels[c[1]])")
        else 
            # 将A柱上面的n-1个通过C移动到B
            solve!(a, c, b, n-1)
            # 将A柱最下面的n号圆盘移动到C
            plate = pop!(a)
            push!(c, plate)
            println("$(plate): $(labels[a[1]]) ==> $(labels[c[1]])")
            # 将B柱上面的n-1个通过A移动到C
            solve!(b, a, c, n-1)
        end 
    end 

    solve!(a, b, c, n)
end 

demo_hanoi()

结果如:

1: A ==> C
2: A ==> B
1: C ==> B
3: A ==> C
1: B ==> A
2: B ==> C
1: A ==> C

23.2 高斯八皇后问题

国际象棋的棋盘是 8×8 的格子。
国际象棋手马克斯·贝瑟尔于 1848 年提出如下问题:
在 8×8 格的国际象棋上摆放八个皇后,
使其不能互相攻击,
即任意两个皇后都不能处于同一行、同一列或同一斜线上,
问有多少种摆法。
高斯认为有 76 种方案。
1854 年在柏林的象棋杂志上不同的作者发表了 40 种不同的解,
后来有人用图论的方法解出 92 种结果。

23.2.1 穷举法

要用编程的方法解决,
首先想到的是,
每个皇后有64个位置可选,
穷举可以考虑648≈2.8×1014种组合,
即百万亿级别的组合,
计算量太大。

实际上,
对于每一种可行的摆法,
因为每一行有且仅有一个皇后,
穷举时所以只需要考虑每一行的皇后在那一列,
88=16,777,216种组合,
即约一千万种组合。
这个组合数目虽然很大,
但对于现代计算机来说可以很快地完成穷举。

这里记录一个Python编程实现。
将一种可能的摆法存入一个长度为8的列表,
每个元素代表对应的行的皇后位置。
虽然可以写一个8重循环,
但是这样的程序过于繁琐。
所以,
采用八进制的想法,
[0,0,0,0,0,0,0,0]出发,
每次给个位加1,
遇到8就向下一位进1,
直到循环88次。
写一个函数判断新的一个位置是否合法。

import time

## 检查一种摆法是否合法
## x是长度为8的列表,代表从低位到高位的8进制数字,
## 用每个数字代表一行的棋子所在的列。
def is_solution(x):
    for i in range(7):
        for j in range(i+1, 8):
            di = x[j] - x[i]
            if di==0 or di==j-i or di==i-j :
                return False
    return True
            
## 穷举进入下一个摆法
def next_board(x):
    x[0] += 1
    for i in range(7):
        if(x[i]==8):
            x[i+1] += 1
            x[i] = 0
    return x
            
def queens_exaust():
    board = [0]*8
    nmax = 8**8
    ## boards用来存放所有的摆法,
    ## 每种摆法表示为8个元素的列表
    boards = []
    nb = 0
    for i in range(nmax):
        if is_solution(board):
            print(str(nb) + ',' + ','.join(map(str, board)))
            boards.append(board.copy())
            nb += 1
        
        board = next_board(board)
    return boards


time_start=time.time()
res1 = queens_exaust()
time_end=time.time()
print('穷举法用时', time_end-time_start)
print('解的个数:', len(res1))

用时50秒,得到了92个解。

下面是Julia版本的程序:

## 检查一种摆法是否合法
## x是长度为8的数组,第i个元素是第i行的棋子所在的列序号
function is_solution(x)
    for i in 1:7
        for j in (i+1):8
            di = x[j] - x[i]
            if di==0 || di==j-i || di==i-j
                return false
            end
        end
    end
    return true
end

## 穷举进入下一个摆法
## 把长度为8的数组x看成是有8位数的8进制数,但数字都加1,
## 次序是从低位到高位
function next_board(x)
    x[1] += 1
    for i in 1:7
        if x[i]==9
            ## 进位
            x[i+1] += 1
            x[i] = 1
        end
    end

    return x
end

function queens_exaust()
    board = ones(Int8, 8)
    nmax = 8^8
    nbmax = 1000
    nb = 0
    boards = zeros(Int8, nbmax, 8)
    for i in 1:nmax
        if is_solution(board)
            nb += 1
            println(board)
            boards[nb,:] = board
        end

        board = next_board(board)
    end
    boards = boards[1:nb,:]
    return boards
end
@time queens_exaust()

用时0.93秒,得到92个解。

23.2.2 递归算法

穷举法完全不考虑已经摆放的棋子,
所以另一种更好的做法是使用递归算法,
先在第一行摆下一颗棋子,
这有8种摆法;
然后,在第二行试图摆下第二颗棋子,
使得与第一颗棋子不冲突;
再考虑第三颗棋子,
如此一直到第八颗棋子。
这个过程中如果某颗棋子无法摆放,
就退回到上一颗棋子的下一个位置;
找到一种摆法后,
也考虑最后一颗棋子的下一个位置。

下面是从百度百科网站复制的Python版本的递归算法程序。

## 用长度为8的列表A表示一种摆法,
## 用cur表示当前要摆放的棋子序号,0 <= cur < 8
def queens(A, cur=0):
    if cur == len(A):
        ## 如果当前棋子序号为8,表示找到了一种摆法
        print(','.join(map(str, A)))
        boards.append(A.copy())
        return 0
    ## 对每颗棋子col遍历
    for col in range(len(A)):
        ## 将当前棋子cur摆放在col列,
        A[cur] = col
        ## 设置摆放是否合法的初值为真
        flag = True
        ## 判断cur号棋子摆放在col列,是否与0到cur-1号棋子有冲突
        ## row是用来遍历0到cur-1号棋子的变量
        for row in range(cur):
            ## 以下判断摆放在第cur行、第col列的棋子,
            ## 是否与第row行、A[row]列的棋子冲突
            if A[row] == col or abs(col - A[row]) == cur - row:
                flag = False
                break
        ## 如果摆放第cur号棋子在第col列成功,
        ## 就考虑下一颗棋子(递归调用);
        ## 如果摆放不成功,就摆放到col的下一列继续判断
        ## 这样会遍历每颗棋子与前面棋子的不冲突的位置
        if flag:
            queens(A, cur+1)

boards = []
queens([None]*8)

也是92个结果,用时仅30毫秒。

下面是Julia版本的程序:

## 递归算法
## 用长度为8的数组A表示一种摆法,
## 用cur表示当前要摆放的棋子序号,1 <= cur <= 8
function queens()
    nbmax = 1000
    nb = 0
    boards = zeros(Int8, nbmax, 8)

    function queens_rec(A, cur=1)
        if cur == 9
            ## 如果当前棋子序号为9,表示找到了一种摆法
            nb += 1
            boards[nb,:] = A
            ##println(join(string.(A), ","))
            return
        end # if cur

        ## 对当前要摆放的棋子遍历所有列位置试摆放
        for col in 1:8
            ## 将当前棋子cur摆放在col列,
            A[cur] = col
            ## 设置摆放是否合法的初值为真
            flag = true
            ## 判断cur号棋子摆放在col列,是否与1到cur-1号棋子有冲突
            ## row是1到cur-1号棋子的变量
            for row in 1:(cur-1)
                ## 以下判断摆放在第cur行、第col列的棋子,
                ## 是否与第row行、A[row]列的棋子冲突
                if A[row] == col || abs(col - A[row]) == cur - row
                    flag = false
                    break
                end
            end # for row

            ## 如果摆放第cur号棋子在第col列成功,
            ## 就考虑下一颗棋子(递归调用);
            ## 如果摆放不成功,就摆放到col的下一列继续判断
            ## 这样会遍历每颗棋子与前面棋子的不冲突的位置
            if flag
                queens_rec(A, cur+1)
            end
        end # for col
    end # function queens_rec

    queens_rec(zeros(Int8, 8), 1)
    boards = boards[1:nb,:]
    println("找到解的个数:", nb)

    return boards
end # function queens
@time queens()

找到92个解,用时0.1秒。

23.2.3 找到变换等价的摆法

还可以继续考虑这些解法中哪些是不能通过左右反射、上下反射,
旋转90、180、270度、沿主对角线反转、沿反对角线反转得到的,
按如果能通过变换得到就分为一组。
可以验证,这些变换构成一个变换群,
从而可以用来定义等价类,
可以通过变换变成相同的解法为同一类。
找到12个类。

import DataFrames: DataFrame
import CSV

function board_equals(x, y)
    ## 棋盘的8元素存储到8x8的0-1矩阵存储
    bs = length(x)
    function board_to_mat(z)
        mat = zeros(Int,bs,bs)
        for i in 1:bs
            mat[i,z[i]] = 1
        end # for i
        return mat
    end # board_to_mat

    xm = board_to_mat(x)
    ym = board_to_mat(y)

    # 左右反射
    function reflect_lr(z)
        return z[:, end:-1:begin]
    end # reflect_lr

    # 上下反射
    function reflect_ud(z)
        return z[end:-1:begin, :]
    end # reflect_ud

    function idtran(z)
        return z
    end
    
    # 逆时针旋转90度, rotl90
    # 旋转180度, rot180
    # 顺时针旋转90度,rotr90
    # 转置:transpose
    # 沿反对角线反转:reflect_lr ∘ rotl90

    funcs = [reflect_lr, reflect_ud, 
        rotl90, rotr90, rot180,
        transpose, reflect_lr ∘ rotl90]

    for i in 1:length(funcs)
        f = funcs[i]
        ynew = f(ym)
        if all(ynew .== xm)
            return true
        end # if
    end # for f

    return false
end # board_equals

## 标记通过变换可以得到的摆法
function group_boards(boards)
    b = copy(boards)
    nb = size(b, 1)    # 摆法个数
    g = zeros(Int, nb) # 分组编码,每种摆法一个值
    ng = 1   # 分组编码初值
    g[1] = 1 # 第一中摆法分组为1 

    for j in 2:nb # 对从第二种摆法开始的每一种摆法
        newgroup = true
        for i in 1:(j-1) 
            ## 判断第j种摆法是否与前面的第i种摆法可转换,
            ## 如果可转换,将第j摆法标记为第i中摆法的分组编码
            if board_equals(b[i,:], b[j,:])
                g[j] = g[i]
                newgroup = false
                break
            end # if
        end # for i
        if newgroup
            ng += 1
            g[j] = ng
        end # if
    end # for j

    ## 保存为csv
    println("找到分组个数:", ng)
    grouped = [1:nb boards g]
    qn = ["solution"; "Q" .* string.(1:8); "group"]
    df = DataFrame(grouped, Symbol.(qn))
    sort!(df, :group)
    df[:, :solution] = 1:nb
    CSV.write("queens_group_julia.csv", df)
    
    return grouped
end # group_boards

boards = queens()
grouped = group_boards(boards);

结果的CSV文件:

solution,Q1,Q2,Q3,Q4,Q5,Q6,Q7,Q8,group
1,1,5,8,6,3,7,2,4,1
2,1,7,5,8,2,4,6,3,1
3,3,6,4,2,8,5,7,1,1
4,4,2,7,3,6,8,5,1,1
5,5,7,2,6,3,1,4,8,1
6,6,3,5,7,1,4,2,8,1
7,8,2,4,1,7,5,3,6,1
8,8,4,1,3,6,2,7,5,1
9,1,6,8,3,7,4,2,5,2
10,1,7,4,6,8,2,5,3,2
11,3,5,2,8,6,4,7,1,2
12,4,7,5,2,6,1,3,8,2
13,5,2,4,7,3,8,6,1,2
14,6,4,7,1,3,5,2,8,2
15,8,2,5,3,1,7,4,6,2
16,8,3,1,6,2,5,7,4,2
17,2,4,6,8,3,1,7,5,3
18,3,8,4,7,1,6,2,5,3
19,4,2,8,6,1,3,5,7,3
20,4,7,3,8,2,5,1,6,3
21,5,2,6,1,7,4,8,3,3
22,5,7,1,3,8,6,4,2,3
23,6,1,5,2,8,3,7,4,3
24,7,5,3,1,6,8,2,4,3
25,2,5,7,1,3,8,6,4,4
26,3,6,2,7,1,4,8,5,4
27,4,1,5,8,2,7,3,6,4
28,4,6,8,3,1,7,5,2,4
29,5,3,1,6,8,2,4,7,4
30,5,8,4,1,7,2,6,3,4
31,6,3,7,2,8,5,1,4,4
32,7,4,2,8,6,1,3,5,4
33,2,5,7,4,1,8,6,3,5
34,3,6,2,7,5,1,8,4,5
35,3,6,8,1,4,7,5,2,5
36,4,8,1,5,7,2,6,3,5
37,5,1,8,4,2,7,3,6,5
38,6,3,1,8,5,2,4,7,5
39,6,3,7,2,4,8,1,5,5
40,7,4,2,5,8,1,3,6,5
41,2,6,1,7,4,8,3,5,6
42,3,1,7,5,8,2,4,6,6
43,3,5,7,1,4,2,8,6,6
44,4,6,1,5,2,8,3,7,6
45,5,3,8,4,7,1,6,2,6
46,6,4,2,8,5,7,1,3,6
47,6,8,2,4,1,7,5,3,6
48,7,3,8,2,5,1,6,4,6
49,2,6,8,3,1,4,7,5,7
50,3,7,2,8,6,4,1,5,7
51,4,2,5,8,6,1,3,7,7
52,4,8,5,3,1,7,2,6,7
53,5,1,4,6,8,2,7,3,7
54,5,7,4,1,3,8,6,2,7
55,6,2,7,1,3,5,8,4,7
56,7,3,1,6,8,5,2,4,7
57,2,7,3,6,8,5,1,4,8
58,2,8,6,1,3,5,7,4,8
59,4,1,5,8,6,3,7,2,8
60,4,7,5,3,1,6,8,2,8
61,5,2,4,6,8,3,1,7,8
62,5,8,4,1,3,6,2,7,8
63,7,1,3,8,6,4,2,5,8
64,7,2,6,3,1,4,8,5,8
65,2,7,5,8,1,4,6,3,9
66,3,6,4,1,8,5,7,2,9
67,4,2,7,3,6,8,1,5,9
68,4,8,1,3,6,2,7,5,9
69,5,1,8,6,3,7,2,4,9
70,5,7,2,6,3,1,8,4,9
71,6,3,5,8,1,4,2,7,9
72,7,2,4,1,8,5,3,6,9
73,3,5,2,8,1,7,4,6,10
74,4,6,8,2,7,1,3,5,10
75,5,3,1,7,2,8,6,4,10
76,6,4,7,1,8,2,5,3,10
77,3,5,8,4,1,7,2,6,11
78,3,6,8,2,4,1,7,5,11
79,3,7,2,8,5,1,4,6,11
80,4,2,8,5,7,1,3,6,11
81,5,7,1,4,2,8,6,3,11
82,6,2,7,1,4,8,5,3,11
83,6,3,1,7,5,8,2,4,11
84,6,4,1,5,8,2,7,3,11
85,3,6,2,5,8,1,7,4,12
86,3,6,8,1,5,7,2,4,12
87,4,2,7,5,1,8,6,3,12
88,4,7,1,8,5,2,6,3,12
89,5,2,8,1,4,7,3,6,12
90,5,7,2,4,8,1,3,6,12
91,6,3,1,8,4,2,7,5,12
92,6,3,7,4,1,8,2,5,12

韭菜热线原创版权所有,发布者:风生水起,转载请注明出处:https://www.9crx.com/75993.html

(0)
打赏
风生水起的头像风生水起普通用户
上一篇 2023年9月4日 23:36
下一篇 2023年9月5日 23:43

相关推荐

  • 提前储蓄退休的好处

    无论您年龄多大,开始为退休储蓄永远不会太早。我很清楚地知道,当你停止工作时,担心你的财务状况在此时似乎不是首要任务。毕竟,您可能还需要几十年才能退休,而且您可能还有学生贷款或其他债务需要偿还。然而,尽管这并不总是那么容易,但现在严格遵守储蓄将使您能够在以后获得经济回报。 以下是五个令人信服的理由,说明为什么提前为退休储蓄是确保您的黄金岁月有利可图且无压力的最…

    2023年8月21日
    13600
  • 始终像企业主一样思考

    我们从未停止学习,我们始终努力改进我们的投资方法,并从我们和他人的错误中吸取教训。然而,在我们终生追求成为更好的投资者的过程中,我们严格遵守一条重要规则:始终像企业主一样思考。 在投资中,短期思考的诱惑可能是巨大的: “那只股票一直在上涨,也许我们应该买一些?” “那只股票表现这么好,也许我们应该卖掉它并获利?” “那只股票一直是狗!我们把它卖掉吧。你总是可…

    2023年11月11日
    9400
  • 北京大学R语言教程(李东风)第36章:R方差分析

    36.1 单因素方差分析 单因素方差分析可以看成基础统计中两样本t检验的一个推广, 要比较试验观测值的某个因变量(称为“指标”)按照一个分组变量(称为“因素”)分组后, 各组的因变量均值有无显著差异。 设因素A将所有观测分为m个组, 每组对因变量进行r次观测, 且各次观测相互独立, 模型为 yij=eijμi+eij,i=1,2,…,m,&nbsp…

    2023年11月25日
    6200
  • 晨星表示,锂业的最佳机会来了

    锂业的最佳机会 晨星公司表示,最近的抛售使得锂股极具吸引力,两家公司在这方面处于领先地位。 锂 似乎现有的所有可充电电子设备。全球范围内电动汽车的发展。可再生能源依靠大量电池来储存电力。如果遇到危险!将这三种金属捆绑在一起的答案以“都有这种银白色金属的共同点”结尾,很少有观众在家里会脱口而出这个简单的 200 美元问题:什么是锂? 在过去的二十年里,用这种元…

    2023年8月4日
    8800
  • 投资新兴世界秩序第3部分

    作者: Inbok Song、Sherwood Zhang、 Vivek Tanneer 在我们全球供应链系列的最后一部分中,投资组合经理 Inbok Song 和 Sherwood 张 着眼于正在重新配置其网络的公司,投资组合经理 Vivek Tanneeru 给出了他对投资机会的评估。 要点 在高价值和低价值市场中,出于不同的原因,公司正在以多种方式彻底…

    2023年9月13日
    8500

发表回复

登录后才能评论
客服
客服
关注订阅号
关注订阅号
分享本页
返回顶部