0

我能够提出一种算法（逻辑）来解决河内塔问题的 k-peg 解决方案，但是当我实现我的代码时，我遇到了分段错误。

void move(int number_of_disks, int source, int dest, vector <int> free_peg, int pointer)
    {
        int p;

        if (1 == number_of_disks)
        {
            moves++;
            move_top_disk (source, dest);
        }

        if(free_peg.size() > 2)
            p = number_of_disks/2;
        else 
            p = number_of_disks - 1;

        moves++;
        //Move top "p" disks from peg 1 to peg i
        move(p, source, free_peg.back(),free_peg, pointer); 
        //Move "n - p - 1" disks from peg 1 to another peg 
        move(number_of_disks - p - 1, source, free_peg[pointer--], free_peg, pointer++);
        //Move the "last disk" from the source peg to the destination
        move_top_disk(source, dest);
        //Move "n - p - 1" disks from peg (i - 1) to the final peg
        move(number_of_disks - p - 1, free_peg[pointer--], dest, free_peg, pointer++);
        //Move "p" disks from peg i to the destination
        move(p, free_peg.back(), dest, free_peg, pointer);
    }

这个想法很简单，我保留了一个免费的钉子（或塔）向量，并在我移动磁盘时更新它。所以对于 6 个 pegs 和 n 个磁盘的情况，我有一个源、一个目标和 4 个空闲 pegs。这个想法是将 (n - p) where p ~ n/2 从源移动到 free_peg[3] （第四个自由钉）。现在我的向量中只有 3 个空闲钉，我使用这 3 个空闲钉将 (n - p - 1) 个磁盘移动到 free_peg[2]，然后将最后一个磁盘从源移动到目标。所以现在我有 2 个免费挂钩和 1 个来源 = 3 个免费挂钩。接下来，我需要使用 3 个空闲的 peg（包括现在空闲的源）将 (n - p - 1) 个磁盘从 peg[2] 移动到目的地。最后，使用 4 个空闲 peg 将 p 个磁盘从 free_peg[3] 移动到目的地。但是，当我在我的代码中实现它时，我遇到了分段错误，有人可以帮我解决这个问题吗？

4

1 回答 1

3

我能够解决 k-peg 通用解决方案，感谢您的帮助。以下是算法的运行方式：

void move(int number_of_disks, int source, int dest, vector <int> free_peg)
    {
        int p, middle, g;

        if (1 == number_of_disks)
        {
            moves++;
            move_top_disk (source, dest);
        }

        else
        {
            moves++;

            if(free_peg.size() >= 2)
                p = number_of_disks/2;
            else
                p = number_of_disks - 1;

            //Move top "p" disks from peg 1 to peg i
            middle = free_peg.back();
            free_peg.pop_back();
            free_peg.push_back(dest);
            move(p, source, middle,free_peg);

            //Move "n - p " disks from peg 1 to another peg
            free_peg.pop_back();
            move(number_of_disks - p, source, dest, free_peg);

                    //Move p from current peg to the final peg
            free_peg.push_back(source);
            move(p, middle, dest, free_peg);
        }
    }
于 2012-09-22T22:02:17.840 回答