河內塔問題

題目:

輸入一個數代表圓盤的數量，再輸入一個數代表第幾個步驟。

輸出該步驟要如何移動圓盤，若該步驟不存在，輸出"Step out of range!"，若圓盤數不合法，輸出"Invalid disk number!"

範例輸出:

解題思路:
這題是河內塔的變化題。
在寫之前可以先寫出原始版本的程式:

#include <stdio.h>
void hanoi(int n,char a,char b,char c)
{
    if(n==1)
        printf("move %d from %c to %c\n",n,a,c);
    else
    {
        hanoi(n-1,a,c,b);
        printf("move %d from %c to %c\n",n,a,c);
        hanoi(n-1,b,a,c);
    }
}
int main()
{
    int n;
    printf("how many disks: ");
    scanf("%d",&n);
    hanoi(n,'A','B','C');
    return 0;
}

hanoi這個函式可以理解成把問題分為n與n-1的圓盤，第n個是當前處理的目標，而剩下的n-1個則是丟到遞迴中繼續處理。
而

hanoi(n-1,a,c,b);

這行可以用:n-1的圓盤由A經過C最後放到B來想，下面那行也是同樣的邏輯。

然後再處理out of range的狀況，也就是超出(2^n) -1的時候。
接下來只需要再宣告一個變數s來記錄當前是第幾個步驟，當等於所求步驟數時，再將其輸出即可。

程式碼:

#include<stdio.h>
int s = 1;
int step;
void hanoi(int n, char a, char b, char c);
void move(char m, char n, int now_disk);
int main()
{
 int n, range = 1;
 printf("How many disks do you select?");
 scanf_s("%d", &n);
 if (n < 0)
  printf("Invalid disk number!");
 else
 {
  for (int i = 1; i <= n; i++)
  {
   range *= 2;
  }
  range -= 1;
  printf("Which step do you want to print?");
  scanf_s("%d", &step);
  if (step > range)
   printf("Step out of range!");
  else
  {
   hanoi(n, 'A', 'B', 'C');
  }
  return 0;
 }


 return 0;
}

void hanoi(int n, char a, char b, char c)
{
 if (n == 1)
  move(a, c, n);
 else
 {
  hanoi(n - 1, a, c, b);
  move(a, c, n);
  hanoi(n - 1, b, a, c);
 }
}
void move(char m, char n, int now_disk)
{
 if (s == step)
  printf("Disk %d move from %c to %c\n", now_disk, m, n);
 s++;
}