1.百钱买百鸡

  1.     /**
  2.      * 百钱买百鸡
  3.      * 鸡翁一，值钱五，鸡母一，值钱三，鸡雏三值钱一，百钱买百鸡，问翁，母、雏各几何？
  4.      * 释义：
  5.      * 公鸡5文钱一只，母鸡3文钱一只，小鸡3只一文钱。如果用100文钱买100只鸡，那么，公鸡、母鸡、小鸡各应该买多少只？
  6.      */
  7.     public static void buyChooks() {
  8.         int money = 100;//钱数
  9.         int chooks = 100;//鸡的总数
  10.         boolean hasSolution = false;
  11.         for (int cocks = 0; cocks <= chooks; cocks++) {//公鸡的数量
  12.             for (int hens = 0; hens <= chooks; hens++) {//母鸡的数量
  13.                 int chickens = chooks - cocks - hens;//小鸡的数量
  14.                 if (cocks * 5 + hens * 3 + chickens / 3.0 == money) {
  15.                     hasSolution = true;
  16.                     //%2d=结果以2位整数输出，如果不足，前面用空格补位
  17.                     System.out.printf("公鸡[ %2d ]只，母鸡[ %2d ]只，小鸡[ %2d ]只 \n", cocks, hens, chickens);
  18.                 }
  19.             }
  20.         }
  21.         if (!hasSolution) {
  22.             System.out.printf("求解完成。无解！");
  23.         }
  24.     }

调用：

  1.         buyChooks();

输出：

  1. 公鸡[ 0 ]只，母鸡[ 25 ]只，小鸡[ 75 ]只 
  2. 公鸡[ 4 ]只，母鸡[ 18 ]只，小鸡[ 78 ]只 
  3. 公鸡[ 8 ]只，母鸡[ 11 ]只，小鸡[ 81 ]只 
  4. 公鸡[ 12 ]只，母鸡[ 4 ]只，小鸡[ 84 ]只

2.五家共井

  1.     /**
  2.      * 五家共井
  3.      * 今有五家共井，甲二绠不足如乙一绠，乙三绠不足如丙一绠，丙四绠不足如丁一绠，丁五绠不足如戊一绠，戊六绠不足如甲一绠。
  4.      * 如各得所不足一绠，皆逮。问井深，绠长各几何？
  5.      * 释义：
  6.      * 绠：绳索，逮：到达井底。
  7.      * 现在有五家共用一口井，甲乙丙丁戍各有一条绳子汲水，
  8.      * 甲绳*2 + 乙绳 = 井深，
  9.      * 乙绳*3 + 丙绳 = 井深，
  10.      * 丙绳*4 + 丁绳 = 井深，
  11.      * 丁绳*5 + 戊绳 = 井深，
  12.      * 戊绳*6 + 甲绳 = 井深，
  13.      * 求甲乙丙丁戊的绳子长度和井深。
  14.      * 解：
  15.      * 假设所有绳子长度和井的深度都是正整数
  16.      * 甲绳=乙绳+丙绳/2;
  17.      * 乙绳=丙绳+丁绳/3;
  18.      * 丁绳=戊绳+甲绳/5;
  19.      * 因为都是整数，所以：
  20.      * 丙绳必为2的整倍数；
  21.      * 丁绳必为3的整倍数；
  22.      * 戊绳必为4的整倍数；
  23.      * 甲绳必为5的整倍数；
  24.      */
  25.     public static void oneWellFiveUsers() {
  26.         int len1, len2, len3, len4, len5, len;//定义甲乙丙丁戊的绳子长度和井深
  27.         for (len5 = 4; ; len5 += 4) {//戊绳
  28.             for (len1 = 5; ; len1 += 5) {//甲绳
  29.                 len4 = len5 + len1 / 5;//丁绳
  30.                 if (len4 % 3 != 0) {//丁绳不是3的整倍数
  31.                     continue;
  32.                 }
  33.                 len3 = len4 + len5 / 4;//丙绳
  34.                 if (len3 % 2 != 0) {//丙绳不是2的整倍数
  35.                     continue;
  36.                 }
  37.                 len2 = len3 + len4 / 3;//乙绳
  38.                 if (len2 + len3 / 2 < len1) {//切回len5循环，因为len1太长了。
  39.                     break;
  40.                 }
  42.                 if (len2 + len3 / 2 == len1) {
  43.                     len = 2 * len1 + len2;
  44.                     System.out.printf("各自绳长为:甲[%d],乙[%d],丙[%d],丁[%d],戊[%d]；井深[%d]", len1, len2, len2, len4, len5, len);
  45.                     return;
  46.                 }
  47.             }
  48.         }
  49.     }

调用：

  1.         oneWellFiveUsers();

输出：

  1. 各自绳长为:甲[265],乙[191],丙[191],丁[129],戊[76]；井深[721]

3.鸡兔同笼

参考 常用算法指南(一)基本算法思想 ，3.1 穷举算法思想

