一个小编程题-类似约瑟夫环问题 - 我没有座右铭 - ITeye技术网站

一个小编程题-类似约瑟夫环问题 - 我没有座右铭 - ITeye技术网站
        一个数列,把第一个元素删除,然后把第二个元素放到数列的最后,依次操作下去,直到把数列中所有的数都删除,要求依次打印出这个过程中删除的数。

        想一下这个过程类似于约瑟夫环,相当于把数组当成一个环,然后每隔一个数删掉一个数,直到把所有的数删完,当然这个过程中要打印出被删除的数。

1. /** 
2.  * 思路：弄一个bit数组和目标数组一一对应,如果目标数据项被'删除', 
3.  * 那么在对应的bit数组上做一下标记,下次数step的时候会跳过这些 
4.  * 别标记的bit。 
5.  *  
6.  * @param array 
7.  */  
8. public static void pirntFromArray(int[] array){  
9.     int len = array.length;  
10.     BitSet bitSet = new BitSet(len);  
11.     int p = 0;  
12.     for(int i=0;i<len;i++){  
13.         System.out.print(array[p] + " ");  
14.         bitSet.set(p);  
15.         int s = 2;  
16.         while(s > 0 && i != len - 1){  
17.             p = (len - p) == 1 ? 0 : p + 1;  
18.             if(!bitSet.get(p)){  
19.                 s -- ;  
20.             }  
21.         }  
22.     }  
23. }  

Read full article from 一个小编程题-类似约瑟夫环问题 - 我没有座右铭 - ITeye技术网站

POJ 3517 -- And Then There Was One (Joseph)

POJ 3517 -- And Then There Was One (Joseph)

Description

Let’s play a stone removing game.
Initially, n stones are arranged on a circle and numbered 1, …, n clockwise (Figure 1). You are also given two numbers k and m. From this state, remove stones one by one following the rules explained below, until only one remains. In step 1, remove stone m. In step 2, locate the k-th next stone clockwise from m and remove it. In subsequent steps, start from the slot of the stone removed in the last step, make k hops clockwise on the remaining stones and remove the one you reach. In other words, skip (k − 1) remaining stones clockwise and remove the next one. Repeat this until only one stone is left and answer its number. For example, the answer for the case n = 8, k = 5, m = 3 is 1, as shown in Figure 1.

Initial state	Step 1	Step 2	Step 3	Step 4
Step 5	Step 6	Step 7	Final state

http://blog.csdn.net/code_or_code/article/details/38702275
数字1到n成环，先叉数字m，往下数k个，直到最后只有一个数字，输出它。
http://www.bkjia.com/ASPjc/866918.html
经典的约瑟夫环问题嘛。有点小小的变形而已。给你N个人围成一个环（编号1~N），从第M个人开始，每隔K个人报一次数，报数的人离开该环。
求最后剩下的人的编号。
约瑟夫问题的数学递推解法：
（1）第一个被删除的数为 (m - 1) % n。
        （2）假设第二轮的开始数字为k，那么这n - 1个数构成的约瑟夫环为k, k + 1, k + 2, k +3, .....,k - 3, k - 2。做一个简单的映射。
             k         ----->  0 
             k+1    ------> 1 
             k+2    ------> 2 
               ... 
               ... 
             k-2    ------>  n-2 
        这是一个n -1个人的问题，如果能从n - 1个人问题的解推出 n 个人问题的解，从而得到一个递推公式，那么问题就解决了。假如我们已经知道了n -1个人时，最后胜利者的编号为x，利用映射关系逆推，就可以得出n个人时，胜利者的编号为 (x + k) % n。其中k等于m % n。代入(x + k) % n  <=>  (x + (m % n))%n <=> (x%n + (m%n)%n)%n <=> (x%n+m%n)%n <=> (x+m)%n
        （3）第二个被删除的数为(m - 1) % (n - 1)。
        （4）假设第三轮的开始数字为o，那么这n - 2个数构成的约瑟夫环为o, o + 1, o + 2,......o - 3, o - 2.。继续做映射。
             o         ----->  0 
             o+1    ------> 1 
             o+2    ------> 2 
               ... 
               ... 
             o-2     ------>  n-3 

         这是一个n - 2个人的问题。假设最后的胜利者为y，那么n -1个人时，胜利者为 (y + o) % (n -1 )，其中o等于m % (n -1 )。代入可得 (y+m) % (n-1)
         要得到n - 1个人问题的解，只需得到n - 2个人问题的解，倒推下去。只有一个人时，胜利者就是编号0。下面给出递推式：
          f [1] = 0; 

          f [ i ] = ( f [i -1] + m) % i; (i>1) 

1.     int n,m,k;  
2.     while(~scanf("%d%d%d",&n,&k,&m))  
3.     {  
4.         if(n==0 && m==0 && k==0)  
5.             break;  
6.         int s=0;  
7.         for(int i=2;i<=n-1;i++)  
8.             s=(s+k)%i;  
9.         printf("%d\n",(s+m)%n+1);  
10.     } 

