每日一题C++版(拼凑面额)

编程是很多偏计算机、人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”,通过每天一道编程题目来强化和锻炼自己的编程能力(最起码不会忘记编程)

特别说明:编程题来自“牛客网”和“领扣”以及热心小伙伴的题目。由于小白有时想锻炼某一类编程方法,所以提供的代码不一定是最优解,但是本文提供的编程代码均为通过测试代码。

拼凑面额

题目描述

给你六种面额1、5、10、20、50、100元的纸币,假设每种币值的数量都足够多,编写程序求组成N元(N为0-10000的非负整数)的不同组合的个数。

输入描述:

输入为一个数字N,即需要拼凑的面额

输出描述:

输出也是一个数字,为组成N的组合个数。

示例

输入

5

输出

2

解析

最喜欢和钱有关的题目,谁给小白十个亿,小白也能一个月把它花掉。本题其实就是给定一个整数和一个数组,查看有多少种相加的组合方式。我们可以换一种思考方式,比如我们有一张10元钱,其某种组成方式中有一张5元钱,见变成了:(10-5)元钱有多少种组合方式,这样一直循环下去,最后变成0元钱。

利用这种想法,我们可以使用递归的方法来求取结果。但是这里面有一个小小的注意事项,就是递归的循环中后面减去的纸币面值应该大于等于前一次循环的面值。为实现这个需求,需要将当前循环的纸币面值也传入下一次递归中。

代码

#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
 
 int count = 0;
 vector<int> money;
 Solution(){};
 Solution(vector<int> money_) :money(money_){}
 void kindofway(int sum, int i)
 {
   int index = money.size();
   for (; i < index; i++)
   {
     int last = sum - money[i];
     if (last==0)
     {
       count++;
       break;
     }
     else if (last>0)
     {
       kindofway(last, i);
     }
     else
     {
       break;
     }
   }
 }

private:

};

int main()
{
 int sum;
 vector<int> money = { 1, 5, 10, 20, 50, 100 };
 while (cin>>sum)
 {
   Solution solution(money);
   solution.kindofway(sum, 0);
   int count = solution.count;
   cout << count << endl;
 }
 return 0;
}

(0)

相关推荐

  • Python|奇/偶数倒数求和之循环与递归的奥秘

    前言今天我们来解决粉丝提出的一个问题,如图: 问题描述编写一个函数,输入n为偶数时,调用函数求1/2+1/4+...+1/n,当输入n为奇数时,调用函数1/1+1/3+...+1/n,输出结果示例:输 ...

  • C语言每日一练(002)

    题目 求数组元素之和 代码 首先,需要构造一个求和函数.这里求和函数有两种构造方法,一种是迭代法,另一个种是递归法. 迭代法求和函数 int sum(int a[], int n) { int i = ...

  • C++面向对象程序设计 笔记整理(1)——编程基础

    字符与字符串 大小写转换 void lower_or_upper_case(char c) { int transferred_c; if ( ('a'<=c) && (c< ...

  • 递归和非递归实现规律函数

    递归和非递归实现规律函数

  • 算法|1到100求和学算法之无尽的递归

    引言递归作为一种算法在程序设计语言中广泛应用,是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现像.绝大多数编程语言支持函数的自调用,在这些语言中函数可以通过调用自身来进行递归.计算 ...

  • leetcode_3.29

    leetcode_3.29

  • 【黑客数学·每日一题】暑假期间“每日一题”汇总版

    各位黑客伙伴们: 大家好!随着暑期的结束,我们迎来了崭新的学期,"每日一题"的发布时间也正式恢复为常规的每周一到周五的下午(一周五期). 有部分黑客伙伴们在暑假安排了各种各样精彩活 ...

  • 每日一题 C++版(走迷宫)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • 每日一题 C++版(汽水瓶)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • 每日一题 C++版(简单密码)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • 每日一题 C++版(分类有效的IP地址和掩码)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • 每日一题 C++版(坐标移动)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • 每日一题C++版(组成最大的数)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • 每日一题C++版(电话号码分身)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • 每日一题C++版(区间合并)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...