pzq25 2016-11-09 00:58 采纳率: 0%
浏览 1164

约瑟夫问题,递归函数不对

图片说明

 #include<stdio.h>               //约瑟夫问题,共n个人,从x开始数数,数到y时去掉,要求最后剩下的一个人编号为1 

typedef int elemtype;
typedef struct{
        elemtype data;
        struct Node *next;
        }*Linklist,Node;

int f(Node *start,int n,int y,Linklist L)   //递归算法 
{
    Node *s,*p;
    elemtype e;
    int i;
    if (n==1&&start->data==1) return 1;     //若最后剩下1,则返回1 
    if (n==1) {printf("%d\n",start->data);return 0;} //其他则输出最后的编号,并返回0 
    for (i=1,p=start;i<y-1;i++)    // 删除数到y的 
    {
        p=p->next;
    }
    s=p->next;
    e=s->data;
    p->next=s->next;
    free(s);        
    printf("%d\t",e);           //输出删除的编号 
    start=p->next;
    f(start,n-1,y,L);
}
void TraverseList(Linklist L)
{
     Node *p=L;
     while(p->data!=5)
     {
             printf("%d\t",p->data);
             p=p->next;
     }
     printf("\n");
}       
int main() 
{
    Linklist L;
    L=(Linklist)malloc(sizeof(Node));
    Node *start,*p,*s;
    int y,n,x,i,c;
    printf("请输入总人数:\n");
    scanf("%d",&n);
    L->data=1;                //编号 
    L->next=NULL;
    p=L;
    for (i=2;i<=n;i++)
    {
        s=(Node*)malloc(sizeof(Node));
        s->data=i;
        s->next=p->next;
        p->next=s;
        p=p->next;
    }
    p->next=L;          //围圈 
    TraverseList(L);
    for (x=1;x<2;x++)   //先固定x只能为1 
    {
        for (i=1,p=L;i<x;i++) p=p->next;  
        start=p;
        for(y=2;y<n;y++)    //y可从2~n-1变化 
        {
            if (f(start,n,y,L)==1) printf("x:%d\t y:%d\n",x,y);   //如果返回值为1,说明最后剩下了1,输出x,y的值 
            Linklist L;   //由于前面删除了链表,所以重新建立单循环链表 
            L=(Linklist)malloc(sizeof(Node));
            L->data=1;
            L->next=NULL;
            p=L;
            for (i=2;i<=n;i++)
            {
                s=(Node*)malloc(sizeof(Node));
                s->data=i;
                s->next=p->next;
                p->next=s;
                p=p->next;
            }
            p->next=L;
            TraverseList(L);
        }
    }
    getch();
    return 0;
}  
  • 写回答

1条回答 默认 最新

报告相同问题?

悬赏问题

  • ¥20 数学建模,尽量用matlab回答,论文格式
  • ¥15 昨天挂载了一下u盘,然后拔了
  • ¥30 win from 窗口最大最小化,控件放大缩小,闪烁问题
  • ¥20 易康econgnition精度验证
  • ¥15 msix packaging tool打包问题
  • ¥28 微信小程序开发页面布局没问题,真机调试的时候页面布局就乱了
  • ¥15 python的qt5界面
  • ¥15 无线电能传输系统MATLAB仿真问题
  • ¥50 如何用脚本实现输入法的热键设置
  • ¥20 我想使用一些网络协议或者部分协议也行,主要想实现类似于traceroute的一定步长内的路由拓扑功能