如何索引汉诺塔中移动磁盘的每个步骤（递归方法）

Question

在TOH(河内塔)中打印从源到目的地的移动磁盘可以很容易地写在C/C++中。(具有递归功能) 但是我们如何在每一步打印索引呢？ C代码-

#include<stdio.h>
void tower( int disk, int peg1, int peg2, int peg3);// function declaration
int main()
{
    int disk;
    int peg1= 1, peg2= 2, peg3= 3;//numbering 
    puts("enter disk");
    scanf("%d", &disk);//read disks
    tower(disk, peg1, peg2, peg3);//function using
    return 0;
}
void tower( int disk, int peg1, int peg2, int peg3)//function definition
{
    
    if(disk ==1)//if only 1 disk is avialable
    {
    printf("move disk from peg%d to peg%d\n",peg1,peg3);//moving disk from source to destination
    }
    else
    {
      tower(disk-1, peg1,peg3,peg2);//moving n-1 disk from peg 1 to peg2 using peg3
      printf("move disk from peg%d to peg%d\n", peg1,peg3);//move last biggest disk
      tower(disk-1,peg2,peg1,peg3);//moving n-1 disk from peg2 to peg3 using peg1
    }

它工作并打印输出。

但是有没有办法索引（1,2，...）每一步 -

将磁盘从 peg1 移动到 peg3
将磁盘从 peg1 移动到 peg2

Answer 1

首先请注意，您不需要 printf 其他内容分支，因为这是由你的递归函数库管理的案例.

要打印索引，最简单的解决方案（如果我们排除全局变量）会给你的递归函数一个额外的指针参数引用一个整数，该整数是打印的行数。每次你打印一行，此指针引用的整数递增 1。这给出下面的函数 tower_ptr：

#include <stdio.h>

void tower_ptr(int * index, int disk, int src, int tmp, int dst) {    
  if(disk == 1) {
    (*index) ++;
    printf("%d. move %d -> %d\n", *index, src, dst);
  } else {
    tower_ptr(index, disk - 1, src, dst, tmp);
    tower_ptr(index, 1, src, - 1, dst);
    tower_ptr(index, disk - 1, tmp, src, dst);
  }
}

int main() {
  int index = 0;
  int disk;
  puts("enter disk");
  scanf("%d", &disk);
  tower_ptr(&index, disk, 1, 2, 3);
  return 0;
}

另一个解决方案是给你的函数一个额外的参数这是下一个要打印的索引。函数returns的个数索引打印。这给出了下面的函数 tower_int：

#include <stdio.h>

int tower_int(int index, int disk, int src, int tmp, int dst) {    
  if(disk == 1) {
    printf("%d. move %d -> %d\n", index + 1, src, dst);
    return index + 1;
  } else {
    index = tower_int(index, disk - 1, src, dst, tmp);
    index = tower_int(index, 1, src, - 1, dst);
    index = tower_int(index, disk - 1, tmp, src, dst);
    return index;
  }
}

int main() {
  int index = 0;
  int disk;
  puts("enter disk");
  scanf("%d", &disk);
  tower_int(0, disk, 1, 2, 3);
  return 0;
}

如何索引汉诺塔中移动磁盘的每个步骤（递归方法）

How to index each steps of moving disk in Tower of Hanoi (recursive approach)

c

recursion

function

towers-of-hanoi