4.猴子吃桃

  1.     /**
  2.      * 猴子吃桃
  3.      * 某天一只猴子摘了一堆桃子，具体多少不知道，猴子每天吃了其中一半然后在多吃一个，
  4.      * 第二天则吃剩余的一半然后再多吃一个，长此往复，直到第10天，猴子发现只有一个桃子了。问这只猴子在第一天摘了多少个桃子？
  5.      * 解：
  6.      * 由题可知
  7.      * a₁₀ = 1;
  8.      * a₉ = (a₁₀ + 1) * 2;
  9.      * 。。。
  10.      * a₂ = (a₃ + 1) * 2;
  11.      * a₁ = (a₂ + 1) * 2
  12.      * 所以，第一天的桃子是第二天的桃子数量+1的2倍
  13.      */
  14.     public static int monkeyEatPeaches(int day) {
  15.         int peach = 1;
  16.         if (day == 10) {//第十天的桃子
  17.             return peach;
  18.         }
  19.         peach = (monkeyEatPeaches(day + 1) + 1) * 2;//第一天的桃子是第二天的桃子数量+1的2倍
  20.         return peach;
  21.     }

调用：

  1.         int day = 1;
  2.         int peaches = monkeyEatPeaches(day);
  3.         System.out.println("猴子第一天的桃子数量为：" + peaches);

输出：

  1. 猴子第一天的桃子数量为：1534

5.舍罕王赏麦

  1.     /**
  2.      * 舍罕王赏麦
  3.      * 传说国际象棋的发明者是古印度的西萨·班·达一尔，当时的国王是舍罕，世人称为舍罕王。
  4.      * 当时舍罕王比较贪玩，畏惧在想的西萨·班·达一尔发明了国际象棋献给舍罕王。
  5.      * 舍罕王非常喜欢，为了奖励西萨·班·达一尔，便许诺可以满足他踢出的任何要求。
  6.      * 西萨·班·达一尔灵机一动，指着8*9=64的棋盘说：“陛下，请您按照棋盘的格子上次我一点麦子吧，
  7.      * 第一个小格赏我1粒麦子，第二个小格赏我2粒，第三个小格赏4粒，以后每一小格都比钱一个小格赏的麦粒数增加一倍，
  8.      * 只要把棋盘上全部的64个小格按照这样方法得到的麦粒都赏赐给我，我就心满意足了。”
  9.      * 舍罕王觉得这是一个很小的要求，就满口答应了，命人按照要求准备麦子。
  10.      * 但是，不就大臣计算的结果令舍罕王大惊失色。问题是：舍罕王需要赏赐出多少粒麦子？
  11.      * 解：
  12.      * 第一格：2⁰ = 1；
  13.      * 第二格：2¹ = 2；
  14.      * 第三格：2² = 4；
  15.      * 第四格：2³ = 8；
  16.      * ……
  17.      * 第六十四格：2⁶³=
  18.      * 将每一格的数量加起来：
  19.      * sum = 2⁰+2¹+2²+……+2⁶³；
  20.      * 用求和公式表示为：
  21.      * ₆₃
  22.      * ∑ 2ⁱ
  23.      * ⁱ⁼⁰
  24.      *
  25.      * @param gridNum 格子数量
  26.      */
  27.     public static void rewardWheat(int gridNum) {
  28.         double temp = 1;//每一格的数量
  29.         double sum = 0;//总数
  30.         for (int i = 0; i < gridNum; i++) {
  31.             if (i == 0) {//第一格是1粒
  32.                 temp = 1;
  33.             } else {
  34.                 temp *= 2;//从第二格开始，都是2的i-1次幂
  35.             }
  36.             sum += temp;
  37.         }
  38.         System.out.println("舍罕王需要赏赐出麦子粒数为: " + sum);
  39.     }
  42.     static long count = 0;

调用：

  1.         int gridNum = 64;
  2.         rewardWheat(gridNum);

输出：

  1. 舍罕王需要赏赐出麦子粒数为: 1.8446744073709552E19

这个结果相当于：1.8446744073709552乘10的19次方，19位数，而1亿是9尾数，而一兆（万亿为兆），也才是10的12次方.

6.汉诺塔

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

  1.     /**
  2.      * 汉诺塔
  3.      * 又称为河内塔。勃拉玛是古印度的一个开天辟地的神，其在一个庙宇中留下了三根金刚石棒。
  4.      * 第一根上面套着64个大小不一的圆形金片。其中，最大的金片在最底下，其余的依次叠上去，且一个比一个小。
  5.      * 勃拉玛要求众僧将该金刚石棒中的金片逐一移到另一根棒上，
  6.      * 规定依次只能移动一个金片，且金片在放到棒上时，大的只能放在小的下面，但是可以利用中间的一根棒作为辅助移动使用。
  7.      *
  8.      * @param n 圆盘数
  9.      * @param a 第一根金刚石棒
  10.      * @param b 中间的辅助石棒
  11.      * @param c 第三根金刚石棒
  12.      */
  13.     public static void hanoiGame(int n, char a, char b, char c) {
  14.         if (n == 1) {//圆盘数为1，直接从a移动到c
  15.             System.out.printf("第 %2d 次移动：圆盘从%c棒移动到%c棒\n", ++count, a, c);
  16.         } else {//剩余圆盘数不为1，借助中间辅助的石棒进行移动
  17.             hanoiGame(n - 1, a, c, b);
  18.             System.out.printf("第 %2d 次移动：圆盘从%c棒移动到%c棒\n", ++count, a, c);
  19.             hanoiGame(n - 1, b, a, c);
  20.         }
  21.     }

调用：

  1.         hanoiGame(4, 'A', 'B', 'C');//圆盘数量越多，需要消耗的步数将成几何级增长。所以此处以4位例。

