c - ハノイ タワーズ - リストを使用した反復型

Question

3 つのロッドと n 個のディスクを使用して、標準的なハノイ タワー アルゴリズムを作成したいと考えています。でも、リストの使い方も学びたいので、これを組み合わせることができると思いました。

それぞれが 1 本のロッドを表す 3 つの要素を作成することを考えました。それらのすべてにdiscs[]配列があり、たとえば、ロッドに 5 つのディスクがある場合、配列には[1, 2, 3, 4, 5]要素が含まれます。

わかりました、私は構造などを実装しましたが、私の質問は - 実際にハノイの塔の反復をどのように解決するのですか?

ロッドをループして、ディスクごとにどこに行くことができるかをチェックし、最初にチェックされた位置に移動してから、ループを繰り返すだけで大丈夫ですか?

Answer 1

リストで生活を過度に複雑にする必要はありません。配列を使用します。

#include <stdio.h>

#define DISKS 4 // 10 max
int stacks[3][DISKS];
int sps[3];

void init(int from)
{
  int i;
  sps[2] = sps[1] = sps[0] = 0;
  for (i = 0; i < DISKS; i++)
    stacks[from][i] = DISKS - i; // disk radius
  sps[from] = DISKS;
}

void print(void)
{
  int i, j, k;
  for (i = DISKS - 1; i >= 0; i--)
  {
    for (j = 0; j < 3; j++)
    {
      if (sps[j] > i)
      {
        for (k = 0; k < 10 - stacks[j][i]; k++)
          printf(" ");
        for (k = 0; k < 2 * stacks[j][i]; k++)
          printf("x");
        for (k = 0; k < 10 - stacks[j][i]; k++)
          printf(" ");
      }
      else
      {
        printf("                    "); // 10 * 2
      }
      printf("  ");
    }
    printf("\n");
  }
  printf("_________/\\_________  _________/\\_________  _________/\\_________\n\n");
}

void solve(int to, int from, int cnt)
{
  int other = from ^ to ^ 3;

  if (!cnt) return;

  solve(other, from, cnt - 1);

  stacks[to][sps[to]++] = stacks[from][--sps[from]];
  print();

  solve(to, other, cnt - 1);
}

int main(void)
{
  init(0);
  print();
  solve(2, 0, DISKS);
  return 0;
}

出力 ( ideone ):

         xx                                                       
        xxxx                                                      
       xxxxxx                                                     
      xxxxxxxx                                                    
_________/\_________  _________/\_________  _________/\_________


        xxxx                                                      
       xxxxxx                                                     
      xxxxxxxx                 xx                                 
_________/\_________  _________/\_________  _________/\_________



       xxxxxx                                                     
      xxxxxxxx                 xx                   xxxx          
_________/\_________  _________/\_________  _________/\_________



       xxxxxx                                        xx           
      xxxxxxxx                                      xxxx          
_________/\_________  _________/\_________  _________/\_________



                                                     xx           
      xxxxxxxx               xxxxxx                 xxxx          
_________/\_________  _________/\_________  _________/\_________



         xx                                                       
      xxxxxxxx               xxxxxx                 xxxx          
_________/\_________  _________/\_________  _________/\_________



         xx                   xxxx                                
      xxxxxxxx               xxxxxx                               
_________/\_________  _________/\_________  _________/\_________


                               xx                                 
                              xxxx                                
      xxxxxxxx               xxxxxx                               
_________/\_________  _________/\_________  _________/\_________


                               xx                                 
                              xxxx                                
                             xxxxxx               xxxxxxxx        
_________/\_________  _________/\_________  _________/\_________



                              xxxx                   xx           
                             xxxxxx               xxxxxxxx        
_________/\_________  _________/\_________  _________/\_________



                                                     xx           
        xxxx                 xxxxxx               xxxxxxxx        
_________/\_________  _________/\_________  _________/\_________



         xx                                                       
        xxxx                 xxxxxx               xxxxxxxx        
_________/\_________  _________/\_________  _________/\_________



         xx                                        xxxxxx         
        xxxx                                      xxxxxxxx        
_________/\_________  _________/\_________  _________/\_________



                                                   xxxxxx         
        xxxx                   xx                 xxxxxxxx        
_________/\_________  _________/\_________  _________/\_________


                                                    xxxx          
                                                   xxxxxx         
                               xx                 xxxxxxxx        
_________/\_________  _________/\_________  _________/\_________

                                                     xx           
                                                    xxxx          
                                                   xxxxxx         
                                                  xxxxxxxx        
_________/\_________  _________/\_________  _________/\_________