文档章节

C语言程序设计-猴子选大王[链表应用]

a
 acmlover
发布于 2014/01/03 15:16
字数 590
阅读 106
收藏 0

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;
}

转自:http://www.acmerblog.com/c-programing-2-2508/

本文转载自:

共有 人打赏支持
a
粉丝 0
博文 1
码字总数 0
作品 0
郑州
私信 提问
通过“选出猴王”对struct产生一点疑问,请各位大虾讲解一下。

最近在恶补c语言,昨天在做一个“选出猴王”的小练习题,应该也有人遇到过这个题,大概就是好多猴子围成一圈,编成号,从1-N,然后从1号开始报数,顺时针猴子依次报数加1,如果有猴子报的数字...

侃侃大仙
2012/11/09
355
3
全国青少年信息学奥林匹克分区联赛(NOIP)竞赛大纲

(#表示普及组不涉及) 一、初赛内容与要求 (一)计算机的基本常识 诞生与发展 特点 在现代社会中的应用 计算机系统的基本组成 计算机的工作原理# 计算机中的数的表示 计算机信息安全基础知...

海天一树X
11/06
0
0
php 经典的算法题你懂的

有5个人偷了一堆苹果,准备在第二天分赃。晚上,有一人遛出来,把所有菜果分成5份,但是多了一个,顺手把这个扔给树上的猴了,自己先拿1/5藏了。没想到其他四人也都是这么想的,都如第一个人...

zchd
2013/06/17
0
0
PHP常见的算法

1:快速排序 <?php function quick_sort($array) { if(count($array) <= 1) { return $array; } $left_arr = array(); $right_arr = array(); $key = $array[0];......

雨醉风尘
2016/02/29
31
0
用php实现约瑟夫环问题,求指导

问题:一群猴子排成一圈,按 1,2,...,n 依次编号。然后从第 1 只开始数,数到第 m 只,把它踢出圈,从它后面再开始数, 再数到第 m 只,在把它踢出去...,如此不停的进行下去, 直到最后只剩下...

狂沙lover
2014/02/24
1K
4

没有更多内容

加载失败,请刷新页面

加载更多

SpringBoot整合Mybatis扫描不到Mapper的问题

参考资料 1、SpringBoot整合Mybatis扫描不到Mapper的问题

哎小艾
17分钟前
4
0
网络相关.md

https://github.com/acBool/Blogs/blob/master/%E7%BD%91%E7%BB%9C%E7%9B%B8%E5%85%B3/%E7%BD%91%E7%BB%9C%E7%9B%B8%E5%85%B3.md URL URL: 全称Uniform Resource Location,统一资源定位符,......

壹峰
17分钟前
1
0
Ubuntu虚拟机无法连接到网络

查看本机中控制面板---管理工具---服务 找到服务(本地) 确保 VMware DHCP Service 和VMware NAT Service 服务已经启动 查看Ubuntu的ip地址 显示ip则连接成功...

唐十三郎
23分钟前
0
0
MyEclipse开发教程:REST Web Service(二)

MyEclipse 在线订购年终抄底促销!火爆开抢>> MyEclipse最新版下载 使用MyEclipse开发RESTWeb服务来放大您的Web应用程序。在本教程示例中,您将创建一个简单的Web服务来维护客户列表。你将学...

电池盒
24分钟前
0
0
线程sleep和yield的区别

1.sleep()方法暂停当前线程后,会给其他线程执行机会,线程优先级对此没有影响。yield()方法会给优先级相同或更高的线程更高的执行机会。 2.sleep()方法会将线程转入阻塞状态,直到阻塞时间结...

勇敢的飞石
24分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部