递归
程序调用自身的编程技巧称为递归（ recursion）。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
理论上，递归三要素可分为：
- 递归的终结点；
- 递归的公式；
- 递归的方向必须走向终结点；
示例1：累加求和
/** * 求 1 - n 的和 */ public static int f(int n){ if(n == 1 ) { return 1; } return f(n - 1) + n; }
- 递归的终结点：f(1) = 1;
- 递归的公式：f(n) = f(n-1) + n；
- 递归的方向走向终结点 f(1);
公式的转换
对于公式 f(x) = f(x + 1) + 2 来说，其递归的方向为正无穷，当他的终结点为 f(1) 时，就需要转换公式来解决。
即：令 x = x - 1; 则 f(x) = f(x - 1) - 2;
示例2：n 的阶乘
public static int f(int n){ if(n == 1){ return 1 ; }else{ return f(n - 1) * n; } }
- 递归的终结点：f(1) = 1;
- 递归的公式
- n!= 1*2*3*4*5*6*...*(n-1)*n
f(n) = 1*2*3*4*5*6*...*(n-1)*n
f(n) = f(n-1)*n
- 递归的方向走向终结点 f(1);
示例3：非规律化递归：啤酒问题
啤酒2元1瓶，4个盖子可以换一瓶，2个空瓶可以换一瓶，问10元可以喝多少瓶，剩余多少盖子和瓶子 （15 3 1）
/** * 啤酒2元1瓶，4个盖子可以换一瓶，2个空瓶可以换一瓶 * @param money 多少钱 * @param count 喝了多少瓶 * @param gaizi 剩余盖子数 * @param pingzi 剩余瓶子数 * @return */ public static int[] canDrink(int money,int count, int gaizi, int pingzi) { if (money > 1 || gaizi >= 4 || pingzi >= 2) { if (money > 0 && money != 1) { return canDrink(money - 2, ++count, ++gaizi, ++pingzi); } if (gaizi >= 4) { gaizi = gaizi - 4 + 1; return canDrink(money, ++count, gaizi, ++pingzi); } if (pingzi >= 2) { pingzi = pingzi - 2 + 1; return canDrink(money, ++count, ++gaizi, pingzi); } } return new int[]{count, gaizi, pingzi}; }
解法2：
// 定义一个静态变量存储可以喝酒的总数 public static int totalNum; public static int lastPingZiNum; public static int lastGaiZiNum; public static void buyBeer(int money){ // a.拿钱买酒 int number = money / 2 ; // 累加起来 totalNum += number; // 算出当前剩余的全部盖子和瓶子数，换算成金额继续购买。 int currentPingZiNum = lastPingZiNum + number ; int currentGaiZiNum = lastGaiZiNum + number ; // 把他们换算成金额 int totalMoney = 0 ; totalMoney +=(currentPingZiNum/2)*2; //算出剩余的瓶子 lastPingZiNum = currentPingZiNum % 2 ; // 换算盖子 totalMoney+=(currentGaiZiNum / 4) * 2; lastGaiZiNum = currentGaiZiNum % 4 ; // 继续拿钱买酒 if(totalMoney >= 2){ buyBeer(totalMoney); } }
取模与取余
https://www.cnblogs.com/zhangziqiu/archive/2011/03/30/ComputerCode.html
https://www.jianshu.com/p/5e1a83e8be3b
取模与取余区别
- 概念上：取模是计算机术语，取余属于数学概念；
- 结果上：当同号的两个数相除，二者相同，有负数的情况下，结果不同；
- 在 Java 中，
%运算符代表取余操作。 - 计算上：
- 取余运算在计算商值时商值向 0 方向舍入，商值靠近0原则；
- 取模运算在计算商值时商值向负无穷方向舍入，商值小原则；
计算步骤
对于整型数，取余和取模的步骤是一样的
对于整数a，b，若想求其余数和模，则有：
整数商：c = a / b ;
取余/取模：r = a - b * c
取余和取模的区别在于整数商的计算方式不同，取余运算的整数商参考靠近0原则，取模运算的整数商参考商值小原则。
例子
以 5 与 3 之间运算举例：
取模
简述 |
商值 |
计算过程 |
取模值 |
5 mod 3 = 2 |
5/3 = 1.66 商取小原则 商=1 |
5 - 3 * 1 = 2 |
2 |
-5 mod 3 = 1 |
-5/3 = -1.66 商取小原则 商=-2 |
-5 - (3 * -2) = 1 |
1 |
5 mod -3 = -1 |
5/-3 = -1.66 商取小原则 商=-2 |
5 - (-3 * -2) = -1 |
-1 |
-5 mod -3 = -2 |
-5/-3 = 1.66 商取小原则 商=1 |
-5 - (-3 * 1) = 2 |
-2 |
取余
简述 |
商值 |
计算过程 |
取余值 |
5 rem 3 = 2 |
5/3 = 1.66 商靠0原则 商=1 |
5 - 3 * 1 = 2 |
2 |
-5 rem 3 = -2 |
-5/3 = -1.66 商靠0原则 商=-1 |
-5 - (3 * -1) = - 2 |
-2 |
5 rem -3 = 2 |
5/-3 = -1.66 商靠0原则 商=-1 |
5 - (-3 * -1) = 2 |
2 |
-5 rem -3 = -2 |
-5/-3 = 1.66 商靠0原则 商=1 |
-5 - (-3 * 1) = - 2 |
-2 |
深入理解
在 12 模的时钟中；假设当前时针指向 6 点，而准确时间是 2 点，调整时间最少有以下两种拨法
倒拨4小时：6-4=2 |
正拨8小时：(6+8) mod 12=2 |
除此之外，还有 正拨 8 +12 小时等，(6+20) mod 12 = 2；
mod 为取模，在正整数中结果等于取余数。
即上面结果表明，正拨（加法）的结果可以用倒拨（减法）来替代！
而对于如何用一个正数来替代一个负数（减法可以看到加一个负数），数学上有一个概念叫做同余。
同余
两个整数 a，b，若他们的除以整数 m 所得的余数相等，则称 a，b 对于模 m 同余。记作 a ≡ b (mod m)，读作 a 与 b 关于模 m 同余。
举例：
2 mod 12 = 2
14 mod 12 = 2
26 mod 12 = 2
所以，2、14、26 关于模 12 同余
应用
取模的本质是：取模的值，必定在模的范围内；所以，计算机领域引用该特性，使元素路由算法不超出边界，并有规则存放。
首先确定模(范围)；元素取模，使元素有规则的落入模的范围内容器中。即余数的范围小于除数的值。
举例：
对于两个整数 a，b
如果 a <= b，令 r = a % b，则 0 <= r < b，且只有当 a = b 时，r = 0；
3 % 5 = 3
2 % 5 = 2
5 % 5 = 0
