【演算法-Java實作】 換錢的方法數（暴力遞回法）
文章目錄
- 【演算法-Java實作】 換錢的方法數（暴力遞回法）
- 一.問題描述：
- 二.問題解答：
- **舉例：**
- **思路：==暴力遞回==**
- 三.演算法分析：
- **使用遞回時應該考慮1.如何設計遞回函式 2.遞回的終止條件**
- ==代碼如下==
一.問題描述：
給定一個整型陣列arr，arr中的值為正數且不重復，每個值代表一種面值的貨幣，每種貨幣可以使用任意張，
給定一個整數target，代表要換的錢數，求換錢的方法數，
二.問題解答：
該題有暴力遞回法、記憶搜索法、動態規劃法，本文介紹在解題時最容易想到的暴力遞回
暴力遞回在計算時會有大量的重復計算，但在筆試面試中暴力遞回是解題的思路，記憶搜索和動態規劃都是基于暴力遞回的優化手段，
舉例：
arr=[5,10,25,1]，target=0
組成0元的方法有1種，就是所有貨幣都不用，則回傳0；
arr=[5,10,25,1]，target=15
組成15元的方法有6種，分別是：3張5元，1張5元+1張10元，1張10元+5張1元，10張1元+1張5元，2張5元+5張1元，15張1元，所以回傳6，
思路：暴力遞回
arr=[5,10,25,1]，target=1000
**1.**用0張5元的貨幣，讓[10,25,1]組成剩下的1000，最終方法數記為res1，
**2.**用1張5元的貨幣，讓[10,25,1]組成剩下的995，最終方法數記為res2，
**3.**用2張5元的貨幣，讓[10,25,1]組成剩下的990，最終方法數記為res3，
…
**201.**用200張5元的貨幣，讓[10,25,1]組成剩下的0，最終方法數記為res201，
則res1+res2+res3+…+res201為最終總方法數，
三.演算法分析：
1.時間復雜度為O(N),遍歷陣列，最差情況下時間復雜度為O(target的N次方)
2.額外空間復雜度O(N),遞回堆疊的深度即為陣列長度，
3.遞回：遞回就是程式運行時自己呼叫自己，一個遞回程序就是出入堆疊的程序，
使用遞回時應該考慮1.如何設計遞回函式 2.遞回的終止條件
代碼如下
import java.util.Scanner;
/**
* @author hkd
*
* 問題：換錢的方法數
暴力遞回法
*
*/
public class ExchangeMoney {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.nextLine();
String[] str = s.split(",");
int target = in.nextInt();
int[] arr = new int[str.length];
for (int i = 0; i < arr.length; i++) {
arr[i] = Integer.parseInt(str[i]);
}
int result = getResult(arr, 0, target);
System.out.println(result);
}
public static int getResult(int[] arr, int index, int target) {
if (arr.length == 0 || arr == null || target < 0) {
return 0;
} else {
return process(arr, index, target);
}
}
//實作(暴力遞回)
public static int process(int[] arr, int index, int target) {
// res記錄結果數
int res = 0;
// 遞回終止條件，index是否已經到達陣列最后
// 此時當target為0時，表示此方法可行，res置1
if (index == arr.length) {
res = target == 0 ? 1 : 0;
} else {
for (int i = 0; arr[index] * i <= target; i++) {
res += process(arr, index + 1, target - arr[index] * i);
}
}
return res;
}
}
res += process(arr, index + 1, target - arr[index] * i);
}
}
return res;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/236577.html
標籤：java