当前位置: 代码迷 >> C语言 >> [求助]一个圆桌找人问题
  详细解决方案

[求助]一个圆桌找人问题

热度:452   发布时间:2006-08-23 22:57:13.0
[求助]一个圆桌找人问题
问题:有13个人,分别标号为1到13,按顺序围绕圆桌坐下,从第一个人开始按顺序数数:1,2,3,数到3的人退出,再从下一个人重新开始数,问最后剩下的两个人是多少号?
要求:用c语言编程。
搜索更多相关的解决方案: 圆桌  顺序  c语言  数数  

----------------解决方案--------------------------------------------------------

用数组去模拟一下就可以了


----------------解决方案--------------------------------------------------------
我觉得你应该baidu一下
----------------解决方案--------------------------------------------------------

希望能够有个比较详细的解答


----------------解决方案--------------------------------------------------------
记得以前已经讨论过这个问题了,
你看一下,有详细的程序解释。
[URL=http://www.bc-cn.net/blog/user1/2260/archives/2006/1083.shtml]http://www.bc-cn.net/blog/user1/2260/archives/2006/1083.shtml[/URL]
----------------解决方案--------------------------------------------------------


#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

#define MAX 13 //圆桌围的最大人数

typedef struct Node{//定义节点
int inum;
struct Node *next;
}Node;

int _tmain(int argc, _TCHAR* argv[])
{
Node *pHead = (Node *)malloc(sizeof(Node));//申请头节点,这个节点是多余的,可以不用头节点
if(pHead == NULL)
{
printf("pHead Malloc Error!!");
exit(-1);
}
pHead->inum = MAX;
pHead->next = NULL;
for(int i = MAX; i > 0; i--)
{//为每个人申请一个节点,并围成一个圈 
Node *pNode = (Node *)malloc(sizeof(Node));
if(pNode == NULL)
{
printf("pNode[%d] Malloc Error!!",i);
exit(-1);
}
pNode->next = pHead->next;
pHead->next = pNode;
pNode->inum = i;
}
Node *pNode;
for(pNode = pHead; pNode->next; pNode = pNode->next); //找最后一个节点
pNode->next = pHead;//把最后一个节点指向头节点

int icount = MAX;
pNode = pHead->next;//pNode为删除后的第一个节点,最开始指向第一个节点
Node *pPre = pHead;//pPre指向pNode的前一个节点
while(icount > 2)//直到找到剩两个节点时截止
{
for(int inum = 0; inum < 2; inum++)
{ //找到下一个要删除的节点
pPre = pNode;
pNode = pNode->next;
if(pNode == pHead)
{//如果是头指针,则跳过
pPre = pNode;
pNode = pNode->next;
}
}
pPre->next = pNode->next;
free(pNode);
pNode = pPre->next;
if(pNode == pHead)
{//如果是头指针,则跳过
pPre = pNode;
pNode = pNode->next;
}
icount--;
}
printf("%d,%d\n",pHead->next->inum,pHead->next->next->inum);
free(pHead);
_getch();
return 0;
}


----------------解决方案--------------------------------------------------------
上楼用链表,强!!!!!!!!!!!!
根本就不要用吗

----------------解决方案--------------------------------------------------------

我在IT一粟-[玩的博客民工]博客上发现一种用递归求解的方法,如下:
n个人报数的问题,可以使用c语言进行简单的递归实现。


问题描述:

n个人围成一个圈,编号为1~n,从第1号开始报数,报到3的倍数的人离开(即每数到第三个就离开),一直数下去,直到最后只剩下1人。求剩下的这个人的原始编号。

问题理解:

在将这个问题转化为编程解决的时候,需要考虑如下几个问题:

1. 使用数组来存放人。假设人的数目为count,为了编程的方便,人的编号从0到count-1,只需要在最后输出的时候加上1就可以。

2. 对“数到三的人离开”的理解:编程解决的时候,我们应当将“离开”转化为程序表示,因此可以在初始化数组时将各个元素设为默认值1表示未离开,设为0表示此人已经离开。

3. 正因为我们的“离开”不是数组里某个元素的消失,而只是其值的改变,故在不断往下数的时候,可能会遇到值不为0的元素,因此需要设置一个变量来记录是否数了三个值不为0的元素。

4. 使用一个计数器now来表示当前数到几,now初值为0,数到下一个元素时不管其值是否为0,都增加一。因此假设剩下最后一个人,要求其原始编号,只需要用now%count即可。


编程实现:

根据上述理解,可以得到下面的C语言递归实现:

#i nclude <stdio.h>

#define COUNT 4 /*人的数目可在此更改*/

/*

功能:计算出最后剩余的人的编号,从0到count-1

参数:peopele[] : 存放人的数组

Count : 共有多少个人

Now : 当前数到了几,从0开始,不断往上增加

Left : 当前还剩下几人没’离开’,范围为1-count

返回:返回值为最后剩余的人的编号,从0到count-1

*/

int func(int people[], int count, int now, int left) {

if (left <= 1) {

/*如果只剩下一个人没走开,但now当前标识的元素可能值为0,故要寻找从

now开始的第一个值不为0的元素*/

for (;people[now%count]==0;now++);

/*返回该编号*/

return now%count;

}

else {

/*如果还剩下1人以上,则往下数三个值还不为0的元素*/

/*i用来标识是否数了三个*/

int i = 0;

for (;i<3;now++)

/*不论数到的元素值是否为0,now都要增加1,但i则需要元素值不为0才能增加1*/

people[now%count] == 0 ?i :i++ ;

/*将第三人设为0表示已走开*/

people[(now-1)%count] = 0;

/*还没’离开’的人数减1*/

left--;

/*开始新的递归*/

return func(people,count,now,left);

}

}

/*功能:调用递归函数func()*/

void main() {

/*初始化人的数组,编号从0开始,到count-1*/

int people[COUNT];

int i;

/*各元素初始值为1,表示都未离开*/

for (i=0; i<COUNT; i++)

people[i] = 1;

/*输出计算结果,因为编号从0开始,故输出时加1*/

printf ("%d\n",func(people,COUNT,1,COUNT)+1);

}


----------------解决方案--------------------------------------------------------
谢谢lyn_gemini和hrp313。
----------------解决方案--------------------------------------------------------
  相关解决方案