频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
约瑟夫问题之循环链表
2017-03-11 09:29:34           
收藏   我要投稿

约瑟夫问题之循环链表:1顺序建立循环链表+循环链表中的符合题意的元素结点的删除,2注意只有一个人玩死亡游戏的情况。

约瑟夫问题
Time Limit: 1000MS Memory Limit: 65536KB

n个人想玩残酷的死亡游戏,游戏规则如下:
n个人进行编号,分别从1到n,排成一个圈,顺时针从1开始数到m,数到m的人被杀,剩下的人继续游戏,活到最后的一个人是胜利者。
请输出最后一个人的编号。

Input
输入n和m值。

Output
输出胜利者的编号。

Example Input
5 3

Example Output
4

Hint
第一轮:3被杀第二轮:1被杀第三轮:5被杀第四轮:2被杀

Author

以下为accepted代码1

#include 
#include 
struct node
{
    int Data;
    struct node *next;
}*head, *tail;
void Build(int n);//顺序建立循环链表
void Search_ans(struct node *h, int m);//循环链表中删除满足题意的元素结点
int main()
{
    int n, m;
    while(scanf("%d %d", &n, &m) != EOF)
    {
        if(n == 1)
            printf("%d\n", n);
        else
        {
            head = (struct node *)malloc(sizeof(struct node));
            head->Data = 1;//循环链表中头结点不再为空
            head->next = NULL;
            tail = head;
            Build(n);//顺序建立循环链表
            Search_ans(head, m);//循环链表中删除满足题意的元素结点
        }
    }
    return 0;
}
void Build(int n)//顺序建立循环链表
{
    struct node *p;
    for(int i = 2; i < n; i++)
    {
        p = (struct node *)malloc(sizeof(struct node));
        p->Data = i;
        p->next = tail->next;
        tail->next = p;
        tail = p;
    }
    p = (struct node *)malloc(sizeof(struct node));
    p->Data = n;
    tail->next = p;
    p->next = head;
}
void Search_ans(struct node *h, int m)//在循环链表中删除满足题意的元素结点
{
    int cnt = 0;
    struct node *q, *p;
    q = tail->next;
    p = head;
    while(p->next != p)
    {
        cnt++;
        if(cnt % m == 0)
        {
            q->next = p->next;
            free(p);
            p = q->next;
        }
        else
        {
            q = p;
            p = p->next;
        }
    }
    printf("%d\n", p->Data);
}


/***************************************************
User name: 
Result: Accepted
Take time: 0ms
Take Memory: 108KB
Submit time: 2017-03-10 21:04:59
****************************************************/

以下为accepted代码2

#include 
#include 
struct node
{
    int Data;
    struct node *next;
}*head, *tail;
void Build(int n);//顺序建立循环链表
void Search_ans(struct node *h, int m);//循环链表中删除满足题意的元素结点
int main()
{
    int n, m;
    while(scanf("%d %d", &n, &m) != EOF)
    {
        head = (struct node *)malloc(sizeof(struct node));
        head->Data = 1;//循环链表中头结点不再为空
        head->next = NULL;
        tail = head;
        Build(n);//顺序建立循环链表
        Search_ans(head, m);//循环链表中删除满足题意的元素结点
    }
    return 0;
}
void Build(int n)//顺序建立循环链表
{
    struct node *p;
    for(int i = 2; i < n; i++)
        p = (struct node *)malloc(sizeof(struct nod

    {e));
        p->Data = i;
        p->next = tail->next;
        tail->next = p;
        tail = p;
    }
    if(n != 1)
    {
        p = (struct node *)malloc(sizeof(struct node));
        p->Data = n;
        tail->next = p;
        p->next = head;
    }
    else
    {
        head->next = head;
    }
}
void Search_ans(struct node *h, int m)//在循环链表中删除满足题意的元素结点
{
    int cnt = 0;
    struct node *q, *p;
    q = tail->next;
    p = head;
    while(p->next != p)
    {
        cnt++;
        if(cnt % m == 0)
        {
            q->next = p->next;
            free(p);
            p = q->next;
        }
        else
        {
            q = p;
            p = p->next;
        }
    }
    printf("%d\n", p->Data);
}
点击复制链接 与好友分享!回本站首页
上一篇:actor、reactor与proactor模型
下一篇:BZOJ1415 NOI2005 聪聪与可可(期望dp+预处理)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站