河内塔 - 迭代，使用列表 [英] Hanoi Towers - iterative, using lists

问题描述

我想写标准河内塔algorythm，用3杆，和n光盘。但我也想学习如何使用列表，所以我想我可以结合这一点。

I want to write standard Hanoi Towers algorythm, using 3 rods, and n discs. But I'd also like to learn how to use lists, so I thought I could combine this.

我想到了创建3个元素，每个重presenting单杆。他们每个人都将有光盘[] 数组，例如，如果一杆将有5盘阵列将包含 [1，2，3 ，4，5] 元素。

I thought about creating 3 elements, each representing single rod. Every one of them will have discs[] array, and for example if a rod will have 5 discs the array will contain [1, 2, 3, 4, 5] elements.

好吧，我实现结构等，但我的问题是 - 如何真正解决河内塔迭代？

Ok, I implemented structures etc, but my question is - how to actually solve hanoi towers iterative?

是否确定在棒只是循环，并为每盘检查它在哪里可以去，并将其移动到第一位置检查 - 再重复循环

Is it ok to just loop over the rods, and for every disc check where can it go, and move it to the first checked position - and then repeat the loop?

推荐答案

没有必要与名单过于复杂你的生活。使用数组。

No need to overcomplicate your life with lists. Use arrays.

#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        
_________/\_________  _________/\_________  _________/\_________

这篇关于河内塔 - 迭代，使用列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！