Joseph problem

发现脑袋有点被教科书和习惯禁锢了，joseph 这个问题在大二的时候是用循环链表实现的。
今天做创新工程的笔试题目，我也用相同的方法做的。回来反思，那样效率太低，尤其是当要报的数据非常大
时，所以想了一个新算法，主要是数学计算预测大概位置，使得每删除一个人，最多一遍循环。

1 #include <stdio.h>
  2 #include <stdlib.h>
  3 /*m is the number of human
  4 *n is the counter number
  5 */
  6 int joseph(int m,int n)
  7 {
  8 int *flag;/* 1 means in ,0 means out*/
  9 int i,j;
 10 flag=(int *)malloc((m+1)*sizeof(int));
 11 for(i=0;i<m+1;i++)
 12 flag[i]=1;
 13 /*fast algo*/
 14 /*inital value */
 15 int period, factor,remainder;
 16 int say;
 17 int suffix;
 18 period=m;
 19 factor=(int)n/period;
 20 remainder=n%period;
 21 period=m;
 22 say=0;
 23 int search;
 24
 25 suffix=0;
 26 while(period>1)
 27 {
 28 factor=(int)(n-suffix)/period;
 29 remainder=(n-suffix)%period;
 30
 31 if(remainder==0)
 32 {
 33 search=period;
 34 }
 35 else
 36 search=remainder;
 37 int c=0;
 38 for(j=1;j<=m && c<search;j++)
 39         {
 40             if(flag[j]==1)
 41             {
 42                 c++;
 43             }
 44         }
 45          say=j-1;
 46          flag[j]=0;
 47         printf("**\n");
 48        period=period-1;
 49     suffix=0;
 50     for(j=say+1;j<=m; j++)
 51     {
 52         if(flag[j]==1)
 53             suffix++;
 54     }
 55        printf("say %d %d\n",say,suffix);
 56     }
 57 return say;
 58 }
 59
 60 int main(int argc, char **argv)
 61 {
 62     int m,n,say;
 63     m=atoi(argv[1]);
 64     n=atoi(argv[2]);
 65     say=joseph(m,n);
 66     printf("%d\n",say);
 67     return 0;
 68 }

gcc -g -o joseph joseph.c
 ./joseph 4 8