要求:用c语言编程。
用数组去模拟一下就可以了
#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);
}