12.三色旗

经典问题算法(下) - 图1

  1.     /**
  2.      * 三色旗
  3.      * 有一条绳子，上面挂有白、红、蓝三种颜色的多面旗子，这些旗子的排列是无序的。
  4.      * 现在要将绳子上的旗子按蓝、白、红三种颜色进行归类排列，但是只能在绳子上进行旗子的移动，并且每次只能调换两个旗子。
  5.      * 问如何采用最少的步骤来完成三色旗的排列
  6.      * 解：
  7.      * 用b来表示蓝色（blue）旗子
  8.      * 用w来表示白色（write）旗子
  9.      * 用r来表示红色（red）旗子
  10.      * 在0～(blue-1)之间放蓝色旗子，blue～(write-1)之间放白色旗子，write～(red-1)之间放红色旗子
  11.      */
  12.     public static void threeColorFlags() {
  13.         while (flags[write] == 'b') {
  14.             blue++;//向后移动蓝旗
  15.             write++;//向后移动白旗
  16.         }
  17.         while (flags[red] == 'r') {
  18.             red--;
  19.         }
  21.         while (write <= red) {
  22.             if (flags[write] == 'r') {//红旗
  23.                 swap(flags, write, red);//对调红旗和白旗
  24.                 red--;
  25.                 while (flags[red] == 'r') {//向前移动红旗
  26.                     red--;
  27.                 }
  28.             }
  29.             while (flags[write] == 'w') {//白旗
  30.                 write++;
  31.             }
  32.             if (flags[write] == 'b') {//蓝旗
  33.                 swap(flags, write, blue);//对调
  34.                 blue++;
  35.                 write++;
  36.             }
  37.         }
  38.     }
  40.     static void swap(char[] flags, int x, int y) {
  41.         char temp = flags[x];
  42.         flags[x] = flags[y];
  43.         flags[y] = temp;
  44.         flagsCount++;
  45.         System.out.printf("第%d次对调后：", flagsCount);
  46.         for (char flag : flags) {
  47.             System.out.printf(" %c ", flag);
  48.         }
  49.         System.out.printf("\n");
  50.     }
  52.     static char[] flags = "rwbwwbrbwr".toCharArray();
  53.     static int blue = 0, write = 0, red = flags.length - 1, flagsCount = 0;

调用：

  1.         System.out.print("三色旗初始排序：");
  2.         for (char c : flags) {
  3.             System.out.print(c + " ");
  4.         }
  5.         System.out.print("\n");
  6.         threeColorFlags();
  7.         System.out.printf("对调结束后，blue = %d, write = %d, red = %d", blue, write, red);

输出：

  1. 三色旗初始排序：r w b w w b r b w r 
  2. 第1次对调后： w  w  b  w  w  b  r  b  r  r 
  3. 第2次对调后： b  w  w  w  w  b  r  b  r  r 
  4. 第3次对调后： b  b  w  w  w  w  r  b  r  r 
  5. 第4次对调后： b  b  w  w  w  w  b  r  r  r 
  6. 第5次对调后： b  b  b  w  w  w  w  r  r  r 
  7. 对调结束后，blue = 3, write = 7, red = 6

13.渔夫捕鱼

  1.     /**
  2.      * 渔夫捕鱼
  3.      * 一个典型的递推问题
  4.      * 某天晚上，A、B、C、D、E五个渔夫合伙捕鱼，捕到一定数量之后便停止捕鱼，各自到岸边休息。
  5.      * 第二天早晨，渔夫A第一个醒来，他将鱼分作五份，把多余的一条扔回河里，拿其中自己的一份回家去了。
  6.      * 渔夫B第二个醒来，也将鱼分作五份，扔掉多余的一条，拿走自己的一份。
  7.      * 渔夫C第三个醒来，也将鱼分作五份，扔掉多余的一条，拿走自己的一份。
  8.      * 渔夫D第四个醒来，也将鱼分作五份，扔掉多余的一条，拿走自己的一份。
  9.      * 渔夫E第五个醒来，也将鱼分作五份，扔掉多余的一条，拿走自己的一份。
  10.      * 问，五渔夫至少捕到多少条鱼？
  11.      * 解：
  12.      * 每一个渔夫醒来，都应该是5的倍数再加1.
  13.      * 所以，最后一个渔夫E醒来的时候，鱼的数量至少为6，
  14.      * D醒来的时候至少为6*5+1=31
  15.      * C醒来的时候至少为31*5+1=156
  16.      * 以此类推
  17.      */
  18.     public static void fisherCatchFish() {
  19.         int fisherNum = 5;//渔夫数量
  20.         int finishNum = fisherNum + 1;//最后一个渔夫醒来的时候，鱼的数量
  21.         int n = fisherNum - 1;
  22.         while (n > 0) {
  23.             finishNum = finishNum * 5 + 1;//每个渔夫醒来时候鱼的数量
  24.             n--;
  25.         }
  26.         System.out.printf("渔夫至少捕到 %d 条鱼。", finishNum);
  27.     }

