"递归"实现"约瑟夫环"，"汉诺塔"

一：约瑟夫环问题是由古罗马的史学家约瑟夫提出的，问题描述为：编号为1,2,….n的n个人按顺时针方向围坐在一张圆桌周围，每个人持有一个密码（正整数），一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始报数，报到m时停止报数，报m的那个人出列，将他的密码作为新的m值，从他顺时针方向的下一个人开始重新从1报数，数到m的那个人又出列；如此下去，直到圆桌周围的人全部出列为止。

一般情况下，循环链表就可以解决这个问题，但是我正在学习递归，所以就递归实现了，下面附上代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN sizeof(struct josepf)

struct josepf
{
    int  id;
    char passwd[20];
    struct josepf * next;
};

int joseph(struct josepf *,struct josepf *,int);

int joseph(struct josepf *trans,struct josepf *tail,int passwd1)
{
    char passwd[20];
    int i;
    struct josepf *q,*p,*next,*s;
    if(passwd1 == 1)                 //注意：如果传的密码是1，就表示下一个人直接出
    {
        s = trans->next;
        tail->next = s;
        strcpy(passwd,trans->passwd);
        printf("第%d个人出列(密码:%s)\n",trans->id,trans->passwd);
        free(trans);
        if(s->next != s)
        {
            joseph(s,tail,atoi(passwd));
        }
        else
            printf("第%d个人出列(密码:%s)\n",s->id,s->passwd);
    }
    else                             //其他情况都要循环去找
    {
        for(i = 1,p = trans;i != passwd1;i++,p = p->next)
            q = p;
        next = p->next;
        strcpy(passwd,p->passwd);
        q->next = next;
        printf("第%d个人出列(密码:%s)\n",p->id,p->passwd);
        free(p);
        if(next->next != next)
        {
                joseph(next,q,atoi(passwd));
        }
        else
            printf("第%d个人出列(密码:%s)\n",next->id,next->passwd);
    }
}
int main(int argc,char *argv[])
{
    struct josepf *p1,*p2,*head,*tail;
    int  num,firstpasswd;
    int  i,id = 1;
    printf("请输入人数:");
    scanf("%d",&num);
    printf("请输入初始密码:");
    scanf("%d",&firstpasswd);
    p1 = (struct josepf *)malloc(LEN);
    head = p1;
    printf("请输入第1个人的密码:");
    scanf("%s",p1->passwd);
    p1->id = 1;
    for(i = 1;i < num;i++)
    {
        p2 = (struct josepf *)malloc(LEN);
        printf("请输入第%d个人的密码:",i+1);
        scanf("%s",p2->passwd);
        p2->id = i+1;
        p1->next = p2;
        p1 = p2;
    }
    p1->next = head;
    tail = p1;
    joseph(head,tail,firstpasswd);  
    return 0;
}

二：法国数学家爱德华·卢卡斯曾编写过一个印度的古老传说：在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。

典型的递归问题，先上代码

#include<stdio.h>

int times = 1;

void move(char x,int floor,char z)
{
    times++;
    printf("将第%d层从 %c 移动到 %c\n",floor,x,z);
}

void hanoi(int floor,char x,char y,char z)      //将x上以y为辅助塔移动到z上.
{
    if(floor == 1)
    {
        move(x,1,z);
    }
    else
    {
        hanoi(floor-1,x,z,y);                   //将x上以z为辅助塔移动到y上
        move(x,floor,z);
        hanoi(floor-1,y,x,z);                   //将y上以x为辅助塔移动到z上 这三步基本上是从宏观上把握,实际上移动的只有move函数
    }
}


int main(int argc,char *argv[])
{
    int  floor;
    printf("请输入塔的层数:");
    scanf("%d",&floor);
    hanoi(floor,'x','y','z');
    printf("总的移动次数:%d\n",times);
}

总结：有关递归问题，既精妙又复杂，这是一种形式上简单但是内部复杂的模型，我们要做的就是找到最基本的步骤，即整个过程再重复什么事，当然大过程和小过程重复的事情必须是一样的， 然后总结出解决一个小过程的方法，然后解决大的问题就好了。