100分求一算法
杀人游戏
N个人坐成一圈玩杀人游戏，按顺时针编号 1 2 3 4 ... ...
从1号开始顺时针开始数到第m号就杀掉第一个人，被杀掉的人要退出游戏。
如果数到了编号的末尾，就逆时针方向继续数，如果又数到了编号的开头，就恢复顺时针继续。
重复，直至杀掉所有人，当剩下最后一个人时，游戏结束，聪明的你能告诉我活到最后的幸存者最初的编号是多少吗？
输入数据：N、M
输出数据：幸存者的编号
考核标准：技术语言不限，程序输出结果必须正确，内存使用越少越好，程序的执行时间越快越好。
[解决办法]
http://www.emsky.net/bbs/read.php?tid=14977
http://topic.csdn.net/t/20030226/09/1466709.html
[解决办法]
最基本的方法是： 循环链表。
如果想效率高又要代码量小，就找找数学规律吧。（考虑用数组）
[解决办法]
这是约瑟夫环的变形问题
可以用循环单链表来做，当然也可以用数组，呵呵。
[解决办法]
约瑟夫环,
根据楼主的要求,应该用双向循环链表来实现
[解决办法]
以前玩ACM时候看到过～
[解决办法]
应该使用双向链表
如果数到了编号的末尾，就逆时针方向继续数，如果又数到了编号的开头，就恢复顺时针继续。
不用循环的
[解决办法]
楼上的理解错了，怎么可能会逆序呢？
[解决办法]
#include <stdio.h>
#include <stdlib.h>
#define N 5
#define M 3
struct node
{
int v;
struct node *next;
}*p,*head,*c;
struct node* run(struct node* head, int value)
{
struct node* p=head;
struct node* p2 = NULL;
while (p!=p-> next)
{
int i=0;
for ( ;i <value-2; ++i)
{
p = p-> next;
}
p2 = p-> next;
p-> next = p-> next-> next;
p = p-> next;
free(p2);
}
return p;
}
int main()
{
c = (struct node*)malloc(sizeof(struct node));
c-> v = 1;
c-> next = NULL;
head = c;
p = c;
int i=2;
for( ;i <=N; ++i)
{
c = (struct node*)malloc(sizeof(struct node));
c-> v = i;
c-> next = NULL;
p-> next = c;
p=c;
}
c-> next = head;
/*struct node* pp = head;
for (i=0; i <30; ++i)
{
printf( "%d\n ",pp-> v);
pp = pp-> next;
}*/
printf( "%d ",run(head,M)-> v);
system( "pause ");
return 0;
}
[解决办法]
时间复杂度最好,空间复杂度也最好的方法是一个递规式.
看具体数学的第一章约瑟夫环.上面总结了一个递规式.
自己去实现吧.
[解决办法]
/*约瑟夫环,没有头结点*/
#include <conio.h>
#include <stdlib.h>
typedef struct node
{
int data;
struct node *next;
}node;
int huan(int length,int ge)
{
int i,j;
node *first,*head,*p,*q;
/*head=(node *)malloc(sizeof(node));
if(!head)return 0;
head-> next=head;
*/
first=(node *)malloc(sizeof(node));
if(!first)return 0;
first-> next=first;
first-> data=1;
for(i=0;i <length-1;i++)
{
p=(node *)malloc(sizeof(node));
if(!p)return 0;
p-> data=length-i;
p-> next=first-> next;
first-> next=p;
}
p=first;q=first;
do
{
q=q-> next;
}while(q-> next!=p);
for(i=1;1;i++)
{
if(p==q)break;
if(i%ge==0)
{
printf( "%d out\n ",p-> data);
q-> next=p-> next;
free(p);
p=q-> next;
continue;
}
p=p-> next;
q=q-> next;
}
printf( "%d ",p-> data);
/*p=first;
do
{
printf( "%d ",p-> data);
p=p-> next;
}
while(p!=first);
*/
}
main()
{
huan(11,3);
getch();
}
[解决办法]
约瑟夫环的问题，网上很多的
[解决办法]
如果要求效率比较高的话，用链表是不大好的。效率回降低不少的，用数组就可以。