调用：

  1.         fisherCatchFish();

输出：

  1. 渔夫至少捕到 3906 条鱼。

14.爱因斯坦的阶梯

  1.     /**
  2.      * 爱因斯坦（Einstein）的阶梯
  3.      * 数论问题
  4.      * Einstein有一天给他的朋友出了一个题目，有一个楼，其两层之间有一个很长的阶梯。
  5.      * 如果一个人每步上2阶，最后剩1阶；
  6.      * 如果一个人每步上3阶，最后剩2阶；
  7.      * 如果一个人每步上5阶，最后剩4阶；
  8.      * 如果一个人每步上6阶，最后剩5阶；
  9.      * 如果一个人每步上7阶；最后刚好一阶也不剩。
  10.      * 问这个阶梯至少有多少阶？
  11.      * 解：
  12.      * 右最后一个条件可知，阶梯的数量肯定为7的整数倍，
  13.      * 那可以从7开始，每次递加7，来判断是不是达到其他条件，直到找出都符合的那个值
  14.      */
  15.     public static void ladder() {
  16.         int ladderNum;
  17.         double max = 2.147483648e9;//2.147483648乘以10的9次方，也就是2147483648，int的最大取值范围
  18.         for (int i = 7; ; i += 7) {
  19.             if (i % 6 == 5 && i % 5 == 4 && i % 3 == 2 && i % 2 == 1) {
  20.                 ladderNum = i;
  21.                 break;
  22.             }
  23.             if (i > max - 1) {//i的值太大了,放弃寻找
  24.                 System.out.printf("未找到合适的解");
  25.                 return;
  26.             }
  27.         }
  28.         System.out.printf("这个阶梯至少有%d阶。", ladderNum);
  29.     }

调用：

  1.         ladder();

输出：

  1. 这个阶梯至少有119阶。

15.兔子产仔

参考 常用算法指南(一)基本算法思想 3.2 递推算法思想

16.常胜将军（取火柴游戏）

  1.     /**
  2.      * 常胜将军
  3.      * 甲和乙两个人玩取火柴的游戏，共有21根火柴，每个人每次最多取4根火柴，最少取1根火柴。
  4.      * 如果某个人取到最后一根火柴则输了，甲让乙先抽取，结果每次都是甲嬴，这是为什么？
  5.      * 解：
  6.      * 甲最后一次取完只剩一根，取之前应该是2-5根
  7.      * 所以在剩余2-5根的时候，甲只要剩余1根火柴，把其他全部取走就可以保证胜利了，
  8.      * 并且甲不是最后一次取火柴时，必须让剩余数大于5根，也就是剩余至少为6根，才可以保证赢。
  9.      */
  10.     public static void theBlow() {
  11.         int matchstickNum = 21;
  12.         Random random = new Random();
  13.         int n = 1;//计数器，n为单数的时候乙取，n为双数的时候甲取
  14.         System.out.printf("共计 %2d 根火柴\n", matchstickNum);
  15.         while (matchstickNum > 0) {
  16.             int num = random.nextInt(4) + 1;
  17.             if (n % 2 == 0 && matchstickNum >= 2 && matchstickNum <= 5) {//甲最后一次取火柴
  18.                 num = matchstickNum - 1;
  19.             } else if (n % 2 == 0 && matchstickNum - num < 6) {
  20.                 //甲不是最后一次取火柴，但是取完后剩余火柴数少于6根，减少甲取的数量，让剩余数不小于6根，否则可能会输
  21. //                num = num - (6 - (matchstickNum - num));
  22.                 num = matchstickNum - 6;
  23.                 if (num < 1) {//甲至少取一根
  24.                     num = 1;
  25.                 }
  26.             }
  27.             if (matchstickNum - num < 0) {//剩余的火柴全部取走
  28.                 num = matchstickNum;
  29.             }
  30.             matchstickNum -= num;
  31.             if (n % 2 == 0) {
  32.                 if (matchstickNum == 0) {
  33.                     System.out.printf("甲取了最后一根火柴,所以甲输了。");
  34.                 } else {
  35.                     System.out.printf("甲取了%2d 根火柴,剩余%2d 根\n", num, matchstickNum);
  36.                 }
  37.             } else {
  38.                 if (matchstickNum == 0) {
  39.                     System.out.printf("乙取了最后一根火柴,所以乙输了。");
  40.                 } else {
  41.                     System.out.printf("乙取了%2d 根火柴,剩余%2d 根\n", num, matchstickNum);
  42.                 }
  43.             }
  44.             n++;
  45.         }
  46.     }

