每天一個C語言小項目，提升你的編程能力！

漢諾塔問題源自印度一個古老的傳說

印度教的“創造之神”梵天創造世界時做了 3 根金剛石柱，其中的一根柱子上按照從小到大的順序摞著 64 個黃金圓盤。梵天命令一個叫婆羅門的門徒將所有的圓盤移動到另一個柱子上，移動過程中必須遵守以下規則：

（1）每次只能移動柱子最頂端的一個圓盤；

（2）每個柱子上，小圓盤永遠要位于大圓盤之上。

在漢諾塔問題中，當圓盤個數不大于 3 時，多數人都可以輕松想到移動方案，隨著圓盤數量的增多，漢諾塔問題會越來越難。也就是說，圓盤的個數直接決定了漢諾塔問題的難度，解決這樣的問題可以嘗試用分治算法，將移動多個圓盤的問題分解成多個移動少量圓盤的小問題，這些小問題很容易解決，從而可以找到整個問題的解決方案。

編譯環境：Visual Studio 2019/2022，EasyX插件

這是經典問題漢諾塔的解題演示動畫，代碼如下：

#include 
#include 
#include 
#define MAX 64        // 圓盤的最大數目
#define NULL 0




// 定義棧
struct STKNODE
{
  int a[4];
};


struct STK 
{
  STKNODE*  stack[MAX];
  int      top;
};




// 定義全局變量
STK s[3];          // 聲明三個棧，分別代表一號二號三號鋼針上圓盤的狀態
int v = 5;          // 調整速度
 




// 函數聲明
void Initstk(STK* s);              // 初始化棧
void Hannoi(int n, char a, char b, char c);    // 漢諾塔遞歸
void start();                  // 開始畫面
void Move(int n, char a, char b);        // 移動過程
int switchab(char a);              // 返回鋼針號
void adjust();                  // 調整速度暫停