输出：

  1. 第  1 次移动：圆盘从A棒移动到B棒
  2. 第  2 次移动：圆盘从A棒移动到C棒
  3. 第  3 次移动：圆盘从B棒移动到C棒
  4. 第  4 次移动：圆盘从A棒移动到B棒
  5. 第  5 次移动：圆盘从C棒移动到A棒
  6. 第  6 次移动：圆盘从C棒移动到B棒
  7. 第  7 次移动：圆盘从A棒移动到B棒
  8. 第  8 次移动：圆盘从A棒移动到C棒
  9. 第  9 次移动：圆盘从B棒移动到C棒
  10. 第 10 次移动：圆盘从B棒移动到A棒
  11. 第 11 次移动：圆盘从C棒移动到A棒
  12. 第 12 次移动：圆盘从B棒移动到C棒
  13. 第 13 次移动：圆盘从A棒移动到B棒
  14. 第 14 次移动：圆盘从A棒移动到C棒
  15. 第 15 次移动：圆盘从B棒移动到C棒

7.窃贼问题

  1.     /**
  2.      * 窃贼问题
  3.      * 有一个窃贼带着一个背包去偷东西，房屋共有5件物品，其重量和价值如下：
  4.      * 物品1: 6公斤，48元；
  5.      * 物品2：5公斤，40元；
  6.      * 物品3：2公斤，12元；
  7.      * 物品4: 1公斤，8元；
  8.      * 物品5：1公斤，7元；
  9.      * 窃贼希望能够拿到最大价值的东西，而窃贼的背包最多可以装重量8公斤的物品，那么窃贼应该装那些物品才能达到要求。
  10.      * 解：
  11.      * 这个题可以采用数学的排列组合思想
  12.      * 将所有不超过8公斤的组合进行对比，找出总价值最大的那个组合即可
  13.      * 将所有物品按照价值排序，先拿出价值最大的，再从剩余的的物品中拿出价值最大的，看看总重量有没有超重，没有超重就放入，
  14.      * 超重就换下一个价值较大的，以此类推。便可以得到一个组合，然后再拿第二个和其他物品进行组合，对比之前哪个总价值比较大
  15.      *
  16.      * @param articles 所有物品
  17.      */
  18.     public static void thief(List<Article> articles) {
  19.         int QUOTA_WEIGHT = 8;
  20.         int maxValue = 0;
  21.         List<Article> maxArticles = new ArrayList<>();
  22.         Collections.sort(articles, new Comparator<Article>() {
  23.             @Override
  24.             public int compare(Article o1, Article o2) {
  25.                 if (o1.value > o2.value) {
  26.                     return -1;
  27.                 } else if (o1.value < o2.value) {
  28.                     return 1;
  29.                 } else {
  30.                     return 0;
  31.                 }
  32.             }
  33.         });
  35.         //开始获取组合，先拿出价值最大的，再从剩余的的物品中拿出价值最大的，看看总重量有没有超重，没有超重就放入，超重就换下一个
  36.         for (int i = 0; i < articles.size(); i++) {
  37.             Article article = articles.get(i);
  38.             int articleValue = article.value;
  39.             int articleWeight = article.weight;
  40.             int tempValue = articleValue;
  41.             int tempWeight = articleWeight;
  42.             List<Article> tempArticles = new ArrayList<>();
  43.             tempArticles.add(article);
  44.             for (int j = 0; j < articles.size(); j++) {
  45.                 Article article2 = articles.get(j);
  46.                 if (article2 == article) {
  47.                     continue;
  48.                 }
  49.                 int article2Value = article2.value;
  50.                 int article2Weight = article2.weight;
  51.                 if (tempWeight + article2Weight <= QUOTA_WEIGHT) {
  52.                     tempWeight += article2Weight;
  53.                     tempValue += article2Value;
  54.                     tempArticles.add(article2);
  55.                 }
  56.                 if (tempValue > maxValue) {//当前价值已经超过之前记录的最大值
  57.                     maxValue = tempValue;
  58.                     maxArticles.clear();
  59.                     tempArticles.forEach(maxArticles::add);
  60.                 }
  61.                 if (tempWeight >= QUOTA_WEIGHT) {//当前重量已达到最大值
  62.                     break;
  63.                 }
  64.             }
  65.         }
  66.         System.out.printf("不超过[%d]公斤的物品的最大价值为: %d\n", QUOTA_WEIGHT, maxValue);
  67.         System.out.print("物品为：");
  68.         maxArticles.forEach(e -> {
  69.             System.out.print(e.name + ",");
  70.         });
  71.         System.out.print("\n");
  72.     }
  74.     //物品
  75.     static class Article {
  76.         String name;//物品名称
  77.         int value;//物品价值
  78.         int weight;//物品重量
  80.         public Article(String name, int value, int weight) {
  81.             this.name = name;
  82.             this.value = value;
  83.             this.weight = weight;
  84.         }
  85.     }

调用：

  1.         List<Article> articles = new ArrayList<>();
  2.         articles.add(new Article("商品1", 48, 6));
  3.         articles.add(new Article("商品2", 40, 5));
  4.         articles.add(new Article("商品3", 12, 2));
  5.         articles.add(new Article("商品4", 8, 1));
  6.         articles.add(new Article("商品5", 7, 1));
  7.         thief(articles);

输出：

  1. 不超过[8]公斤的物品的最大价值为: 63
  2. 物品为：商品4,商品1,商品5,

