最先大學講到這個問題時,就是學習C語言到數組的時候,只須要用數組和指針就能夠解決,好像解決的方法還不少。
主要須要解決兩個問題:
1.指針循環遞增到數組結尾時,須要跳轉到數組開頭。
2.出列後,數組中相應的值設爲0。
其實還要考慮到一個小問題,好比:總人數100人,數到13出列,若是剛開始指針在數組的第一位,數到13時,就對應數組的第14個數,這確定不行。因此數組設爲a[101],a[0]不計入人數,從a[1]至a[100]計入1至100的數字。web
#include <stdio.h> #include <time.h> #define NUM 100 //The total number of people who stand around in a circle . #define REP 15 //The counting number the REP-th person who will be executed . unsigned jos(unsigned n,unsigned rec) { unsigned a[n+1],b[n],i,j=1; //From a[1] to a[n] is the number of 1 to n; and the numbers from b[0] to b[n-1] is the result of Josephus permutation. unsigned *pio=a; a[0]=999; //The count begins at 0(zero),and the next count is 1.a[0] can be assigned any value beyond 0 and NUM. for(i=1;i<=n;i++){ //Assign the value from 1 to n to a[1]......a[n] respectively . pio++; *pio=i; } pio=&a[0]; //Initialize *pio. for(i=0;i<n+1;i++){ for(j=1;j<=rec;j++){ if(i==n) break; //Once i=n, the for loop of j ends , then the for loop of i also ends. if(pio==&a[n+1]) pio=&a[1]; //pio++,but there is an exception ,when the counting comes to the end a[n+1] , it should restart from a[1]. else pio++; //printf("%ld\t",(pio-&a[0])); /*Psb. 1*/if(*pio==0) j=j-1; /*Psb. 2*/else if((j==rec)){ b[i]=*pio; *pio=0; //Once j comes to the counting number , set the corresponding value of a[] to zero . j=1; //Set j to 1, and the loop repeats. break; //Get out of j loop. } } } for(i=0;i<n;i++) (i%10==9)?printf("%-5d\n",b[i]):printf("%-5d",b[i]); //Print b[], 10 numbers per row. return b[n-1]; } int main(void) { clock_t start, end; start = clock(); // Time on. if(REP>NUM){ printf("ERROR !\nThe counting number is bigger than the total number of people !\n "); return 1; } int mp,i=0; mp = jos(NUM,REP); printf("\nThe final number is %d.\n\n\n",mp); end = clock(); //Time off . printf("time=%.4f\n", (double)(end - start) / CLOCKS_PER_SEC); return 0; }