c - 河内塔 - 迭代，使用列表

Question

我想编写标准的河内塔算法，使用 3 根杆和 n 盘。但我也想学习如何使用列表，所以我想我可以把它结合起来。

我想创建 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        
_________/\_________  _________/\_________  _________/\_________