8.马踏棋盘

  1.     /**
  2.      * 马踏棋盘
  3.      * 国际象棋的棋盘有8行8列6个单元格，无论将马放于棋盘的哪个单元格，都可以让马踏遍棋盘的每个单元格。
  4.      * 问马该怎么走才可以踏遍棋盘的每个单元格
  5.      */
  6.     public static void horseTreadChessboard(Coordinate coordinate) {
  7.         Coordinate next = new Coordinate(0, 0);
  8.         if (coordinate.x < 0 || coordinate.x > 7 || coordinate.y < 0 || coordinate.y > 7) {//已出棋盘
  9.             return;
  10.         }
  11.         if (chessboard[coordinate.x][coordinate.y] != 0) {//已经走过这里
  12.             return;
  13.         }
  14.         chessboard[coordinate.x][coordinate.y] = stepNum;//记录当前坐标是第几步走的
  15.         stepNum++;
  17.         if (stepNum > 64) {//全部走完，输出
  18.             for (int x = 0; x < 8; x++) {
  19.                 for (int y = 0; y < 8; y++) {
  20.                     System.out.printf("[%d][%d] 第 %2d 步 \n", x, y, chessboard[x][y]);
  21.                 }
  22.             }
  24.         } else {
  25.             for (int i = 0; i < 8; i++) {
  26.                 next.x = coordinate.x + COORDINATE[i].x;
  27.                 next.y = coordinate.y + COORDINATE[i].y;
  28.                 if (next.x < 0 || next.x > 7 || next.y < 0 || next.y > 7) {//当前方向越界
  29.                     continue;
  30.                 }
  31.                 horseTreadChessboard(next);
  32.             }
  33.         }
  34. //        chessboard[coordinate.x][coordinate.y] = 0;//清除步数序号
  35. //        stepNum--;//减少步数
  36.     }
  38.     static int[][] chessboard = new int[8][8];//马所走过的棋盘的横纵坐标
  39.     static int stepNum = 1;//总共走过的步数
  41.     //马可以移动的八个方向坐标
  42.     static final Coordinate[] COORDINATE = {
  43.             new Coordinate(-1, -2),//横向左移1位，纵向上移2位
  44.             new Coordinate(-1, 2),
  45.             new Coordinate(1, -2),
  46.             new Coordinate(1, 2),//横向右移1位，纵向下移2位
  47.             new Coordinate(-2, -1),
  48.             new Coordinate(-2, 1),
  49.             new Coordinate(2, -1),
  50.             new Coordinate(2, 1),
  51.     };
  53.     //马可以移动的方向
  54.     static class Coordinate {
  55.         int x;//横向坐标
  56.         int y;//纵向坐标
  58.         public Coordinate(int x, int y) {
  59.             this.x = x;
  60.             this.y = y;
  61.         }
  62.     }

调用：

  1.         Coordinate startLocation = new Coordinate(1, 1);//初始位置
  2.         horseTreadChessboard(startLocation);

输出：

  1. [0][0] 第 27 步 
  2. [0][1] 第 24 步 
  3. [0][2] 第  7 步 
  4. [0][3] 第  2 步 
  5. [0][4] 第 35 步 
  6. [0][5] 第 43 步 
  7. [0][6] 第 21 步 
  8. [0][7] 第  4 步 
  9. [1][0] 第  8 步 
  10. [1][1] 第  1 步 
  11. [1][2] 第 26 步 
  12. [1][3] 第 23 步 
  13. [1][4] 第  6 步 
  14. [1][5] 第  3 步 
  15. [1][6] 第 34 步 
  16. [1][7] 第 42 步 
  17. [2][0] 第 25 步 
  18. [2][1] 第 28 步 
  19. [2][2] 第  9 步 
  20. [2][3] 第 18 步 
  21. [2][4] 第 36 步 
  22. [2][5] 第 22 步 
  23. [2][6] 第  5 步 
  24. [2][7] 第 20 步 
  25. [3][0] 第 10 步 
  26. [3][1] 第 17 步 
  27. [3][2] 第 37 步 
  28. [3][3] 第 29 步 
  29. [3][4] 第 12 步 
  30. [3][5] 第 19 步 
  31. [3][6] 第 41 步 
  32. [3][7] 第 33 步 
  33. [4][0] 第 38 步 
  34. [4][1] 第 30 步 
  35. [4][2] 第 11 步 
  36. [4][3] 第 45 步 
  37. [4][4] 第 40 步 
  38. [4][5] 第 32 步 
  39. [4][6] 第 13 步 
  40. [4][7] 第 62 步 
  41. [5][0] 第 16 步 
  42. [5][1] 第 46 步 
  43. [5][2] 第 39 步 
  44. [5][3] 第 31 步 
  45. [5][4] 第 14 步 
  46. [5][5] 第 44 步 
  47. [5][6] 第 51 步 
  48. [5][7] 第 56 步 
  49. [6][0] 第 54 步 
  50. [6][1] 第 59 步 
  51. [6][2] 第 15 步 
  52. [6][3] 第 47 步 
  53. [6][4] 第 52 步 
  54. [6][5] 第 57 步 
  55. [6][6] 第 63 步 
  56. [6][7] 第 50 步 
  57. [7][0] 第 61 步 
  58. [7][1] 第 48 步 
  59. [7][2] 第 53 步 
  60. [7][3] 第 58 步 
  61. [7][4] 第 64 步 
  62. [7][5] 第 49 步 
  63. [7][6] 第 55 步 
  64. [7][7] 第 60 步

