資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時裝研究
法律研究最少硬幣找零問題
給定一條硬幣列表 C(c1, c2, ……Cn) 和一個值 V。現在的問題是使用最少的硬幣數量來進行找零 V。
注意 − 假設有無限數量的硬幣 C
在這個問題中，我們將考慮一組不同的硬幣 C{1, 2, 5, 10}，每種型別的硬幣都有無限的數量。為了找零所需的價值，我們將嘗試使用最少數量的任何型別的硬幣。
例如，對於值 22 − 我們將選擇 {10, 10, 2}，最少 3 枚硬幣。
此演算法的時間複雜度 id O(V)，其中 V 是值。
輸入和輸出
Input: A value, say 47 Output: Enter value: 47 Coins are: 10, 10, 10, 10, 5, 2
演算法
findMinCoin(value)
輸入 − 找零的值
輸出 −硬幣集合。
Begin
coins set with value {1, 2, 5, 10}
for all coins i as higher value to lower value do
while value >= coins[i] do
value := value – coins[i]
add coins[i], in thecoin list
done
done
print all entries in the coin list.
End示例
#include<iostream>
#include<list>
#define COINS 4
using namespace std;
float coins[COINS] = {1, 2, 5, 10};
void findMinCoin(int cost) {
list<int> coinList;
for(int i = COINS-1; i>=0; i--) {
while(cost >= coins[i]) {
cost -= coins[i];
coinList.push_back(coins[i]); //add coin in the list
}
}
list<int>::iterator it;
for(it = coinList.begin(); it != coinList.end(); it++) {
cout << *it << ", ";
}
}
main() {
int val;
cout << "Enter value: ";
cin >> val;
cout << "Coins are: ";
findMinCoin(val);
cout << endl;
}輸出
Enter value: 47 Coins are: 10, 10, 10, 10, 5, 2
更新於: 15-6月-2020
1K+ 次瀏覽
廣告