个人中心
gpt4 book ai didi

javascript - 如何通过回溯递归地修改数组元素？

转载 作者：塔克拉玛干 更新时间：2023-11-02 21:13:13 26 4
gpt4 key购买 nike

我写了一种 N-Queens 算法，只处理垂直和水平威胁检测。因此，它更像是一个 N-Towers 解决方案查找器。

为此，我使用了递归。这是一个众所周知的算法。对于棋盘的每个方格，我都放置了一个塔。对于每个放置的塔，我尝试放置另一个塔(这是递归调用)。如果没有剩余的塔可以放置，则意味着程序已找到解决方案并且递归级别必须返回。如果所有棋盘都已与剩余的塔交叉放置，则表示程序未找到解决方案，递归级别必须返回。

我的递归函数有两个参数:必须放置的塔的数量和棋盘(字符串数组的数组；字符串等于“T”表示塔已放置在此棋盘的正方形中，“- "表示方 block 是空的)。

问题

我的算法似乎找到所有解决方案并将它们显示为棋盘，使用“-”(如果运行良好，则使用“T”)符号。上面解释了这种表示法。

然而，即使解决方案的数量看起来是正确的，显示的解决方案/棋盘也只包含“-”。

我想我没有在我的递归调用中正确传递我的数组数组(即:棋盘)。

这个问题的说明

2个塔，一个2*2方格的棋盘，有两种解法，很正常。但是只有“-”，没有出现“T”……就是这个问题。确实:

--

--

代码:关注我的递归函数

    /**
     * RECURSIVE FUNCTION. If there are still towers to place, this function tries to place them. If not, it means a
     * solution has been found : it's stored in an array (external to this function).
     * If this function can't place a tower, nothing happens.
     * Else, it places it and makes the recursive call.
     * Each recursion level does this for each next (to the placed tower) chessboard's squares.
     * @param number_of_left_towers how many remaining towers to place there are (if 0, it means a solution has been
     * found)
     * @param array_array_chessboard the chessboard
     * @returns {Number} the return is not important
     */
    function placeTower(number_of_left_towers, array_array_chessboard) {
        if (number_of_left_towers == 0) {
            return solutions.push(array_array_chessboard);
        }

        for (var current_x = 0; current_x < number_of_lines; current_x++) {
            for (var current_y = 0; current_y < number_of_columns; current_y++) {
                if (array_array_chessboard[current_x][current_y] == "-" && canBePlaced(array_array_chessboard, current_x, current_y)) {
                    array_array_chessboard[current_x][current_y] = "T";
                    placeTower(number_of_left_towers - 1, array_array_chessboard);
                    array_array_chessboard[current_x][current_y] = "-";
                }
            }
        }
    }

代码:带有所有源代码的 JSFiddle

https://jsfiddle.net/btcj6uzp/

您还可以在下面找到相同的代码:

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Recursive algorithm of the N-Towers</title>
</head>
<body>

<script type="text/javascript">
    /**
     * Finds all the solutions to the N-Towers algorithm.
     *
     * @param number_of_towers number of towers to try to place in the chessboard
     * @param number_of_lines chessboard's ones
     * @param number_of_columns chessboard's ones
     * @returns {nTowersSolutions} array containing all the solutions
     */
    function nTowersSolutions(number_of_towers, number_of_lines, number_of_columns) {
        /*
        NB
        "T" = "Tower" = presence of a tower in this square of the chessboard
        "-" = "nothing" = no tower in this square of the chessboard
        (used for both solutions displaying and finding)
         */

        var solutions = [];
        var array_array_chessboard = []; // Represents the chessboard
        for(var i = 0; i < number_of_lines; i++) {
            array_array_chessboard[i] =  new Array(number_of_columns);
            for(var j = 0; j < number_of_columns; j++) {
                array_array_chessboard[i][j] = "-"; // We initialize the chessboard with "-"
            }
        }

        /**
         * Uses HTML to display the found solutions, in the Web page
         */
        this.displaySolutions = function() {
            var body = document.body;
            solutions.forEach((array_array_chessboard) => {
                array_array_chessboard.forEach(function(array_chessboard) {
                    array_chessboard.forEach((square) => {
                        body.innerHTML += square; // New cell
                    });
                    body.innerHTML += "<br />"; // New line
                });
                body.innerHTML += "<br /><br />"; // New solution
            });
        };

        /**
         * RECURSIVE FUNCTION. If there are still towers to place, this function tries to place them. If not, it means a
         * solution has been found : it's stored in an array (external to this function).
         * If this function can't place a tower, nothing happens.
         * Else, it places it and makes the recursive call.
         * Each recursion level does this for each next (to the placed tower) chessboard's squares.
         * @param number_of_left_towers how many remaining towers to place there are (if 0, it means a solution has been
         * found)
         * @param array_array_chessboard the chessboard
         * @returns {Number} the return is not important
         */
        function placeTower(number_of_left_towers, array_array_chessboard) {
            if (number_of_left_towers == 0) {
                return solutions.push(array_array_chessboard);
            }

            for (var current_x = 0; current_x < number_of_lines; current_x++) {
                for (var current_y = 0; current_y < number_of_columns; current_y++) {
                    if (array_array_chessboard[current_x][current_y] == "-" && canBePlaced(array_array_chessboard, current_x, current_y)) {
                        array_array_chessboard[current_x][current_y] = "T";
                        placeTower(number_of_left_towers - 1, array_array_chessboard);
                        array_array_chessboard[current_x][current_y] = "-";
                    }
                }
            }
        }

        /**
         * Can this tower be placed ?
         * @param array_array_chessboard
         * @param new_x
         * @param new_y
         * @returns {boolean}
         */
        function canBePlaced(array_array_chessboard, new_x, new_y) {
            for(var i = 0; i < array_array_chessboard.length; i++) {
                for(var z = 0; z < array_array_chessboard[i].length; z++) {
                    if(array_array_chessboard[i][z] == "T"
                            && (
                                    new_x == z || new_y == i // Horizontal and vertical checks
                            )
                    ) {
                        return false;
                    }
                }
            }
            return true;
        }

        placeTower(number_of_towers, array_array_chessboard);
        return this;
    }

    // <!-- CHANGE THESE PARAMETERS' VALUE TO TEST -->
    nTowersSolutions(2, 2, 2).displaySolutions();
</script>

</body>
</html>

最佳答案

你的问题很可能只有一个(二维)数组，它是全局的，所以最后你的解决方案都指向同一个数组，这将是我们的递归函数完全返回之前的最后一个状态. 

array_array_chessboard[current_x][current_y] = "T";
placeTower(number_of_left_towers - 1, array_array_chessboard);
array_array_chessboard[current_x][current_y] = "-";

如果我对上面的理解正确，你就是(遍历所有位置，ish)
1) 将 T 分配给一个位置
2) 在该位置用 T 解决所有板
3) 将“-”分配给之前的位置

