約瑟夫問題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;
}