// 主函數
void main()
{
  int n, ta[4] = {115, 500, 285, 518};      // 第一個圓盤的位置
  printf("盡量小于16
");              // 因為大于十六時就會顯示有誤，但程序可以正常運行
  printf("請輸入漢諾塔的層數（1~64）：");
  scanf("%d", &n);
  STKNODE** p;
  p = (STKNODE**)malloc(n * sizeof(STKNODE **));  // 聲明一個元素為 n 個的動態 STKNODE 型指針數組
  for (int i2 = 0; i2 < n; i2 ++)
  {
    p[i2] = (STKNODE *)malloc(sizeof(STKNODE));  // 為每一個指針申請空間
  } 
  Initstk(&s[0]);
  Initstk(&s[1]);
  Initstk(&s[2]);                  // 將三個棧初始化
  start();                    // 呈現開始畫面
  setfillcolor(GREEN);              // 圓盤的顏色
  for (int i=0; i < n; i++)
  {
    ta[0] += 5;
    ta[1] -= 20;
    ta[2] -= 5;
    ta[3] -= 20;
    solidrectangle(ta[0], ta[1], ta[2], ta[3]);      // 畫出n個從大到小一次疊放的黃色圓盤
    ++s[0].top;                  // 進棧
    for (int i1 = 0; i1 < 4; i1++)
    {
      p[i]->a[i1] = ta[i1];
      s[0].stack[s[0].top] = p[i];      // 記錄每個矩形的位置，top為圓盤的個數
    }
  }  
  Hannoi(n, 'a', 'b', 'c');            // 漢諾塔遞歸函數
  system("pause");
  printf("				Game Over!
");
}






///////////////////////////////////////////////////
// 函數定義


// 漢諾塔的遞歸
void Hannoi(int n, char a, char b, char c)  
{
  if(n == 1)
    Move(1, a, c);
  else
  {
    Hannoi(n-1, a, c, b);
    Move(n, a, c);
    Hannoi(n-1, b, a, c);
    }
}


// 棧的初始化
void Initstk(STK *s) 
{  
  int i;
  s->top = 0;
  for (i = 0; i <= MAX; i++)
    s->stack[++s->top] = NULL;
  s->top = 0;
}


// 移動過程
void Move(int n, char a, char b)
{
  int i3, i4 = 0, i5 = 0;          
  i3 = b - a;                        // 目的鋼針與源鋼針的位置差值
  i4 = switchab(a);                    // 源鋼針鋼針號
  i5 = switchab(b);                    // 目的鋼針號
  STKNODE *q1, *q0;                    // 兩個中間結點用于源棧和目的棧間的值得傳遞，q1為目的棧，q0為源棧
  q1 = (STKNODE *)malloc(sizeof(STKNODE));
  q0 = (STKNODE *)malloc(sizeof(STKNODE));


  // 源棧與目的棧值的傳遞
  q0 = s[i4].stack[s[i4].top];
  ++s[i5].top;                      // 進棧
  q1->a[0] = q0->a[0] + i3 * 200;
  q1->a[1] = 500 - s[i5].top * 20;
  q1->a[2] = q0->a[2] + i3 * 200;
  q1->a[3] = 500 - s[i5].top * 20 + 18;
  s[i5].stack[s[i5].top] = q1;
  --s[i4].top;                      // 出棧


  // 向上運動
  while (q0->a[1] >= 100)
  {
    setfillcolor(GREEN);
    solidrectangle(q0->a[0], q0->a[1], q0->a[2], q0->a[3]);
    adjust();                      // 調整函數
    Sleep(10 * v);                    // 暫停（ms）
    setfillcolor(WHITE);
    solidrectangle(q0->a[0], q0->a[1], q0->a[2], q0->a[3]);
    setlinecolor(RED);
    line((q0->a[0] + q0->a[2]) / 2, q0->a[1], (q0->a[0] + q0->a[2]) / 2, q0->a[3]);  // 重新畫上被擦掉原有的紅線
    q0->a[1] -= 10;
    q0->a[3] -= 10;
  }


  // 向左或右運動，與 i3 的正負有關
  while (q0->a[2] != q1->a[2])
  {
    setfillcolor(GREEN);
    solidrectangle(q0->a[0], q0->a[1], q0->a[2], q0->a[3]);
    adjust();
    Sleep(10 * v);
    setfillcolor(WHITE);
    solidrectangle(q0->a[0], q0->a[1], q0->a[2], q0->a[3]);
    if (i3 < 0)                      // i3<0向左移
    {
      q0->a[0] -= 20;
      q0->a[2] -= 20;
    } 
    else                        // i3>0向右移
    {
      q0->a[0] += 20;
      q0->a[2] += 20;
    }
  }


  // 向下運動
  while (q0->a[3] <= q1->a[3])
  {
    setfillcolor(GREEN);
    solidrectangle(q0->a[0], q0->a[1], q0->a[2], q0->a[3]);
    adjust();
    Sleep(10 * v);
    setfillcolor(WHITE);
    solidrectangle(q0->a[0], q0->a[1], q0->a[2], q0->a[3]);
    setlinecolor(RED);
    if (q0->a[1] > 100)                  // 重畫被擦掉的紅線
    {
      line((q0->a[0] + q0->a[2]) / 2, q0->a[1], (q0->a[0] + q0->a[2]) / 2, q0->a[3]);
    }
    q0->a[1] += 10;
    q0->a[3] += 10;
  }


  // 在目的鋼針上的相應位置繪制出黃色矩形塊
  setfillcolor(GREEN);
  solidrectangle(q1->a[0], q1->a[1], q1->a[2], q1->a[3]);
}


// 繪制開始界面
void start()
{


  // 初始化畫面大小
  initgraph(800, 650);


  // 背景設為白色
  setbkcolor(WHITE);


  // 用白色填充整個畫面
  cleardevice();
  
  // 繪制彩虹，形成一道彩虹，摘自 easyx 幫助文檔示例程序
  float H, S, L; 
  H = 0;      // 色相
  S = 1;      // 飽和度
  L = 0.5f;    // 亮度
  setlinestyle(PS_SOLID, 2);                // 設置線寬為 2
  for(int r = 600; r > 544; r--)
  {
    H += 5;
    setlinecolor( HSLtoRGB(H, S, L) );
    circle(750, 900, r);
  }


  // 說明
  settextstyle(50, 0, "華文楷體");
  settextcolor(RED);
  outtextxy(200, 150, "漢諾塔移動動畫");
  settextstyle(20, 0, "黑體");
  outtextxy(600, 200, "BY:Ronald");
  outtextxy(500, 200, "版本V1.1");
  settextstyle(50, 0, "黑體");
  settextcolor(GREEN);
  outtextxy(200, 350, "隨便按一個鍵開始吧！");


  // 檢測鍵盤敲擊
  getch();


  // 清空開始界面
  cleardevice();


  // 繪制運動畫面的的環境
  setlinecolor(RED);


  // 三根紅色線段作為鋼針
  line(400, 110, 400, 500);
  line(600, 110, 600, 500);
  line(200, 110, 200, 500);


  // 長方體形的底座
  setfillcolor(LIGHTGRAY);
  fillrectangle(80, 501, 720, 510); 
  
  // 暫停按鈕
  solidrectangle(360, 540, 440, 580);
  settextstyle(30, 0, "黑體");
  settextcolor(GREEN);
  outtextxy(370, 550, "暫停");                              
  settextstyle(20, 0, "宋體");
  settextcolor(RED);
  outtextxy(300, 580, "鼠標暫停后請按空格繼續");


  // 加速按鈕
  solidrectangle(160, 540, 240, 580);
  settextstyle(30, 0, "黑體");
  settextcolor(GREEN);
  outtextxy(170, 550, "加速");
  settextstyle(20, 0, "宋體");
  settextcolor(RED);
  outtextxy(170, 580, "請按 d");


  // 減速按鈕
  solidrectangle(560, 540, 640, 580);
  settextstyle(30, 0, "黑體");
  settextcolor(GREEN);
  outtextxy(570, 550, "減速");
  settextstyle(20, 0, "宋體");
  settextcolor(RED);
  outtextxy(570, 580, "請按 a");


  // 說明
  settextstyle(50, 0, "宋體");
  settextcolor(GREEN);
  outtextxy(10, 10, "正在進行中請欣賞：");
}


// 判斷目的鋼針與源鋼針的鋼針號返回鋼針號
int switchab(char a)
{
  switch (a)
  {
    case 'a':
      return 0;
    case 'b':
      return 1;
    case 'c':
      return 2;
    default:
      return 0;
  }
}


// 調整函數，實現加速，減速，暫停
void adjust()
{
  char f;                        // 接收鍵盤敲進去的按鈕和鼠標點擊時賦予的變化值


  // 用 f 接受鍵盤的鍵入值
  if(kbhit())
    f = getch();


  // 檢測鼠標消息
  if (MouseHit()==true)                  
  {


    // 接收鼠標消息
    MOUSEMSG Mouse;
    Mouse = GetMouseMsg();


    // 響應鼠標消息
    if (Mouse.x >= 360 && Mouse.x <= 440 && Mouse.y >= 540 && Mouse.y <= 580 && Mouse.mkLButton)
    {
      f = ' ';
    }
    if (Mouse.x >= 160 && Mouse.x <= 240 && Mouse.y >= 540 && Mouse.y <= 580 && Mouse.mkLButton)
    {
      f = 'd';
    }
    if (Mouse.x >= 560 && Mouse.x <= 640 && Mouse.y >= 540 && Mouse.y <= 580 && Mouse.mkLButton)
    {
      f = 'a';
    }
  }


  // 作用于動畫
  switch(f)
  {
    
    // 暫停
    case ' ':
    
      // 用‘繼續’覆蓋‘暫停’  
      settextstyle(30, 0, "黑體");
      settextcolor(GREEN);
      outtextxy(370, 550, "繼續");  
      getch();
    
      // 繼續后變回顯示‘暫停’
      settextstyle(30, 0, "黑體");
      settextcolor(GREEN);
      outtextxy(370, 550, "暫停");  
      break;
    
    // 減速
    case 'a':
    
      // 當被點擊時，‘減速’位置震動一下
      setfillcolor(LIGHTGRAY);
      solidrectangle(560, 540, 640, 580);
      settextstyle(30, 0, "黑體");
      settextcolor(GREEN);
      outtextxy(575, 545, "減速"); 
      Sleep(30);
    
      // 減速
      v++; 
    
      // 回原位
      setfillcolor(LIGHTGRAY);
      solidrectangle(560, 540, 640, 580);
      settextstyle(30, 0, "黑體");
      settextcolor(GREEN);
      outtextxy(570, 550, "減速");
      break;
    
    // 加速
    case 'd':
      setfillcolor(LIGHTGRAY);
      solidrectangle(160, 540, 240, 580);
      settextstyle(30, 0, "黑體");
      settextcolor(GREEN);
      outtextxy(165, 545, "加速");
      Sleep(30);
      setfillcolor(LIGHTGRAY);
      solidrectangle(160, 540, 240, 580);
      settextstyle(30, 0, "黑體");
      settextcolor(GREEN);
      outtextxy(170, 550, "加速");


      // 加速
      v--;
    
      // v 最小為1
      if (v <= 0)              
      {
        v = 1;
      }
      break;
    
    default:
      break;
  } 
  
  f = 'r';                  // f 初始化為 r
  FlushMouseMsgBuffer();            // 清空鼠標消息
}

大家趕緊去動手試試吧！

審核編輯：湯梓紅