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 つのペグと n 個のディスクの場合、1 つのソース、1 つの宛先、および 4 つの空きペグがあります。アイデアは、ソースから free_peg[3] (4 番目のフリー ペグ) に (n - p) (p ~ n/2) を移動することです。現在、ベクターには 3 つの空きペグしかありません。これらの 3 つの空きペグを使用して (n - p - 1) ディスクを free_peg[2] に移動し、最後のディスクをソースから宛先に移動します。これで、2 つの空きペグと 1 つのソース = 3 つの空きペグができました。次に、(n - p - 1) 個のディスクを peg[2] から 3 つの空きペグ (現在は空きになっているソースを含む) を使用して移動先に移動する必要があります。最後に、4 つのフリー ペグを使用して、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 に答える