约瑟环c语言
‘壹’ 数据结构中的约瑟夫环问题用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;i<N;i++)
a[i]=i+1;
for(i=0;i<N;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;i<N;i++)
if(a[i]!=0)
printf("\n最后一个数为:%d\n",a[i]);
}
两年前念书的时候写的,献丑了!
‘贰’ 约瑟夫环问题c语言
解决问题的核心步骤：
1.建立一个具有n个链结点，无头结点的循环链表
2.确定第1个报数人的位置
3.不断地从链表中删除链结点，直到链表为空
void JOSEPHUS(int n,int k,int m) //n为总人数，k为第一个开始报数的人，m为出列者喊到的数
{
/* p为当前结点r为辅助结点，指向p的前驱结点list为头节点*/
LinkList p,r,list;
/*建立循环链表*/
for(int i=0,i<n,i++)
{
p=(LinkList)malloc(sizeof(LNode));
p->data=i;
if(list==NULL)
list=p;
else
r->link=p;
r=p;
}
p>link=list; /*使链表循环起来*/
p=list; /*使p指向头节点*/
/*把当前指针移动到第一个报数的人*/
for(i=0;i<k;i++)
{
r=p；
p=p->link;
}
/*循环地删除队列结点*/
while(p->link!=p)
{
for(i=0;i<m;i++)
{
r=p;
p=p->link;
}
r->link=p->link;
printf("被删除的元素：%4d ",p->data);
free(p);
p=r->link;
}
printf("\n最后被删除的元素是：％4d",P->data);
}
‘叁’ C语言 约瑟夫环
#include<iostream>
usingnamespacestd;
typedefstructcircle_node
{
intseq;
intval;
circle_node*next;
circle_node(int_val,int_seq)
{
val=_val;
seq=_seq;
next=NULL;
}
}circle_node_t;
voidjoseph()
{
intloop;cin>>loop;
while(loop--)
{//
intN,M;
cin>>N>>M;
intval;
cin>>val;
circle_node_t*head=newcircle_node_t(val,1);
head->next=head;//建立第一个节点
circle_node_t*tail=head;
//建环
intseq=2;
for(intn=1;n<N;n++)
{//
cin>>val;
circle_node_t*xnode=newcircle_node(val,seq++);
xnode->next=tail->next;
tail->next=xnode;
tail=xnode;
}
//调试一下看看有没有输出
//circle_node_t*pp=head;
//if(pp)
//{//
//do
//{//
//cout<<pp->seq<<",";
//pp=pp->next;
//}while(pp!=head);
//cout<<endl;
//do
//{//
//cout<<pp->val<<",";
//pp=pp->next;
//}while(pp!=head);
//cout<<endl;
//}
circle_node_t*p=head;
circle_node_t*q=tail;
//依次出圈
intm=M-1;
while(1)
{//
if(m>N)
{//
m%=N;//避免多次绕圈
}
for(;m;m--)
{//
q=p;
p=p->next;
}
q->next=p->next;//删除p
cout<<p->seq<<"";
N--;
m=p->val-1;
deletep;
p=NULL;
if(N==0)
{//
head=NULL;
break;
}
else
{
p=q->next;
}
}
cout<<endl;
}
}
最外面的输出一般是这样的
intloop;cin>>loop;
while(loop--)
{
//每次的处理
}
‘肆’ 约瑟夫环（求助C语言高手）
运行过了，结果是编号为2的人。
#include<stdio.h>
main(){
int a[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int count = 17;
int last = 0;
while(count > 1){
int num = 0;
while(num<6){
if(a[last%17]!=0)
num++;
last++;
}
while(a[last%17]==0)
last++;
a[last%17] = 0;
while(a[last%17]==0)
last ++;
count--;
int i;
for(i=0;i<17;i++)
printf("%d ", a[i]);
printf("\n");
}
}
每次结果：0为罚下的人，1为依然在场的人。
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 1 1 0 1 1 1
1 1 1 0 1 1 0 1 1 1 1 1 1 0 1 1 1
1 1 1 0 1 1 0 1 1 1 1 0 1 0 1 1 1
1 1 0 0 1 1 0 1 1 1 1 0 1 0 1 1 1
1 1 0 0 1 1 0 1 1 1 1 0 0 0 1 1 1
1 1 0 0 1 0 0 1 1 1 1 0 0 0 1 1 1
1 1 0 0 1 0 0 1 1 1 1 0 0 0 1 1 0
1 1 0 0 1 0 0 1 1 1 0 0 0 0 1 1 0
1 1 0 0 1 0 0 1 0 1 0 0 0 0 1 1 0
1 1 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0
1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0
1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
‘伍’ 求解约瑟夫环问题 C语言
链表方法
这个就是约瑟夫环问题的实际场景，有一种是要通过输入n,m,k三个正整数，来求出列的序列。这个问题采用的是典型的循环链表的数据结构，就是将一个链表的尾元素指针指向队首元素。
p->link=head
解决问题的核心步骤：
1.建立一个具有n个链结点，无头结点的循环链表
2.确定第1个报数人的位置
3.不断地从链表中删除链结点，直到链表为空
void
JOSEPHUS(int
n,int
k,int
m)
//n为总人数，k为第一个开始报数的人，m为出列者喊到的数
{
/*
p为当前结点
r为辅助结点，指向p的前驱结点
list为头节点*/
LinkList
p,r,list;
/*建立循环链表*/
for(int
i=0,i<n,i++)
{
p=(LinkList)malloc(sizeof(LNode));
p->data=i;
if(list==NULL)
list=p;
else
r->link=p;
r=p;
}
p>link=list;
/*使链表循环起来*/
p=list;
/*使p指向头节点*/
/*把当前指针移动到第一个报数的人*/
for(i=0;i<k;i++)
{
r=p；
p=p->link;
}
/*循环地删除队列结点*/
while(p->link!=p)
{
for(i=0;i<m-1;i++)
{
r=p;
p=p->link;
}
r->link=p->link;
printf("被删除的元素：%4d
",p->data);
free(p);
p=r->link;
}
printf("\n最后被删除的元素是：％4d",P->data);
}
‘陆’ 如何用C语言解约瑟夫环
按你表达的意思，如果原来每3个删除一个正确的话，把if(3=...)体中的count = 0;改为count = 1;就可以了。因为题意就变为“第一次隔3删除，以后隔2删除”了。
‘柒’ C语言约瑟夫环问题
#include<stdio.h>
#defineN17//人数
#defineM11//出局人号码
voidmain()
{
inta[N],i,call_n=0,out_n=0;
for(i=0;i<N;i++)a[i]=0;
i=0;
while(1){//循环报数
if(a[i]==0){//如果健在
if(out_n==(N-1))break;//如果仅剩一人
call_n++;//报数
call_n%=M;//最大为M，到了M就从0开始
if(call_n==0){
a[i]=1;//出局标记
out_n++;
printf("%d",i+1);//显示出局人号码
}
}
i++;i%=N;//循环转向下一人
}
printf(" 最后剩余者的编号是：%d ",i+1);
}
‘捌’ 约瑟夫环（c语言）
怎么了，代码看不懂？
约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后结果+1即为原问题的解。
首先我们列出一些有关约瑟夫环的结果：
1 1 2 2 3 2 4 1 5 4 6 1 7 4 8 7 9 1 10 4
11 7 12 10 13 13 14 2 15 5 16 8 17 11 18 14 19 17 20 2021 2 22 5 23 8 24 11 25 14 26 17 27 20 28 23 29 26 30 29
31 1 32 4 33 7 34 10 35 13 36 16 37 19 38 22 39 25 40 28
41 31 42 34 43 37 44 40 45 43 46 46 47 2 48 5 49 8 50 11
51 14 52 17 53 20 54 23 55 26 56 29 57 32 58 35 59 38 60 41
61 44 62 47 63 50 64 53 65 56 66 59 67 62 68 65 69 68 70 171 4 72 7 73 10 74 13 75 16 76 19 77 22 78 25 79 28 80 31
81 34 82 37 83 40 84 43 85 46 86 49 87 52 88 55 89 58 90 61
91 64 92 67 93 70 94 73 95 76 96 79 97 82 98 85 99 88 100 91
意思是，前一个数为约瑟夫环的人数，后一个数为最后出去的人的号码。
从上面的表中我们可以归纳出以下两个规则：
规则1:若上一组数字中最后保留号比人数少一，则下一数从1开始记。
例如第三组（3,2）为上一组，最后保留好为2，比3少1，下一组的数字（4,1），最后保留号为1
规则2:若上一组数字为最后保留号与人数相等，则下一数从2开始记。
‘玖’ 用c语言实现约瑟夫环
正好之前写过基础的约瑟夫环，稍作修改就可以满足你的题目
#include<stdio.h>
#include<stdlib.h>
typedefstruct_node{
intid;
intkey;
struct_node*next;
}Linklist;
intmain(){
intn,m;
scanf("%d%d",&n,&m);
inti,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 ",head->id);
free(head);
return0;
}
‘拾’ 求用c语言编写约瑟夫环的程序
#include<stdio.h>
struct
list//建立一个结构体，包括每个人的编号，密码和下一级的指针
{
int
id;
int
code;
struct
list
*next;
};
typedef
struct
list
list;//把结构体用list表示
list*
input(int
n)//链表的初始化
{
list
*p,*q,*l;
int
i,m;
p=new
list;
l=new
list;
l->next=NULL;
p=l;
p->id=1;//第一个人的初始化
scanf("%d",&m);
p->code=m;
for(i=2;i<=n;i++)//第二个人到第num个人的初始化
{
q=new
list;
q->id=i;
scanf("%d",&m);
q->code=m;
q->next=NULL;
p->next=q;
p=q;
}
p->next=l;//使表尾指向表头，成循环链表
return
p;
}
int
main()
{
int
num,m1,i;
list
*q,*p;
while(scanf("%d",&num)!=EOF)
{
printf("第一次的密码为:");
scanf("%d",&m1);
p=input(num);
//printf("%4d\n",head->id);
printf("出队的顺序为:");
while(p->next!=p)
{
for(i=1;i<=m1;i++)
{
q=p;
p=p->next;
//printf("--\n",p->id);
}
m1=p->code;
printf("%4d",p->id);
q->next=p->next;
delete
p;
p=q;
}
printf("%4d",p->id);
delete
p;
printf("\n");
}
}