1. struct Link{  
2.     int data;  
3.     Link* next;  
4.     Link* pre;  
5. }node[10001];  
6.   
7. int main()  
8. {  
9.     int n,k,m;  
10.     while(scanf("%d%d%d",&n,&k,&m),n||k||m)  
11.     {  
12.         for(int i=1;i<=n;i++)                            //构建双向循环链表  
13.         {  
14.             node[i].data=i;  
15.             node[i].next=(i==n)?&node[1]:&node[i+1];  
16.             node[i].pre=(i==1)?&node[n]:&node[i-1];  
17.         }  
18.         Link* p=&node[m];  
19.         p->pre->next=p->next;  
20.         p->next->pre=p->pre;  
21.         p=p->next;  
22.         int loop=k;  
23.         int t=1;  
24.         while(p->next!=p)  
25.         {  
26.             if(k%(n-t)==0)            //优化，若无会TLE  
27.                 loop=k;  
28.             else  
29.                 loop=k%(n-t);  
30.             for(int i=1;i<loop;i++)  
31.                 p=p->next;  
32.             p->pre->next=p->next;  
33.             p->next->pre=p->pre;  
34.             p=p->next;  
35.             t++;  
36.         }  
37.         printf("%d\n",p->data);  
38.   
39.     }  
40.     return 0;  
41. }  

Also refer http://blog.csdn.net/kenden23/article/details/30050425
Read full article from 3517 -- And Then There Was One

POJ 1012 -- Joseph

POJ 1012 -- Joseph

Description

The Joseph's problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, . . ., n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved.

Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys. You have to determine such minimal m that all the bad guys will be executed before the first good guy.

Input

The input file consists of separate lines containing k. The last line in the input file contains 0. You can suppose that 0 < k < 14.

Output

The output file will consist of separate lines containing m corresponding to k in the input file.

Sample Input

3
4
0

Sample Output

5
30

k个好人与k个坏蛋站一圈，前k个都是好人，从1开始报数，报道m的枪毙，下一个再从1开始报数，以此类推！求一个数m，当剩下k个人时，满足他们都是好人

a[j]为第j次退出圈的人的编号（从0开始），每退出一个人，圈就缩小，圈中的人的

编号就相应的改变，这点很重要！！！比如k=5时，3个退出的人的编号

 依次是4、3、3，对应开始时的编号就是5、4、6

设a[i]表示第i个出局者的位置，a[i-1]表示第i-1个出局者的位置，则

a[i]=a([i-1]-1+m)%len (len表示当前人数)

剪枝为：前k个人的编号永远不变，若退出的人在前k个人之前，则该方案错误

                即if(a[j]<k) break;

http://chaoshuimm.iteye.com/blog/1039305

1. /*  
2. 　测试ｍ是否满足要求 
3. 　k: 有2ｋ个人 
4. 　ｍ：每数到ｍ就出局 */  
5. bool test(int k, int m) {  
6.     int i = 0, len = 2 * k;　//len: 当前总人数  
7.     while(len > k) {  
8.         i = (i + m - 1) % len;  //每次出局人是出局前的len 个人中的第i 个, 下标从0 开始  
9.         if(i < k)      
10.             return false;  
11.         len--;  //没出局一个,修改len  
12.     }  
13.     return true;  
14. }  
15.   
16. int main() {  
17.     int k;  
18.     int a[14] = {0};    //数组保存计算过的数据, 不保存的话会超时,  
19.                         //其实很无聊,就14个数据,还整这么大的数据量  
20.     while(scanf("%d", &k) && k) {  
21.          if(!a[k]) {    //如果a[k]为0 就进行测试  
22.             int t = k + 1;  //测试从k+1开始,下于K+1的测试没必要  
23.             while(true) {  
24.                 if(test(k, t)) {  
25.                     a[k] = t;  
26.                     break;  
27.                 }  
28.                 else  
29.                     t++;  
30.                 if(t == 2 * k)//跳过不必要的测试  
31.                     t += k + 1;  
32.             }  
33.         }  
34.         printf("%d\n", a[k]);  
35.     }  
36.     return 0;  
37. } 

  据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

  本题类似于这样一则描述：17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事：15个教徒和15 个非教徒在深海上遇险，必须将一半的人投入海中，其余的人才能幸免于难，于是想了一个办法：30个人围成一圆圈，从第一个人开始依次报数，每数到第九个人就将他扔入大海，如此循环进行直到仅余15个人为止。问怎样排法，才能使每次投入大海的都是非教徒。

http://fayaa.com/code/view/26765/
http://www.cnblogs.com/pcwl/archive/2011/04/26/2029188.html
http://www.xuebuyuan.com/723343.html
Read full article from 1012 -- Joseph