題目清單：
- 上樓梯
- 走格子
- 硬币表示
- 合法括号
- 水窪數目
一、上樓梯
代碼塊：
/*
題目描述：
有個小孩正在上樓梯，樓梯有n階台階，小孩一次可以上1階、2階、3階。
請實作一個方法，計算小孩有多少種上樓的方式？
為了防止溢出，請将結果 Mod 10000007
給定一個正整數int n，請傳回一個數，代表上樓的方式數。
*/
/*
思路：（自下而上——想）
比如：把問題的規模往小的方面想：
上一節樓梯會有幾種走法，上兩節樓梯有幾種走法，一次類推到一個大問題
*/
import java.util.Scanner;
public class 上樓梯 {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(f(n));
}
//使用遞歸求總的走法，适合規模小的樓梯
static int mod = 10000007;
static int f(int n){
if(n < 0)return 0;
if(n == 0|| n == 1)return 1;
if(n == 2)return 2;
if(n == 3)return 4;
return f(n-1)%mod + f(n-2)%mod + f(n-3)%mod;
}
}
二、走格子
代碼塊：（兩種解法：遞歸和遞推）
/*
題目描述：
有一個x*y的網格，一個機器人隻能走格點且隻能向右或向下走，要從左上角走到右下角。
請設定一個算法，計算機器人有多少種走法？
給定兩個正整數int x，int y，請傳回機器人的走法數目，保證x+y小于等于12.
*/
import java.util.Scanner;
public class 走格子 {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int row = sc.nextInt();
int col = sc.nextInt();
long start = System.currentTimeMillis();
System.out.println(f1(row, col));
System.out.println("遞歸耗時："+(System.currentTimeMillis()-start)+"ms");
System.out.println(f2(row, col));
System.out.println("疊代耗時："+(System.currentTimeMillis()-start)+"ms");
}
//使用遞歸求解（效率非常的低），相對抽象、簡便
static int f1(int x, int y){
if(x == 1 || y == 1)return 1;
return f1(x-1, y) + f1(x, y-1);
}
//使用遞推求解（效率非常的高），相對具體、複雜
static int f2(int x, int y){
int[][]arr = new int[x][y];
//當隻有一行的情況
for(int i = 0; i < y; i++){
arr[0][i] = 1;
}
//當隻有一列的情況
for(int i = 0; i < x; i++){
arr[i][0] = 1;
}
//當多行多列的情況
for(int i = 1; i < x; i++){
for(int j = 1; j < y; j++){
arr[i][j] = arr[i-1][j]+arr[i][j-1];
}
}
return arr[x-1][y-1];
}
}
三、硬币表示
/*
題目描述：
假設我們有八種面值不同的硬币{1，2，5，10，20，50，100，200}，用這些硬币組合構成要給給定的數值n。
例如n = 200，那麼一種可能的組合方式為 200 = 3×1 + 1×2 + 1×5 + 2×20 + 1×50 + 1×100.
問總共有多少種可能的組合方式？（from projectEuler of website）
類似的題目有：
【華為面試題】1分，2分，5分的硬币有三種，組合為1角，共有多少種組合？
題解：1*x + 2*y + 5*z = 10（0<=x<=10, 0<=y<=5, 0<=z<=2）
【創新工廠筆試題】有1分，2分，5分，10分四種硬币，每種硬币數量無限，
給定n分錢，有多少組合可以組成n分錢？
*/
public class 硬币表示 {
public static void main(String[] args){
int[]values = {1, 5, 10, 25};
for(int i = 1; i < 101; i++){
int ways = count(i, values, 3);
System.out.println(i+"————"+ways);
}
}
//n：使用者給的硬币面值；coins：擁有的硬币面值；cur：可選範圍（0~3）
static int count(int n, int[]coins, int cur){
//如果硬币面值小于等于0，直接傳回一個0
if(n <= 0)return 0;
//如果可選範圍等于0，說明沒得選了，即隻能選一種了
if(cur == 0)return 1;
//res：存儲表示種數
int res = 0;
/*
1，不選；
2.選一個；
3，選兩個……
*/
//for循環的判斷條件 i*coins[cur]：當一種硬币面值*數量小于等于使用者給的面值
for(int i = 0; i*coins[cur] <= n; i++){
//shengyu：每循環一次剩餘的錢數
int shengyu = n - i*coins[cur];
//用res存儲每種面值硬币的表示種數
res += count(shengyu, coins, cur-1);
}
//遞歸完成後，傳回硬币的表示種數res
return res;
}
}
四、合法括号
/*
題目描述：
實作一種算法，列印n對括号的全部有效組合（即左右括号正确配對）
輸入：3
輸出：((())), (()()), (())(), ()(()), ()()()
*/
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class 合法括号 {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Set<String> res1 = f1(n);
System.out.println("遞歸法：\n"+res1);
Set<String> res2 = f2(n);
System.out.println("疊代法：\n"+res2);
}
//遞歸解法
static Set<String> f1(int n){
Set<String> set = new HashSet<String>();
if(n == 1){
set.add("()");
return set;
}
Set<String> temp = f1(n-1);
for(String str : temp){
set.add("()"+str);
set.add(str+"()");
set.add("("+str+")");
}
return set;
}
//疊代解法
static Set<String> f2(int n){
Set<String> set = new HashSet<String>();
set.add("()");
if(n == 1)return set;
for(int i = 2; i <= n; i++){
Set<String> temp = new HashSet<String>();
for(String str : set){
temp.add("()"+str);
temp.add(str+"()");
temp.add("("+str+")");
}
set = temp;
}
return set;
}
}
五、水窪數目
package com.算法基礎課_6深入遞歸;
/*
題目描述：
有一個大小為N×M的園子，雨後積起了水。八連通的積水被認為是連接配接在一起的。請求出園子裡總共右多少水窪？
（八連通指的是下圖中相對W的*的部分）
***
*W*
***
限制條件：N，M <= 100
輸入N=10，M=12
園子如下圖（W表示積水，.表示沒有積水）
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
輸出：
3
*/
import java.util.Scanner;
public class 水窪數目 {
static int N, M;
static char c[][];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//花式接收資料
N = sc.nextInt();
M = sc.nextInt();
c = new char[N][];
for(int i = 0; i < N; i++){
c[i] = sc.next().toCharArray();
}
//深搜處理資料
int cnt = 0;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
if(c[i][j] == 'W'){
dfs(i, j);//将這個水窪的所有的W變為.
cnt++;
}
}
}
//一般列印結果
System.out.println(cnt);
}
//深搜代碼實作
static void dfs(int x, int y){
c[x][y] = '.';
//判斷八個方向
for(int i = -1; i < 2; i++){//i: 0 -1 1
for(int j = -1; j < 2; j++){//j: 0 -1 1
//保證目前坐标的四個方向都在園子内部
if(x+i>=0 && x+i<=N-1 && y+j>=0 && y+j<=M-1){
if(c[x+i][y+j] == 'W'){
dfs(x+i,y+j);
}
}
}
}
}
}
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)