趣解约瑟夫环 (C/C++爱好者 !!可能会值得你看!!）

引言:

本题其实是来源于一个非常著名的犹太故事--------约瑟夫环!

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

编译环境: Debain Ubuntu gcc

测试图片:

解题思路:
数学公式推导:

  /* If number = 3

     * f(1) = 0

     * f(2) = 1 = (f(1) + 3) % 2

     * f(3) = 1 = (f(2) + 3) % 3

     * f(4) = 0 = (f(3) + 3) % 4

     * f(5) = 3 = (f(4) + 3) % 5

     * ...

     * f(n) = x = (f(n-1) + 3) % n

     * */

   结果应该是f(n)+1。
参考代码:

  1 #include <iostream>
  2 #include <list>      //链表
  3 using namespace std;
  4 int main()
  5 {
  6     int total  = 0;
  7     cin >> total;    //输入环总数
  8     int number = 3;  //循环
  9     int last = 0;    // f(1) = 0
 10     for(int i = 2; i <= total; ++i)
 11         last = (last + number) % i;
 14     cout<< last+1 <<endl;
 15     return 0;
 16 }