河内问题塔

Question

嗨大家我在河内的塔上遇到了一个问题:
我们给了一堆交替颜色的圆柱体交替堆叠在一起.
我的工作是将相同颜色的两个堆栈分开,
我可以使用递归为常规的河内塔写代码(算法),但我无法弄清楚这一部分.有人可以帮忙吗？
常规河内问题的代码:

#include<iostream>

using namespace std;
int count=0;

void hanoi(char a,char b,char c,int x)
{
  if(x>1)
  {
    hanoi(a,c,b,x-1);
    hanoi(a,b,c,1);
    hanoi(c,b,a,x-1);
  }
  else
  {
    cout<<"Move a Disk from "<<a<<" to "<<b<<endl; count++;  
  }
}

int main()
{
  int n;
  cout<<"Enter the height of stack";
  cin>>n;
  hanoi('A','B','C',n);
  cout<<"\nNo. of changes done:"<<count;

  return 0;
}

Answer 1

解决问题n时间,交替使用解决方案.

int main()
{
    int n;
    cout<<"Enter the height of stack";
    cin>>n;

    char startPeg = 'A';
    char interPeg = 'B';
    char slnPeg = 'C';

    while(n > 0) {
        hanoi(startPeg,interPeg,slnPeg,n);
        n--;
        char temp = startPeg;
        startPeg = slnPeg;
        slnPeg = temp;
    }

    return 0;
}

这是它的工作原理.假设我们的堆栈颜色为红色(R)和黄色(Y),高度为5个单位:

     |           |           |
    Y|Y          |           |
   RR|RR         |           |
  YYY|YYY        |           |
 RRRR|RRRR       |           |
YYYYY|YYYYY      |           |     

第一次运行后,它看起来像这样:

     |           |           |
     |           |          Y|Y    
     |           |         RR|RR
     |           |        YYY|YYY
     |           |       RRRR|RRRR
     |           |      YYYYY|YYYYY

第二次运行后,它看起来像这样:

     |           |           |    
    Y|Y          |           |
   RR|RR         |           |
  YYY|YYY        |           |
 RRRR|RRRR       |      YYYYY|YYYYY

第三次运行后,它看起来像这样:

     |           |           |    
     |           |          Y|Y
     |           |         RR|RR
     |           |        YYY|YYY
 RRRR|RRRR       |      YYYYY|YYYYY

第四轮之后,这个:

     |           |           |    
     |           |           |
    Y|Y          |           |
   RR|RR         |        YYY|YYY
 RRRR|RRRR       |      YYYYY|YYYYY

在第五次也是最后一次运行之后,这个:

     |           |           |    
     |           |           |
     |           |          Y|Y
   RR|RR         |        YYY|YYY
 RRRR|RRRR       |      YYYYY|YYYYY

在这一点上你已经完成了.

如果你急于递归,请执行以下操作:

void painful(char start, char inter, char sln, int n) {
    if(n == 0) return;
    hanoi(start,inter,sln);
    painful(sln,inter,start,n-1);
}

int main()
{
    int n;
    cout<<"Enter the height of stack";
    cin>>n;

    painful('A','B','C',n);

    return 0;
}