• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

C语言约瑟夫环的2种实现方法

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

具体的数学实现方法就不写了,网上有大把大把的

这里写两种最容易理解的版本

 

第一种是最简单的链表实现方法

#include<stdio.h>
#include<stdlib.h>
/*
第一种是链表法
首先创建一个循环单链表
将每一个参加该游戏的人设定为一个节点 
每个节点的data域代表了每个人的编号
总共有n个人参加游戏 
当轮流报数到m的时候,该玩家出局 out
order代表了每个人的报数情况
在删除节点方面,我选用带头节点循环单链表
引入两个指针pre和q,当pre是q的前节点
每一次需要删除q时,只需要动用pre即可
由于是两个节点,所以当链表中只剩一个节点
即p==q的时候,就是停止循环的条件 
*/
typedef struct node{
    int data;
    struct node *next;
}Node,*pointer;
int main(){
    int m=3;
    int n=41;
    pointer head=(pointer)malloc(sizeof(Node));
    pointer tail=head;
    head->next=NULL;
    int number=1;
    while(number<=n)
    {
        pointer s=(pointer)malloc(sizeof(Node));
        s->data=number++;
        tail->next=s;
        tail=s;
    }
    tail->next=head->next;
    pointer pre=tail;
    pointer q=head->next;
    int order=1;
    while(pre!=q)
    {
        if(order==m)
        {
            printf("out of the game %d\n",q->data);
            pre->next=q->next;
            free(q); 
            q=pre->next;
            order=1;
        }
        else
        {
            pre=q;
            q=q->next;
            order++;
        }
    }
    printf("\n the winner is %d\t",pre->data);
} 

 第二种是数组成环实现

/*
设定一个参赛者数组,数组的名字为gamer
n,m设定与上面的链表设定一样
number代表参赛者的人数
pos代表当前报数者的位置
当报数者的报数为3时,将其out,然后其数组置为0
为了使数组形成环,就需要用到队列中学到的知识 
使用pos=(pos+1)%n
当pos==n-1的时候(数组的最后一位)
pos+1会变到的数组的第一位,从而形成闭环 
 
*/
int main()
{
    int m=3,n=41;//m是出局编号,n是参赛者人数
    int number=n;
    int pos=0; 
    int order=1;
    int gamer[41];
    for(int i=0;i<41;i++)
        gamer[i]=i+1;
    while(number>1)
    {
        if(gamer[pos]!=0)//当报数者没有出局的时候,也就是其数组没有被置为0 
        {
            if(order==m)//如果被order为3了,将其数值置为0 
            {
                printf("gamer %d out\n",gamer[pos]);
                gamer[pos]=0;
                pos=(pos+1)%n;
                number--;
                order=1;
            }
            else
            {
                ++order;
                pos=(pos+1)%n;
            }
        }
        else//如果数值为0,则跳过当前元素 
            pos=(pos+1)%n;
    }
    for(int i=0;i<41;i++)
        if(gamer[i]!=0)
            printf("winner is %d\n",gamer[i]);
}

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap