文档章节

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

a
 acmlover
发布于 2014/01/03 15:16
字数 590
阅读 93
收藏 0
点赞 0
评论 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
郑州
一天一练之算法——约瑟夫问题

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

_编程菜鸟_ ⋅ 2014/09/03 ⋅ 1

php 经典的算法题你懂的

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

zchd ⋅ 2013/06/17 ⋅ 0

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

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

侃侃大仙 ⋅ 2012/11/09 ⋅ 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 ⋅ 0

用php实现约瑟夫环问题,求指导

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

狂沙lover ⋅ 2014/02/24 ⋅ 4

libevent源码深度剖析

原文地址:http://blog.csdn.net/sparkliang/article/details/4957667 libevent源码深度剖析一 ——序幕 张亮 1 前言 Libevent是一个轻量级的开源高性能网络库,使用者众多,研究者更甚,相关...

晨曦之光 ⋅ 2012/03/09 ⋅ 0

为什么要学习C语言 C语言优势分析

不止一个学生问到我:“老师,为什么我们的应用程序设计要学C语言而不是别的?C语言不是已经过时了吗?如果现在要写一个Windows程序,用VB或Dephi开发多快呀,用C行吗?退一万步,为什么选择C而...

C语言 ⋅ 2017/12/11 ⋅ 0

董付国老师6本Python系列教材被北大、复旦等近百所高校选作教材

2013年,我校计划开设Python程序设计课程,但是市面上已有的教材很难让人满意,要么就是只介绍一点点基本语法没什么案例;要么就是插入大量软件安装截图或者代码运行结果凑篇幅,虽然看起来很...

oh5w6hinug43jvrhhb ⋅ 2017/12/15 ⋅ 0

一个新手小白是怎么安排如何自学C语言/C++程序员、工程师的

谈及C语言,我想C语言功能强大都应该知道、应用广泛,一旦掌握了后,你就可以理直气壮地对他人说“我是电脑高手!”,而且以后若是再自学其他语言就显得轻而易举了。忧虑的是,C语言般博大精...

小辰带你看世界 ⋅ 2017/12/31 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

服务网关过滤器

过滤器作用 我们的微服务应用提供的接口就可以通过统一的API网关入口被客户端访问到了。但是,每个客户端用户请求微服务应用提供的接口时,它们的访问权限往往都需要有一定的限制,系统并不会...

明理萝 ⋅ 21分钟前 ⋅ 1

【2018.06.21学习笔记】【linux高级知识 14.1-14.3】

14.1 NFS介绍 NFS服务全称是NetWork File System:网络文件系统,最早有sun公司开发的,4.0版本由Netapp公司开发,是基于RPC远程过程调用(Remote Procedure Call)协议的服务。 14.2 NFS服务...

lgsxp ⋅ 30分钟前 ⋅ 0

Day18 vim编辑模式、命令模式与练习

编辑模式 命令模式 :nohl 不高亮显示 :x与:wq类似,如果在更改文件之后操作,两者效果一样;如果打开文件,没有任何操作; :wq会更改mtime,但是:x不会。 练习题 扩展 vim的特殊用法 ht...

杉下 ⋅ 33分钟前 ⋅ 0

Enum、EnumMap、EnumSet

1、Enum 不带参数 public enum Car { AUDI { @Override public int getPrice() { return 25000; } }, MERCEDES { ......

职业搬砖20年 ⋅ 34分钟前 ⋅ 0

Java中的锁使用与实现

1.Lock接口 锁是用来控制多个线程访问共享资源的方式,一般来说,一个锁能够防止多个线程同时访问共享资源。 在Lock出现之前,java程序是靠synchronized关键字实现锁功能的,而Java SE5之后,...

ZH-JSON ⋅ 35分钟前 ⋅ 0

线程组和 ThreadLocal

前言 在上面文章中,我们从源码的角度上解析了一下线程池,并且从其 execute 方法开始把线程池中的相关执行流程过了一遍。那么接下来,我们来看一个新的关于线程的知识点:线程组。 线程组 ...

猴亮屏 ⋅ 36分钟前 ⋅ 0

相对路径和绝对路径

基本概念   文件路径就是文件在电脑中的位置,表示文件路径的方式有两种,相对路径和绝对路径。在网页设计中通过路径可以表示链接,插入图像、Flash、CSS文件的位置。   物理路径:物理路...

临江仙卜算子 ⋅ 40分钟前 ⋅ 0

消息队列属性及常见消息队列介绍

什么是消息队列? 消息队列是在消息的传输过程中保存消息的容器,用于接收消息并以文件的方式存储,一个队列的消息可以同时被多个消息消费者消费。分布式消息服务DMS则是分布式的队列系统,消...

中间件小哥 ⋅ 42分钟前 ⋅ 0

java程序员使用web3j进行以太坊开发详解

如何使用web3j为Java应用或Android App增加以太坊区块链支持,教程内容即涉及以太坊中的核心概念,例如账户管理包括账户的创建、钱包创建、交易转账,交易与状态、智能合约开发与交互、过滤器...

笔阁 ⋅ 43分钟前 ⋅ 0

vim编辑模式、vim命令模式

vim编辑模式 使用vim filename 进入的界面是一般模式,在这个模式下虽然我们能够查看,复制,剪切,粘贴,但是不能编辑新的内容,如何能直接写入东西呢?这就需要进入编辑模式了,从一般模式...

李超小牛子 ⋅ 45分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部