(1)百钱买百鸡问题
来自《算经》，大意：公鸡5文钱一只，母鸡3文钱一只，小鸡1文钱3只，如果用100文钱，买一百只鸡，那么公鸡、母鸡和小鸡各买多少只？
分析：这是一个非常经典的不定方程问题，可能有多个解。假设x、y和z，分别代表公鸡、母鸡和小鸡的数量，那么应该满足：1)x + y + z = 100; 2)5x + 3y + z/3 = 100;
Java版本算法如下：
/**
* 计算m钱买n鸡问题
* @param m
* @param n
*/
void hundredBuyChicken(int m ,int n){
int x,y,z;
for (x = 0;x<=n;x++){
for (y = 0;y<=n;y++){
z = n - x -y;
if (z>0 && z %3 == 0 && x*5 + y*3+z/3 == m){
System.out.printf("公鸡：%d只，母鸡：d%只，小鸡：d%只",x,y,z);
}
}
}
}
Kotlin版本：
/**
* 计算m钱买n鸡问题
* @param m
* @param n
*/
fun hundredBuyChicken(m: Int, n: Int) {
var x: Int
var y: Int
var z: Int
x = 0
while (x <= n) {
y = 0
while (y <= n) {
z = n - x - y
if (z > 0 && z % 3 == 0 && x * 5 + y * 3 + z / 3 == m) {
System.out.printf("公鸡：%d只，母鸡：d%只，小鸡：d%只", x, y, z)
}
y++
}
x++
}
}
(2)猴子吃桃问题
大意是：某天一只猴子摘了一堆桃子，具体数量未知。猴子每天吃掉其中的一半然后再多吃一个，第二天吃剩余的一半然后再多吃一个，······，直到第10天，猴子发现只有一个桃子。问猴子在第一天摘了多少桃子？
思路：假设a表示第n天剩余的桃子数量，那么有关系：
a = (a
+1) * 2;
a = (a
+1) * 2;
······
a = (a
+1) * 2;
a = 1;
Java版本：
int peach(int n){
int num;
if (n == 1){
return 1;
}else {
num = (peach(n-1)+1)*2;
}
return num;
}
Kotlin版本：
fun peach(n: Int): Int {
val num: Int
num = if (n == 1) {
return 1
} else {
(peach(n - 1) + 1) * 2
}
return num
}
(3)舍罕王赏麦问题
一个著名的级数求和问题，大意是：在国际象棋的8 x 8 = 64格子里，第一个格子放1粒麦子，第二个格子放2粒麦子，第三个格子放4粒麦子，······，以此类推，直到64个格子。每个格子里的麦子数是它前一个格子的2倍。
Java版本的算法如下：
long computeWheat(int n){
long tmp, sum;
tmp =1;
sum = 0;
for (int i = 1;i<=n;i++){
sum = sum + tmp;
tmp = tmp *2;
}
return sum;
}
Kotlin版：
fun computeWheat(n: Int): Long {
var tmp: Long
var sum: Long
tmp = 1
sum = 0
for (i in 1..n) {
sum = sum + tmp
tmp = tmp * 2
}
return sum
}
(4)汉诺塔问题
汉诺塔问题来自于古印度，又称河内塔问题。大意是：有3根柱子，分别为A、B、C。柱子A上有64个大小不一的圆形金片，其中最大的金片在最底下，其余的依次叠上去，且一个比一个小。柱子B和柱子C上开始没有金片。要求将柱子A上的金片，移动到柱子B或者柱子C上。规定一次只能移动一个金片，且金片放到柱子上时，大的只能放到小的下面。在此过程中，可以使用另外一个柱子作为辅助。
基本思想：1）将A柱上的n-1个圆盘移到B柱上；2）将A柱上的1个圆盘移到C柱上；3）将B柱上的n-1个圆盘移到C柱上。整个过程使用了递归算法。
算法的Java版本：
int count = 0;
/**
* 汉诺塔问题
* @param n 圆盘数量
* @param a 初始柱子名称，例如A
* @param b 移动的辅助柱子名称，例如B
* @param c 移动的目标柱子名称，例如C
*/
void hanoiTower(int n, char a, char b, char c) {
if (n == 1) {
System.out.printf("第%d次移动：\t圆盘从%c柱移动到%c柱\n", ++count, a, c);
} else {
hanoiTower(n - 1, a, c, b);
System.out.printf("第%d次移动：\t圆盘从%c柱移动到%c柱\n", ++count, a, c);
hanoiTower(n - 1, b, a, c);
}
}
Kotlin版本：
var count = 0
fun hanoiTower(n: Int, a: Char, b: Char, c: Char) {
if (n == 1) {
System.out.printf("第%d次移动：\t圆盘从%c柱移动到%c柱\n", ++count, a, c)
} else {
hanoiTower(n - 1, a, c, b)
System.out.printf("第%d次移动：\t圆盘从%c柱移动到%c柱\n", ++count, a, c)
hanoiTower(n - 1, b, a, c)
}
}
(5)窃贼问题
大意：有一个窃贼带着一个背包去偷东西，房屋中共有5件物品，其重量和价值如下：
物品1：6公斤，48元；
物品2：5公斤，40元；
物品3：2公斤，12元；
物品4：1公斤，8元；
物品5：1公斤，7元；
窃贼希望拿最大价值的东西，而窃贼的背包最多可装重量8公斤的物品，那么窃贼应该装上面哪些物品才能达到要求呢？
主要思路：
- 首先，将物品 i 试着添加到方案中；
- 然后判断是否超重，如果未超，则继续添加下一个物品，重复第一步；
- 如果超重，则将该物品排除在方案之外；并判断此时所有未排除物品的价值是否小于已有最大值；如果满足，就不必再尝试后续物品了。
Java版本算法：
class ThingType { //物品结果
double value;//价值
double weight;//重量
boolean isSelect;//是否选中到方案
}
static double maxValue; //方案最大价值
static double totalValue; //物品总价值
static double maxWeight;//窃贼能拿的最大重量
static int num;//物品数量
static boolean[] selectedArray; //临时选中数组
void thiefSolve(ThingType[] goods, int i, double weight, double value) {
if (weight + goods[i].weight <= maxWeight) { //判断当前方案i重量是否超出限制
selectedArray[i] = true;
if (i < num - 1) { //不是最后一个物品
thiefSolve(goods, i + 1, weight + goods[i].weight, value);
} else {
for (int k = 0; k < num; k++) {
goods[k].isSelect = selectedArray[k];
}
maxValue = value;//保存当前方案的最大价值
}
}
selectedArray[i] = false;//取消物品i的选择状态
if (value - goods[i].value > maxValue) { //还可以继续添加物品
if (i < num - 1) {
thiefSolve(goods, i + 1, weight, value - goods[i].value);
} else {
for (int k = 0; k < num; k++) {
goods[k].isSelect = selectedArray[k];
}
maxValue = value - goods[i].value;//保存当前方案的最大价值
}
}
}
Kotlin版本：
internal inner class ThingType {
//物品结果
var value //价值
= 0.0
var weight //重量
= 0.0
var isSelect //是否选中到方案
= false
}
fun thiefSolve(goods: Array<ThingType>, i: Int, weight: Double, value: Double) {
if (weight + goods[i].weight <= maxWeight) { //判断当前方案i重量是否超出限制
selectedArray[i] = true
if (i < num - 1) { //不是最后一个物品
thiefSolve(goods, i + 1, weight + goods[i].weight, value)
} else {
for (k in 0 until num) {
goods[k].isSelect = selectedArray[k]
}
maxValue = value //保存当前方案的最大价值
}
}
selectedArray[i] = false //取消物品i的选择状态
if (value - goods[i].value > maxValue) { //还可以继续添加物品
if (i < num - 1) {
thiefSolve(goods, i + 1, weight, value - goods[i].value)
} else {
for (k in 0 until num) {
goods[k].isSelect = selectedArray[k]
}
maxValue = value - goods[i].value //保存当前方案的最大价值
}
}
}
companion object {
var maxValue //方案最大价值
= 0.0
var totalValue //物品总价值
= 0.0
var maxWeight //窃贼能拿的最大重量
= 0.0
var num //物品数量
= 0
var selectedArray //临时选中数组
: BooleanArray
}
只看上述的算法，并不容易理解。还需要看初始化及传入的数据，这里用窃贼问题的数据做几点说明：
- 初始化数据，物品数量num = 5，goods是一个size=5的数组；物品总价值totalValue = 48 + 40 +12 + 8+ 7 = 115 ，maxValue初始值为0 ，maxWeight = 8;
- 开始调用thiefSolve()方法时，传入的参数是：thiefSolve(goods, 0, 0.0, totalValue); weight = 0.0，value = totalValue；
- 可以看出，weight表示当前方案的总重量；value表示当前方案的总价值，不过它并不是从0开始，而是反过来计算，初始值为最大值totalValue，然后随着 i 的增加减去不在方案中的物品价值。
(6)鸡兔同笼问题
鸡兔同笼问题于1500年前，由《孙子算经》所记载。大致是：在一个笼子里关着若干鸡和兔，从上面数有35个头，从下数共有94只脚。问鸡、兔各有多少只？
穷举法的Java版本：
int chicken;
int rabbit;
boolean computeChickenRabbit(int head,int foot){
int i,j;
for (i =0;i<=head;i++){
j = head - i;
if (i*2 + 4*j == foot){
chicken = i;
rabbit = j;
return true;
}
}
return false;
}
Kotlin版本：
var chicken = 0
var rabbit = 0
fun computeChickenRabbit(head: Int, foot: Int): Boolean {
var i: Int
var j: Int
i = 0
while (i <= head) {
j = head - i
if (i * 2 + 4 * j == foot) {
chicken = i
rabbit = j
return true
}
i++
}
return false
}
还有一种不使用穷举法的求解算法，它更为简单，主要思想是：一只鸡有一个头和两只脚，一只兔子有一个头和四只脚，那么所有的脚减去2倍的头，就是多余的兔子的另外两只脚。Java版本如下：
void computeChickenRabbit2(int head,int foot,int rabbitNum,int chickenNum){
rabbitNum = (foot - head*2)/2;
chickenNum = head - rabbitNum;
}
(7)八皇后问题
八皇后问题是1850年高斯提出的，是一个经典的回溯算法问题。大意是：在国际象棋的64个单元格中，摆放8个皇后，使其不能互相攻击，也就是说任意两个皇后不能处于同一列、同一行或者同一斜线上。问共有多少种摆法？每种是怎么摆的？
简略介绍一下国际象棋：它起源于亚洲，具体来自古印度，还是中国，尚有争论；同中国象棋一样，国际象棋共有32个棋子，每方16个，没有中国象棋的士、炮，增加了王后。王、王后各1个，车、马、象各2个，再加8个兵。
主要思路：采用递归的方式来求解，思路如下：
- 首先在棋盘的某个位置放置一个皇后；
- 放置下一个皇后，判断该皇后是否与前面的皇后形成互相攻击，若不互相攻击，则继续放下一个皇后；若相互攻击，则调整位置，再继续判断；
- 当放置完8个不形成攻击的皇后，就形成一个解，将其输出。
八皇后问题共有92个解，下面的算法会输出所有的解。为了便于理解，对输出结果做一点说明，如输出：1 6 8 3 7 4 2 5 ，表示第一个皇后放在第1行，第1列；第二个皇后放在第2行，第6列，第三个皇后放在第3行，第8列，······，依此类推。
Java版本：
/**
* 八皇后问题
*/
public class EightQueen {
final static int MAX = 8;
static int[] posArray = new int[MAX];
static int count;
public static void main(String[] args) {
eightQueen(0);
System.out.println("Solution count : " + count);
}
static void eightQueen(int n) {
if (n == MAX) {
printSolution();
return;
}
for (int i = 0; i < MAX; i++) {
posArray[n] = i; //在第n行的i列上放置
if (!willAttack(n)) {//不会引起冲突，就继续下一行
eightQueen(n + 1);
}
}
}
/**
* 和已有皇后是否相互攻击
*
* @param n
* @return
*/
static boolean willAttack(int n) {
for (int i = 0; i < n; i++) {
//如果同一列，或者列、行差值相等即斜率相等（对角线），会互相攻击
if (posArray[i] == posArray[n] || Math.abs(n - i) == Math.abs(posArray[i] - posArray[n])) {
return true;
}
}
return false;
}
/**
* 打印输出结果，下标加1进行调整
*/
static void printSolution() {
count++;
for (int i = 0; i < posArray.length; i++) {
System.out.print((posArray[i] + 1) + " ");
}
System.out.println();
}
}
Kotlin版本：
object EightQueen {
const val MAX = 8
var posArray = IntArray(MAX)
var count = 0
@JvmStatic
fun main(args: Array<String>) {
eightQueen(0)
println("Solution count : " + count)
}
fun eightQueen(n: Int) {
if (n == MAX) {
printSolution()
return
}
for (i in 0 until MAX) {
posArray[n] = i //在第n行的i列上放置
if (!willAttack(n)) { //不会引起冲突，就继续下一行
eightQueen(n + 1)
}
}
}
/**
* 和已有皇后是否相互攻击
*
* @param n
* @return
*/
fun willAttack(n: Int): Boolean {
for (i in 0 until n) {
//如果同一列，或者列、行差值相等即斜率相等（对角线），会互相攻击
if (posArray[i] == posArray[n] || Math.abs(n - i) == Math.abs(
posArray[i] - posArray[n]
)
) {
return true
}
}
return false
}
/**
* 打印输出结果，下标加1进行调整
*/
fun printSolution() {
count++
for (i in posArray.indices) {
print((posArray[i] + 1).toString() + " ")
}
println()
}
}
初看这个算法时，觉得这不是只输出一个解吗？printSolution()也才打印一次啊？怎么会输出92个解呢？注意这是一个递归调用，对于皇后每一行、每一列的可能位置都做了遍历。就拿放置第一个皇后为例，它可能出现在任意一列，针对每一个可能位置，对第二个皇后的放置有不同影响，依此类推。每一种可能，都处理到第8个皇后为止。所以，这个算法会输出所有的解。
(8)假银币问题
大意是这样的：有8枚银币，其中一枚是假币。但是，从外观和做工上无法分辨真假，只知道假币的重量比真币稍轻。要求使用一个天平，以最少的步骤寻找假银币？
主要思路：采用递归分治的思想来求解这个问题，步骤如下：
- 将所有的银币等分成2份，放在天平的两边；
- 因为假币的分量较轻，因此天平较轻的一侧中一定包含假币；
- 再将较轻的一侧中的银币等分为两份，重复上述的做法；
- 直到剩下最后两枚银币，可以直接找出。
关于等分，这里有一个问题，如果银币总数是奇数，是没法等分的。有一些书籍上，对奇偶情况分别判断，分别处理，使得算法既长，又重复，一点也不简练。在此，稍微改动一下，并不进行等分，而是进行3分，分3组。前2组银币个数相等，第三组个数不定。如果前2组重量一样，说明假币在第三组。
Java版本：
/**
* 假银币问题
*
* @param coinArray 包含假银币的数组
* @param low 起始位置
* @param high 结束位置
* @param n 个数
* @return 假银币的在数组中的下标，从0开始
*/
int falseCoin(int[] coinArray, int low, int high, int n) {
int num1, num2, num3;
int sum1 = 0, sum2 = 0;
if (n == 1) {
return low;
}
if (n % 3 == 0) {
num1 = num2 = n / 3;
} else {
num1 = num2 = n / 3 + 1;
}
num3 = n - num1 - num2;
for (int i = 0; i < num1; i++) {
sum1 += coinArray[i];
}
for (int i = 0; i < num2; i++) {
sum2 += coinArray[i];
}
if (sum1 < sum2) { //假币在第一组
return falseCoin(coinArray, low, low + sum1 - 1, sum1);
} else if (sum1 > sum2) { //假币在第二组
return falseCoin(coinArray, low + num1, low + sum1 + num2 - 1, sum2);
} else {//假币在第三组
return falseCoin(coinArray, low + num1 + num2, high, num3);
}
}
kotlin版本：
fun falseCoin(coinArray: IntArray, low: Int, high: Int, n: Int): Int {
val num1: Int
val num2: Int
val num3: Int
var sum1 = 0
var sum2 = 0
if (n == 1) {
return low
}
if (n % 3 == 0) {
num2 = n / 3
num1 = num2
} else {
num2 = n / 3 + 1
num1 = num2
}
num3 = n - num1 - num2
for (i in 0 until num1) {
sum1 += coinArray[i]
}
for (i in 0 until num2) {
sum2 += coinArray[i]
}
return if (sum1 < sum2) { //假币在第一组
falseCoin(coinArray, low, low + sum1 - 1, sum1)
} else if (sum1 > sum2) { //假币在第二组
falseCoin(coinArray, low + num1, low + sum1 + num2 - 1, sum2)
} else { //假币在第三组
falseCoin(coinArray, low + num1 + num2, high, num3)
}
}
(9)三色旗问题
大意是这样的：在一条绳子上挂有白、红、蓝三种颜色的多面旗子，这些旗子的排列是无序的。现要将绳子上的旗子按蓝、白、红三种颜色进行归类排列，每次可以调换两个旗子，问如何采用最少的步骤来完成？
主要思路：使用三个变量blue、white、red来表示旗子的顺序下标，初始时，blue、white均为0，red为旗子总数减1；在[ 0, blue-1]放置蓝色旗子，在[ blue, white-1 ]放置白色旗子，在[ red+1, length-1]放置红色旗子；[ white, red ]这个区间放置还未处理的旗子。每一次都处理变量write指向位置的元素，分3种情况：
- 如果white所在的位置是白旗，直接white++ ;
- 如果white所在的位置是蓝旗，将white处的元素与blue对调，然后blue++、white++；
- 如果white所在的位置是红旗，将white处的元素与red对调，然后red-- ；
Java版本：
/**
* 三色旗问题
*
* @param color 由'b'、'w'、'r'组成的无序字符数组
*/
void threeFlags(char[] color) {
int blue, white, red;
blue = white = 0;
red = color.length - 1;
while (color[white] == 'b') { //蓝旗
blue++;
white++;
}
while (color[red] == 'r') { //红旗
red--;
}
while (white <= red) {
if (color[white] == 'r') {
swap(color,white,red);
red--;
while (color[red] == 'r'){
red--;
}
}
if (color[white] == 'w'){
white++;
}
if (color[blue] == 'b'){
swap(color,white,blue);
white++;
blue++;
}
}
}
void swap(char[] charArray, int x, int y) {
char tmp = charArray[x];
charArray[x] = charArray[y];
charArray[y] = tmp;
}
Kotlin版本：
/**
* 三色旗问题
*
* @param color 由'b'、'w'、'r'组成的无序字符数组
*/
fun threeFlags(color: CharArray) {
var blue: Int
var white: Int
var red: Int
white = 0
blue = white
red = color.size - 1
while (color[white] == 'b') { //蓝旗
blue++
white++
}
while (color[red] == 'r') { //红旗
red--
}
while (white <= red) {
if (color[white] == 'r') {
swap(color, white, red)
red--
while (color[red] == 'r') {
red--
}
}
if (color[white] == 'w') {
white++
}
if (color[blue] == 'b') {
swap(color, white, blue)
white++
blue++
}
}
}
fun swap(charArray: CharArray, x: Int, y: Int) {
val tmp = charArray[x]
charArray[x] = charArray[y]
charArray[y] = tmp
}
(10)渔夫捕鱼问题
大意是这样的：某天，A、B、C、D、E 五个渔夫合伙捕了很多鱼，天黑后到岸边各自休息。第二天早晨，渔夫A第一个醒来，他将鱼分作五份，把多余的一条扔回河中，拿自己的一份回家去了。渔夫B第二个醒来，也将鱼分作五份，扔掉多余的一条，拿走自己的一份······以此类推，直到最后一个渔夫E醒来，也将鱼分作五份，扔掉多余的一条，拿走自己的一份。问五渔夫至少捕到多少条鱼呢？
先来看看一个错误的分析，这种分析非常地误导人。网络和书籍上的某些作者，都陷入了这个陷阱中，包括开始的自己。
- 每个渔夫醒来的时候，鱼的数量都应该是5的倍数再加1。先来看看最后一个渔夫E，鱼的数量最少应该是6。在他扔掉一条鱼之后，仍然可以平均分为5份；
- 渔夫D醒来的时候，鱼的数量应该是：6*5 + 1 = 31；
- 渔夫C醒来的时候，鱼的数量应该是：31*5+1 = 156；
- 渔夫B醒来的时候，鱼的数量应该是：156*5+1 = 781;
- 渔夫A醒来的时候，鱼的数量应该是：781*5 + 1 = 3906；那么，渔夫至少合伙捕到3906条鱼。
由上得到，这是一个递推的式子，公式：S
= 5S
+1;
这个分析乍一看，好像没什么问题。但拿笔在草稿本上算一算、画一画，就感到哪里不对劲了。让我们先来跟着它的分析，找到矛盾之处。
先假设上述分析没有问题，渔夫E醒来后的鱼数是6，渔夫D醒来后的鱼数是31，只看这两个数据就够了。从问题中，渔夫D比渔夫E先醒来，他将鱼数分作5份，扔掉多余的一条，拿走自己的一份。31条鱼，扔掉一条，还有30条，分作5份，每份6条，他拿走自己的一份，剩下应该有24条。随后，渔夫E醒来，此时鱼的数量应该是24，并不是6。这就是矛盾所在，所以上述分析是错误的，得出的公式也是错误的。
由上可知，如果渔夫E醒来后鱼的数量是6，渔夫D醒来后的鱼数肯定不是31，那么就想问一问，渔夫D醒来后的正确鱼数是多少？
假设渔夫D醒来后的正确鱼数是N，那么从问题描述中可以得到：N - 1 -
= 6 ，由它得出N =
+ 1；这显然不对，因为鱼的条数不可能是小数。所以，很显然，渔夫E醒来后的鱼数不可能为6。初始感觉是错误的。
我们先来推导一下正确的公式，将问题倒过来递推，以渔夫E醒来后的鱼数作为第一项。
假设S
S- 1 -
= S
由此可得：
S+ 1 , n
{1,2,3,4,5}
在本问题中，因为只有5个渔夫，第一项S，第二项S
，第三项S
，第四项S
，都必须能被4整除，而第五项S
无此要求。
那么，现在第一项S的值是多少呢？显然不能再靠感觉了。由上可知：
- S
的值必须被4整除，因此它的最小值为4；
- 因为S
、S
、S
也必须被4整除；所以如果发现有不能被整除的情况，那么可以推断，S
- 重新设置S
- S
可以不被4整除。
Java版本算法：
/**
* 5渔夫捕鱼问题
*/
public class FishProblem {
static int initValue = 4;
/**
* 5渔夫捕鱼问题求解
* @return 渔夫捕鱼问题的最少鱼数
*/
static int fiveFishmanProblem(){
int sum = initValue;
while (true){
for (int i=0;i<4;i++){ //只需要处理前4个值，保证被4整除
if (sum % 4 != 0){
break;
}
sum = sum *5/4+1;
}
if (sum%4 == 0){
break;
} else {
initValue += 4; //重置s1的值
sum = initValue;
}
}
sum = sum *5/4+1; //第5个值单独计算，不需要满足被4整除
return sum;
}
public static void main(String[] args) {
int result = fiveFishmanProblem();
System.out.println("result = "+result +" , S1 = "+ (initValue *5/4 +1));
}
运行这个程序，可以得出：
result = 3121 , S1 = 1276
从结果得知，渔夫E醒来时，鱼的数量是1276，他扔了一条，带走了255条；五渔夫总共捕获了至少3121条。
Kotlin版本：
/**
* 5渔夫捕鱼问题
*/
object FishProblem {
var initValue = 4
/**
* 5渔夫捕鱼问题求解
* @return 渔夫捕鱼问题的最少鱼数
*/
fun fiveFishmanProblem(): Int {
var sum = initValue
while (true) {
for (i in 0..3) { //只需要处理前4个值，保证被4整除
if (sum % 4 != 0) {
break
}
sum = sum * 5 / 4 + 1
}
if (sum % 4 == 0) {
break
} else {
initValue += 4 //重置s1的值
sum = initValue
}
}
sum = sum * 5 / 4 + 1 //第5个值单独计算，不需要满足被4整除
return sum
}
@JvmStatic
fun main(args: Array<String>) {
val result = fiveFishmanProblem()
println("result = " + result + " S1 = " + (initValue * 5 / 4 + 1))
}
}
让我们继续深入一下，上述算法是否可以扩充到任意个渔夫？很显然，简单的传递一个渔夫数量参数是不行的，因为不同的渔夫数量，得出的推导公式是不同的。让我们来分别考虑。
二渔夫情况：这个很简单，S=3，S
=7，两个人最少捕获7条鱼。
三渔夫情况：可以推导获得以下公式：
假设S
S= S
由此可得：
S+ 1 , n
可以得出这样的结论：S、S
必须被2整除，S
无此限制。
Java版本：
/**
* 3渔夫捕鱼问题
*/
public class FishProblem {
static int initValue = 2;
static int threeFishmanProblem(){
int sum = initValue;
while (true){
for (int i=0;i<2;i++){ //只需要处理前2个值，保证被2整除
if (sum % 2 != 0){
break;
}
sum = sum *3/2+1;
}
if (sum%2 == 0){
break;
} else {
initValue += 2; //重置s1的值
sum = initValue;
}
}
sum = sum *3/2+1; //第3个值单独计算，不需要满足被2整除
return sum;
}
public static void main(String[] args) {
int result = threeFishmanProblem();
System.out.println("result = "+result +" , S1 = "+ (initValue *3/2 +1));
}
}
运行此程序，得到的结果是：
result = 25 , S1 = 10
可以得知，三渔夫最少捕获25条鱼。
类似的，四渔夫推导公式：
S - 1 -
= S
由此可得：
S =
+ 1 , n
{1,2,3,4}
它的Java实现就省略了，和上面的大同小异。
综上所述，可以得到m个渔夫推导公式：
S - 1 -
= S
由此可得：
S =
+ 1 , n
{1,2,......,m}
它的Java代码实现：
/**
* m渔夫捕鱼问题
*/
public class FishProblem {
static int initValue = 0;
/**
* m渔夫捕鱼问题
*
* @return
*/
static int mFishman(int m) {
if (m == 1) {
return 3;
}
initValue = m - 1;
int sum = initValue;
while (true) {
for (int i = 0; i < m - 1; i++) { //只需要处理前m-1个值，保证被m-1整除
if (sum % (m - 1) != 0) {
break;
}
sum = sum * m / (m - 1) + 1;
}
if (sum % (m - 1) == 0) {
break;
} else {
initValue += (m - 1); //重置s1的值
sum = initValue;
}
}
sum = sum * m / (m - 1) + 1; //第m个值单独计算，不需要满足被m-1整除
return sum;
}
public static void main(String[] args) {
int m = 6; //随便设置
int result = mFishman(m);
System.out.println("result = "+result +" S1 = "+ (initValue *m/(m-1) +1));
}
}
Kotlin版本就省略了，毕竟这一小节已经很长了。
(11)爱因斯坦的阶梯
大意是这样的：有一个楼，其两层之间有一个很长的阶梯。如果一个人每步上2阶，最后剩1阶；如果每步上3阶，最后剩2阶；如果每步上5阶，最后剩4阶；如果每步上6阶，最后剩5阶；如果每步上7阶，最后刚好一阶不剩。问这个阶梯至少有多少阶？
主要思路：阶数与上面这些数字，存在特定的关系，比如是7的倍数、奇数等，通过遍历，找到满足这些关系的数。
Java版本：
int computeEinsteinStairs() {
int count = 7;
for (int i = 0; i < 100; i++) {
if (count % 2 == 1 && count % 3 == 2 && count % 5 == 4 && count % 6 == 5) {
break;
}
count = 7 * (i + 1);
}
return count;
}
Kotlin版本：
fun computeEinsteinStairs(): Int {
var count = 7
for (i in 0..99) {
if (count % 2 == 1 && count % 3 == 2 && count % 5 == 4 && count % 6 == 5) {
break
}
count = 7 * (i + 1)
}
return count
}
(12)常胜将军问题
大意是这样的：甲乙两人玩轮流抽火柴的游戏，共有21根火柴。每个人每次最多取4根火柴，最少取1根，取到最后一根火柴的判输。甲让乙先抽，结果每次都是甲赢。这是为什么？
分析：把问题倒过来看，不从21开始分析，以乙拿火柴时的可能数量倒序分析：
- 如果乙拿火柴时火柴数为1，那么按照规则，乙必输，甲要争取这种情况；
- 如果乙拿火柴时火柴数是2-5，那么他总可以留下一根，则乙必胜，甲要避免这种情况；
分析火柴数大于5的情况。如果乙取火柴时，火柴数是6，那么：
- 乙取1根，剩5根，甲取4根，留1根，甲胜；
- 乙取2根，剩4根，甲取3根，留1根，甲胜；
- 乙取3根，剩3根，甲取2根，留1根，甲胜；
- 乙取4根，剩2根，甲取1根，留1根，甲胜；
可以看到：只要甲取的火柴数，等于5减去乙取的火柴数，那么甲必胜。也就是说，如果火柴数是6，遵照这个规则，那么谁先拿，谁必输。
由此可以推断，如果火柴数是7、8、9、10，那么先拿的一方可以让剩下的火柴数等于6，从而获胜。即谁先拿，谁必胜。
再考虑火柴数是11，此时不论拿几根火柴，都会让剩下的数量在区间[ 7, 10 ]，必输。即谁先拿，谁必输。
同样的道理，如果火柴数在区间[ 12, 16 ]，那么先拿者总可以让剩下的火柴数等于11，必胜。即谁先拿，谁必胜。
综上所述，可以得到更一般的规律：如果火柴初始数量等于(5n+1)，n {1,2,3,......}，那么谁先拿，谁必输；如果不等，那么谁先拿，谁必胜。
实现方案：如果火柴初始数量S=(5n+1)，先拿者拿走m个，其中m {1,2,3,4}，不论m是多少，后拿者只要拿走(5 - m)个，就可以让剩余火柴数朝着1递进，从而实现必胜的目标，即先拿必输。如果火柴初始数量S
(5n+1)，那么先找到一个值K，K满足
，然后先拿者只要拿走( S - K )根火柴，就可以保证必胜，即先拿必胜。
回归到本小节最开始的问题，火柴的初始值是21，满足(5n+1)，其中n=4，所以根据上面的规律：先拿必输。乙先拿，乙必输，这也是甲每次都赢的原因。
Java版本：
import java.util.Random;
/**
* 常胜将军问题
*/
public class AlwaysWinQ {
static String personA = "甲";
static String personB = "乙";
static void alwaysWinQ(int matchNum) {
int n = (matchNum - 1) / 5;
int r = (matchNum - 1) % 5;
int leftNum = matchNum;
int bGetNumPerTime, aGetNumPerTime;
int count = 0;
Random random = new Random();
if (r == 0) {
System.out.println("满足(5n+1)，结论：先拿者必输。实际过程如下：");
while (leftNum > 1) {
//乙先拿，随机拿几个
bGetNumPerTime = 1 + random.nextInt(4);
aGetNumPerTime = 5 - bGetNumPerTime;
System.out.println("第" + (++count) + "次循环，" + personB + "拿走了" + bGetNumPerTime
+ "根火柴，剩下" + (leftNum - bGetNumPerTime) + "根，" + personA + "拿走了"
+ aGetNumPerTime + "根火柴，剩下" + (leftNum - bGetNumPerTime - aGetNumPerTime));
leftNum -= aGetNumPerTime + bGetNumPerTime;
}
if (leftNum == 1) {
System.out.println("最后一次循环，剩余火柴数量为1，" + personB + "拿走，" + personA + "获胜！");
}
} else {
System.out.println("不满足(5n+1)，结论：先拿者必胜。实际过程如下：");
int bGetNumFirstTime = matchNum - (5 * n + 1);
System.out.println(personB + "先拿，拿走" + bGetNumFirstTime + "根火柴。剩余：" + (leftNum - bGetNumFirstTime));
leftNum -= bGetNumFirstTime;
while (leftNum > 1) {
//乙已经拿过了，现在轮到甲拿，数量随机
aGetNumPerTime = 1 + random.nextInt(4);
bGetNumPerTime = 5 - aGetNumPerTime;
System.out.println("第" + (++count) + "次循环，" + personA + "拿走了" + aGetNumPerTime
+ "根火柴，剩下" + (leftNum - aGetNumPerTime) + "根，" + personB + "拿走了"
+ bGetNumPerTime + "根火柴，剩下" + (leftNum - bGetNumPerTime - aGetNumPerTime));
leftNum -= aGetNumPerTime + bGetNumPerTime;
}
if (leftNum == 1) {
System.out.println("最后一次循环，剩余火柴数量为1，" + personA + "拿走，" + personB + "获胜！");
}
}
}
public static void main(String[] args) {
int matchNum = 21;
System.out.println("轮流抽火柴游戏，火柴总数：" + matchNum + "，规则：" + personB + "先拿，每次最少拿1根，最多拿4根；拿到最后一根的判输。");
System.out.println();
int repeatNum = 5;
System.out.println("重复玩" + repeatNum + "次，看看结果是否一致");
for (int i = 0; i < repeatNum; i++) {
System.out.println("********************");
alwaysWinQ(matchNum);
System.out.println();
}
}
}
当matchNum=21时，以下是部分输出：
轮流抽火柴游戏，火柴总数：21，规则：乙先拿，每次最少拿1根，最多拿4根；拿到最后一根的判输。
满足(5n+1)，结论：先拿者必输。实际过程如下：
第1次循环，乙拿走了1根火柴，剩下20根，甲拿走了4根火柴，剩下16
第2次循环，乙拿走了2根火柴，剩下14根，甲拿走了3根火柴，剩下11
第3次循环，乙拿走了3根火柴，剩下8根，甲拿走了2根火柴，剩下6
第4次循环，乙拿走了3根火柴，剩下3根，甲拿走了2根火柴，剩下1
最后一次循环，剩余火柴数量为1，乙拿走，甲获胜！
当matchNum=22时，以下是部分输出：
轮流抽火柴游戏，火柴总数：22，规则：乙先拿，每次最少拿1根，最多拿4根；拿到最后一根的判输。
不满足(5n+1)，结论：先拿者必胜。实际过程如下：
乙先拿，拿走1根火柴。剩余：21
第1次循环，甲拿走了1根火柴，剩下20根，乙拿走了4根火柴，剩下16
第2次循环，甲拿走了4根火柴，剩下12根，乙拿走了1根火柴，剩下11
第3次循环，甲拿走了4根火柴，剩下7根，乙拿走了1根火柴，剩下6
第4次循环，甲拿走了2根火柴，剩下4根，乙拿走了3根火柴，剩下1
最后一次循环，剩余火柴数量为1，甲拿走，乙获胜！
从输出结果，验证了上面总结的规律。
鉴于本小节有点长，Kotlin版省略。
(13)新郎和新娘问题
大意是这样的：有三对新婚夫妇参加集体婚礼，三个新郎为A、B、C，三个新娘为X、Y、Z。主持人一时忘了谁应该和谁结婚，于是他便问这6个人中的三个。这三个人开起了玩笑，全都给了错误的答案，如下：
- 新郎A说他将和新娘X结婚；
- 新娘X说她将和新郎C结婚；
- 新郎C说他将和新娘Z结婚。
到底谁应该和谁结婚呢？
主要思路：遍历可能的组合，并将错误的答案排除。
分析：这个问题，通过直观分析就可以获得答案。CX、CZ都是错误的组合，所以只能是CY。AX是错误的组合，所以只能是AZ，剩下一个BX。结果是AZ、BX、CY这种结婚方案。但是如果夫妇数量扩展了，直观分析就变得麻烦了。借助于程序，处理起来就要方便得多。首先，还是基于3对夫妇进行编程，后续再扩展。
有些算法使用了2个数组，分别是新郎、新娘数组，bridegroomArray[] = {'A','B','C'}，brideArray[] = {'X','Y','Z'}。这里简化一下，只使用一个新娘数组brideArray[] = {'X','Y','Z'}。新郎的顺序A、B、C设定不变，对应的下标index固定为0,1,2。i、j、k分别代表着A、B、C对应新娘的下标，可以得出下面的条件：
brideArray[ i ]
'X' ；
brideArray[ k ]
brideArray[ k ]
Java版本：
static void groomBrideQ() {
char[] brideArray = {'X', 'Y', 'Z'};
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
if (i != j && j != k && k != i) {
if (brideArray[i] != 'X' && brideArray[k] != 'X' && brideArray[k] != 'Z') {
System.out.println("A*" + brideArray[i]);
System.out.println("B*" + brideArray[j]);
System.out.println("C*" + brideArray[k]);
}
}
}
}
}
}
输出：
A*Z
B*X
C*Y
Kotlin版：
fun groomBrideQ() {
val brideArray = charArrayOf('X', 'Y', 'Z')
for (i in 0..2) {
for (j in 0..2) {
for (k in 0..2) {
if (i != j && j != k && k != i) {
if (brideArray[i] != 'X' && brideArray[k] != 'X' && brideArray[k] != 'Z') {
println("A*" + brideArray[i])
println("B*" + brideArray[j])
println("C*" + brideArray[k])
}
}
}
}
}
}
扩展到4对新婚夫妇，新郎为A、B、C、D，新娘为X、Y、Z、W。如果不额外添加错误条件，还用上面的，是有很多个组合的。下面的算法额外添加了3个错误条件，使得组合只有一个。错误条件的文字描述就省略了，看代码应该可以推测出来。
Java版本：
static void groomBrideQ() {
char[] brideArray = {'X', 'Y', 'Z', 'W'};
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
for (int k = 0; k < 4; k++) {
for (int l = 0; l < 4; l++) {
if (i != j && j != k && k != l && l != i && i != k && i != l && j != l) {
if (brideArray[i] != 'X' && brideArray[k] != 'X' && brideArray[k] != 'Z'
&& brideArray[i] != 'W' && brideArray[j] != 'X' && brideArray[k] != 'W') {
System.out.println("A*" + brideArray[i]);
System.out.println("B*" + brideArray[j]);
System.out.println("C*" + brideArray[k]);
System.out.println("D*" + brideArray[l]);
}
}
}
}
}
}
}
输出：
A*Z
B*W
C*Y
D*X
(14)三色球问题
大意是这样的：一个黑盒中放着3个红球、3个黄球和6个绿球，如果从其中取出8个球，那么取出的球中有多少种颜色搭配？
分析：这是一个经典的排列组合问题，下面分别从数学和编程角度来分析它。
数学角度，以红球作为出发点，有下面几种可能：
- 无红球：只有两种搭配，即2黄6绿，或者3黄5绿，记为C
- 1个红球：问题变成从3黄球6绿球中取出7球，那么至少有一个黄球，故有3种搭配，记为C
- 2个红球：问题变成从3黄球6绿球中取出6球，那么可以没有黄球，比2）要多一种可能，故有4种搭配，记为C
- 3个红球：问题变成从3黄球6绿球中取出5球，同3）一样，可以没有黄球，也有4种搭配，记为C
因此，得出的搭配总数是：C + C
+ C
+ C
= 13 ，即取出的球中有13种颜色搭配。
作为人，很容易在每种情况里，把8这个要求时刻放到脑海里。计算机虽然可以处理庞大的数据，但要求它每种情况都记住并分别计算，那代码写起来就要冗长、困难得多，可读性也差。所以在编程时，更倾向于通用的方式来求解。可以多处理一些数据，范围也可以更大，只要能用通用的条件来过滤这些数据，最终求得正确结果就行。
那么，现在从编程角度分析三色球问题。先不考虑8这个总数要求，单论每种球的极限可能：红球有4种可能(0、1、2、3)、黄球有4种可能、绿球有7种可能。针对这些可能的各种组合(4*4*7=112种)，再用总数为8作为过滤条件，就可以得出正确的结果。举个例子，0红0黄0绿这种方案也在这112种可能当中，但它显然不满足条件，被过滤掉。对计算机来说，多一定数量的计算，无伤大雅。
Java版本：
/**
* 3色球问题
*/
public class ThreeBallQ {
static int threeBallQ(int red, int yellow, int green, int n) {
int count = 0;
for (int i = 0; i <= red; i++) {
for (int j = 0; j <= yellow; j++) {
for (int k = 0; k <= green; k++) {
if (i + j + k == n) {
count++;
}
}
}
}
return count;
}
public static void main(String[] args) {
int count = threeBallQ(3, 3, 6, 8);
System.out.println("有" + count + "种搭配方案");
}
}
输出结果：
有13种搭配方案
结果符合预期。但从算法实现来看，并没有像数学那样分不同情况分别计算。而是使用一种通用的方式，在极限可能的范围并满足特定的条件下求解。这显示出了人脑思维和编程思维的极大不同。这一点在计算机世界是随处可见，面对编程时常常需要将人脑思维切换到编程思维。希望以本小节为例，可以加深你的理解。
Over !
网友评论