调用：

  1.         theBlow();

输出：

  1. 共计 21 根火柴
  2. 乙取了 2 根火柴,剩余19 根
  3. 甲取了 4 根火柴,剩余15 根
  4. 乙取了 1 根火柴,剩余14 根
  5. 甲取了 2 根火柴,剩余12 根
  6. 乙取了 4 根火柴,剩余 8 根
  7. 甲取了 2 根火柴,剩余 6 根
  8. 乙取了 1 根火柴,剩余 5 根
  9. 甲取了 4 根火柴,剩余 1 根
  10. 乙取了最后一根火柴,所以乙输了。

17.新郎和新娘

  1.     /**
  2.      * 新郎和新娘
  3.      * 有三对新郎新娘参加集体婚礼，三个新郎为A、B、C，三个新娘为X、Y、Z。
  4.      * 司仪一时忘了谁应该和谁结婚，于是，他便问参加婚礼的6个人中的三个，得到的回答如下：
  5.      * 新郎A说他将和新娘X结婚；
  6.      * 新娘X说他将和新郎C结婚；
  7.      * 新郎C说她将和新娘Z结婚；
  8.      * 聪明的司仪知道他们在与他开玩笑，但是此时主持人已经推算出了谁应该和谁结婚。
  9.      * 那么到底谁应该和谁结婚呢？
  10.      * 解
  11.      * 由题可知，只要符合上面三个条件，则是错误的
  12.      * 所以只需要将两个char数组按照对应的排列组合，和上面的三个条件匹配，
  13.      * 如果符合其中一个，则错误，
  14.      * 如果上面的都不符合，则组合成功。
  15.      */
  16.     public static void groomAndBride() {
  17. //        char[] groom = {'A', 'B', 'C'};//新郎
  18.         char[] bride = {'X', 'Y', 'Z'};//新娘
  19.         int brideA = 0, brideB = 0, brideC = 0;//三个新郎对应新娘的下标
  20.         for (int i = 0; i < 3; i++) {
  21.             for (int j = 0; j < 3; j++) {
  22.                 for (int k = 0; k < 3; k++) {
  23.                     if (i != j && j != k && i != k) {
  24.                         if (bride[i] == 'X' || bride[k] == 'X' || bride[k] == 'Z') {
  25.                             break;
  26.                         } else {
  27.                             brideA = i;//A的新娘,不能是X
  28.                             brideB = j;
  29.                             brideC = k;//C的新娘，不能是Y和Z
  30.                         }
  31.                     }
  32.                 }
  33.             }
  34.         }
  35.         System.out.printf("A将要和%c结婚;\n", bride[brideA]);
  36.         System.out.printf("B将要和%c结婚;\n", bride[brideB]);
  37.         System.out.printf("C将要和%c结婚;", bride[brideC]);
  38.     }

调用：

  1.         groomAndBride();

输出：

  1. A将要和Z结婚;
  2. B将要和X结婚;
  3. C将要和Y结婚;

