如何停止在Lua中不停地调用函数

2019-7-16 3:46:14

收藏：0

阅读：90

评论：1

我正在忙着阅读《Lua程序设计第4版》书中的第二章，我正在困扰。该程序在实质上打印了一个有8个皇后的国际象棋棋盘，这些皇后被放置在这样一种方式中，即它们中的任何一个都不能攻击其他皇后。但我正在努力找出为什么它会多次打印棋盘。

我一步一步地审查了代码，一旦打印的解决方案完成了第一个棋盘的打印，我认为它只会结束函数，然后跳回到主程序，但出于某种原因它仍然循环。我也是Lua的新手，刚从C转过来，仍在适应其中的一切。

它输出的一个棋盘的图像。X是皇后-https://ibb.co/KsT3R8X

N = 8 -- 棋盘大小

-- 检查位置(n,c)是否没有受到攻击
function isplaceok (a, n, c)
    for i = 1, n - 1 do -- 对于已经放置的每个皇后
        if (a[i] == c) or --同一列?
        (a[i] - i == c - n) or --同一斜向？
        (a[i] + i == c + n) then --同一斜向？
            return false -- 位置可能受到攻击
        end
    end
    return true --没有攻击；位置很好
end

-- 打印检查器
function printsolution (a)
    for i = 1, N do -- 对于每一行
        for j = 1, N do --和每一列
            --写"X"或"-"加上一个空格
            io.write(a[i] == j and "X" or "-", " ")
        end
        io.write("\n")
    end
    io.write("\n")
end

-- 在板上添加从'n'到'N'的所有皇后
function addqueen (a, n)
    if n > N then --所有皇后都已放置？
        printsolution(a)
    else --尝试放置第n个皇后
        for c = 1, N do
            if isplaceok(a, n, c) then
                a[n] = c --在第c列放置第n个皇后
                addqueen(a, n + 1)
            end
        end
    end
end

-- 运行程序
addqueen({}, 1)

用户7396148

程序正在打印8x8国际象棋棋盘所有92种可能的解决方案，这很可能是预期的，因此它似乎正常工作。

要在找到一个解决方案后停止，可以向程序添加一个变量“found”：

local found = false

-- print a board
function printsolution (a)
    for i = 1, N do -- for each row
        for j = 1, N do -- and for each column
            -- write "X" or "-" plus a space
            io.write(a[i] == j and "X" or "-", " ")
        end
        io.write("\n")
    end
    io.write("\n")
    found = true
end

-- add to board 'a' all queens from 'n' to 'N'
function addqueen (a, n)
    if n > N then -- all queens have been placed?
        printsolution(a)
    else -- try to place n-th queen
        for c = 1, N do
            if isplaceok(a, n, c) and found == false then
                a[n] = c -- place n-th queen at column 'c'
                addqueen(a, n + 1)
            end
        end
    end
end

这个“found”变量会随着我们返回到原来的堆栈，停止现有循环的继续递归。

现在为什么这个代码会以这种方式工作，所有的解决方案从哪里来的呢？

这与addqueen中的for循环有关：

    for c = 1, N do
        if isplaceok(a, n, c) then
            a[n] = c
            addqueen(a, n + 1)
        end
    end

每次循环将代码递归调用addqueen更深入地进入。栈永远不会超过9，因为这是N设置的限制。在114次调用addqueen后，第一个解决方案是这样的：

X - - - - - - -
- - - - X - - -
- - - - - - - X
- - - - - X - -
- - X - - - - -
- - - - - - X -
- X - - - - - -
- - - X - - - -

第5个解是我们第一次回到原来的addqueen调用，你可以看到第一个X已经从1x1移动到1x2（n=1 c=2，我们原始的for循环的第二步）：

- X - - - - - -
- - - X - - - -
- - - - - X - -
- - - - - - - X
- - X - - - - -
X - - - - - - -
- - - - - - X -
- - - - X - - -

最终，我们调用addqueen 1952次以检查所有可能的解决方案。

你可以调整代码以打印深度的值，以更好地了解程序运行时堆栈的情况：

-- add to board 'a' all queens from 'n' to 'N'
function addqueen (a, n)
    print(n .. "â†“")
    if n > N then -- all queens have been placed?
        printsolution(a)
    else -- try to place n-th queen
        for c = 1, N do
            if isplaceok(a, n, c) then
                a[n] = c -- place n-th queen at column 'c'
                addqueen(a, n + 1)
            end
        end
    end
    print(n - 1 .. "â†‘")
end

2019-07-16 04:11:51

评论区的留言会收到邮件通知哦~

作者:

用户11518995

如何停止在Lua中不停地调用函数

社区规范

发文指南

社区文章

开源项目 & 应用

🎮 游戏开发

World of Warcraft

Roblox

Defold

LÖVE 2D

🌐 高性能网络与 Web 服务

OpenResty

Kong

Redis

Nmap

LuaJIT

Wapiti

Wireshark

⚙️ 嵌入式系统与应用工具

LuatOS

TeX Live

Awesome WM

Vim/Neovim

FFmpeg

🧠 人工智能与科学计算

Torch

SciLua