汉诺塔的非递归实现

借助堆栈以非递归(循环)方式求解汉诺塔的问题(n, a, b, c),即将N个盘子从起始柱(标记为“a”)通过借助柱(标记为“b”)移动到目标柱(标记为“c”),并保证每个移动符合汉诺塔问题的要求。

输入格式

输入为一个正整数N,即起始柱上的盘数。

输出格式

每个操作(移动)占一行,按柱1 -> 柱2的格式输出。

输入样例

3

输出样例

a -> c
a -> b
c -> b
a -> c
b -> a
b -> c
a -> c

参考代码

/*  hanoi塔的递归实现  
#include<cstdio>
void hanoi(int,char,char,char);
int main(){
    int n;
    scanf("%d",&n);
    hanoi(n,'a','c','b');
    return 0;
} 
void hanoi(int ranks,char origin,char aim,char tmp){
    if(ranks==1)printf("%c -> %c\n",origin,aim);
    else{
        hanoi(ranks-1,origin,tmp,aim);
        printf("%c -> %c\n",origin,aim);
        hanoi(ranks-1,tmp,aim,origin);
    }
} */
/*  使用栈模拟系统栈运行递归的解法  
#include<cstdio>
#define MAXINPUT 64
//定义两个宏以便于在push和hanoi_stimulation函数中批量创建同名变量拷贝栈顶活动的参数
#define PUSH_S(x) sysstack_stimulation[top].x=x  
#define SET(x) x=sysstack_stimulation[top].x
//定义一个结构体,储存模拟活动中的参数信息
typedef struct info{
    char origin,aim,tmp;
    int ranks,step;
}info;
//定义一个模拟栈用于模拟递归过程的活动记录
info sysstack_stimulation[MAXINPUT];
void push(int,char,char,char,int),hanoi_stimulation();
int top;   //栈顶指针
int main(){
    int n;
    scanf("%d",&n);
    push(n,'a','c','b',0);
    while(top>0)hanoi_stimulation(); //模拟栈不为空则循环执行hanoi模拟函数
}
void push(int ranks,char origin,char aim,char tmp,int step){
    top++;  //注意push时要先新开一个栈单元,再存储活动记录
    PUSH_S(ranks);
    PUSH_S(origin);
    PUSH_S(aim);
    PUSH_S(tmp);
    PUSH_S(step);
}
void hanoi_stimulation(){
    int SET(ranks),SET(step);
    char SET(origin),SET(aim),SET(tmp);
    switch(step){
        //根据hanoi的递归函数可知,当ranks不为1时每层的子问题需要进行三步处理
        case 0:     //case为0存在两种情况,ranks为1时打印语句,ranks不为1说明是刚压入栈的“递归”子活动
            if(ranks==1){
                printf("%c -> %c\n",origin,aim);
                break;
            }else{  
                sysstack_stimulation[top].step++;  
                push(ranks-1,origin,tmp,aim,0);    //继续向栈中压入ranks规模更小的子函数
                //相当于模拟hanoi(ranks-1,origin,tmp,aim);
                return;   //return而不是break,这样可以不执行后面的弹栈操作,使活动记录暂时“休眠”在栈中
            }
        case 1:     //case为1时说明第一步的子活动递归完成返回了,后栈顶活动完成了第一步处理
            sysstack_stimulation[top].step++;
            push(1,origin,aim,tmp,0);
            //将ranks为1的活动压入栈顶,实际上相当于模拟printf("%c -> %c\n",origin,aim);
            return;
        case 2:     //case为2的情况同理
            sysstack_stimulation[top].step++;
            push(ranks-1,tmp,aim,origin,0);
            //相当于模拟hanoi(ranks-1,tmp,aim,origin);
            return;
        default:break;
    }
    top--;     //正常结束的情况(即ranks规模为1,符合递归出口条件时),将栈顶活动弹出
}
/*  使用栈模拟系统栈运行递归的解法:改进
    实际上在使用栈模拟递归时并不需要使用专门的变量step来记录模拟进行的步骤,因为只要栈中活动顺序没有问题,那么与正常递归执行的顺序是
    一致的;但是需要注意的是,如果将递归函数的三步操作一次性压入栈中的话,需要逆序压入,这样栈顶的是第一步操作,然后对栈顶活动继续模拟
    即可(由于二三步操作之前就被压入栈中,因此后续只需要对栈顶活动进行处理即可)    
#include<cstdio>
#define MAXINPUT 64
#define PUSH_S(x) sysstack_stimulation[top].x=x  
#define SET(x) x=sysstack_stimulation[top].x
typedef struct info{
    char origin,aim,tmp;
    int ranks;
}info;
info sysstack_stimulation[MAXINPUT];
void push(int,char,char,char),hanoi_stimulation();
int top;
int main(){
    int n;
    scanf("%d",&n);
    push(n,'a','c','b');
    while(top>0)hanoi_stimulation(); 
}
void push(int ranks,char origin,char aim,char tmp){
    top++; 
    PUSH_S(ranks);
    PUSH_S(origin);
    PUSH_S(aim);
    PUSH_S(tmp);
}
void hanoi_stimulation(){
    int SET(ranks);
    char SET(origin),SET(aim),SET(tmp);
    top--;   //注意这种情况下只需将初始栈中的活动弹出,或替换为三个新的活动即可
    if(ranks==1)printf("%c -> %c\n",origin,aim);
    else{
        push(ranks-1,tmp,aim,origin);
        printf("%c -> %c\n",origin,aim);
        push(ranks-1,origin,tmp,aim);
    }
}

File Transfer

We have a network of computers and a list of bi-directional connections. Each of these connections allows a file transfer from one computer to another. Is it possible to send a file from any computer on the network to any other?

Input Specification

Each input file contains one test case. For each test case, the first line contains N(2N104)N (2≤N≤10^4) ,the total number of computers in a network.
Each computer in the network is then represented by a positive integer between 1 and N. Then in the following lines, the input is given in the format:

I c1 c2

where I stands for inputting a connection between c1 and c2; or

C c1 c2

where C stands for checking if it is possible to transfer files between c1 and c2; or

S

where S stands for stopping this case.

Output Specification

For each C case, print in one line the word “yes” or “no”. if it is possible or impossible to transfer files between c1 and c2, respectively.
At the end of each case, print in one line

The network is connected.

if there is a path between any pair of computers; or

There are k components.

where k is the number of connected components in this network.

Sample Input 1

5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
S

Sample Output 1

no
no
yes
There are 2 components.

Sample Input 2

5
C 3 2
I 3 2
C 1 5
I 4 5
I 2 4
C 3 5
I 1 3
C 1 5
S

Sample Output 2

no
no
yes
yes
The network is connected.

程序框架搭建

int main()
{
    初始化集合;
    do{
    读入一条指令;
    处理指令;
    }while(没结束);
    return 0;
}
int main()
{
    SetType S;
    int n;
    char in;
    scanf("%d\n",&n);
    Initialization(S,n);
    do
    {
        scanf("%c",&in);
        switch(in)
        {
            case 'I':Input_connection(S);break;     //Union(Find)
            case 'C':Check_connection(S);break;     //Find
            case 'S':Check_network(S,n);break;      //集合的根
        }
    }while(in!='S');
    return 0;
}
输入连接
void Input_connection(SetType S)
{
    ElementType u,v;
    SetName Root1,Root2;
    scanf("%d %d\n",&u,&v);
    Root1=Find(s,u-1);
    Root2=Find(s,u-1);
    if(Root1!=Root2)Union(S,Root1,Root2);
}
检查连接
void Check_connection(SetType S)
{
    ElementType u,v;
    SetName Root1,Root2;
    scanf("%d %d\n",&u,&v);
    Root1=Find(s,u-1);
    Root2=Find(s,u-1);
    if(Root1==Root2)cout<<"yes"<<endl;
    else cout<<"no"<<endl;
}
检查整个路径
void Check_network(S,n)
{
    int count=0;
    for(int i;i<n;i++)if(S[i]<0)count++;
    if(count==1)cout<<"The network is connected."<<endl;
    else cout<<"There are "<<count<<" components."<<endl;
}

核心算法TSSN版本的(too simple and naive)

算法1:

SetName Find(SetType S,ElementType X)
{
    for(;S[X]>=0;X=S[X]);
    return X;
}
void Union(SetType S,SetName Root1,SetName Root2)
{
    S[Root1]=Root2; 
}

算法2:

int Find(SetType S[],ElementType X)
{
    int i;
    for(i=0;i<MaxSize&&S[i].Data!=X;i++);
    if(i>=MaxSize)return -1;
    for(;S[i].Parent>=0;i=S[i].Parent);
    return i;
}
void Union(SetType S[],ElementType X1,ElementType X2)
{
    int Root1,Root2;
    Root1=Find(S,X1);
    Root2=Find(S,X2);
    if(Root1!=Root2)S[Root2].Parent=Root1;
}

TSSN版本的特点:永远把Root2接到Root1下面,极端情况:当需要将一个结点和其他所有结点连接且方向一致时,树的高度会一直增加

按秩归并

为什么树会越来越高?

  • 应该把矮树贴到高树上,此时高树的高度不变,矮树的高度+1
  • 树的高度存在哪里?
    • 使用根结点存储树高,S[Root]=-树高; (S中的元素初值仍然初始化为1)
    • 这种算法只有一种情况下高树的高度需要改变:两树高度相等的时候
void Union(SetType S,SetName Root1,SetName Root2)
{
    if(S[Root1]<S[Root2])S[Root2]=Root1;
    else
    {
        if(S[Root1]==S[Root2])S[Root2]++;
        S[Root1]=Root2;
    }
}
  • 另一种做法:比规模
    • 小树贴到大树上 S[Root]=-元素个数
    • 相对来说,这种方法与按秩归并结合的效果更佳
void Union(SetType S,SetName Root1,SetName Root2)
{
    if(S[Root1]<S[Root2])
    {
        S[Root1]+=S[Root2];
        S[Root2]=Root1;
    }
    else{
        S[Root2]+=S[Root1];
        S[Root1]=Root2;
    }
}
  • 以上两种方法统称“按秩归并”
    • 最坏情况下的树高:O(lgN)O(lgN) (等秩归并的次数)

路径压缩

SetName Find(SetType S,ElementType X)
{
    if(S[X]<0)return X;
    else return S[X]=Find(S,S[X]);              //先找到根,把根变成X的父结点,再返回根
}

路径压缩的精髓在于S[X]=Find(S,S[X])
当递归停止后返回的是最后的根结点,注意:同时将根结点下一层结点的父结点值赋为根结点的值,同时返回该层的父结点!
到下一层后,再将下一层的父结点(即上一层结点)的值赋为递归调用返回的上一层父结点的值(根结点的值)
这个过程直到最后,将结点X向上遍历过程中的所有父结点都连接到了最后的根上,使总的高度变为了2!
此外,这里采用的是伪递归,伪递归是非常容易转化为循环的,所以实际上这段代码在编译过程中已经被编译器自动转化为了循环

引理(Tarjan):令T(M,N)为交错执行M>=N次带路径压缩的查找和N-1次按秩归并的最坏情况时间,则存在正常数k1k_1k2k_2使得:
k1Mα(M,N)T(M,N)k2Mα(M,N)k_1Mα(M,N)\leq T(M,N)\leq k_2Mα(M,N)

Ackermann函数

  • A(i,j)=2j    i=1 and j1A(i,j)=2^j\space\space\space\space i=1\space and\space j\geq 1
  • A(i,j)=A(i1,2)    i2 and j=1A(i,j)=A(i-1,2)\space\space\space\space i\geq 2\space and\space j=1
  • A(i,j)=A(i1,A(i,j1))    i2 and j2A(i,j)=A(i-1,A(i,j-1))\space\space\space\space i\geq 2\space and\space j\geq 2

Ackermann函数增长极快,如A(2,4)=2A(2,3)=22A(2,2)=2222A(1,1)=2216=265536A(2,4)=2^{A(2,3)}=2^{2^{A(2,2)}}=2^{2^{2^{2^{A(1,1)}}}}=2^{2^{16}}=2^{65536}

α(M,N)=min{i1A(i,M/N)>lgN}O(lgN)4α(M,N)=min\{i\geq 1|A(i,⌊M/N⌋)>lgN\}\leq O(lg*N)\leq 4

(在自然界会出现的情况中α一般不会超过4)
lgNlg*N=对N递归地求对数,直到结果1\leq 1的次数(lgNlg*N为Ackermann反函数),如:lg(265536)=5lg*(2^{65536})=5

α为满足Ackermann函数大于lgN的i中最小的那一个(α非常小)
综上,当路径压缩和按秩归并结合使用的时候,两者结合的时间复杂度为常数级