18.三色球

  1.     /**
  2.      * 三色球
  3.      * 排列组合问题
  4.      * 一个黑盒中放着3个红球、3个黄球和6个绿球，如果从其中取出8个球，那么取出的球中有多少种颜色搭配呢？
  5.      * 解：
  6.      * 8个球中取出每种球的可能性如下：
  7.      * 取出红球的数量：0-3个；
  8.      * 取出黄球的数量：0-3个；
  9.      * 取出绿球的数量：2-6个；
  10.      */
  11.     public static void threeColorsBall() {
  12.         int ballNum = 0;
  13.         int total = 8;
  14.         System.out.printf("取出球的颜色搭配的可能性：\n");
  15.         for (int i = 0; i <= 3; i++) {//红球
  16.             for (int j = 0; j <= 3; j++) {//黄球
  17.                 for (int k = 2; k <= 6; k++) {//绿球
  18.                     if (i + j + k == total) {
  19.                         System.out.printf("红球 %d ,黄球 %d ,绿球 %d \n", i, j, k);
  20.                         ballNum++;
  21.                     }
  22.                 }
  23.             }
  24.         }
  25.         System.out.printf("共计%d种颜色搭配。\n", ballNum);
  26.     }

调用：

  1.         threeColorsBall();

输出：

  1. 取出球的颜色搭配的可能性：
  2. 红球 0 ,黄球 2 ,绿球 6 
  3. 红球 0 ,黄球 3 ,绿球 5 
  4. 红球 1 ,黄球 1 ,绿球 6 
  5. 红球 1 ,黄球 2 ,绿球 5 
  6. 红球 1 ,黄球 3 ,绿球 4 
  7. 红球 2 ,黄球 0 ,绿球 6 
  8. 红球 2 ,黄球 1 ,绿球 5 
  9. 红球 2 ,黄球 2 ,绿球 4 
  10. 红球 2 ,黄球 3 ,绿球 3 
  11. 红球 3 ,黄球 0 ,绿球 5 
  12. 红球 3 ,黄球 1 ,绿球 4 
  13. 红球 3 ,黄球 2 ,绿球 3 
  14. 红球 3 ,黄球 3 ,绿球 2 
  15. 共计13种颜色搭配。

19.约瑟夫环求解

经典问题算法(下) - 图2

  1.     /**
  2.      * 约瑟夫环求解
  3.      * 约瑟夫环：
  4.      * 罗马人攻占了乔塔帕特，41个人藏在一个山洞中躲过了这场浩劫，这41个人中，包括历史学家Josephus(约瑟夫)和他的一个朋友，
  5.      * 剩余39个人为了表示不向罗马人屈服，决定集体自杀。大家决定了一个自杀方案，
  6.      * 所有这41个人围城一个圆圈，由第一个人开始顺时针报数，每报数为3的人就立刻自杀，
  7.      * 然后再由下一个人重新开始报数，仍然是每报数为3的人就立刻自杀，直到所有人都自杀身亡位置。
  8.      * 约瑟夫和他的朋友并不想自杀，于是约瑟夫想到了一个计策，他们两个同样参与到自杀方案中，但是最后却躲过了自杀。
  9.      *
  10.      */
  11.     public static void josephus( int allNum){
  12.         System.out.println("参与游戏的总人数：" + allNum);
  13.         int aliveNum = allNum;//存活人数
  14.         int [] arr = new int[allNum];
  15.         Arrays.parallelSetAll(arr, index -> 1);//初始化数组的每个元素为1，表示每个人都存活
  17.         int counter = 1;//报数器
  18.         int index = 0;//下标,位置等于下标+1
  19.         while(aliveNum >= 3){//存活人数不足3人时，停止游戏，
  20.             if(index == allNum){
  21.                 index = 0;
  22.             }
  23.             if( arr[index] == 1){//只有每轮存活的人才有权报数，已死亡的直接跳过
  24.                 if(counter == 3){
  25.                     arr[index] = 0;//标记这个人死亡
  26.                     aliveNum--;//有人死亡，存活人数-1
  27.                     counter = 0;//重置报数器
  28.                     System.out.printf("第[%d]个人死亡，初始位置为：[%d]\n",allNum-aliveNum,index+1);
  29.                 }
  30.                 counter++;//报数+1；
  31.             }
  32.             index++;//下标位置+1，轮到下一个人报数
  33.         }
  34.         System.out.print("存活人数不足3人，初始位置为：");
  35.         for(int i = 0;i < allNum;i++){
  36.             if(arr[i] == 1){
  37.                 System.out.print("[" + (i + 1) + "],");
  38.             }
  39.         }
  40.     }

调用：

  1.         josephus(41);

