搜尋
首頁後端開發C++C++程式:計算使用硬幣支付達到n所需的操作次數

C++程式:計算使用硬幣支付達到n所需的操作次數

假設我們有五個數字,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中文網其他相關文章!

陳述
本文轉載於:tutorialspoint。如有侵權,請聯絡admin@php.cn刪除
MySQL中如何使用SUM函数计算某个字段的总和MySQL中如何使用SUM函数计算某个字段的总和Jul 13, 2023 pm 10:12 PM

MySQL中如何使用SUM函数计算某个字段的总和在MySQL数据库中,SUM函数是一个非常有用的聚合函数,它可以用于计算某个字段的总和。本文将介绍如何在MySQL中使用SUM函数,并提供一些代码示例来帮助读者深入理解。首先,让我们看一个简单的示例。假设我们有一个名为"orders"的表,其中包含了顾客的订单信息。表结构如下:CREATETABLEorde

新研究揭示量子蒙特卡洛超越神经网络在突破限制方面的潜力,Nature子刊详述最新进展新研究揭示量子蒙特卡洛超越神经网络在突破限制方面的潜力,Nature子刊详述最新进展Apr 24, 2023 pm 09:16 PM

时隔四个月,ByteDanceResearch与北京大学物理学院陈基课题组又一合作工作登上国际顶级刊物NatureCommunications:论文《TowardsthegroundstateofmoleculesviadiffusionMonteCarloonneuralnetworks》将神经网络与扩散蒙特卡洛方法结合,大幅提升神经网络方法在量子化学相关任务上的计算精度、效率以及体系规模,成为最新SOTA。论文链接:​​https://www.nature.com

Nature刊登量子计算重大进展:有史以来第一个量子集成电路实现Nature刊登量子计算重大进展:有史以来第一个量子集成电路实现Apr 08, 2023 pm 09:01 PM

6 月 23 日,澳大利亚量子计算公司 SQC(Silicon Quantum Computing)宣布推出世界上第一个量子集成电路。这是一个包含经典计算机芯片上所有基本组件的电路,但体量是在量子尺度上。SQC 团队使用这种量子处理器准确地模拟了一个有机聚乙炔分子的量子态——最终证明了新量子系统建模技术的有效性。「这是一个重大突破,」SQC 创始人 Michelle Simmons 说道。由于原子之间可能存在大量相互作用,如今的经典计算机甚至难以模拟相对较小的分子。SQC 原子级电路技术的开发将

计算矩阵右对角线元素之和的Python程序计算矩阵右对角线元素之和的Python程序Aug 19, 2023 am 11:29 AM

一种受欢迎的通用编程语言是Python。它被应用于各种行业,包括桌面应用程序、网页开发和机器学习。幸运的是,Python具有简单易懂的语法,适合初学者使用。在本文中,我们将使用Python来计算矩阵的右对角线之和。什么是矩阵?在数学中,我们使用一个矩形排列或矩阵,用于描述一个数学对象或其属性,它是一个包含数字、符号或表达式的矩形数组或表格,这些数字、符号或表达式按行和列排列。例如−234512367574因此,这是一个有3行4列的矩阵,表示为3*4矩阵。现在,矩阵中有两条对角线,即主对角线和次对

Michael Bronstein从代数拓扑学取经,提出了一种新的图神经网络计算结构!Michael Bronstein从代数拓扑学取经,提出了一种新的图神经网络计算结构!Apr 09, 2023 pm 10:11 PM

本文由Cristian Bodnar 和Fabrizio Frasca 合著,以 C. Bodnar 、F. Frasca 等人发表于2021 ICML《Weisfeiler and Lehman Go Topological: 信息传递简单网络》和2021 NeurIPS 《Weisfeiler and Lehman Go Cellular: CW 网络》论文为参考。本文仅是通过微分几何学和代数拓扑学的视角讨论图神经网络系列的部分内容。从计算机网络到大型强子对撞机中的粒子相互作用,图可以用来模

