約瑟夫環c語言數組
㈠ 如何用c語言解約瑟夫環
按你表達的意思,如果原來每3個刪除一個正確的話,把if(3=...)體中的count = 0;改為count = 1;就可以了。因為題意就變為「第一次隔3刪除,以後隔2刪除」了。
㈡ c語言約瑟夫環問題 請大神給我詳細講解一下這個解法的思路 謝謝!
思路:
(1)
將n個人的編號(1,2,3,。。。,n)存入數組元素num[0],num[1],。。。,num[n-1]中。
程序段為:
p=num;
/***********SPACE***********/
for(i=0;i<n;i++)
/***********SPACE***********/
*(p+i)=i+1;
(2)
模擬報數(k++;),報到3 的人出圈(即對應的數組元素num[i]設置為0),並使出圈的人數+1(m++;),然後再從頭報數,。。。,當出圈人數達到n-1時,報數結束。
程序段為:
i=0;
k=0;
m=0;
while(m<n-1)
{
/***********SPACE***********/
if(*(p+i)!=0) k++;
if(k==3)
{
*(p+i)=0;
k=0;
m++;
}
i++;
if(i==n) i=0;
}
(3)
此時,數組中不為0的那個元素的值就是後留下的那位的編號,找到它輸出即可:
while(*p==0) p++;
printf("%d is left\n",*p);
㈢ 約瑟夫問題 c語言數組
#include <stdafx.h>
#include <IOSTREAM.H>
#define N 63 // 猴子數
#define M 5 // 數數周期
void main()
{
// 編號
int arrId[N] = {0};
for (int i=0; i<N; ++i)
{
arrId[i] = i+1;
}
int nCount = N;
int nMod = 1;
while (nCount > 1)
{
nMod = (nMod-1+M)%nCount;
if (nMod == 0)
nMod = nCount;
cout << "猴子" << arrId[nMod-1] << "被淘汰" << endl;
for (int i=nMod; i<nCount; ++i)
{
arrId[i-1] = arrId[i];
}
--nCount;
}
cout << "最後的猴王是猴子" << arrId[0] << endl;
}
-----------------------------------------------
執行結果:
猴子5被淘汰
猴子10被淘汰
猴子15被淘汰
猴子20被淘汰
猴子25被淘汰
猴子30被淘汰
猴子35被淘汰
猴子40被淘汰
猴子45被淘汰
猴子50被淘汰
猴子55被淘汰
猴子60被淘汰
猴子2被淘汰
猴子8被淘汰
猴子14被淘汰
猴子21被淘汰
猴子27被淘汰
猴子33被淘汰
猴子39被淘汰
猴子46被淘汰
猴子52被淘汰
猴子58被淘汰
猴子1被淘汰
猴子9被淘汰
猴子17被淘汰
猴子24被淘汰
猴子32被淘汰
猴子41被淘汰
猴子48被淘汰
猴子56被淘汰
猴子63被淘汰
猴子11被淘汰
猴子19被淘汰
猴子29被淘汰
猴子38被淘汰
猴子49被淘汰
猴子59被淘汰
猴子6被淘汰
猴子18被淘汰
猴子31被淘汰
猴子43被淘汰
猴子54被淘汰
猴子4被淘汰
猴子22被淘汰
猴子36被淘汰
猴子51被淘汰
猴子3被淘汰
猴子23被淘汰
猴子42被淘汰
猴子61被淘汰
猴子16被淘汰
猴子44被淘汰
猴子7被淘汰
猴子34被淘汰
猴子62被淘汰
猴子37被淘汰
猴子13被淘汰
猴子57被淘汰
猴子53被淘汰
猴子12被淘汰
猴子28被淘汰
猴子47被淘汰
最後的猴王是猴子26
Press any key to continue
㈣ C語言,編了一個程序解決約瑟夫環問題(數組模擬1代表有人,0代表走了)下面的代碼對嗎
#include<stdio.h>
#defineN10
intmain()
{
inta[N];
inti,people=N,n=0;
for(i=0;i<N;i++)
a[i]=1;
i=0;
while(people>0)
{
if(a[i]==1)//非0的才統計
n++;
if(n==3)
{
a[i]=0;
people--;
printf("第%d個人離開 ",i+1);
n=0;
}
i++;
if(i==N)
i=0;
}
return0;
}
㈤ 約瑟夫環問題 用C語言數據結構數組實現....
#include<iostream>
using namespace std;
struct Node//循環節點的定義
{
int number;//編號
Node *next;
};
Node *CreateList(Node *L,int &n,int &m);//建立約瑟夫環函數
void Joseph(Node *L,int n,int m);//輸出每次出列號數函數
Node *DeleteList(Node **L,int i,Node *q);//尋找每次出列人的號數
int LengthList(Node *L);//計算環上所有人數函數
void main()//主函數
{
Node *L;
L=NULL;//初始化尾指針
int n, m;
cout<<"請輸入人數N:";
cin>>n;//環的長度
if(n<1){cout<<"請輸入正整數!";}//人數異常處理
else
{
cout<<"請輸入所報數M:";
cin>>m;
if(m<1){cout<<"請輸入正整數!";}//號數異常處理
else
{
L=CreateList(L,n,m);//重新給尾指針賦值
Joseph(L,n,m);
}
}
system("pause");
}
Node *CreateList(Node *L,int &n,int &m)//建立一個約瑟夫環(尾插法)
{
Node *q;
for(int i=1;i<=n;i++)
{
Node *p;
p=new Node;
p->number=i;
p->next=NULL;
if(i==1) L=q=p;//工作指針的初始化
else
{
q->next=p;
q=q->next;
}
}
q->next=L;
if(L!=NULL){return(L);}//返回尾指針
else cout<<"尾指針異常!"<<endl;//尾指針異常處理
}
void Joseph(Node *L,int n,int m)//輸出每次出列的人
{
int k;
cout<<"請輸入第一個報數人:";
cin>>k;
if(k<1||k>n){cout<<"請輸入1-"<<n<<"之間的數"<<endl;}
else
{
cout<<"\n出列順序:\n";
for(int i=1;i<n;i++)
{
Node *q = new Node;
if(i==1) q=DeleteList(&L,k+m-1,q);//第一個出列人的號數
else q=DeleteList(&L,m,q);
cout<<"號數:"<<q->number<<endl;
delete q;//釋放出列人的存儲空間
}
cout<<"最後一個出列號數是:"<<L->number<<endl;;//輸出最後出列人的號數
}
}
Node *DeleteList(Node **L,int i,Node *q) //尋找每次出列的人
{
if(i==1) i+=LengthList(*L);//順序依次出列情況的處理方式
Node *p;
p=*L;
int j=0;
while(j<i-2) {p=p->next;j++;}
q = p->next;
p->next=p->next->next;
*L = p->next;
return(q);
}
int LengthList(Node *L)//計算環上的人數
{
if(L){cout<<"尾指針錯誤!"<<endl;}//異常處理
else
{
int i=1;
Node *p=L->next;
while(p!=L)
{
i++;
p=p->next;
}
return(i);
}
}
㈥ 數據結構中的約瑟夫環問題用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>
intmain(){
intnum[50],n,m,i,j;
intlen,start=0,counter=1;
printf("總數報數 ");
scanf("%d%d",&n,&m);
if(n<0||n>50)n=50;
if(m<1||m>n)m=n/2;
printf("人數:%d,報數:%d ",n,m);
for(i=0;i<n;++i)num[i]=i+1;//預填
len=n;//len保留隊列中現有人數
while(len){
if(counter==m){
printf("%d",num[start]);
for(j=start;j<len-1;++j)
num[j]=num[j+1];
--len;
counter=1;
}
else{
++counter;
++start;
start%=len;
}
}
printf(" ");
return0;
}
㈧ c語言 約瑟夫環
以下是用「循環鏈表」和「數組」的方法做的!
m,n都可以輸入。
s設為「1」。
這些稍稍改動就可以符合您的要求!
(這可是我兩小時的心血,一定要給點分!!!)
*****************************
用循環鏈表做:
*****************************
#include<malloc.h>
#define LEN sizeof(struct people)
struct people
{
int num;
struct people *next;
};
struct people *creat(int n)
{
int i;
struct people *head,*p1,*p2;
head=NULL;
for(p1=p2,i=1;i<=n;i++)
{
p1=(struct people *)malloc(LEN);
p1->num=i;
if(i==1)
{
head=p1;
}
p2->next=p1;
p2=p1;
}
p1->next=head;
return(head);
}
struct people *del(struct people *p0)
{
struct people *p;
p=p0->next;
p0->next=p->next;
p->next=NULL;
free(p);
}
struct people *count(struct people *head,int n)
{
struct people *d,*p,*p0;
int i,j;
for(j=1,p=head;p->next!=p;j++)
{
if(n==1)
{
for(;p->next!=head;p=p->next){}
head=head->next;
printf("第%d個出局的----%d\n\n",j,p->next->num);
del(p);
}
else
{
for(i=1;i<n;i++)
{
p0=p;
p=p->next;
}
d=p0;
printf("第%d個出局的----%d\n\n",j,p->num);
p=p->next;
if(p->next!=p)
{
del(d);
}
}
}
return(p);
}
main()
{
struct people *head,*left;
int n;
printf("請輸入人數(大於0):");
scanf("%d",&n);
if(n<=0)
{
printf("error\n");
}
else
{
head=creat(n);
printf("請輸入要報的數(大於0):");
scanf("%d",&n);
if(n<=0)
{
printf("error\n");
}
else
{
left=count(head,n);
printf("留下的是:%d號\n",left->num);
}
}
}
***********************************
用數組做:
***********************************
int *del(int *a,int count,int n)
{
int index=0,i=n,x=0;
while(i>1)
{
if(a[index]!=0)
{
x++;
if(x==count)
{
printf("第%d個出局的是%d號\n",(n-i),a[index]);
a[index]=0;
i--;
x=0;
}
}
index=((index+1)%n);
}
return(a);
}
main()
{
int a[100],i,n;
int *p;
printf("請輸入人數(大於0):");
scanf("%d",&n);
for(i=0;i<n;i++)
{
a[i]=i+1;
}
printf("請輸入要報的數(大於0):");
scanf("%d",&i);
p=del(a,i,n);
i=0;
while(p[i]==0)
{
i++;
}
printf("最後留下的是%d號\n",p[i]);
}
㈨ 約瑟夫環(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>
int main() {
int num[50],n,m,i,j;
int len,start = 0,counter = 1;
printf("總數 報數\n");
scanf("%d%d",&n,&m);
if(n < 0 || n > 50 ) n = 50;
if(m < 1 || m > n) m = n/2;
printf("人數:%d,報數:%d\n",n,m);
for(i = 0; i < n; ++i) num[i] = i + 1; // 預填
len = n; // len保留隊列中現有人數
while(len) {
if(counter == m) {
printf("%d ",num[start]);
for(j = start; j < len - 1; ++j)
num[j] = num[j + 1];
--len;
counter = 1;
}
else {
++counter;
++start;
start %= len;
}
}
printf("\n");
return 0;
}