约瑟夫c语言
① 用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<iostream.h>
struct
node
{
int
data;
node
*pnext;
};
void
main()
{
int
n,k,m,i;
node
*p,*q,*head;
cout<<"输入n的值:";
cin>>n;
cout<<"输入起始报数人号码k的值:";
cin>>k;
cout<<"输入
数到m出列的m的值:";
cin>>m;
head=(node*)new
node;
//确定头结点
p=head;
for(i=1;i<=n-1;i++)
//赋初值
{
p->data=i;
p->pnext=(node*)new
node;
//为下一个新建内存
p=p->pnext;
}
p->data=n;
//最后一个单独处理
p->pnext=head;
//指向头，形成循环链表
p=head;
while(p->data!=(p->pnext)->data)
//p->data==(p->pnext)->data表示只剩下一个结点的
{
while(p->data
!=k)
//寻找编号为k的结点
p=p->pnext;
if(m==1)
{
for(i=1;i<=n;i++)
{
cout<<p->data<<'\\t'
;
p=p->pnext
;
}
cout<<'\
';
return;
}
else
for(i=1;i<m-1;i++)
//开始报数
{p=p->pnext;}
//找到报m-1的结点
q=p->pnext;
//q为报m的结点
cout<<q->data<<"\\t";
//输出报m的结点的值
k=(q->pnext)->data;
//k为下一个报数的起点
p->pnext=q->pnext;
//删除报m的结点
}
cout<<p->data<<'\
';
//输出最后一个结点的值
}
③ c语言约瑟夫（Joseph）问题
#include <stdio.h>
#include <stdlib.h>
/*n表示最初有多少个人，银哗碰m表示报数到多少的人离开，函数Joseph返回最后剩下的人的编号*/
int Joseph(int n, int m)
{
int count = n; /*count表示当前圈内剩下的人数*/
int num=0; /*num表示当前报的数*/
int i,j; /*i表示当前报数的人对应的下标*/
int *a, remain;
/*动态申请连续的n个存储单元用来锋谈存放每个人的编号，将空间首地址赋值给a*/
a = (int *)malloc(sizeof(int));
for(i=0; i<n; i++) a[i] = i+1; /*a[i]保存第i个人的编号*/
i = 0; /*从下标为0的人开始报数*/
while(count>1) /*如果剩余人数大于1则循环芦者*/
{
num++;
if(num == m) /*报数到m的人离开*/
{
/*将下标为i的元素删除*/
for(j=i+1; j<count; j++) a[j-1] = a[j];
count--; /*当前剩余人数减1*/
num = 1; /*下一个人重新从1开始报数*/
}
i = m%count; /*计算下一个要报数的人的下标*/
}
remain = a[0]; /*最后只剩下一个人，将其编号赋值给remain*/
return remain;
}
④ 约瑟夫问题c语言实现代码
测试结果:
总人数n=9,报数m=2.
2->4->6->8->1->5->9->7->3
#include<stdio.h>
#include<stdlib.h>
typedefstructnode
{
intdata;
structnode*next;
}node;
typedefnode*Linklist;
//原代码voidCreatLinklist(Linklist*L,intn)
LinklistCreatLinklist(Linklist*L,intn)
{
Linklistp,s;
*L=(Linklist)malloc(sizeof(node));
(*L)->next=NULL;
inti=1;
p=*L;//增加这个语句,让p指向当前结点
if(n!=0)
{
//原代码while(i<=41)
while(i<=n)
{
s=(Linklist)malloc(sizeof(node));
s->data=i++;
p->next=s;
p=s;
}
s->next=(*L)->next;//将笑卖链表循环起来；
}
free(*L);//释放头结点；
returns->next;//返回第一个结点的值；
}
intmain()
{
intn=41;//9
intm=3;//2
inti;
LinklistL;
printf("总人数n=%d,报数m=%d. ",n,m);
//原代码Linklist*p=CreatLinklist(Linklist*L,intn);
Linklistp=CreatLinklist(&L,n);
Linklisttemp;
早升笑m%=n;
while(p!=p->next)
{
for(i=1;i<m-1;i++)
{
陆含p=p->next;
}
printf("%d->",p->next->data);
temp=p->next;
p->next=temp->next;
free(temp);
p=p->next;
}
printf("%d",p->data);
return0;
}
⑤ 约瑟夫环（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>
#define N 9 //总人数
#define K 1 //开始数数的人
#define M 3 //间隔的人数
//给数组赋值
void setDate(int a[],int n)
{ int i;
for(i=0;i<n;i++)
a[i]=i+1;
}
//删除被选中的孩子
void deleted(int a[],int m,int len)
{
int i=m;
do
{
a[i]=a[i+1];
i++;
}while(i<len);
}
//开始play
void play(int a[],int k,int m)
{
int len =N;
int dm=k+m-2;//第一个被剔除的孩子
while(len!=1)
{printf("第%d个孩子被剔除。\n",a[dm]);
deleted(a,dm,len);//将被剔除的孩子从数组中删除
dm=dm+M-1;//下一个被剔除的孩子
len--;//数组的长度减1
if(dm>=len) dm=dm-len;
}
printf("最后一个孩子是%d.",a[0]);//最后一个孩子被放在a[0]中
}
main()
{
int a[N];
setDate(a,N);
play(a,K,M);
}
⑦ 如何用C语言解约瑟夫环
按你表达的意思，如果原来每3个删除一个正确的话，把if(3=...)体中的count = 0;改为count = 1;就可以了。因为题意就变为“第一次隔3删除，以后隔2删除”了。
⑧ 约瑟夫问题c语言
1、约瑟夫问题：Joseph问题的一种描述是：编号为1、2、……、n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。
2、例程：
#include
#include
typedef int ElemType;
typedef struct LNode{
ElemType data;int num;
struct LNode *next;
}LNode,*LinkList;
void CreateList_L(LinkList *L,int n)
{ int i=0;
ElemType e;
LinkList p,q;
*L=(LinkList)malloc(sizeof(LNode));
(*L)-> next=NULL;(*L)-> data=n;
q=*L;
while(i
data=e;p-> num=i+1;
p-> next=NULL;
q-> next=p;
q=p;
i++;
}
p-> next=(*L)-> next;
}
void PrintList(LinkList L)
{ int i=0;
LinkList p;
p=L-> next;
while(i
data)
{
printf("%5d",p-> data);
p=p-> next;
i++;
}
printf("\n");
}
void Put(LinkList *L)
{ int i,m;LinkList p,q;
printf("input a number:\n");
scanf("%d",&m);
q=(*L)-> next;
while((*L)-> data)
{for(i=0;i
next;
}
printf("%5d",q-> num);
m=q-> data;
p-> next=q-> next;
free(q);
q=p-> next;
(*L)-> data=(*L)-> data-1;
}
}
void main()
{LinkList L;
int a;
printf("请输入人数:");
scanf("%d",&a);
printf("请输入密码:");
CreateList_L(&L,a);
printf("您输入的数字为:\n");
PrintList(L);
Put(&L);
}
⑨ 约瑟夫问题 c语言
"*"表示当前数起位置
#include <stdio.h>
int main()
{
int n;
int i, j;
int pos[30];
for(i = 0; i < 30; i++) pos[i] = i+1; //位置输入到数组
i = 0;
n = 30;
while(n > 15){
i += 8;
i %= n;
printf("扔下第 %d 人\n", pos[i]);
n --;
for(j = i; j < n; j++){
pos[j] = pos[j+1];
}
printf("剩下的人: ");
for(j=0;j<n;j++) {
if(j == i) printf("*%d ", pos[j]);
else printf("%d ", pos[j]);
}
printf("\n");
}
return 0;
}
输出:
扔下第 9 人
剩下的人: 1 2 3 4 5 6 7 8 *10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
扔下第 18 人
剩下的人: 1 2 3 4 5 6 7 8 10 11 12 13 14 15 16 17 *19 20 21 22 23 24 25 26 27 28 29 30
扔下第 27 人
剩下的人: 1 2 3 4 5 6 7 8 10 11 12 13 14 15 16 17 19 20 21 22 23 24 25 26 *28 29 30
扔下第 6 人
剩下的人: 1 2 3 4 5 *7 8 10 11 12 13 14 15 16 17 19 20 21 22 23 24 25 26 28 29 30
扔下第 16 人
剩下的人: 1 2 3 4 5 7 8 10 11 12 13 14 15 *17 19 20 21 22 23 24 25 26 28 29 30
扔下第 26 人
剩下的人: 1 2 3 4 5 7 8 10 11 12 13 14 15 17 19 20 21 22 23 24 25 *28 29 30
扔下第 7 人
剩下的人: 1 2 3 4 5 *8 10 11 12 13 14 15 17 19 20 21 22 23 24 25 28 29 30
扔下第 19 人
剩下的人: 1 2 3 4 5 8 10 11 12 13 14 15 17 *20 21 22 23 24 25 28 29 30
扔下第 30 人
剩下的人: 1 2 3 4 5 8 10 11 12 13 14 15 17 20 21 22 23 24 25 28 29
扔下第 12 人
剩下的人: 1 2 3 4 5 8 10 11 *13 14 15 17 20 21 22 23 24 25 28 29
扔下第 24 人
剩下的人: 1 2 3 4 5 8 10 11 13 14 15 17 20 21 22 23 *25 28 29
扔下第 8 人
剩下的人: 1 2 3 4 5 *10 11 13 14 15 17 20 21 22 23 25 28 29
扔下第 22 人
剩下的人: 1 2 3 4 5 10 11 13 14 15 17 20 21 *23 25 28 29
扔下第 5 人
剩下的人: 1 2 3 4 *10 11 13 14 15 17 20 21 23 25 28 29
扔下第 23 人
剩下的人: 1 2 3 4 10 11 13 14 15 17 20 21 *25 28 29
⑩ 求解约瑟夫环问题 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);
}