C語言約瑟夫環問題
編號為 1,2,3,…,n 的 n 個人圍坐一圈,任選一個正整數 m 作為報數上限值,從第一個人開始按順時針方向報數,報數到 m 時停止,報數為 m 的人出列。從出列人的順時針方向的下一個人開始又從 1 重新報數,如此下去,直到所有人都全部出列為止。
算法思想
每個人的編號存放在一個數組 a 中,主函數中決定人數的個數以及報數的上限值 m,設計一個函數實現對應的操作。函數的形參有整型數組 a、整數 n 和 m,n 用來接收傳遞的人數,m 用來接收報數上限,函數的返回值為空;函數體中輸出出列人的順序。
函數中利用循環訪問數組中 n 個元素,每次訪問元素,設定內循環連續訪問 m 個元素,元素訪問的下標為 k,訪問到第 m 個元素時,如果元素不是 0,此時輸出元素 a[k],再設定 a[k] 為 0,繼續訪問后面的元素。
主函數中設定數組 a,從鍵盤輸入 n 和 m,利用循環產生 n 的位置序號存放到數組 a 中,調用函數實現相應的操作。
程序代碼
#include <stdio.h>
#define N 100
int josef(int a[],int n,int m)
{
int i,j,k=0;
for(i=0;i<n;i++)
{
j=1;
while(j<m)
{
while(a[k]==0)
k=(k+1)%n;
j++;
k=(k+1)%n;
}
while(a[k]==0)
k=(k+1)%n;
printf("%d ",a[k]);
a[k]=0;
}
return 0;
}
int main()
{
int a[100];
int i,j,m,n;
printf("input n and m:");
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
a[i]=i+1;
printf("\n output:\n");
josef(a,n,m);
printf("\n");
return 0;
}
調試運行結果
15 個人圍坐在一起,報數上限為 4 時的出列順序如下所示:
input n and m:15 4
output:
4 8 12 1 6 11 2 9 15 10 5 3 7 14 13
100 個人圍坐在一 起,報數上限為 9 時的出列順序如下所示:
input n and m:100 9
output:
9 18 27 36 45 54 63 72 81 90 99 8 19 29 39 49 59 69 79 89 100 11 22 33 44 56 67
78 91 2 14 26 40 52 65 77 92 4 17 32 47 61 75 88 5 21 37 53 70 85 1 20 38 57 74
94 12 31 51 73 95 15 41 62 84 7 34 60 86 13 43 71 98 30 66 97 35 76 10 50 93 42
83 28 87 48 6 68 46 23 3 96 16 25 64 55 58 24 80 82
總結
① 程序由 main() 函數和 josef() 函數組成,main() 函數調用 josef() 函數,用數組名作為函數參數,在主函數和被調用函數中分別定義數組。主函數執行到 josef(a,n,m) 語句時,將數組 a 的首元素的地址傳遞給形參數組 a,程序轉去執行 josef(),形參數組 a 中的元素發生逆序排列,則實參數組 a 也隨之改變,當 josef() 執行完后,返回到主函數中繼續執行被調函數后面的語句。
② 實例中定義函數 josef() 解決問題的難點有兩個:一是如何求下一個出圈的人的位置;二是此人出圈后對這個人的位置如何處理。從第一個人開始報數,報到 m 時,此人出圈,設定變量 j,每次統計出圈的人數,當出圈人數到 m 時,重新開始統計。n 個人圍坐一圈,可看作環狀,設定 k 表示出圈人的下標,則出圈人的下標的計算可用“(k+l)%n”表示。對于第二個問題,首先將出圈人的位置打印輸出,然后將其位置元素設置為 0。
③ 數組名作函數參數時,要求在被調用函數和調用函數中分別定義數組,且形參和實參必須是類型相同的數組。實參和形參數組是指向同一段地址空間的,當主函數執行時,這段空間由實參數組控制,當被調用函數執行時,這段空間由形參數組使用,被調函數執行結束后,該空間又交回給實參數組。
用數組名作為函數參數時,形參與實參之間的傳遞方式為地址傳遞,因此,形參數組的改變會影響實參數組的內容。
C 編譯系統對形參數組的大小不做檢查,只是將實參數組的首地址傳給形參數組,所以形參數組可以不用指定大小。如實例中被調用函數的首部定義為 void josef(int a[], int n,int m),其中的整型數組 a 的定義為 int a[],沒有給出數組的具體大小。
④ 一維數組名、多維數組名都可以作為函數的參數,進行地址傳遞。
- C語言整數逆序輸出
- 將一個從鍵盤輸入的整數存放到一個數組中,通過程序的運行按照數組中的逆序輸出該整數,利用遞歸的方法解決問題。
- 03-10 關注:0
- C語言約瑟夫環問題
- 編號為 1,2,3,…,n 的 n 個人圍坐一圈,任選一個正整數 m 作為報數上限值,從第一個人開始按順時針方向報數,報數到 m 時停止,報
- 03-10 關注:0
- C語言輸出等腰三角形
- 本實例要求從鍵盤輸入任意整數 n,通過程序運行輸出對應高度為 n 的等腰三角形。
- 03-10 關注:0
- C語言字符串加密和解密算法
- 在本實例中要求設計一個加密和解密算法。在對一個指定的字符串加密之后,利用解密函數能夠對密文解密,顯示明文信息。
- 03-09 關注:3
- C語言統計單詞個數,單詞個數算法
- 在實際生活中經常會遇到一個問題:寫英語作文時,常常要求滿足一定的字數。在以往,要么我們一個一個地數;要么我們估算一行的單詞數,
- 03-09 關注:3
- C語言獲取矩陣的最大值及其下標
- 本實例要求使用二維數組將一個 3×4 的矩陣中所有元素的最大值及其下標獲取,通過該程序,掌握二維數組的引用知識。
- 03-09 關注:4
- C語言誰家孩子跑得最慢
- 張、王、李三家各有三個小孩。一天,三家的九個孩子在一起比賽短跑,規定不分年齡大小,跑第一得 9 分,跑第二得 8 分,依次類推。
- 03-09 關注:3
- C語言狼追兔子問題
- 一只兔子躲進了 10 個環形分布的洞的某一個,狼在第一個洞沒有找到兔子,就隔一個洞,到第三個洞去找
- 03-09 關注:2