`
zy3381
  • 浏览: 157627 次
  • 性别: Icon_minigender_1
  • 来自: 昆明
社区版块
存档分类
最新评论

几个人围成一圈||猴子选大王(约瑟夫环)

 
阅读更多
约瑟夫问题是个有名的问题:N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。例如N=6,M=5,被杀掉的人的序号为5,4,6,2,3。最后剩下1号。



一堆猴子都有编号,编号是1,2,3 ...m,这群猴子(m个)按照1-m的顺序围坐一圈,从第1开始数,每数到第N个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。



数组方式

#include<stdio.h>
#define N 5 //总人数
#define M 3 //报数最大值(1-M)
#define R 1 //留下的人数
void main()
{
    //声明一个数组代表N个人
    int r[N];
    //游戏开始之前所有的人都还在,所以当前人数为N
    int size = N;
    int remain = R;
    //设定报数起始值
    int count = 1;
    int i,j;
    //给每个人加上编号
    for(i=0; i<N; i++) r[i] = i+1;

    printf("%d个人从1报数,报到%d的出列,求最后剩余的%d个人\n", N, M, R);

    //循环到当前人数为指定的数目的剩余人数时终止
    while(size != remain)
    {
        //对当前剩余人数进行循环报数
        for(i=0; i<size; i++)
        {
            //报数到3,去掉当前这个人,将后面的人全部往前挪一个位置,当前人数减1,并保持这个for循环停留一次(因为后面一个人挪过来了,所以应该再次在这个位置上重新报数)
            if(count == M)
            {
                printf("第%d个人报数%d,%d号选手出列\n", r[i], count, r[i]);

                for(j=i; j<size-1; j++)
                {
                    r[j] = r[j+1];
                }
                i--;
                size--;
                count = 1;
            }
            else
            {
                printf("第%d个人报数%d\n", r[i], count);
                //继续报数
                count++;
            }
        }
    }
    printf("############剩余的%d个选手############\n", remain);
    for(i=0; i<remain; i++)
    {
        printf("第%d个人报数%d\n", r[i], count, r[i]);
    }

}







链表方式

#include<stdio.h>
#define M 10
#define N 3
#define LEN sizeof(struct Node)
struct Node
{
    int data;
    struct Node *next;
};
//创建一个循环链表
struct Node *create()
{
    int i;
    struct Node *head,*p1,*p2;
    //创建一个头节点
    head = p1 = p2 = (struct Node *)malloc(LEN);
    //头节点赋值
    head->data = 1;
    //使用p1,p2的叉开移动继续创建后面的节点  
    //(1)p2指向新节点  (2)p1的next指向p2  (3)p1和p2都指向新节点位置,repeat
    for(i=1; i<M; i++)
    {
        p2 = (struct Node *)malloc(LEN);
        p2->data = i+1;
        p1->next = p2;
        p1 = p2;
    }
    //将最后一个节点的next指向head
    p1->next = head;
    //返回头指针
    return head;
}
//找到待删除的元素的前一个元素的位置(方便后续的删除和重连接操作)
struct Node *find(struct Node *start,int n)
{
    struct Node *find = start;
    int i;
    for(i=0; i<n-2; i++)
    {
        find = find->next;
    }
    return find;
}

//删除find所指的后面的节点,并将find和find的后后面的节点连接起来
struct Node *del(struct Node *find)
{
    //后后面的节点
    struct Node *temp = find->next->next;
    printf("删除了%d\n", find->next->data);
    free(find->next);
    find->next = temp;
    return temp;
}

void main()
{
    //每一次开始报数的位置
    struct Node *startNode = create();
    //每一次报到N要被删除的数的位置
    struct Node *findNode;
    int i;
    //进行M-1次报数后就只剩下随后一个人
    for(i=0; i<M-1; i++)
    {
        //找一个报数为N的所在的位置
        findNode = find(startNode, N);
        //删掉它并返回下一个继续点的位置
        startNode = del(findNode);
    }
    //输出最后一个人的信息
    printf("#####剩下%d\n", startNode->data);
}





为了方面在链表中删除节点,前面的方法查找的节点实际上找的是待删除的节点的前面一个节点,然后删除的时候就通过这个节点指针将后面一个节点删除,这样的做法很简单,但是感觉很奇怪。昨天看了一下《编程之美》,被里面的一种方法吸引了,果断重写,现在咱这个链表中的节点就是直接找到所在的节点,并且直接把这个节点“删”了^_^,不多说,show code~


#include<stdio.h>
#define N 10
#define M 3
struct Node
{
    int data;
    struct Node *next;
};

//创建循环链表(1-10)
struct Node *create()
{
    int i;
    struct Node *head,*p1,*p2;
    head = p1 = p2 = (struct Node*)malloc(sizeof(struct Node));
    head->data = 1;
    for(i=1; i<N; i++)
    {
        p1 = (struct Node*)malloc(sizeof(struct Node));
        p1->data = i+1;
        p2->next = p1;
        p2 = p1;
    }
    p2->next = head;
    return head;
}

//寻找报数为num的数字(报数范围1-num),返回指向它的指针
struct Node *find(struct Node *start, int num)
{
    struct Node *p = start;
    int i;
    for(i=1; i<num; i++)
    {
        p = p->next;
    }
    return p;
}

//删除p所指向的节点(实际删除的是p后面一个节点)
//基本思想:将p后面一个节点的数据复制到p上,然后让p指向p后后面的节点,然后删掉p后面的节点
//返回的是保存了p后面节点数据的节点
struct Node *del(struct Node *p)
{
    struct Node *pt = p->next;
    p->data = pt->data;
    p->next = pt->next;
    free(pt);
    return p;
}

void main()
{
    int i;
    struct Node *start = create();
    for(i=0; i<N-1; i++)
    {
        start = find(start, M);
        printf("删除%d\n", start->data);
        start = del(start);
    }
    printf("最后剩下%d\n", start->data);
}














分享到:
评论

相关推荐

    猴子选大王问题(约瑟夫问题).docx

    这个问题描述如下:一群编号从1到m的猴子围成一圈,从第1号开始数数,每数到第n号的猴子就离开圈子,然后从下一只继续数,直到圈中只剩下一个猴子,这个猴子即为大王。本篇将探讨如何使用C++语言,通过数组和链表两...

    C++猴子选大王问题也即约瑟夫环问题

    “猴子选大王”问题在计算机科学领域通常被称为约瑟夫环问题。该问题源自古罗马历史学家约瑟夫斯的一个故事,讲述了一群人围成一圈,按照特定规则决定谁将被处决或存活下来。在编程领域中,这个问题被广泛用来考察...

    C 猴子选大王 约瑟夫环

    问题的基本设定是:一群猴子围成一个圈,从某一只猴子开始按顺时针方向编号,然后从第一只开始数数,数到特定数值的猴子出圈,然后继续从下一只猴子开始数,如此循环,直到只剩最后一只猴子,这只猴子就被选为大王。...

    数据结构课程设计 猴子选大王(约瑟夫问题)

    在这个问题中,假设一群猴子围成一个圈,每次从圈中按顺序剔除一只猴子,直至只剩下最后一只,这只猴子即为大王。问题的关键在于如何高效地模拟这个过程。 首先,我们要理解数据结构的选择。由于猴子们围成一个圈,...

    猴子选大王的算法 (约瑟夫环)或称循环链表

    有M只猴子,依次按1到M的顺序坐好,然后从第一只猴子开始报数,数到N(N)的那只猴子就出局,从下一只猴子开始重新开始数....依次...直到只剩下最后一只猴子,则那只猴子就是大王。 要求:只输入M N值,就可以得到...

    约瑟夫环 猴子选大王

    约瑟夫环问题描述如下:假设有一群人围成一个圈,从某个人开始按顺时针或逆时针顺序报数,每次数到特定数值的人会被排除出圈,然后从下一个人继续报数,直到只剩下最后一个人为止,这个人被称为“大王”。...

    约瑟夫环(猴子选大王)

    环形链表,猴子选大王,数到几出去,从几开始数,由用户输入决定

    猴子选大王(C++)带报告

    在这个问题中,一群猴子围成一个圈,每一轮从一只猴子开始按顺时针方向数数,数到特定数值的猴子会被淘汰,这个过程会持续到只剩下最后一只猴子,这只猴子就被选为“大王”。此问题在C++编程中可以运用基本的数据...

    基础算法-python猴子选大王

    python猴子选大王 #!/usr/bin/python # -*- coding: utf-8 -*- N=int(input()) ls=[i for i in range(1,N+1)] step=2 #步长 ptr=1 while len(ls) &gt; 1: #ptr表示列表中第几个元素,没有第0个元素,只有下标为0的...

    猴子选大王(c++)

    这个问题源自一个寓言故事:一群猴子围成一圈,从第一只开始数数,数到指定数值的猴子被淘汰出局,然后从下一只继续数,直到只剩下一个猴子,这个猴子就被选为大王。程序的主要目的是根据猴子的数量和淘汰的条件找出...

    约瑟夫问题(猴子选大王)数学解法

    约瑟夫问题,又称“约瑟夫环”或“猴子选大王”,是一个著名的理论问题,源自古希腊的数学家约瑟夫·弗拉基米尔。这个问题的基本设定是:有一群人围成一个圈,从某个人开始按顺时针方向编号,然后从第一个人开始报数...

    猴子选大王

    一堆猴子都有编号,编号是1,2,3 ...m,这群猴子(m个)按照1-m的顺序围坐一圈,从第1开始数,每数到第N个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。

    数据结构 猴子选大王算法

    该算法模拟了m个猴子排成圈,数到n就出去,最后一个为猴王的过程。该算法的实现需要使用链表这种数据结构来存储猴子的信息。 链表是一种基本的数据结构,它是一种线性的数据结构,通过链式结构将数据元素连接起来。...

    monkey_ok.rar_ 猴子选大王 _Monkey_猴子选大王

    首先,猴子选大王的算法描述如下:假设有一群猴子,它们围成一圈,从某只猴子开始,按顺时针方向依次报数。每当报到特定数字(在这个例子中是3)的猴子就会被排除出去,然后从下一只猴子继续报数,直到只剩下一只...

    基于java数据结构链表写的猴子选大王

    本文将深入探讨一个基于Java数据结构链表实现的经典问题——“猴子选大王”,也称作约瑟夫环问题。该问题源于一个古老的传说,一群猴子围成一个圈,从某一只开始按顺时针方向依次报数,数到特定数值的猴子会被淘汰,...

    C++ 编写的猴子选大王的程序

    根据给定的信息,我们可以分析并总结出以下与“C++ 编写的猴子选大王的程序”相关的知识点: ### C++ 程序设计基础 #### 1. 基本语法结构 - **预处理指令**:如 `#include`、`#define` 等,用于引入头文件或定义...

    猴子选大王四种算法

    里面包含了我的博客‘’算法 -- 猴子选大王的四种方法,并对其时间与内存消耗的分析和对比&PHP;‘’里的全部内容。

    猴子选大王 数据结构课设

    任务:一堆猴子都有编号,编号是1,2,3 ...m ,这群猴子(m个)按照1--m的顺序围坐一圈,从第1开始数,每数到第N个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。 要求: 输入...

    数据结构 猴子选大王 C++

    任务:一堆猴子都有编号,编号是1,2,3 ...m ,这群猴子(m个)按照1-m的顺序围坐一圈,从第1开始数,每数到第N个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王。 要求:输入...

Global site tag (gtag.js) - Google Analytics