約瑟夫環問題：設編號為1，2，3，……，n的n(n>0)個人按順時針方向圍坐一圈，m為任意一個正整數。從第一個人開始順時針方向自1起順序報數，報到m時停止并且報m的人出列，再從他的下一個人開始重新從1報數，報到m時停止并且報m的人出列。如此下去，直到所有人全部出列為止。要求設計一個程式模擬此程序，對任意給定的m和n，求出出列編號序列。
實驗要求：用順序表實作。
實驗內容：
1. 問題描述
約瑟夫環問題。
2．資料結構型別定義
typedef struct{
ElemType data[MaxSize]; //存放資料表中的元素
int length; //存放線性表的長度
}SqList;
3. 模塊劃分
（1）創建建立順序表函式 void CreateList(SqList *&L,ElemType a[],int n)
（2）創建線性表輸出函式 void DispList(SqList *L)
（3）創建洗掉資料元素函式 bool ListDelete(SqList *&L,int i,ElemType &e)
（4）創建銷毀線性表函式 void DestroyList(SqList *&L)
（5）主函式 void main()
4. 設計分析
先在主函式中創建陣列，則此陣列中元素表示每個人的編號，然后將編號寫入線性表，接著通過輸入陳述句輸入n值和m的值，然后通過回圈函式將陣列中的第m%n個數提取出來，相當于洗掉了線性表的這個元素，然后將線性表中元素重新排列，相當于將被洗掉的元素的下一個元素作為陣列的開頭，將線性表重新排列，接著將這個提取出來的元素有順序的存入到一個新的陣列，最后通過輸出陳述句將這個新的陣列輸出出來。
5. 主要代碼
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 50
typedef int ElemType;
typedef struct{
ElemType data[MaxSize]; //存放資料表中的元素
int length; //存放線性表的長度
}SqList; //順序表型別
void CreateList(SqList *&L,ElemType a[],int n) { //建立順序表
int i=0,k=0;
L=(SqList *)malloc(sizeof(SqList));
while(i<n){
L->data[k]=a[i];
k++;i++;
}
L->length=k;
}
void DispList(SqList *L){ //輸出線性表（用來測驗線性表中的元素是否正確）
for(int i=0;i<L->length;i++)
printf("%d",L->data[i]);
printf("\n");
}
bool ListDelete(SqList *&L,int i,ElemType &e){ //洗掉資料元素并將那個元素提取出來
int j;
int k,num=0,p,q;
int a[50];
for(j=0;j<L->length;j++){
a[j]=L->data[j];
}
k=i%L->length;
p=k;
q=(i-1)%L->length;
e=L->data[q];
for(j=1;j<=L->length-1;j++){
L->data[num]=a[p];
num++;
k++;
p=k%(L->length);
}
L->length--;
return true;
}
void DestroyList(SqList *&L){ //銷毀線性表
free(L);
}
int main(){
SqList *L;
ElemType a[50];
int n,i;
scanf("%d",&n);
for(i=1;i<=n;i++){
a[i-1]=i;
}
CreateList(*&L,a,n);
int m,e;
ElemType b[50];
scanf("%d",&m);
for(i=0;i<n;i++){
ListDelete(*&L,m,e);
b[i]=e;
}
for(i=0;i<n;i++){
printf("%d",b[i]);
}
DestroyList(*&L);
return 0;
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/32549.html
標籤：C++ 語言
上一篇：能問下為什么一定要加這一行處理非整數輸入的代碼呢？不加的話為什么輸入其他整數程式會自動清理多余的數，而輸入字符卻不能呢？
下一篇：0x7C92E63C (ucrtbased.dll)處(位于 VS.exe 中)引發的例外: 0xC0000005: 寫入位置 0x00D00000 時發生訪問