9.八皇后问题

  1.     /**
  2.      * 八皇后问题
  3.      * 八皇后问题是高斯于1850年提出，是一个典型的回溯算法的问题。大意如下：
  4.      * 国际象棋的棋盘有8行8列共64个单元格，在棋盘上摆放八个皇后，使其不能互相攻击，
  5.      * 也就是说任意两个皇后都不能处于同一行、同一列或同一斜线上。问总共有多少种摆放方法，每一种摆放方式是怎样的。
  6.      * 目前数学上可以证明八皇后问题总共有92种解。
  7.      * <p>
  8.      * 解：
  9.      * 由题目可知，每一行只能放一个，每一列也只能放一个，
  10.      * 所以，我们可以估计放置的时候，一行一行的放，只要下一行的放置不和之前放置的处于同一列，并且不处于同一斜线上就可以了。
  11.      *
  12.      * @param row 第几行的棋子，也就是第几个棋子
  13.      */
  14.     public static void eightQueen(int row) {
  15.         if (row == ROWS) {//放置完毕，输出
  16.             System.out.println("*********解法" + solutionNum++ + "*********");
  17.             eightQueenOutput();
  18.             return;
  19.         }
  20.         boolean canPut;
  21.         for (int i = 1; i <= 8; i++) {
  22.             columns[row] = i;
  23.             canPut = true;
  24.             for (int j = 0; j < row; j++) {
  25.                 if (columns[j] == columns[row]) {
  26.                     canPut = false;
  27.                 } else if (Math.abs(columns[j] - columns[row]) == (row - j)) {
  28.                     canPut = false;
  29.                 }
  30.             }
  31.             if (canPut) {
  32.                 eightQueen(row + 1);
  33.             } else {
  34.                 //这行无法放置，直接舍弃之前的摆法。
  35.             }
  36.         }
  37.     }
  39.     public static void eightQueenOutput() {
  40.         for (int r = 0; r < ROWS; r++) {
  41.             int column = columns[r];
  42.             for (int c = 1; c < column; c++) {
  43.                 if ((r + c) % 2 == 0) {
  44.                     System.out.print("■ ");//棋盘空位
  45.                 } else {
  46.                     System.out.print("□ ");//棋盘空位
  47.                 }
  48.             }
  49.             System.out.print("☆ ");//皇后放置的位置
  50.             for (int c = column; c < 8; c++) {
  51.                 if ((r + c) % 2 == 0) {
  52.                     System.out.print("■ ");
  53.                 } else {
  54.                     System.out.print("□ ");
  55.                 }
  56.             }
  57.             System.out.print("\n");
  58.         }
  59.     }
  61.     static int solutionNum = 1;//解法计数器
  62.     static int ROWS = 8;//棋子放置的总行数。从第0行开始
  63.     static int[] columns = new int[8];//每一个棋子处于每一行的第几列。第一个元素就是处于第一行，第二个就是处于第二行。

调用：

  1.         int r = 0;
  2.         eightQueen(r);

输出：

  1. *********解法1*********
  2. ☆ □ ■ □ ■ □ ■ □ 
  3. ■ □ ■ □ ☆ ■ □ ■ 
  4. □ ■ □ ■ □ ■ □ ☆ 
  5. ■ □ ■ □ ■ ☆ □ ■ 
  6. □ ■ ☆ □ ■ □ ■ □ 
  7. ■ □ ■ □ ■ □ ☆ ■ 
  8. □ ☆ ■ □ ■ □ ■ □ 
  9. ■ □ ■ ☆ □ ■ □ ■ 
  10. *********解法2*********
  11. ☆ □ ■ □ ■ □ ■ □ 
  12. ■ □ ■ □ ■ ☆ □ ■ 
  13. □ ■ □ ■ □ ■ □ ☆ 
  14. ■ □ ☆ ■ □ ■ □ ■ 
  15. □ ■ □ ■ □ ■ ☆ □ 
  16. ■ □ ■ ☆ □ ■ □ ■ 
  17. □ ☆ ■ □ ■ □ ■ □ 
  18. ■ □ ■ □ ☆ ■ □ ■ 
  19. *********解法n*********
  20. 由于输出太多，此处省略部分解法的输出，可以自行运行代码输出。
  22. *********解法91*********
  23. □ ■ □ ■ □ ■ □ ☆ 
  24. ■ □ ☆ ■ □ ■ □ ■ 
  25. ☆ □ ■ □ ■ □ ■ □ 
  26. ■ □ ■ □ ■ ☆ □ ■ 
  27. □ ☆ ■ □ ■ □ ■ □ 
  28. ■ □ ■ □ ☆ ■ □ ■ 
  29. □ ■ □ ■ □ ■ ☆ □ 
  30. ■ □ ■ ☆ □ ■ □ ■ 
  31. *********解法92*********
  32. □ ■ □ ■ □ ■ □ ☆ 
  33. ■ □ ■ ☆ □ ■ □ ■ 
  34. ☆ □ ■ □ ■ □ ■ □ 
  35. ■ □ ☆ ■ □ ■ □ ■ 
  36. □ ■ □ ■ □ ☆ ■ □ 
  37. ■ ☆ □ ■ □ ■ □ ■ 
  38. □ ■ □ ■ □ ■ ☆ □ 
  39. ■ □ ■ □ ☆ ■ □ ■

