神秘博客

C语言用循环和递归计算汉诺塔

/*
汉诺塔移动次数为2^n-1次 用循环写的话直接先计算次数 然后判断奇数偶数套规律
*/
#include <stdio.h>


static int i = 1;

void judge1(int n, char a, char b, char c);
void judge2(int n, char a, char b, char c);

void move(char a, char b);




int main()
{
  int n;

  puts("请输入圆盘的数量[q退出]: ");

  while (scanf_s("%d", &n) == 1)
  {
    if (n <= 0 || n > 64)
    {
      puts("输入错误, 请输入1-64: ");
      puts("请输入圆盘的数量[q退出]: ");
      continue;
    }
    puts("递归: ");
    judge1(n, 'a', 'b', 'c');
    i = 1;
    puts("循环: ");
    judge2(n, 'a', 'b', 'c');
    i = 1;
    puts("请输入圆盘的数量[q退出]: ");
  }

  system("pause");
  return 0;
}
void judge2(int n, char a, char b, char c)
{
  int i, j, tot = 1;

  for (i = 1; i <= n; i++)
  {
    tot *= 2;
  }
  j = tot - 1;
  while (j > 0)
  {
    
    if (n == 1)
    {
      move(a, c);
      break;
    }
    if (n % 2 == 0)
    {
      if (j % 2 != 0)
      {
        move(a, b);
        j--;
        move(a, c);
        j--;
        move(b, c);
        j--;
      }
      else
      {
        move(a, b);
        j--;
        move(c, a);
        j--;
        move(c, b);
        j--;
      }
    }
    else
    {
      if (j % 2 != 0)
      {
        move(a, c);
        j--;
        move(a, b);
        j--;
        move(c, b);
        j--;
      }
      else
      {
        move(a, c);
        j--;
        move(b, a);
        j--;
        move(b, c);
        j--;
      }
      if (j == 1)
      {
        move(a, c);
        j--;
      }
    }
    
  }
}


void judge1(int n, char a, char b, char c)
{
  

  if (n == 1)
  {
    move(a, c);
  }
  else
  {
    judge1(n - 1, a, c, b);
    move(a, c);
    judge1(n - 1, b, a, c);
  }

  
}
void move(char a, char b)
{
  printf("第 %d 次: %c - %c\n", i, a, b);
  i++;
}

 

版权说明:
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

觉得文章有用就请我吃包辣条吧

微信扫一扫打赏