所以最后你有一个充满“-”的数组，所有的解都指向同一个数组

尝试替换

return solutions.push(array_array_chessboard);

由 

return solutions.push(JSON.decode(JSON.encode(array_array_chessboard)));

以上内容将对您的解决方案进行深度复制，虽然它可能不是进行深度复制的最有效方法，但它很简单。如果您的算法需要非常快，您可能希望以更快的方式克隆您的解决方案。

虽然我不能保证这会起作用，因为我不能运行你的 fiddle

(同样为了可读性，我建议你这样写你的返回:)

solutions.push(JSON.parse(JSON.stringify(array_array_chessboard)));
return;

编辑:为什么要在 Array::from 上使用 JSON.parse+stringify:

如果你只是这样做

solutions.push(Array.from(array_array_chessboard));

第二个维度仍将引用相同的数组，毕竟那是存储字符串数据的地方。

演示(请注意，您需要在 IE 中填充 Array.from，或者只是在不同的浏览器上尝试):

var arr1 = ["a"];
var arr2 = ["b"];
var metaArr = [arr1, arr2];
console.log(metaArr[0][0], metaArr[1][0]); // "a b"

var metaArrClone = Array.from(metaArr);
var metaArrClone[0][0] = "c";
console.log(metaArrClone[0][0]); // "c"
console.log(metaArr[0][0]); // "c"

var metaArrClone2 = JSON.parse(JSON.stringify(metaArr));
console.log(metaArrClone2[0][0]); // "c"
metaArrClone2[0][0] = "d";
console.log(metaArrClone2[0][0]); // "d"
console.log(metaArr[0][0]); // "c"

关于javascript - 如何通过回溯递归地修改数组元素？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40303601/

26 4 0
文章推荐： javascript - 是否有保持 iPhone 摄像头录制的命令？
文章推荐： android - 为什么我无法从 Android native 应用程序登录以测试 Facebook 用户帐户？
文章推荐： android - Libgdx - 渲染许多小 Sprite VS 几个大 Sprite
文章推荐： android - GLES20Canvas.nDrawDisplayList 很慢
塔克拉玛干
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com