10.寻找真假银币

  1.     /**
  2.      * 寻找假银币
  3.      * 现有8枚银币，其中一枚是假币。但是，从外观和做工上无法分辨哪枚是真币哪枚是假币，只知道假币的重量要比真币轻。
  4.      * 要求仅使用一个天平，如何以最少的步骤寻找的假币。
  5.      * 解法，2分法查找(分治思想)
  6.      * 将硬币按照数量分为两等分，放在天平两边，较轻的一边肯定有假币，
  7.      * 再将较轻的那组分为2等分，重复上面的步骤，直到天平两边都只剩下一个硬币，那个较轻的就是假币
  8.      *
  9.      * @param coins 包含一个假币的银币数组。
  10.      * @param min   包含假币的数组中的起始坐标 index
  11.      * @param max   包含假币的数组的结束坐标 index
  12.      */
  13.     public static int findFakeSilverCoin(int[] coins, int min, int max) {
  14.         int size = max - min + 1;//银币的总数量
  15.         int weightLeft = 0, weightRight = 0;
  16.         int mid;//中间值
  17.         if (size % 2 == 0) {//银币数量为偶数
  18.             //直接分为两等分，重量小的那一组包含假币
  19.             mid = (max + min + 1) / 2;//中间值
  20.             for (int i = min; i < mid; i++) {
  21.                 weightLeft += coins[i];
  22.             }
  23.             for (int i = mid; i <= max; i++) {
  24.                 weightRight += coins[i];
  25.             }
  26.             if (weightLeft < weightRight) {
  27.                 if (size == 2) {
  28.                     return min;
  29.                 }
  30.                 return findFakeSilverCoin(coins, min, mid);
  31.             } else {
  32.                 if (size == 2) {
  33.                     return max;
  34.                 }
  35.                 return findFakeSilverCoin(coins, mid, max);
  36.             }
  37.         } else {//银币数量为奇数
  38.             //拿出一个硬币，将剩余的硬币分为两等分，如果这两份的重量一致，则拿出的那个就是假币，如果不一致，重量轻的那一组有假币
  39.             int temp = max;
  40.             max = max - 1;
  41.             mid = (max + min + 1) / 2;//中间值
  42.             for (int i = min; i < mid; i++) {
  43.                 weightLeft += coins[i];
  44.             }
  45.             for (int i = mid; i <= max; i++) {
  46.                 weightRight += coins[i];
  47.             }
  48.             if (weightLeft < weightRight) {
  49.                 if (size == 3) {
  50.                     return min;
  51.                 }
  52.                 return findFakeSilverCoin(coins, min, mid);
  53.             } else if (weightLeft > weightRight) {
  54.                 if (size == 3) {
  55.                     return max;
  56.                 }
  57.                 return findFakeSilverCoin(coins, mid, max);
  58.             } else {
  59.                 return temp;
  60.             }
  61.         }
  62.     }

调用：

  1.         int[] coins = new int[8];
  2.         Arrays.parallelSetAll(coins, index -> 2);//初始化各个银币的重量为2
  3.         coins[4] = 1;//假银币的重量为1
  4.         int fakeIndex = findFakeSilverCoin(coins, 0, coins.length - 1);
  5.         System.out.println("假银币的编号为：" + (fakeIndex + 1));//编号为index+1，因为index是从0开始，编号从1开始

输出：

  1. 假银币的编号为：5

