Lua 学习 chapter2

目录

  1. Eeight Queen
  2. 判断是否可以放置
  3. 递归放置
  4. 只打印第一个值
  5. 排列的方式
  6. 对比

Eight Queen

8皇后问题: 在一个8*8的棋盘上放置八个皇后,她们之间相互不能影响。 通过一个表来存储,键值表示行,值表示列。

判断是否可以放置

因为键值已经保证不会再同一行,所以我们需要判断的就只有列和斜方向的。 在斜方向,左斜和右斜。右斜列减行相同则同处一斜行。左斜行列相加则处于同斜行。

1
2
3
4
5
6
7
8
9
10
local function checkAttack(table, n, c)
    for i = 1, n - 1 do
        if (table[i] == c) or
                (table[i] - i == c - n) or --行列式
                (table[i] + i == c + n) then
            return false
        end
    end
    return true
end

—|—
`

递归放置

通过判断是否每一行都放置了棋子来决定是否打印这个棋谱。 在addQueen中,每一个节点都会一直的递归,所有的节点递归结束。 当然在中间不满足条件的后面的节点就不会递归了。

1
2
3
4
5
6
7
8
9
10
11
12
local function addQueen(table, n)
    if n > N then
        printTable(table)
    else
        for c = 1, N do
            if checkAttack(table, n, c) then
                table[n] = c
                addQueen(table, n + 1)
            end
        end
    end
end

—|—
`

只打印第一个值

在addQueen前面加一个判断,如果打印了一个可行解就不再进行冗余递归了。

排列的方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
---@param t table|number
local function deepCopy(t)
    local result = {}
    if type(t) == "number" then
        table.insert(t, 1, t)
    else
        for i, v in ipairs(t) do
            result[i] = t[i]
        end
    end
    return result
end

---@param table table
---@param n number
---return table
local function insertNumber(t, n)
    local result = {}
    for i = 1, #t + 1 do
        result[i] = deepCopy(t)
        table.insert(result[i], i, n)
    end
    return result
end

---@param t1 table
---@param t2 table
---@return table
local function mergeTable(t1, t2)
    local length = #t1
    for i = 1, #t2 do
        table.insert(t1, length + i, t2[i])
    end
end

---@param table table
---@param n number
---@return table
local function arrangement(t, n)
    local temp = {}
    for i = 1, #t do
        local tt = insertNumber(t[i], n)
        mergeTable(temp, tt)
    end
    return temp
end

local function getArrangement()
    local table = { { 1, 2 }, { 2, 1 } }
    for i = 3, N do
        table = arrangement(table, i)
    end
    return table
end

local tr = getArrangement()
for i, v in ipairs(tr) do
    local flag = true
    for j, k in ipairs(v) do
        if not checkAttack(v, j, k) then
            flag = false
            break
        end
    end
    if flag then
        printTable(v)
    end
end

print("Total number:", #tr)
print("Total answer2:" .. totalResult)
print("Method2 time:", os.clock() - t1)

—|—
`

对比

方法2:排列花费1.604秒,检测花费将近1.1秒,这说明排列还是浪费了很多时间在检测和排列上面的。


糖果

糖果
LUA教程

Lapis框架的常用处理方法

Lapis框架的常用处理方法 Continue reading

MoonScript实现选择排序

Published on February 26, 2017

MoonScript与Redis客户端

Published on January 19, 2017