使用Python的abs()函数计算数值的绝对值使用Python的abs()函数计算数值的绝对值Aug 22, 2023 pm 12:07 PM

使用Python的abs()函数计算数值的绝对值绝对值是一个数与零点的距离,无论这个数是正数还是负数,其绝对值都是非负数。在Python中,我们可以使用内置函数abs()来计算一个数的绝对值。本文将详细介绍abs()函数的使用方法,并给出一些代码示例。abs()函数的语法如下:abs(x)其中,x是需要计算绝对值的数值。下面是一些使用abs()函数的示例:示

清华大学类脑芯片天机芯X登Science子刊封面,机器人版猫捉老鼠上演清华大学类脑芯片天机芯X登Science子刊封面,机器人版猫捉老鼠上演Apr 14, 2023 pm 05:01 PM

​清华大学举办的一场机器人版猫捉老鼠游戏,登上了Science子刊封面。这里的汤姆猫有了新的名字:“天机猫”,它搭载了清华大学类脑芯片的最新研究成果——一款名为TianjicX的28nm神经形态计算芯片。它的任务是抓住一只随机奔跑的电子老鼠:在复杂的动态环境下,各种障碍被随机地、动态地放置在不同的位置,“天机猫”需要通过视觉识别、声音跟踪或两者结合的方式来追踪老鼠,然后在不与障碍物碰撞的情况下向老鼠移动,最终追上它。在此过程中,“天机猫”需要实现实时场景下的语音识别、声源定位、目标检测、避障和决

面向长代码序列的 Transformer 模型优化方法,提升长代码场景性能面向长代码序列的 Transformer 模型优化方法,提升长代码场景性能Apr 29, 2023 am 08:34 AM

阿里云机器学习平台PAI与华东师范大学高明教授团队合作在SIGIR2022上发表了结构感知的稀疏注意力Transformer模型SASA,这是面向长代码序列的Transformer模型优化方法,致力于提升长代码场景下的效果和性能。由于self-attention模块的复杂度随序列长度呈次方增长,多数编程预训练语言模型(Programming-basedPretrainedLanguageModels,PPLM)采用序列截断的方式处理代码序列。SASA方法将self-attention的计算稀疏化

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

AI Hentai Generator

AI Hentai Generator

免費產生 AI 無盡。

熱門文章

R.E.P.O.能量晶體解釋及其做什麼(黃色晶體)
2 週前By尊渡假赌尊渡假赌尊渡假赌
倉庫:如何復興隊友
4 週前By尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒險:如何獲得巨型種子
4 週前By尊渡假赌尊渡假赌尊渡假赌

熱工具

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SecLists

SecLists

SecLists是最終安全測試人員的伙伴。它是一個包含各種類型清單的集合,這些清單在安全評估過程中經常使用,而且都在一個地方。 SecLists透過方便地提供安全測試人員可能需要的所有列表,幫助提高安全測試的效率和生產力。清單類型包括使用者名稱、密碼、URL、模糊測試有效載荷、敏感資料模式、Web shell等等。測試人員只需將此儲存庫拉到新的測試機上,他就可以存取所需的每種類型的清單。

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser是一個安全的瀏覽器環境,安全地進行線上考試。該軟體將任何電腦變成一個安全的工作站。它控制對任何實用工具的訪問,並防止學生使用未經授權的資源。

EditPlus 中文破解版

EditPlus 中文破解版

體積小,語法高亮,不支援程式碼提示功能

mPDF

mPDF

mPDF是一個PHP庫,可以從UTF-8編碼的HTML產生PDF檔案。原作者Ian Back編寫mPDF以從他的網站上「即時」輸出PDF文件,並處理不同的語言。與原始腳本如HTML2FPDF相比,它的速度較慢,並且在使用Unicode字體時產生的檔案較大,但支援CSS樣式等,並進行了大量增強。支援幾乎所有語言,包括RTL(阿拉伯語和希伯來語)和CJK(中日韓)。支援嵌套的區塊級元素(如P、DIV),