11.青蛙过河

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

  1.     /**
  2.      * 青蛙过河
  3.      * 一条河之间有若干个石块间隔，有两队青蛙同时从两边开始过河，每队3只青蛙，这些青蛙只能向前移动，不能向后移动，且一次只能有一只青蛙移动。
  4.      * 在移动过程中，青蛙可以向前面的空位中移动，不可以一次跳过两个位置，但是可以跳过对方一只青蛙进入前面的一个空位。
  5.      * 问两队青蛙该如何移动才能够用最少的步数分别走向对岸
  6.      */
  7.     public static void frogCrossRiver(List<Frog> frogList) {
  8.         for (Frog frog : frogList) {
  9.             if (!frog.canJump) {
  10.                 continue;
  11.             }
  12.             int index = frogList.indexOf(frog);
  14.             int frontIndex = index + frog.jumpDirection;
  15.             int emptyPosition = frog.frogPosition + frog.jumpDirection;
  16.             Frog empty;
  17.             if (frontIndex > 0 && frontIndex < frogList.size()) {
  18.                 empty = frogList.get(frontIndex);
  19.                 if (empty.team != 0) {
  20.                     emptyPosition = frog.frogPosition + 2 * frog.jumpDirection;
  21.                 }
  22.             }
  24.             System.out.printf("青蛙 [%s] 从位置 %d 向 %s 跳到位置 %d。\n", frog.frogName,
  25.                     frog.frogPosition, frog.jumpDirection == 1 ? "右" : "左", emptyPosition);
  26.             frogStepNum++;
  27.             updateFrogQueue(frogList, frog);
  28.             if (finish) {
  29.                 if (checkFrogCrossSuccess(frogList)) {
  30.                     System.out.println("过河成功！总共步数为：" + frogStepNum);
  31.                 } else {
  32.                     System.out.println("过河失败！消耗步数为：" + frogStepNum);
  33.                 }
  34.                 return;
  35.             }
  36.             frogCrossRiver(frogList);
  37.         }
  38.     }
  40.     static boolean finish = false;
  41.     static int frogStepNum = 0;
  43.     private static Frog updateFrogQueue(List<Frog> frogList, Frog frog) {
  44.         //将两个frog交换位置，被交换的那个只能是空位
  45.         int index = frogList.indexOf(frog);
  46.         int jumpDirection = frog.jumpDirection;//青蛙跳的方向
  47.         int jumpDistance = jumpDirection;//青蛙跳的距离
  48.         int emptyIndex = index + jumpDistance;//青蛙跳向的那个位置的index
  49.         Frog empty;//青蛙跳向的那个位置
  50.         if (emptyIndex < 0 || emptyIndex >= frogList.size()) {//青蛙跳向的地方已经过河了
  51.             empty = new Frog(0, "___", frog.frogPosition + jumpDistance, 0, false);
  52.         } else {
  53.             empty = frogList.get(emptyIndex);
  54.         }
  56.         if (empty.team != 0) {//青蛙可以向前跳一步到空位，或者跳过对方一只青蛙进入前面的一个空位。
  57.             jumpDistance = 2 * jumpDirection;
  58.             emptyIndex = index + jumpDistance;
  59.             if (emptyIndex < 0 || emptyIndex >= frogList.size()) {
  60.                 empty = new Frog(0, "___", frog.frogPosition + jumpDistance, 0, false);
  61.             } else {
  62.                 empty = frogList.get(emptyIndex);
  63.             }
  64.             if (empty.team != 0) {
  65.                 throw new RuntimeException("ERROR : 青蛙" + frog.frogName + "要跳向的地方" + empty.frogPosition + "不是空位！");
  66.             }
  67.         }
  68.         frog.frogPosition = frog.frogPosition + jumpDistance;
  69.         empty.frogPosition = frog.frogPosition - jumpDistance;
  70.         if (emptyIndex < 0 || emptyIndex > 6) {
  71.             frogList.set(index, empty);//青蛙跳向的地方已经过河了,直接在青蛙所在位置换一个空位
  72.         } else {
  73.             frogList.set(emptyIndex, frog);
  74.             frogList.set(index, empty);
  75.         }
  77.         System.out.println("现在过河情况为：");
  78.         for (Frog f : frogList) {
  79.             System.out.print(f.frogName + " ");
  80.         }
  81.         System.out.print("\n");
  82.         finish = true;
  83.         //重新判断青蛙是不是可以向前跳
  84.         for (int i = 0; i < frogList.size(); i++) {
  85.             Frog f = frogList.get(i);
  86.             if (f.team == 0) {
  87.                 continue;
  88.             }
  89.             f.canJump = false;
  90.             int frontIndex = i + f.jumpDirection;
  91.             if (frontIndex < 0 || frontIndex >= frogList.size()) {
  92.                 f.canJump = true;
  93.                 finish = false;
  94.                 continue;
  95.             }
  96.             Frog frontFrog = frogList.get(frontIndex);
  97.             if (frogStepNum % 3 != 2 && frontFrog.team == 0 && f.team != frog.team) {
  98.                 f.canJump = true;
  99.                 finish = false;
  100.             }
  101.             if (frogStepNum % 3 == 2 && frontFrog.team == 0 && f.team == frog.team) {
  102.                 f.canJump = true;
  103.                 finish = false;
  104.             }
  105.             int frontIndex1 = i + 2 * f.jumpDirection;
  106.             if (frontIndex1 < 0 || frontIndex1 >= frogList.size()) {
  107.                 f.canJump = true;
  108.                 finish = false;
  109.                 continue;
  110.             }
  111.             Frog frontFrog1 = frogList.get(frontIndex1);
  112.             if (frontFrog1.team == 0 && f.team != frontFrog.team) {
  113.                 f.canJump = true;
  114.                 finish = false;
  115.             }
  117. //            if (empty.frogPosition - f.frogPosition > 0 && empty.frogPosition - f.frogPosition < 3
  118. //                    && f.jumpDirection == 1) {//空位左侧3个位置以内还有team1的青蛙
  119. //                f.canJump = true;
  120. //                finish = false;
  121. //            }
  122. //            if (f.frogPosition - empty.frogPosition > 0 && f.frogPosition - empty.frogPosition < 3
  123. //                    && f.jumpDirection == -1) {//空位右侧3个位置以内还有team2的青蛙
  124. //                f.canJump = true;
  125. //                finish = false;
  126. //            }
  127.         }
  128.         return empty;
  129.     }
  131.     static boolean checkFrogCrossSuccess(List<Frog> frogList) {
  132.         boolean success = true;
  133.         for (Frog frog : frogList) {
  134.             if (frog.team != 0) {
  135.                 success = false;
  136.                 break;
  137.             }
  138.         }
  140.         return success;
  141.     }
  143.     static List<Frog> initFortQueue() {
  144.         List<Frog> frogList = new ArrayList<>();
  145.         frogList.add(new Frog(1, "左①", 0, 1, false));
  146.         frogList.add(new Frog(1, "左②", 1, 1, false));
  147.         frogList.add(new Frog(1, "左③", 2, 1, true));
  148.         frogList.add(new Frog(0, "___", 3, 0, false));
  149.         frogList.add(new Frog(2, "右①", 4, -1, true));
  150.         frogList.add(new Frog(2, "右②", 5, -1, false));
  151.         frogList.add(new Frog(2, "右③", 6, -1, false));
  152.         return frogList;
  153.     }
  155.     /**
  156.      * 青蛙
  157.      */
  158.     static class Frog {
  159.         int team;//青蛙所属队伍
  160.         String frogName;//青蛙名称
  161.         int frogPosition;//青蛙当前位置
  162.         int jumpDirection;//可以跳动的方向-1.向左，1向右
  163.         boolean canJump;//是否可以跳动
  165.         public Frog(int team, String frogName, int frogPosition, int jumpDirection, boolean canJump) {
  166.             this.team = team;
  167.             this.frogName = frogName;
  168.             this.frogPosition = frogPosition;
  169.             this.jumpDirection = jumpDirection;
  170.             this.canJump = canJump;
  171.         }
  172.     }

