Question

求C语言高手帮我做一题：约瑟夫生死者游戏。

[问题描述]
约瑟夫（Joeph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。
[基本要求]
利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。
[测试数据]
m的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。
[实现提示]
程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。设n≤30。此题所用的循环链表中不需要“头结点”,请注意空表和非空表的界限.
[选作内容]
向上述程序中添加在顺序结构上实现的部分。

Answer 1

3 1 #include <stdafx.h>
#include<stdio.h>
struct Node
{
int nSecret ;
int nId ;
Node *pNext ;
} ;
Node *g_pHeader = NULL ;

int main()
{
int M , ns , nCount = 0 , id = 0;
bool bHeader = false ;
// input process ...
printf(" please input the maxmmum value of M : ");
scanf("%d",&M) ;
printf(" please input the secret id and zero over : " ) ;
Node *p = NULL , *last = NULL ;
while( scanf("%d",&ns) && ns != 0 )
{
id++ ;
Node *q = new Node ; // malloc( sizeof( Node ) ) ...
q->nSecret = ns ;
q->nId = id ;
if( !bHeader )
{
bHeader = true ;
p = g_pHeader = q ;
p->pNext = g_pHeader ;
}
else
{
p->pNext = q ;
p = q ;
p->pNext = g_pHeader ;
}
}
// dispose process ...
last = p ; // 最后一个
p = g_pHeader ; // 第一个
while( p != NULL )
{
nCount++ ;
if( last == p )
{
printf("%-4d", p->nId ) ;
delete p ; // free(p)
break ;
}
else if( nCount % M == 0 )
{
// 删除p
M = p->nSecret ;
last->pNext = p->pNext ;
printf("%-4d", p->nId ) ;
delete p ;
p = last->pNext ;
nCount = 0 ;
}
else
{
last = p ;
p = p->pNext ;
}
}
return 0 ;
}

Answer 2

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

typedef struct people
{
int num;
int code;
struct people *next;
}*LinkPtr, Node, *NodePtr;

//创建链表
LinkPtr createLink(int p_num)
{
int i;
LinkPtr head;
NodePtr p;
//头结点
head=(NodePtr)malloc(sizeof(Node));
p=head;
//创建结点，并输入密码
for(i=1; i<=p_num; i++)
{
p->next = (NodePtr)malloc(sizeof(Node));
p=p->next;
p->num = i;
printf("\n输入编号%d密码:",i);
scanf("%d",&p->code);
}
//链表成环
p->next = head->next;
return head;
}

//T除报到m值的人，并按其密码修改m值
void deleteNode(NodePtr p, NodePtr q, int *m)
{
q->next = p->next;
*m = p->code;
printf("%d ",p->num);
free(p);
p=NULL;

}

void josphGame(LinkPtr head, int m)
{
NodePtr p,q;
int i=0;
int j=0;
int record = 0;
p = head;
while(1)
{
//判断游戏是否结束，即所有人出局
if(p->next==p)
{
printf("%d ",p->num);
break;
}
//报数
for(i=0;i<m; i++)
{
q=p;
p=p->next;
}
//T除报到m数的人
deleteNode(p,q,&m);
p=q;

}
}

void main()
{
int m = 0;
int p_num;
LinkPtr head=NULL;
printf("输入m值:");
scanf("%d",&m);
printf("输入人数:");
scanf("%d", &p_num);
head = createLink(p_num);
printf("输出编号:\n");
//游戏开始运行
josphGame(head,m);
printf("\n");
system("PAUSE");

}

运行结果：
输入m值:20
输入人数:7

输入编号1密码:3

输入编号2密码:1

输入编号3密码:7

输入编号4密码:2

输入编号5密码:4

输入编号6密码:8

输入编号7密码:4
输出编号:
6 1 4 7 2 3 5

写完了..花了一个多小时- -实力不行啊

Answer 3

怎么会有这么多约瑟夫问题

Answer 4

晚点打给你啊，太长了