精华内容
下载资源
问答
  • 2032 猴子选大王Description有N只猴子,从1~N进行编号。它们按照编号的顺时针方向排成一个圆圈,然后从第一只猴子开始报数。第一只猴子报的第一个数字为1,以后每只猴子报的数字都是它们前面猴子所报数字加1。如果一...

    2032 猴子选大王

    Description

    有N只猴子,从1~N进行编号。它们按照编号的顺时针方向排成一个圆圈,然后从第一只猴子开始报数。第一只猴子报的第一个数字为1,以后每只猴子报的数字都是它们前面猴子所报数字加1。如果一个猴子报的数字是M,则该猴子出列,下一个猴子重新从1开始报数,直到所有猴子都出列为止,最后一个出列的猴子胜出。你的任务是对于给定猴子数量和报数上限值M,确定出能够被选作大王的猴子的编号。

    Input

    第一行为一个整数N,表示测试数据的组数,接下来的N行中每行包含两个整数,第一个数是猴子的个数,第二个数是报数上限值M(M>1),两数之间由空格分隔。

    Output

    输出共N行,每行为对应输入行获胜猴子的编号。

    Sample Input

    2

    8 5

    5 8

    Sample Output

    3

    1

    #include 

    #include 

    /* 定义链表节点类型 */

    typedef struct node

    {

    int data;

    struct node *next;

    }linklist;

    int creat(int n, int m)

    {

    linklist *head, *p, *s, *q;

    int i,  total;

    /* 创建循环链表,头节点也存信息 */

    head = (linklist*) malloc(sizeof(linklist));

    p = head;

    p->data = 1;

    p->next = p;

    /* 初始化循环链表 */

    for (i = 2; i <= n; i++)

    {

    s = (linklist*) malloc(sizeof(linklist));

    s->data = i;

    s->next = p->next;

    p->next = s;

    p = p->next;

    }

    p = head;

    /* 保存节点总数 */

    total = n;

    q = head;

    /* 只剩一个节点时停止循环 */

    while (total != 1)

    {

    /* 报数过程,p指向要删除的节点 */

    for (i = 1; i 

    {

    p = p->next;

    }

    /* q 指向 p 节点的前驱 */

    while (q->next != p)

    {

    q = q->next;

    }

    /* 删除 p 节点 */

    q->next = p->next;

    /* 保存被删除节点指针 */

    s = p;

    /* p 指向被删除节点的后继 */

    p = p->next;

    /* 释放被删除的节点 */

    free(s);

    /* 节点个数减一 */

    total--;

    }

    //free(p);

    /* 打印最后剩下的节点序号 */

    int vsdata=p->data;

    free(p);

    return vsdata;

    }

    int  main()

    {

    int  n[10], m[10];

    /* 读入问题条件 */

    int k;

    scanf("%d", &k);

    for (int i=0;i

    {

    scanf("%d%d",&n[i],&m[i]);

    }

    for (int ii=0;ii

    {

    printf("%d\n",creat(n[ii],m[ii]));

    }

    return 0;

    }

    展开全文
  • n只猴子选大王,选举办法如下:所有猴子按1、2、3、……、n编号围坐一圈,从第1号开始按照1、2、3、……、m报数,凡报m号的退出圈外,如此循环报数,直到圈内剩下一只猴子时,这只猴子就是大王。n和m由键盘输入,...

    n只猴子要选大王,选举办法如下:所有猴子按1、2、3、……、n编号围坐一圈,从第1号开始按照1、2、3、……、m报数,凡报m号的退出圈外,如此循环报数,直到圈内剩下一只猴子时,这只猴子就是大王。n和m由键盘输入,打印出最后剩下的猴子号码。

    如果用单向循环链表实现。

    //循环链表
    #include<stdio.h>
    typedef struct node
    {
        struct node *next;
        int data;
    }Li;
    //初始化循环链表
    Li *Init()
    {
        Li *L;
        L=(Li*)malloc(sizeof(Li));
        L->data=1;
        L->next=L;
        return L;
    }
    //尾插法 因为顺序和插入顺序一样
    Li* Insert(Li *r,int e)
    {
        Li *q;//r指向最后结点
        q=(Li*)malloc(sizeof(Li));
        q->data=e;
        //r->next=q;错误 单链表插入先动后在动前 警示
        //q->next=r;错误
        q->next=r->next;
        r->next=q;
        r=q;//r永远指向尾结点
        return r;
    }
    void Creat(Li *l,int e)
    {
        Li *r=l;//r为尾结点
        int n;
        for(n=2;n<=e;n++)
        {
            r=Insert(r,n);
        }
    }
    void Dawang(Li *l,int k)//k为每次删除的位置 n为多少只猴子
    {
        Li *p=l,*q;
        int j;//计数器
        while(p->next!=p)
        {
            j=1;
            while(j<k-1)//找到k-1的结点
            {
                p=p->next;
                j++;
            }
            //删除第n个结点
            q=p->next;
            p->next=q->next;
            free(q);
            //
            p=p->next;
        }
        printf("\n被选出来的大王为%d\n",p->data);
    
    }
    int main()
    {
        Li *L;
        int j,k,n;
        L=Init();
        printf("输入有多少只猴子和要删除个数");
        scanf("%d%d",&n,&k);
        Creat(L,n);
        Dawang(L,k);
    }
    

     如果用单链表实现,不用循环的写法(实际上也是循环的思路)

    #include<stdio.h>
    #include<stdlib.h>
    typedef struct node
    {
        struct node *next;
        int data;
    }Li;
    //初始化循环链表
    Li *Init()
    {
        Li *L;
        L=(Li*)malloc(sizeof(Li));
        L->next=NULL;
        return L;
    }
    
    //尾插法 因为顺序和插入顺序一样
    Li* Insert(Li *r,int e)
    {
        Li *q;//r指向最后结点
        q=(Li*)malloc(sizeof(Li));
        q->data=e;
        r->next=q;
        q->next=NULL;
        r=q;//r永远指向尾结点
        return r;
    }
    void Creat(Li *l,int e)//创建单链表
    {
        Li *r=l;//r为尾结点
        int n,j;
        for(n=1;n<=e;n++)
        {
            r=Insert(r,n);
        }
    }
    void deleted(Li *l,int i)//删除结点使用
    {
         Li *p=l,*q;
        int j=0;
        //寻找i-1结点
        while(p->next&&j<i-1)
        {
            p=p->next;
            j++;
        }
        //删除点没有找到
        if(j>i-1)
        {
            printf("error");
            return 0;
        }
        q=p->next;
        p->next=q->next;
        free(q);
    }
    void dawang(Li *l,int k,int n)//k为每次删除的猴子 n为多少只猴子
    {
        Li *p=l,*q=l;
        int m=0;//计数器
        int i;
        while(1)
        {
            q=q->next;
            m++;
            //第一 找删除位置 两种情况 在中间某个位置 或要删除的结点在单链表的首结点
            if(m==k-1)//定位到m-1个结点后将m结点删除,然后继续开始从1开始计数
            {
                if(q->next!=NULL)
                {
                    deleted(q,1);
                    //printf("%d  **\n",q->data);
                    m=0;
                    n--;//猴子数量减去一
                }
                else
                {
                    deleted(p,1);//删除首结点位置
                    q=p;//p指针指向q的位置
                    m=0;
                    n--;
                }
            }
            //第二 要看路上计数时到达尾部 那么就重新指向首结点
            if(q->next==NULL)//走到头了以后回到起点
            {
                q=p;//p永远指向首结点,作用就是给q赋
            }
            if(n==1)//当n猴子删成只有一个了就终止循环
            {
                break;
            }
        }
        printf("猴王是:%d号\n",p->next->data);
    }
    /*void bianli(Li *L)
    {
    
        Li *p=L->next;
        printf("单链表为:");
        while(p)
        {
            printf("%d ",p->data);
            p=p->next;
        }
        printf("\n");
    }*/
    int main()
    {
        Li *L;
        int j,k,n;
        L=Init();
        printf("输入有多少只猴子和位置");
        scanf("%d%d",&n,&k);
        Creat(L,n);
        dawang(L,k,n);
    }
    

    两种方法,都可出来结果

    输入有多少只猴子和位置10 4
    猴王是:5号

    结束;

    展开全文
  • 循环链表 猴子选大王

    千次阅读 2015-02-27 18:05:00
    猴子选大王 */ #include #include typedef struct monkey { int num; struct monkey * next; } monkey_t; //head指向第一个节点,tail指向最后一个节点 monkey_t *head = NULL, *tail = NULL; void create(in
    /*
        循环链表
        猴子选大王
    */
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct monkey {
        int num;
        struct monkey * next;
    } monkey_t;
    //head指向第一个节点,tail指向最后一个节点
    monkey_t *head = NULL, *tail = NULL;
    
    void create(int nn) {   //猴子的个数
        int i;
        monkey_t *p = NULL, *q = NULL;  //p指向一个新分配的节点,q指向当前最后一个节点
    
        p = (monkey_t *)malloc(sizeof (monkey_t));
        p->num = 1;
        p->next = NULL;
        head = p;
        q = p;
        for (i = 2; i <= nn; i++) {
            p = (monkey_t *)malloc(sizeof (monkey_t));
            p->num = i;
            p->next = NULL;
            q->next = p;
            q = p;
        }
        tail = q;
        tail->next = head;  //形成闭环
    }
    
    int select(int mm) {
        int x = 0, res;
        monkey_t *p = NULL, *q = NULL;  //p指向当前要判断的节点,q跟随在p的后面,比p慢一拍
    
        q = tail;
        do {
            p = q->next;    //定位p
            x++;
            if (x % mm == 0) {
                printf("The deleted monkey's number is No.%d\n", p->num);
                q->next = p->next;
                free(p);
                //p = NULL;
            } else {
                q = p;  //q跟进一步
            }
        } while (q != q->next); //循环直到只剩下一个节点
        //head = q;
        res = q->num;
        free(q);
        return res;
    }
    
    int main() {
        int n, m;
    
        printf("Please input the number of monkey.\n");
        scanf("%d", &n);
        printf("Please input the number of interval m.\n");
        scanf("%d", &m);
    
        create(n);
        printf("monkey king is No.%d\n", select(m));
        return 0;
    }
    
    
    
    

    展开全文
  • 猴子选大王的源码,这是用循环链表做的,可不是用数组做的哦。
  • 2032 猴子选大王 Description 有N只猴子,从1~N进行编号。它们按照编号的顺时针方向排成一个圆圈,然后从第一只猴子开始报数。第一只猴子报的第一个数字为1,以后每只猴子报的数字都是它们前面猴子所报数字加1。...

    2032 猴子选大王

    Description

    有N只猴子,从1~N进行编号。它们按照编号的顺时针方向排成一个圆圈,然后从第一只猴子开始报数。第一只猴子报的第一个数字为1,以后每只猴子报的数字都是它们前面猴子所报数字加1。如果一个猴子报的数字是M,则该猴子出列,下一个猴子重新从1开始报数,直到所有猴子都出列为止,最后一个出列的猴子胜出。你的任务是对于给定猴子数量和报数上限值M,确定出能够被选作大王的猴子的编号。

    Input

    第一行为一个整数N,表示测试数据的组数,接下来的N行中每行包含两个整数,第一个数是猴子的个数,第二个数是报数上限值M(M>1),两数之间由空格分隔。

    Output

    输出共N行,每行为对应输入行获胜猴子的编号。

    Sample Input

    2

    8 5

    5 8

    Sample Output

    3

    1

     

    #include <stdio.h>
    #include <stdlib.h>
    
    /* 定义链表节点类型 */
    typedef struct node
    {
        int data;
        struct node *next;
    }linklist;
    
    int creat(int n, int m)
    {
     linklist *head, *p, *s, *q;
     int i,  total;
     /* 创建循环链表,头节点也存信息 */
        head = (linklist*) malloc(sizeof(linklist));
        p = head;
        p->data = 1;
        p->next = p;
        /* 初始化循环链表 */
        for (i = 2; i <= n; i++)
        {
            s = (linklist*) malloc(sizeof(linklist));
            s->data = i;
            s->next = p->next;
            p->next = s;
            p = p->next;
        }
    
        p = head;
    
        /* 保存节点总数 */
        total = n;
    
        q = head;
        /* 只剩一个节点时停止循环 */
        while (total != 1)
        {
            /* 报数过程,p指向要删除的节点 */
            for (i = 1; i < m; i++)
            {
                p = p->next;
            }
    
            /* q 指向 p 节点的前驱 */
            while (q->next != p)
            {
                q = q->next;
            }
            /* 删除 p 节点 */
            q->next = p->next;
            /* 保存被删除节点指针 */
            s = p;
            /* p 指向被删除节点的后继 */
            p = p->next;
            /* 释放被删除的节点 */
            free(s);
            /* 节点个数减一 */
            total--;
        }
    	//free(p);
        /* 打印最后剩下的节点序号 */
    	int vsdata=p->data;
    	free(p);
    	return vsdata;
    
    }
    int  main()
    {
        int  n[10], m[10];
        /* 读入问题条件 */
        int k;
    
        scanf("%d", &k);
    
    	for (int i=0;i<k;i++)
    	{
    		scanf("%d%d",&n[i],&m[i]);
    	}
    	for (int ii=0;ii<k;ii++)
    	{
    		 printf("%d\n",creat(n[ii],m[ii]));
    	}
    
    	return 0;
    }
    

      

    转载于:https://www.cnblogs.com/love533/p/3493168.html

    展开全文
  • /* *Copyright (c) 2017,烟台大学计算机与控制工程学院 *All rights reserved. *文件名称:项目5- 一群猴子
  • 题目:猴子选大王,现有n个猴子,一开始从第k个猴子开始从1开始报数,报到t的猴子会被淘汰,然后又从它的下一个猴子从1开始报数,如此循环,一直到只剩下一个猴子,这个猴子就是大王了,求得每次被淘汰猴子的编号及...
  • 之前写过用回溯算法解决猴子选大王的博客,前几天学了循环链表,所以打算用循环链表解决一下该问题,下面给各位看官上代码: #include <stdio.h> #include <stdlib.h> typedef struct node { int num;/...
  • /* ...  * All rights reserved.  * 文件名称:test.cpp  * 作 者:李晓凯 ... * 问题描述:一群猴子,编号是1,2,3…m,这群猴子(m个)按照1-m的顺序围坐一圈,从第一只开始数,每数到第n个,该猴
  • 循环链表是指最后一个空间指向头节点的链表类型,可以用于需要在多个数据之间来回循环的题目,比如约瑟夫问题(上面这道就是约瑟夫问题的改版)。普通约瑟夫问题可以用数组做,如上面这道题,用数组做就是这样: ..
  • 问题及代码: /* ...* All rights reserved. * 文件名称:Project4.cpp * 作 者:李楠 * 完成日期:2015年1月21...* 问题描述:一群猴子,编号是1,2,3,...m,这群猴子(m个)按照1-m的顺序围坐一圈。 从第1个开始数。每
  • 如此不断循环,最后剩下的一只猴子为猴王。请问是原来第几号猴子当选猴王?输入输入在一行中给一个正整数N(<=1000)。输出在一行中输出当选猴王的编号。样例输入11样例输出7AC代码如下:#...
  • 有n只猴子,按顺时针方向围成一圈选大王(编号从1到n),从第1号开始报数,一直数到m,数到m的猴子退出圈外,剩下的猴子再接着从1开始报数。就这样,直到圈内只剩下一只猴子时,这个猴子就是猴王,编程求输入n,m后...
  • } **循环链表:**通过猴子选大王的题目来写 题目: ( 100分 ) 具体要求如下: 让 N 只候选猴子围成一圈(最多100只猴子),从某位置起顺序编号为 1 ~ N 号;从第 1 号开始报数,每轮从 1 报到 3 ,凡报到 3 的猴子...
  • 如此不断循环,最后剩下的一只猴子为猴王。请输出猴子退出圈子的次序以及当选的猴王编号。 函数接口定义 int KingOfMonkey(int n,linklist *head); 裁判测试程序样例: #include <stdio
  • 循环链表---猴子选大王

    千次阅读 2010-03-24 15:47:00
    谢谢合作 题目描述:n只猴子选大王,选举方法如下:所有猴子按 1,2 ……… n 编号并按照顺序围成一圈,从第 k 个猴子起,由1开始报数,报到m时,该猴子就跳出圈外,下一只猴子再次由1开始报数,如此循环,直到圈...
  • 1 描述:一群猴子新猴王。新猴王的选择方法是:让N只候选猴子围成一圈,从某位置起顺序编号为1~N号。从第1号开始报数,每轮从1报到3,凡报到3...3 //用循环链表4 #include5 #include67 typedef struct node8 {9 ...
  • 学C语言中的链表必写的的一个程序哦。对于入门者非常非常有用。对于围成圆圈数数也适用。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 698
精华内容 279
关键字:

猴子选大王循环链表