首页 > 专题系列 > C基础练习 > C语言程序设计-猴子选大王[链表应用]
2013
12-18

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

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

 

 


  1. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。

  2. 第23行:
    hash = -1是否应该改成hash[s ] = -1

    因为是要把从字符串s的start位到当前位在hash中重置

    修改提交后能accept,但是不修改居然也能accept

  3. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  4. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  5. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。