假設我們有五個數字,N,A,B,C,D。我們從數字0開始,結束於N。我們可以透過一定數量的硬幣來改變一個數字,具體操作如下:
- 將數字乘以2,支付A個硬幣
- 將數字乘以3,支付B個硬幣
- 將數字乘以5,支付C個硬幣
- 增加或減少數字1,支付D個硬幣
我們可以任意次數以任意順序執行這些操作。我們需要找到達到N所需的最少硬幣數量
因此,如果輸入是N = 11; A = 1; B = 2; C = 2; D = 8,那麼輸出將是19,因為最初x為0。
用8個硬幣將x增加1(x=1)。
用1個硬幣將x乘以2(x=2)。
用2個硬幣將x乘以5(x=10)。
用8個硬幣增加1(x=11)。
步驟
為了解決這個問題,我們將按照以下步驟進行:
Define one map f for integer type key and value Define one map vis for integer type key and Boolean type value Define a function calc, this will take n if n is zero, then: return 0 if n is in vis, then: return f[n] vis[n] := 1 res := calc(n / 2) + n mod 2 * d + a if n mod 2 is non-zero, then: res := minimum of res and calc((n / 2 + 1) + (2 - n mod 2)) * d + a) res := minimum of res and calc(n / 3) + n mod 3 * d + b if n mod 3 is non-zero, then: res := minimum of res and calc((n / 3 + 1) + (3 - n mod 3)) * d + b) res := minimum of res and calc(n / 5) + n mod 5 * d + c if n mod 5 is non-zero, then: res := minimum of res and calc((n / 5 + 1) + (5 - n mod 5)) if (res - 1) / n + 1 > d, then: res := n * d return f[n] = res From the main method, set a, b, c and d, and call calc(n)
Example
讓我們來看下面的實作以更好地理解−
#include <bits/stdc++.h> using namespace std; int a, b, c, d; map<long, long> f; map<long, bool> vis; long calc(long n){ if (!n) return 0; if (vis.find(n) != vis.end()) return f[n]; vis[n] = 1; long res = calc(n / 2) + n % 2 * d + a; if (n % 2) res = min(res, calc(n / 2 + 1) + (2 - n % 2) * d + a); res = min(res, calc(n / 3) + n % 3 * d + b); if (n % 3) res = min(res, calc(n / 3 + 1) + (3 - n % 3) * d + b); res = min(res, calc(n / 5) + n % 5 * d + c); if (n % 5) res = min(res, calc(n / 5 + 1) + (5 - n % 5) * d + c); if ((res - 1) / n + 1 > d) res = n * d; return f[n] = res; } int solve(int N, int A, int B, int C, int D){ a = A; b = B; c = C; d = D; return calc(N); } int main(){ int N = 11; int A = 1; int B = 2; int C = 2; int D = 8; cout << solve(N, A, B, C, D) << endl; }
輸入
11, 1, 2, 2, 8
輸出
19
以上是C++程式:計算使用硬幣支付達到n所需的操作次數的詳細內容。更多資訊請關注PHP中文網其他相關文章!

C 在現代編程中依然重要,因其高效、靈活和強大的特性。 1)C 支持面向對象編程,適用於系統編程、遊戲開發和嵌入式系統。 2)多態性是C 的亮點,允許通過基類指針或引用調用派生類方法,增強代碼的靈活性和可擴展性。

C#和C 在性能上的差異主要體現在執行速度和資源管理上:1)C 在數值計算和字符串操作上通常表現更好,因為它更接近硬件,沒有垃圾回收等額外開銷;2)C#在多線程編程上更為簡潔,但性能略遜於C ;3)選擇哪種語言應根據項目需求和團隊技術棧決定。

1)c relevantduetoItsAverity and效率和效果臨界。 2)theLanguageIsconTinuellyUped,withc 20introducingFeaturesFeaturesLikeTuresLikeSlikeModeLeslikeMeSandIntIneStoImproutiMimproutimprouteverusabilityandperformance.3)

C 在現代世界中的應用廣泛且重要。 1)在遊戲開發中,C 因其高性能和多態性被廣泛使用,如UnrealEngine和Unity。 2)在金融交易系統中,C 的低延遲和高吞吐量使其成為首選,適用於高頻交易和實時數據分析。

C 中有四種常用的XML庫:TinyXML-2、PugiXML、Xerces-C 和RapidXML。 1.TinyXML-2適合資源有限的環境,輕量但功能有限。 2.PugiXML快速且支持XPath查詢,適用於復雜XML結構。 3.Xerces-C 功能強大,支持DOM和SAX解析,適用於復雜處理。 4.RapidXML專注於性能,解析速度極快,但不支持XPath查詢。

C 通過第三方庫(如TinyXML、Pugixml、Xerces-C )與XML交互。 1)使用庫解析XML文件,將其轉換為C 可處理的數據結構。 2)生成XML時,將C 數據結構轉換為XML格式。 3)在實際應用中,XML常用於配置文件和數據交換,提升開發效率。

C#和C 的主要區別在於語法、性能和應用場景。 1)C#語法更簡潔,支持垃圾回收,適用於.NET框架開發。 2)C 性能更高,需手動管理內存,常用於系統編程和遊戲開發。

C#和C 的歷史與演變各有特色,未來前景也不同。 1.C 由BjarneStroustrup在1983年發明,旨在將面向對象編程引入C語言,其演變歷程包括多次標準化,如C 11引入auto關鍵字和lambda表達式,C 20引入概念和協程,未來將專注於性能和系統級編程。 2.C#由微軟在2000年發布,結合C 和Java的優點,其演變注重簡潔性和生產力,如C#2.0引入泛型,C#5.0引入異步編程,未來將專注於開發者的生產力和雲計算。


熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

Video Face Swap
使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

熱工具

SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)

MinGW - Minimalist GNU for Windows
這個專案正在遷移到osdn.net/projects/mingw的過程中,你可以繼續在那裡關注我們。 MinGW:GNU編譯器集合(GCC)的本機Windows移植版本,可自由分發的導入函式庫和用於建置本機Windows應用程式的頭檔;包括對MSVC執行時間的擴展,以支援C99功能。 MinGW的所有軟體都可以在64位元Windows平台上運作。

PhpStorm Mac 版本
最新(2018.2.1 )專業的PHP整合開發工具

SublimeText3漢化版
中文版,非常好用

記事本++7.3.1
好用且免費的程式碼編輯器