約瑟夫環的數組，約瑟夫環數組

約瑟夫環的數組，約瑟夫環數組

    最近忙著提升自身的訪談能力，美其曰：“提高自身的業務能力”，兩字呵呵。感覺在公司前途一片黑暗，連絲曙光都不見，好在我有一顆強大的❤，感謝mother 。因為模擬對象中有一位學習中等，在班中揚言..... 此處略去一百字，所以我就想到自己教過的學生中就有這麼一位。 然後就和他QQ聊了兩句，我怎麼能這麼敬業呢O__O"…。 沒想到該學生現在准備學IOS，IOS可是我一直想去學沒學的技術啊，簡直帥爆了。 今天早上他給我發了一道題：約瑟夫環的數組實現。為了打發我郁悶苦逼的心情和大把的時間，做了一下。 最後發現網上有寫好的demo比我的要好，於是乎我就重新整理，添加了注釋。題和正解如下：

  

約瑟夫環的數組實現

約瑟夫(Josephus)問題是由古羅馬的史學家約瑟夫提出的,他參加並記錄了公元 66-70 年猶太人反抗羅馬的起義。約瑟夫作為一個將軍,設法守住了裘達 伯特城達 47 天之久,在城市淪陷之後,他和 40 名將士在附近的一個洞穴中避難。在哪裡,將士們群情激奮並表示:要投降毋寧死。於是,約瑟夫建議每個人輪流殺死他旁邊的人,而這個順序是由抽簽決定的。約瑟夫有預謀地抓到了
最後一簽並且做為洞穴中兩個幸存者之一生存下來。

約瑟夫環問題的具體描述是:設有編號為 1,2,......,n 的 n(n>0)個人圍成一 個圈,從第一個人開始報數,報到 m 時停止報數,報 m 的人出圈,再從他的 下一個人起重新報數,

報到 m 時停止報數,報 m 的出圈,......,如此下去,知道只剩下一人為止。當任意給定 n 和 m 後,設計算法求 n 個人出圈的次序。

假設有n=5  ,5個人： 1 ，2 ， 3， 4， 5 ，

從第1個人開始報數字， 如果報的數字m為 2， 這個人被同伴殺死，出局
被殺死人的順序是： 2, 4, 3, 1, 5

 

代碼如下

1 /// <summary> 2 /// 約瑟夫環的數組實現 3 /// </summary> 4 /// <param name="n">總人數</param> 5 /// <param name="m">從編號為幾開始數數</param> 6 /// <param name="k">數到幾的人出局</param> 7 public static void Josehp(int n, int m, int k) 8 { 9 10 //創建一個和總人數相同長度的數組 11 int[] array = new int[n]; 12 for (int i = 0; i < n; i++) 13 { 14 array[i] = i + 1; //循環給每一個數組元素賦值，編號為 1, 2, 3, 4 ,...., n 15 } 16 17 18 int count = 0; //記錄數數的標號 19 20 int number = n; //記錄剩余的總人數 21 22 while (number > 1) 23 { 24 for (int i = 0; i < n; i++) //循環遍歷數據裡面的每一個元素 25 { 26 if (m != 1) //如果不是從編號1開始 27 { 28 i = m - 1; //從 m 為的成員開始， m 為的這個人 為第1個人 29 m = 1; 30 } 31 if (array[i] == 0) //判斷array[i] 這個人是否已經出局，如果出局，繼續循環，判斷下一位 32 continue; 33 count++; 34 if (count == k) //如果要數的數字與出局數字相同 35 { 36 Console.Write(array[i] + " "); //輸出出局的編號 37 array[i] = 0; //將該位置標記為0 38 count = 0; //數數標號從0開始 39 number--; //總人數 -1 40 } 41 } 42 } 43 44 45 //循環判斷不為0的元素，即為最終留下的人 46 for (int i = 0; i < n; i++) 47 { 48 if (array[i] != 0) 49 { 50 Console.Write(array[i]); 51 break; 52 } 53 } 54 55 Console.WriteLine(); 56 } 約瑟夫環的數組實現 1 static void Main(string[] args) 2 { 3 Console.WriteLine("請輸入總人數："); 4 int m = int.Parse(Console.ReadLine()); 5 6 Console.WriteLine("請輸入報數："); 7 int n = int.Parse(Console.ReadLine()); 8 9 Console.Write("總人數是{0}, 從第{1}個人開始數數, 數到{2}時出局，出局人的順序是：",m,1,n); 10 Josehp(m,1,n); 11 12 Console.ReadLine(); 13 } 測試代碼

 

用數組實現約瑟夫環的問題

其實用數組很難的
建議你用循環鏈表,不過我用數組寫一個給你不知道你會不會看得懂
void shuzu(int n,int m,int s)
{//n為元素個數,m為要刪除的號數,s是當前要刪除的
//同時s也是報數的開始
int a[],j,i;
for(i=1;i<n+1;i++)
a[i]=i;//排列
printf("\n");
for(i=n;i>=2;i--)//i為當前的表(數組中非0元)長
{s=(s+m-1)%i;//是要刪除,同時也控制轉向
if(s==0)s=i;//當s=i時不轉向所以s還不為0而是i
printf("%d",a[s]);
for(j=s;j<=i-1;j++)
a[j]=a[j+1];//從s開始都前移一位,這樣刪除s
}
printf("\n");
printf("%d",a[i]);
}
 

用數組實現C語言 約瑟夫環問題

#include<stdio.h>

#define max 100

int main()

{

int JOSEPHU[max];

int N,M,begin; /* N: total number M: skip begin: begin */

int flag=0; /* If flag is equal to M, print the current number. */

int i; /* Contrl tht loop */

printf("Input N,M and begin: ");

scanf("%d %d %d",&N,&M,&begin);

printf("\n");

begin=begin-1;

/* Assignment the array and assignment the element not used 0 and finally display it. */

for(i=0;i<N;i++)

{

JOSEPHU[i]=i+1;

printf("%d ",JOSEPHU[i]);

}

for(i=N;i<max;i++)

JOSEPHU[i]=0;

printf("\n\n");

/* JOSEPHU[begin]=JOSEPHU[begin-1] */

for(i=2;;i++)

{

if(JOSEPHU[begin]!=JOSEPHU[N-1]) /* If the current element is not equal to the last elemnet of array JOSEPHU,then the next element. */

begin++;

else

{

begin=0; /* If the current element is equal to the last element,then the first element. */

while(JOSEPHU[begin]<0) /* When there are negative elements,skip them. */

begin++;

if(i%M==0) /* If satisfied, print the element and assignment it as negative, and increase the value of flag. */

{

printf("%d ",JOSEPHU[begin]);

JOSEPHU[begin]=-JOSEPHU[begin];

flag++;

}

if(flag==N) /* If flag is equal to total number, the loop is broken. */

break;

......余下全文>>