调用：

  1.         List<Frog> frogList = initFortQueue();
  2.         System.out.println("青蛙初始位置为：");
  3.         for (Frog f : frogList) {
  4.             System.out.print(f.frogName + " ");
  5.         }
  6.         System.out.print("\n");
  7.         frogCrossRiver(frogList);

输出：

  1. 青蛙初始位置为：
  2. 左① 左② 左③ ___ 右① 右② 右③ 
  3. 青蛙 [左③] 从位置 2 向 右 跳到位置 3。
  4. 现在过河情况为：
  5. 左① 左② ___ 左③ 右① 右② 右③ 
  6. 青蛙 [右①] 从位置 4 向 左 跳到位置 2。
  7. 现在过河情况为：
  8. 左① 左② 右① 左③ ___ 右② 右③ 
  9. 青蛙 [右②] 从位置 5 向 左 跳到位置 4。
  10. 现在过河情况为：
  11. 左① 左② 右① 左③ 右② ___ 右③ 
  12. 青蛙 [左③] 从位置 3 向 右 跳到位置 5。
  13. 现在过河情况为：
  14. 左① 左② 右① ___ 右② 左③ 右③ 
  15. 青蛙 [左②] 从位置 1 向 右 跳到位置 3。
  16. 现在过河情况为：
  17. 左① ___ 右① 左② 右② 左③ 右③ 
  18. 青蛙 [左①] 从位置 0 向 右 跳到位置 1。
  19. 现在过河情况为：
  20. ___ 左① 右① 左② 右② 左③ 右③ 
  21. 青蛙 [右①] 从位置 2 向 左 跳到位置 0。
  22. 现在过河情况为：
  23. 右① 左① ___ 左② 右② 左③ 右③ 
  24. 青蛙 [右①] 从位置 0 向 左 跳到位置 -1。
  25. 现在过河情况为：
  26. ___ 左① ___ 左② 右② 左③ 右③ 
  27. 青蛙 [右②] 从位置 4 向 左 跳到位置 2。
  28. 现在过河情况为：
  29. ___ 左① 右② 左② ___ 左③ 右③ 
  30. 青蛙 [右②] 从位置 2 向 左 跳到位置 0。
  31. 现在过河情况为：
  32. 右② 左① ___ 左② ___ 左③ 右③ 
  33. 青蛙 [右②] 从位置 0 向 左 跳到位置 -1。
  34. 现在过河情况为：
  35. ___ 左① ___ 左② ___ 左③ 右③ 
  36. 青蛙 [左③] 从位置 5 向 右 跳到位置 7。
  37. 现在过河情况为：
  38. ___ 左① ___ 左② ___ ___ 右③ 
  39. 青蛙 [左②] 从位置 3 向 右 跳到位置 4。
  40. 现在过河情况为：
  41. ___ 左① ___ ___ 左② ___ 右③ 
  42. 青蛙 [左①] 从位置 1 向 右 跳到位置 2。
  43. 现在过河情况为：
  44. ___ ___ 左① ___ 左② ___ 右③ 
  45. 青蛙 [左①] 从位置 2 向 右 跳到位置 3。
  46. 现在过河情况为：
  47. ___ ___ ___ 左① 左② ___ 右③ 
  48. 青蛙 [右③] 从位置 6 向 左 跳到位置 5。
  49. 现在过河情况为：
  50. ___ ___ ___ 左① 左② 右③ ___ 
  51. 青蛙 [左②] 从位置 4 向 右 跳到位置 6。
  52. 现在过河情况为：
  53. ___ ___ ___ 左① ___ 右③ 左② 
  54. 青蛙 [左①] 从位置 3 向 右 跳到位置 4。
  55. 现在过河情况为：
  56. ___ ___ ___ ___ 左① 右③ 左② 
  57. 青蛙 [右③] 从位置 5 向 左 跳到位置 3。
  58. 现在过河情况为：
  59. ___ ___ ___ 右③ 左① ___ 左② 
  60. 青蛙 [右③] 从位置 3 向 左 跳到位置 2。
  61. 现在过河情况为：
  62. ___ ___ 右③ ___ 左① ___ 左② 
  63. 青蛙 [右③] 从位置 2 向 左 跳到位置 1。
  64. 现在过河情况为：
  65. ___ 右③ ___ ___ 左① ___ 左② 
  66. 青蛙 [右③] 从位置 1 向 左 跳到位置 0。
  67. 现在过河情况为：
  68. 右③ ___ ___ ___ 左① ___ 左② 
  69. 青蛙 [右③] 从位置 0 向 左 跳到位置 -1。
  70. 现在过河情况为：
  71. ___ ___ ___ ___ 左① ___ 左② 
  72. 青蛙 [左②] 从位置 6 向 右 跳到位置 7。
  73. 现在过河情况为：
  74. ___ ___ ___ ___ 左① ___ ___ 
  75. 青蛙 [左①] 从位置 4 向 右 跳到位置 5。
  76. 现在过河情况为：
  77. ___ ___ ___ ___ ___ 左① ___ 
  78. 青蛙 [左①] 从位置 5 向 右 跳到位置 6。
  79. 现在过河情况为：
  80. ___ ___ ___ ___ ___ ___ 左① 
  81. 青蛙 [左①] 从位置 6 向 右 跳到位置 7。
  82. 现在过河情况为：
  83. ___ ___ ___ ___ ___ ___ ___ 
  84. 过河成功！总共步数为：27