主题:[讨论]编写一算法解决约瑟夫问题
人魚◎泡泡
[专家分:0] 发布于 2007-03-14 15:07:00
设有N个人为坐在圆桌周围,现从第S个人开始报数,数到第M个人出列,然后从出列的下一个人重新开始报数,数到第M个人又出列……如此重复直到所有的人全不出列为止,例如当N=8,M=4,S=1,得到的新序列为:4,8,5,2,1,3,7,6
回复列表 (共25个回复)
21 楼
zzc0816 [专家分:130] 发布于 2007-03-25 11:28:00
[color=C0C0C0]以前写的个代码。
发出供LZ参考!!![/color]#include <stdio.h>
[color=0000FF]#include <stdlib.h>
#define N 15
#define M 3
typedef struct node
{ int index;
struct node * next;
} Node, *pNode;
void initlist(pNode * list);
void output(pNode list);
void main()
{ pNode headlist = NULL;
initlist(&headlist);
output(headlist);
system("pause");
} void initlist(pNode * list)
{ pNode temp,temp1;
int i = 0;
temp = (pNode)malloc(sizeof(Node));
if(temp == NULL)
{
printf("Malloc Failure!\n");
exit(-1);
}
temp1 = temp;
while(i < N)
{
temp->next = (pNode)malloc(sizeof(Node));
if(temp->next == NULL)
{
printf("Malloc Failure!\n");
exit(-1);
}
temp = temp->next;
temp->index = i + 1;
i++;
}
temp->next = temp1->next;
*list = temp1->next;
free(temp1);
} void output(pNode list)
{
pNode temp1,temp2;
temp1 = list;
temp2 = temp1;
int number = 1,count = 0;
while(number < N)
{
count++;
if(count == M)
{
temp2->next = temp1->next;
count = 0;
free(temp1);
temp1 = temp2->next;
number ++;
continue;
}
temp2 = temp1;
temp1 = temp1->next;
}
printf("The last person is:%d\n",temp1->index);
free(temp1);
}[/color]
22 楼
hackhou [专家分:60] 发布于 2007-03-28 00:04:00
我的博客里有这样的程序。欢迎你到我那里去看。不过我是用C++写的。不知道你看的懂吗?
23 楼
勇敢懦夫 [专家分:0] 发布于 2007-04-15 12:29:00
#include <iostream.h>
struct Node
{
int data;
struct Node* next;
};
//删除节点超做
void deletelist(Node* h)
{
Node* q=h->next;
h->next=q->next;
delete q;
}
//创建一个不带头接点的链表
Node* createlist(int m)
{
Node* head=new Node;
Node* p=head;
p->data=1;
p->next=NULL;
for(int i=2;i<=m;i++)
{
Node* q=new Node;
q->data=i;
p->next=q;
p=q;
if(i==m)
{
p->next=head;
}//最后一个指针指向头节电
}
return head;
}
//主要调用完成超做函数
void fun(Node* h,int k,int n)
{
Node*p=h;
int m=1;
int a=1;
int w;
while(m<=k-2)
{
p=p->next;
m++;
if((m==k-1)&&(a<=n-1))
{
w=p->next->data;
cout<<"被弹出的第"<<a<<"个元素为"<<endl;
cout<<w<<endl;
deletelist(p);
m=0;
a++;
if(a==n)
{
cout<<"被弹出的第"<<n<<"个元素为"<<endl;
cout<<p->data;
cout<<endl;
}
}
}
}
//主函数
int main()
{ int m;
int k;
cout<<"请输入元素个数M"<<endl;
cin>>m;
cout<<"请输入弹出的元素的位数K"<<endl;
cin>>k;
Node* head=createlist(m);
fun(head,k,m);
return(0);
}
24 楼
xxgamexx [专家分:90] 发布于 2007-04-15 20:19:00
我前几天用C++写的 通过测试了
#include <iostream.h>
struct Tnode
{
int data;
Tnode *next;
};//节点定义
class TPclass
{
public:
TPclass(int ms,int mb,int mm);
void Creat();
//int OutNode(Tnode *p);
void Print();
~TPclass()
{
Tnode *temp;
for(temp=flag;temp->next!=NULL;temp=temp->next)
delete(temp);
}
protected:
Tnode *head,*tail,*flag;
int sump,beginp,m;
};
TPclass::TPclass(int ms,int mb,int mm)//初始化
{
head=NULL;
tail=NULL;
sump=ms;
beginp=mb;
m=mm;
flag=NULL;
}
void TPclass::Creat()//建立循环表
{
Tnode *temp=NULL;
int number=1;
head=new Tnode;
tail=new Tnode;
head->data=1;
head->next=tail;
tail->data=sump;
tail->next=head;//建立头和尾
while(number!=(sump-1))//中间插的人的数量 按一定的位置顺序
{
temp=new Tnode;
temp->data=sump-number;
temp->next=head->next;
cout<<temp->data<<endl;
head->next=temp;
number++;
}
}
void TPclass::Print()
{
Tnode *temp=head,*p=NULL;//temp:开始的变量
while(temp->data!=beginp)
temp=temp->next;
while(sump!=2)//留两个 可以设置变量 让用户选择
{
for(int i=1;i<=m;i++)//选人
temp=temp->next;
p=temp->next;//p=temp
temp->next=p->next;
cout<<p->data<<endl;
delete(p);
sump--;
}
flag=temp;
for(int i=1;i<=2;i++)
{
cout<<"the last"<<temp->data;//因为留了两个
temp=temp->next;
}
}
void main()
{
int stop;
TPclass TP(20,5,2);
TP.Creat();
TP.Print();
cin >>stop;
}
25 楼
billwang1 [专家分:0] 发布于 2007-05-13 21:55:00
到这个网站看有没有
算法源码吧 [url=http://www.sfcode.cn/]http://www.sfcode.cn/[/url]
我来回复