文档章节

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

a
 acmlover
发布于 2014/01/03 15:16
字数 590
阅读 98
收藏 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
郑州
php 经典的算法题你懂的

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

zchd
2013/06/17
0
0
通过“选出猴王”对struct产生一点疑问,请各位大虾讲解一下。

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

侃侃大仙
2012/11/09
266
3
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

没有更多内容

加载失败,请刷新页面

加载更多

下一页

angular 解决其他电脑不能访问的问题。

ng serve --host 0.0.0.0 --disable-host-check

miaojiangmin
今天
1
0
优酷视频文件怎么转换格式

  以前在优酷上下载视频都只是在手机上观看,但随着科技的发展,对于视频的要求也逐渐增多,不再只是观看视频那么简单,在精彩的部分还会将其单独分割出来,然后进行视频剪辑,可以做出我们...

萤火的萤火
今天
0
0
数据结构:散列

在一个数据结构中查找key元素,用顺序查找、二分查找都需要经过一系列关键之比较才能查找到结果,平均查找长度与数据量有关,元素越多比较次数就越多。 如果根据元素的关键字就能知道元素的存...

京一
今天
0
0
Apache RocketMQ 正式开源分布式事务消息

近日,Apache RocketMQ 社区正式发布4.3版本。此次发布不仅包括提升性能,减少内存使用等原有特性增强,还修复了部分社区提出的若干问题,更重要的是该版本开源了社区最为关心的分布式事务消...

阿里云云栖社区
今天
30
0
使用JavaScript和MQTT开发物联网应用

如果说Java和C#哪个是最好的开发语言,无疑会挑起程序员之间的相互怒怼,那如果说JavaScript是动态性最好的语言,相信大家都不会有太大的争议。随着越来越多的硬件平台和开发板开始支持JavaS...

少年不搬砖老大徒伤悲
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部