约瑟夫问题c语言
‘壹’ 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语言编程问题：约瑟夫问题求解
用一个循环链表就可以完成了！
#include<stdio.h>
struct node{
int data;
struct node *next;
}node,*list,*p,*r;
void JOSEPHU(int n,int k,int m)
{
int i,j;
list=NULL;
for(i=1;i<=n;i++)
{
p=(struct node*)malloc(sizeof(node));
p->data=i;
if(list==NULL)
list=p;
else
r->next=p;
r=p;
}
p->next=list; /*建立一个循环链表*/
p=list;
for(i=1;i<=n+1;i++)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n"); /*打印链表,并检查循环链表是不输入正确*/
p=list;
i=1;
while(p&&i<k)
{ r=p;
p=p->next;
++i;
}
for(i=1;i<n;i++)
{
for(j=1;j<m;j++)
{ r=p;
p=p->next;
}
printf("The out=%d\n",p->data);
r->next=p->next;
}
}
void main()
{
int x, y, z;
printf("input the lenth n\n");/*n,k,m分别代表总的人数，第一个报数的人，间隔的人数*/
scanf("%d",&x);
printf("input the start k\n");
scanf("%d",&y);
printf("input the m\n");
scanf("%d",&z);
JOSEPHU(x,y,z);
}
‘叁’ 简单的约瑟夫问题C语言
#include<stdio.h>
#include<stdlib.h>
#define N 17
#define M 5
int main(void)
{
int person[N];
int sum =17;
int i=0;
int j=0;
for (i=0;i<17;i++)
{
person[i]=1;
}
i=0;
while(sum>1)
{
if(person[i])
{
j++;
if(j==5)
{
person[i]=0;
printf("%d ",i+1);
sum--;
j=0;
}
}
else
{
;
}
i++;
if(i==16)
{
i=0;
}
}
for (i=0;i<17;i++)
{
if(person[i])
{
printf("The last is %d.\n",i+1);
}
}
return 0;
}
‘肆’ 约瑟夫问题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>
#include<stdlib.h>
void main()
{
int y(int n,int m);
int p,q,r;
printf("请输入参选人的个数p和开始的位置q： ");
scanf("%d%d",&p,&q);
r=y(p,q);
printf("最后那个人的初始位置是：%d ",r);
}
int y(int n,int m)
{
int i,j=0,s=0,l;
int *a=(int *)malloc(sizeof(int));
int *b=(int *)malloc(sizeof(int));
for(i=0;i<n;i++)
{
a[i]=i+1;
}
a[n]=-1;
for(i=0;j!=n;i++)
{
if(a[i]==-1)
i=0;
if(a[i]!=0 && a[i]!=-1)
s++;
if(s==m)
{
b[j]=a[i];
a[i]=0;
j++;
s=0;
}
}
for(i=0;i<n;i++)
{
printf("%5d",b[i]);
}
printf(" ");
l=b[n-1];
return l;
}
(5)约瑟夫问题c语言扩展阅读：
大体思路如下：
①、read(a)
②、b:=1,c:=1{b为某一组的元素个数，c为累计所加到的数}
③、while c<a do (b:=b*2,c:=b+c){超过目标时停止加数}
⑥、c:=c-b{退到前一组}
⑦、x:=a-c{算出目标为所在组的第几个元素}
⑧、ans:=x*2-1{求出该元素}
⑨、write(ans)
‘陆’ 数据结构中的约瑟夫环问题用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语言
"*"表示当前数起位置
#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语言怎么解决约瑟夫问题
我自己写的直接用一维数组解决
#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语言
#include<stdio.h>
#include<stdlib.h>
intmain()
{
intn,m,i,j;
char*mk;
printf("输入n和m,用空格分开：");
scanf("%d%d",&n,&m);
mk=(char*)malloc(n*sizeof(char)+1);
for(i=0;i<=n;++i) mk[i]=0;
i=0;
j=1;
while(i<=(n-1)*m)
{
if(mk[j]==0)
{
++i;
if(i%m==0)
mk[j]=1;
}
++j;
if(j==n+1)
j=1;
}
for(i=1;i<=n;++i)
{
if(mk[i]==0)
printf("%d ",i);
}
free(mk);
return;
}
‘拾’ 用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;
}