数据结构约瑟夫环代码(约瑟夫环数据结构c++编程)
用数据结构编写约瑟夫环算法思想
这个算法是利用单链表编写的,主函数里的算法理解起来可能有点难,但是时间复杂度低。这是完整的核宽cpp 代码,你可以直接复制过去再测试!
#include iostream.h
#include stdlib.h
struct Member//定义结构体闷轮
{
int number;
int password;
Member *next;
};
class Joseph
{
public:
Member *frist;//头指针
int size;
Joseph(void);
~Joseph(void);
int Size(void) const;//返回长度
Member *Index(int i);//定位
void Create(int i);//构造循环单链表
int Delete(int i);//删除结点并返回number的值
};
Joseph::Joseph()
{
//frist=new Member;
Member *p=new Member;
frist=p;
size=0;
}
Member *Joseph::Index(int i)
{
if(i==0)return frist;
Member *p=frist-next;
int j=1;
while(ji)
{
p=p-next;
j++;
}
return p;
}
int Joseph::Size(void)const
{
return size;
}
void Joseph::Create(int i)
{
for(int j=1;j=i;j++)
{
Member *p=Index(j-1);
Member *q=new Member;
q-number=j;
p-next=q;
size++;
};
//Member *p=Index(i);
//p-next=frist;
}
Joseph::~Joseph(void)
{
Member *p,*q;
p=frist;
while(size!=0)
{
q=p;
p=p-next;
delete q;
size--;
}
size=0;
frist=NULL;
}
int Joseph::Delete(int i)
{
Member *s,*p=Index(i-1);
s=p-next;
p-next=p-next-next;
int x=s-number;
cout蚂氏信x" ";
int y=s-password;
delete s;
size--;
return y;
}
void main(void)
{
Joseph jos;
int i;
cout"Please input number of people :"endl;
cini;
jos.Create(i);
int frist;//设初始值
cout"Please input the frist number :"endl;
cinfrist;
for(int k=1;k=i;k++)//用循环输入每个人的密码
{
cout"please input No."k"`s password:"endl;
Member *b=jos.Index(k);
cinb-password;
}
cout"The final is :"endl;
int l=frist%i;
if (l==0) l=i;
for(int b=i-1;b0;b--)
{
frist=jos.Delete(l);
l=(frist+l-1)%b;
int e=jos.Size();
if(l==0)
l=e;
}
jos.Delete(l);
coutendl;
}
数据结构C语言的约瑟夫环怎么做?
参考代码:\x0d\x0a#include\x0d\x0a#include\x0d\x0a#include\x0d\x0atypedef struct LNode{\x0d\x0aint number;\x0d\x0astruct LNode *next;\x0d\x0a} LNode,*Linklist;\x0d\x0aint main()\x0d\x0a{\x0d\x0aint M,N;\x0d\x0aint i;\x0d\x0aLinklist L,r;\x0d\x0aprintf("Please input two M , N:");\x0d\x0ascanf("%d%d",M,N);\x0d\x0aL = (Linklist)malloc(N * sizeof(struct LNode));\x0d\x0aif(L == NULL) printf("Error!\n"),exit(0);\x0d\x0ar = L;\x0d\x0afor(i = 1;i next = L + i;\x0d\x0a老指橘r-number = i;\x0d\x0a 侍团 r = r-next;\x0d\x0a}\x0d\x0ar-next = L;\x0d\x0ar-number = N;\x0d\x0a逗配while(r != r-next)\x0d\x0a{\x0d\x0afor(i = 0;i next;\x0d\x0aprintf("%4d",r-next-number);\x0d\x0ar-next = r-next-next;\x0d\x0a}\x0d\x0aprintf("\n When N = %d and M = %d,Josephus,hiding in position %d survive.\n",N,M,r-number);\x0d\x0afree(L);\x0d\x0a}
数据结构中的约瑟夫环问题用C语言怎么编写出来啊?
题目:有n个人围成一圈,顺序排号。从第一个人开始报数(从1到3报数),凡报到3的人退出
弊凳灶圈子,问最后留下的是原来第几号的那位。
1.
程序分析:这是一粗盯个比较经典的算法--约瑟夫环问题.
2.个人分析:
算法比较经典,对于这样的问题本应该使用链表的形式会比较容易.约瑟夫环算法
则体现了使用数组来完成链表该完成租扮的功能,虽然形式上完全不相同,但却求出了
相同的结果.有异曲同工之妙.总之我个人认为是数组中非常经典的算法了.希望本
人写的代码不会叫大家啐骂!
3.程序源代码:
#include
stdio.h
#define
N
50
#define
S
3
void
main()
{
int
a[N];
int
i,k;
int
sum=N;
k=0;
for(i=0;iN;i++)
a[i]=i+1;
for(i=0;iN;i++)
printf("%-4d",a[i]);
printf("\n");
for(i=0;;i++)
{
if(sum==1)
break;
if(a[i%N]!=0)
{
k++;
}
if(k==S)
{
k=0;
//printf("%4d",a[i%N]);
a[i%N]=0;
sum--;
}
}
for(i=0;iN;i++)
if(a[i]!=0)
printf("\n最后一个数为:%d\n",a[i]);
}
两年前念书的时候写的,献丑了!
用c语言实现约瑟夫环
正好之前写过基础的察雀约瑟夫环,稍作修改就可以满足你的题目
#include?stdio.h
#include?stdlib.h
typedef?struct?_node?{
????int?id;
????int?key;
????struct?_node?*next;
}?Linklist;
int?main()?{
int?n,?m;
scanf("%d?%d",?n,?m);
int?i,?count?=?0;
Linklist?*head?=?(Linklist*)malloc(sizeof(Linklist)),?*tail?=?head;
head-id?=?1;
scanf("%d",?head-key);
head-next?=?head;
for(i?=?2;?i?=?n;?i++)?{
Linklist?*p?=?(Linklist*)malloc(sizeof(Linklist));
p-id?=?i;
scanf("%d",?p-key);
p-next?=?head;
tail-next?=?世没败p;
tail?=?p;
}
while(head?!=?tail)?{
if(++count?%?m)?{
tail?=?head;
}?else?{
????m?=?head-key;
????count?=?0;
printf("%d?"搜颤,?head-id);
tail-next?=?head-next;
free(head);
}
head?=?tail-next;
}
printf("%d\n",?head-id);
free(head);
return?0;
}
约瑟夫环问题的代码
首先,这个代码输出的是,约瑟夫环到达的让腊最后位置。输出结果是15。
//把iostream这个文件中的内容复制到这个地方。
#includeiostream
using namespace std;
int main()
{
//定义一个常量的整形100,表示人的个数。纳键
const int n=100;
//定义约瑟夫环的参数。
int m=30;
//定义一个数组,用于计算约瑟夫环的位置。
int a[n];
//给数组赋值,让数组的每个值就是这个元素的编号。
for(int j=0;jn;j++)
a[j]=j+1;
//定义一个标志k,当K等于N的时候,表示到达约瑟夫环的最后位置。
int k=1;
int i=-1;
while(1)
{
for(int j=0;jm;)
{
//不停的取数组的下一个元素。
i=(i+1)%n;
//如果这个元素没有被标记为0,说明这个位置还没有被排除,j加1,进入下一个循环
if(a[i]!=0)
j++;
}
//如果标志K等于n,说明约瑟夫环的循环到达最后一个位置,跳出While死循环。
if(k==n)
break;
//否则,把这个位置的元素设为零,标志它被排除。
a[i]=0;
//标志+1。
k++;
}
//输出约瑟夫环到达洞滑巧的最后一个位置。
couta[i]endl;
return 0;
}