- #define REMOVED -1
- // #define VERBOSE_DEBUG 1
- void joseph_UT1(void)
- {
- // int val[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}; // 7
- // int val[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}; // 11
- //
- int val[] = {1, 2, 3, 4, 5, 6, 7, 8, }; // 1
- int len = sizeof val/ sizeof(val[0]);
- printf ("%d\\n", joseph(val, len, 0, 2));
- }
- void joseph_UT2(void)
- {
- int val[2048], i, j;
- for (i=1; i<2048; ++i) {
- memset(val, sizeof(val), 0x00);
- for (j=0; j<i; ++j)
- val[j]=j+1;
- printf ("\\t\\t%d\\t\\t%d\\n", i, joseph(val, i, 0, 1));
- }
- }
- void joseph_UT3(void)
- {
- unsigned int i;
- for (i=1; i<2048; ++i) {
- printf ("\\t\\t%u\\t\\t%u\\n", i, joseph_bit_operation(i));
- }
- }
- /*
- * joseph number (j) of given number (i)
- * when in step 1, i.e. 1, 2, 1, 2, 1, 2, ....
- *
- * i j i_bin j_bin
- * --------------------------------
- * 8 1 1000 0001
- * 9 3 1001 0011
- * 10 5 1010 0101
- * 11 7 1011 0111
- * 12 9 1100 1001
- * 13 11 1101 1011
- * 14 13 1110 1101
- * 15 15 1111 1111
- * 16 1 10000 0001
- */
- int joseph_bit_operation(unsigned int i) {
- unsigned int a = i, exp, mask = 0x1;
- for (exp=0; a; ++exp) // count bit order of leftmost 1, 1101's left most 1 bit order is 4
- a>>=1;
- mask <<= exp; // now, 1101 will get 10000 as mask
- i <<= 1; // 1101 -> 11010
- i ^= mask; // 1101 ^ 10000 = 1010
- i += 1; // the joseph number
- return i;
- }
- // STEP = 2; // 1, 2, 3, 1, 2, 3
- int joseph(int val[], int cnt, int init_pos, int step)
- {
- int end = cnt;
- int pos = init_pos, i;
- if (cnt<=1) return val[0];
- while (cnt>1)
- {
- for (i=0; i<step; ++i){
- do {
- pos += 1;
- pos %= end; /* if (pos>=end) pos -= end; */
- } while (val[pos]==REMOVED);
- }
- #ifdef VERBOSE_DEBUG
- printf("remove %d\\n", val[pos]);
- #endif
- val[pos] = REMOVED;
- do {
- pos += 1;
- pos %= end;
- } while (val[pos]==REMOVED);
- --cnt;
- }
- #ifdef VERBOSE_DEBUG
- printf("The last one is %d\\n", val[pos]);
- #endif
- return val[pos];
- }
- int main(int argc, char argv[])
- {
- //joseph_UT1();
- //joseph_UT2();
- joseph_UT3();
- return 1;
- }
- //该片段来自于http://www.codesnippet.cn/detail/2407201513212.html
来源: http://www.codesnippet.cn/detail/2407201513212.html