输出：

  1. 参与游戏的总人数：41
  2. 第[1]个人死亡，初始位置为：[3]
  3. 第[2]个人死亡，初始位置为：[6]
  4. 第[3]个人死亡，初始位置为：[9]
  5. 第[4]个人死亡，初始位置为：[12]
  6. 第[5]个人死亡，初始位置为：[15]
  7. 第[6]个人死亡，初始位置为：[18]
  8. 第[7]个人死亡，初始位置为：[21]
  9. 第[8]个人死亡，初始位置为：[24]
  10. 第[9]个人死亡，初始位置为：[27]
  11. 第[10]个人死亡，初始位置为：[30]
  12. 第[11]个人死亡，初始位置为：[33]
  13. 第[12]个人死亡，初始位置为：[36]
  14. 第[13]个人死亡，初始位置为：[39]
  15. 第[14]个人死亡，初始位置为：[1]
  16. 第[15]个人死亡，初始位置为：[5]
  17. 第[16]个人死亡，初始位置为：[10]
  18. 第[17]个人死亡，初始位置为：[14]
  19. 第[18]个人死亡，初始位置为：[19]
  20. 第[19]个人死亡，初始位置为：[23]
  21. 第[20]个人死亡，初始位置为：[28]
  22. 第[21]个人死亡，初始位置为：[32]
  23. 第[22]个人死亡，初始位置为：[37]
  24. 第[23]个人死亡，初始位置为：[41]
  25. 第[24]个人死亡，初始位置为：[7]
  26. 第[25]个人死亡，初始位置为：[13]
  27. 第[26]个人死亡，初始位置为：[20]
  28. 第[27]个人死亡，初始位置为：[26]
  29. 第[28]个人死亡，初始位置为：[34]
  30. 第[29]个人死亡，初始位置为：[40]
  31. 第[30]个人死亡，初始位置为：[8]
  32. 第[31]个人死亡，初始位置为：[17]
  33. 第[32]个人死亡，初始位置为：[29]
  34. 第[33]个人死亡，初始位置为：[38]
  35. 第[34]个人死亡，初始位置为：[11]
  36. 第[35]个人死亡，初始位置为：[25]
  37. 第[36]个人死亡，初始位置为：[2]
  38. 第[37]个人死亡，初始位置为：[22]
  39. 第[38]个人死亡，初始位置为：[4]
  40. 第[39]个人死亡，初始位置为：[35]
  41. 存活人数不足3人，初始位置为：[16],[31],

20.双色球随机摇号

  1.     /**
  2.      * 双色球随机摇号
  3.      * 随机生成6个蓝色球，范围1-32，不允许重复，1个红球，范围1-16
  4.      */
  5.     public static void doubleChromosphere() {
  6.         Set<Integer> blueBalls = new HashSet<>();
  7.         Random random = new Random();
  9.         while (blueBalls.size() < 6) {
  10.             int ball = 1 + random.nextInt(32);
  11.             if (!blueBalls.contains(ball)) {
  12.                 blueBalls.add(ball);
  13.             }
  14.         }
  16.         int redBall = 1 + random.nextInt(16);
  17.         System.out.print("蓝球为：");
  18.         blueBalls.forEach(ball -> System.out.printf("%2d  ", ball));
  19.         System.out.printf(" 红球为：%2d\n", redBall);
  20.     }

调用：

  1.         for (int i = 0; i < 10; i++) {
  2.             System.out.printf("第%2d注 ", 1 + i);
  3.             doubleChromosphere();
  4.         }

输出：

  1. 第 1注 蓝球为：22  23   8  12  29  30   红球为： 4
  2. 第 2注 蓝球为：21   9  10  11  13  30   红球为：15
  3. 第 3注 蓝球为：20   6   8  25  11  27   红球为：10
  4. 第 4注 蓝球为：16   3  25  27  13  14   红球为：14
  5. 第 5注 蓝球为：17  20  22  12  29  15   红球为：16
  6. 第 6注 蓝球为： 3   4  22  11  29  14   红球为：14
  7. 第 7注 蓝球为： 5   6  24  26  30  15   红球为： 7
  8. 第 8注 蓝球为： 3   4   7  10  27  15   红球为： 7
  9. 第 9注 蓝球为： 1   4   9  11  12  15   红球为：13
  10. 第10注 蓝球为：19   5   6  23  27  31   红球为：10

经典问题算法就这些.