Java二十八：遞歸和取模與取余
遞歸
程序調(diào)用自身的編程技巧稱為遞歸（ recursion）。一般來(lái)說(shuō)，遞歸需要有邊界條件、遞歸前進(jìn)段和遞歸返回段。當(dāng)邊界條件不滿足時(shí)，遞歸前進(jìn)；當(dāng)邊界條件滿足時(shí)，遞歸返回。
理論上，遞歸三要素可分為：
遞歸的終結(jié)點(diǎn)；
遞歸的公式；
遞歸的方向必須走向終結(jié)點(diǎn)；
引用java遞歸實(shí)現(xiàn)99乘法表
package com.example.demo.test4;
/**
* @program: test
* @description:
* @author: liulq
* @create: 2022-01-11 10:45
*/
publicclass Day {
? ? ? ?public static void main(String args[]) {
? ? ? ? ? ?m(9);
? ? ? ?}
? ? ? ?/**
? ? ? ? * 打印出九九乘法表
? ? ? ? * @param i
? ? ? ? */
? ? ? ?public static void m(int i) {
? ? ? ? ? ?if (i == 1) {
? ? ? ? ? ? ? ?System.out.println("1*1=1 ");
? ? ? ? ? ?} else {
? ? ? ? ? ? ? ?m(i - 1);
? ? ? ? ? ? ? ?for (int j = 1; j <= i; j++) {
? ? ? ? ? ? ? ? ? ?System.out.print(j + "*" + i + "=" + j * i + " ");
? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ?System.out.println();
? ? ? ? ? ?}
? ? ? ?}
}
示例1：累加求和
/**
* 求 1 - n 的和
*/
public static int f(int n){
? ?if(n == 1 ) {
? ? ? ?return1;
? ?}
? ?return f(n - 1) + n;
}
遞歸的終結(jié)點(diǎn)：f(1) = 1;
遞歸的公式：f(n) = f(n-1) + n；
遞歸的方向走向終結(jié)點(diǎn) f(1);
公式的轉(zhuǎn)換
對(duì)于公式 f(x) = f(x + 1) + 2 來(lái)說(shuō)，其遞歸的方向?yàn)檎裏o(wú)窮，當(dāng)他的終結(jié)點(diǎn)為 f(1) 時(shí)，就需要轉(zhuǎn)換公式來(lái)解決。
即：令 x = x - 1; 則 f(x) = f(x - 1) - 2;
示例2：n 的階乘
public static int f(int n){
? ?if(n == 1){
? ? ? ?return1 ;
? ?}else{
? ? ? ?return f(n - 1) * n;
? ?}
}
遞歸的終結(jié)點(diǎn)：f(1) = 1;
遞歸的公式
n!= 123456...(n-1)n f(n) = 123456...*(n-1)*n f(n) = f(n-1)*n
遞歸的方向走向終結(jié)點(diǎn) f(1);
示例3：非規(guī)律化遞歸：啤酒問(wèn)題
啤酒2元1瓶，4個(gè)蓋子可以換一瓶，2個(gè)空瓶可以換一瓶，問(wèn)10元可以喝多少瓶，剩余多少蓋子和瓶子 （15 3 1）
/**
* 啤酒2元1瓶，4個(gè)蓋子可以換一瓶，2個(gè)空瓶可以換一瓶
* @param money 多少錢
* @param count 喝了多少瓶
* @param gaizi 剩余蓋子數(shù)
* @param pingzi 剩余瓶子數(shù)
* @return
*/
publicstaticint[] 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);
? ? ? ?}
? ?}
? ?returnnewint[]{count, gaizi, pingzi};
}
解法2：
// 定義一個(gè)靜態(tài)變量存儲(chǔ)可以喝酒的總數(shù)
publicstaticint totalNum;
publicstaticint lastPingZiNum;
publicstaticint lastGaiZiNum;
public static void buyBeer(int money){
? ?// a.拿錢買酒
? ?int number = money / 2 ;
? ?// 累加起來(lái)
? ?totalNum += number;
? ?// 算出當(dāng)前剩余的全部蓋子和瓶子數(shù)，換算成金額繼續(xù)購(gòu)買。
? ?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 ;
? ?// 繼續(xù)拿錢買酒
? ?if(totalMoney >= 2){
? ? ? ?buyBeer(totalMoney);
? ?}
}
取模與取余區(qū)別
概念上：取模是計(jì)算機(jī)術(shù)語(yǔ)，取余屬于數(shù)學(xué)概念；
結(jié)果上：當(dāng)同號(hào)的兩個(gè)數(shù)相除，二者相同，有負(fù)數(shù)的情況下，結(jié)果不同；
在 Java 中，
%?運(yùn)算符代表取余操作。計(jì)算上：
取余運(yùn)算在計(jì)算商值時(shí)商值向 0 方向舍入，商值靠近0原則；
取模運(yùn)算在計(jì)算商值時(shí)商值向負(fù)無(wú)窮方向舍入，商值小原則；
計(jì)算步驟
對(duì)于整型數(shù)，取余和取模的步驟是一樣的
對(duì)于整數(shù)a，b，若想求其余數(shù)和模，則有：
整數(shù)商：c = a / b ;
取余/取模：r = a - b * c
取余和取模的區(qū)別在于整數(shù)商的計(jì)算方式不同，取余運(yùn)算的整數(shù)商參考靠近0原則，取模運(yùn)算的整數(shù)商參考商值小原則。
例子
以 5 與 3 之間運(yùn)算舉例：
取模
簡(jiǎn)述商值計(jì)算過(guò)程取模值5 mod 3 = 25/3 = 1.66 ?商取小原則 ?商=15 - 3 * 1 = 22-5 mod 3 = 1-5/3 = -1.66 商取小原則 商=-2-5 - (3 * -2) = 115 mod -3 = -15/-3 = -1.66 商取小原則 商=-25 - (-3 * -2) = -1-1-5 mod -3 = -2-5/-3 = 1.66 商取小原則 商=1-5 - (-3 * 1) = 2-2
取余
簡(jiǎn)述商值計(jì)算過(guò)程取余值5 rem 3 = 25/3 = 1.66 ?商靠0原則 ?商=15 - 3 * 1 ?= 22-5 rem 3 = -2-5/3 = -1.66 商靠0原則 商=-1-5 - (3 * -1) = - 2-25 rem -3 = 25/-3 = -1.66 商靠0原則 商=-15 - (-3 * -1) = ?22-5 rem -3 = -2-5/-3 = 1.66 商靠0原則 商=1-5 - (-3 * 1) = - 2-2
深入理解
在 12 模的時(shí)鐘中；假設(shè)當(dāng)前時(shí)針指向 6 點(diǎn)，而準(zhǔn)確時(shí)間是 2 點(diǎn)，調(diào)整時(shí)間最少有以下兩種撥法
倒撥4小時(shí)：6-4=2正撥8小時(shí)：(6+8) mod 12=2
除此之外，還有 正撥 8 +12 小時(shí)等，(6+20) mod 12 = 2；
mod 為取模，在正整數(shù)中結(jié)果等于取余數(shù)。
即上面結(jié)果表明，正撥（加法）的結(jié)果可以用倒撥（減法）來(lái)替代！
而對(duì)于如何用一個(gè)正數(shù)來(lái)替代一個(gè)負(fù)數(shù)（減法可以看到加一個(gè)負(fù)數(shù)），數(shù)學(xué)上有一個(gè)概念叫做同余。
同余
兩個(gè)整數(shù) a，b，若他們的除以整數(shù) m 所得的余數(shù)相等，則稱 a，b 對(duì)于模 m 同余。記作 a ≡ b (mod m)，讀作 a 與 b 關(guān)于模 m 同余。
舉例：
2 mod 12 = 2
14 mod 12 = 2
26 mod 12 = 2
所以，2、14、26 關(guān)于模 12 同余
應(yīng)用
取模的本質(zhì)是：取模的值，必定在模的范圍內(nèi)；所以，計(jì)算機(jī)領(lǐng)域引用該特性，使元素路由算法不超出邊界，并有規(guī)則存放。
首先確定模(范圍)；元素取模，使元素有規(guī)則的落入模的范圍內(nèi)容器中。即余數(shù)的范圍小于除數(shù)的值。
舉例：
對(duì)于兩個(gè)整數(shù) a，b
如果 a <= b，令 r = a % b，則 0 <= r < b，且只有當(dāng) a = b 時(shí)，r = 0；
3 % 5 = 3
2 % 5 = 2
5 % 5 = 0
參考的文章：
https://www.cnblogs.com/zhangziqiu/archive/2011/03/30/ComputerCode.html
https://www.jianshu.com/p/5e1a83e8be3b
總結(jié)：
1、引用遞歸可以實(shí)現(xiàn)java的一些復(fù)雜的實(shí)現(xiàn)，簡(jiǎn)化代碼
2、概念上：取模是計(jì)算機(jī)術(shù)語(yǔ)，取余屬于數(shù)學(xué)概念；
結(jié)果上：當(dāng)同號(hào)的兩個(gè)數(shù)相除，二者相同，有負(fù)數(shù)的情況下，結(jié)果不同；
在 Java 中，
%?運(yùn)算符代表取余操作。計(jì)算上：
取余運(yùn)算在計(jì)算商值時(shí)商值向 0 方向舍入，商值靠近0原則；
取模運(yùn)算在計(jì)算商值時(shí)商值向負(fù)無(wú)窮方向舍入，商值小原則；
3、取余和取模的區(qū)別在于整數(shù)商的計(jì)算方式不同，取余運(yùn)算的整數(shù)商參考靠近0原則，取模運(yùn)算的整數(shù)商參考商值小原則。
4、在一些精確度的需求時(shí)會(huì)用到
