有20个学生依次从0到19编号，从第一个同学开始报数，从1报到3，凡是报到3的同学出列，剩下的同学还是按照1、2、3的次序报数，编程求出最后出列的同学的编号
怎么用一维数组来编呀？高手指点^_^
----------------解决方案--------------------------------------------------------
这个问题是很经典的,也是有名字的,称做josephus问题~
#include<stdio.h>
#include<conio.h>
main()
{
int num=10; //假设有10个小孩
int interval; //报的数
int a[num],i;
char flag='y';
while(flag=='y')
{
for(i=0;i<num;i++) //给孩子编号
{
a[i]=i+1;
printf("%d ",a[i]);
}
printf("\nplease enter the interval : ");
scanf("%d",&interval);
int k=1,j; //k表示第几个小孩,当k==num时,表示结束
i=-1;
while(1)
{
for(j=0;j<interval;)
{
i=(i+1)%num;
if(a[i]!=0)
j++;
}
if(k==num) break;
printf("%d ",a[i]);
a[i]=0; //表示孩子已经离开
k++;
}
printf("\nthe last one is : %d" ,a[i]);
printf("\ncontinue? y/n\n\n");
flag=getch();
}
}
----------------解决方案--------------------------------------------------------
想不到，这么快就有回复了，而且相当详细。
太激动了……
----------------解决方案--------------------------------------------------------
这个问题用循环链表实现起来很简单
----------------解决方案--------------------------------------------------------
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct LNode{
int data ;
struct LNode next;
}LNode,*LinkList;
int find_list(LinkList &L,int n)
{
int j=0;
L=(LinkList)malloc(sizeof(LNode));
LinkList p,q;
p=(LinkList)malloc(sizeof(LNode));
q=L;
for(int i=0;i<n;i++)//给循环链表赋值
{
p->data=i+1;
L->next=p;
L=p;
}
L->next=q;
L=L->next;
free(p);
while(L->next!=L)
{
L=L->next;
j++;
if(j==3)
{
L->next=L->next->next;//删除报3的人
}
}
return L->data;//返回最后一个人的编号
}
----------------解决方案--------------------------------------------------------
这个问题这个论坛上有很多人问过拉
感觉用连表要懂点 呵呵
----------------解决方案--------------------------------------------------------
原题：
用户输入M,N值，从1至N开始顺序循环数数，每数到M输出该数值，直至全部输出。写出C程序。（约瑟夫环问题 Josephus）
提示：
由于当某个人退出圆圈后，报数的工作要从下一个人开始继续，剩下的人仍然是围成一个圆圈的，可以使用循环表，由于退出圆
圈的工作对应着表中结点的删除操作，对于这种删除操作频繁的情况，选用效率较高的链表结构，为了程序指针每一次都指向一个具
体的代表一个人的结点而不需要判断，链表不带头结点。所以，对于所有人围成的圆圈所对应的数据结构采用一个不带头结点的循环
链表来描述。设头指针为p，并根据具体情况移动。
为了记录退出的人的先后顺序，采用一个顺序表进行存储。程序结束后再输出依次退出的人的编号顺序。由于只记录各个结点的
number值就可以，所以定义一个整型一维数组。如：int quit[n];n为一个根据实际问题定义的一个足够大的整数。
代码：
/********************************************************************
created: 2006/06/14
filename: C:\Documents and Settings\Administrator\桌面\tmpp\josephus.c
file path: C:\Documents and Settings\Administrator\桌面\tmpp
file base: josephus
file ext: c
author: A.TNG
version: 0.0.1
purpose: 实现 Josephus 环问题
用户输入M,N值，从1至N开始顺序循环数数，每数到M输出该数值，
直至全部输出。写出C程序。（约瑟夫环问题 Josephus）
*********************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
/* 结构体和函数声明 */
typedef struct _node_t
{
int n_num;
struct _node_t *next;
} node_t;
node_t *node_t_create(int n);
node_t *node_t_get(node_t **pn, int m);
/* 功能函数实现 */
/*
* name: node_t_create
* params:
* n [in] 输入要构造的链表的个数
* return:
* 返回构造成功的环形单向链表指针
* notes:
* 构造节点数量为 n 的环形单向链表
*
* author: A.TNG 2006/06/14 17:56
*/
node_t * node_t_create(int n)
{
node_t *p_ret = NULL;
if (0 != n)
{
int n_idx = 1;
node_t *p_node = NULL;
/* 构造 n 个 node_t */
p_node = (node_t *) malloc(n * sizeof(node_t));
if (NULL == p_node)
return NULL;
else
memset(p_node, 0, n * sizeof(node_t));
/* 内存空间申请成功 */
p_ret = p_node;
for (; n_idx < n; n_idx++)
{
p_node->n_num = n_idx;
p_node->next = p_node + 1;
p_node = p_node->next;
}
p_node->n_num = n;
p_node->next = p_ret;
}
return p_ret;
}
/*
* name: main
* params:
* none
* return:
* int
* notes:
* main function
*
* author: A.TNG 2006/06/14 18:11
*/
int main()
{
int n, m;
node_t *p_list, *p_iter;
n = 20; m = 6;
/* 构造环形单向链表 */
p_list = node_t_create(n);
/* Josephus 循环取数 */
p_iter = p_list;
m %= n;
while (p_iter != p_iter->next)
{
int i = 1;
/* 取到第 m-1 个节点 */
for (; i < m - 1; i++)
{
p_iter = p_iter->next;
}
/* 输出第 m 个节点的值 */
printf("%d\n", p_iter->next->n_num);
/* 从链表中删除第 m 个节点 */
p_iter->next = p_iter->next->next;
p_iter = p_iter->next;
}
printf("%d\n", p_iter->n_num);
/* 释放申请的空间 */
free(p_list);
system("PAUSE");
}
----------------解决方案--------------------------------------------------------