`
mabaoshan
  • 浏览: 6823 次
  • 性别: Icon_minigender_1
  • 来自: 北京
最近访客 更多访客>>
社区版块
存档分类
最新评论

【原创】关于最少硬币数问题的思索

阅读更多

  

  今天去参加一个面试,其中有道笔试题是关于最少硬数币问题的,其实是个很简单的问题,思路无非就是优先选择大面值硬币构成目标金额,使用略小面值处理零头。弄两个长度相等的数组,一个由大到小依次存储硬币面值,一个初始值全部为零。遍历硬币数组,取面值尝试构成目标金额,用目标金额减去已构成金额后,继续迭代。

  问题就是:我们在日常的开发工作中经常会拿到一个任务后简单思索后就拿机器开始写代码,实现逻辑的正确性,严谨性都由程序运行结果来验证。当手头没有机器或者不让使用机器的时候,居然不知道怎么去梳理逻辑了,或者说大脑根本就在告诉你,这个上机器上跑一下就行了。

  我的答案:在处理简单逻辑的时候,用脑子想一下程序逻辑,直接上机写代码;复杂的逻辑,借助下图画梳理思路,然后再写代码。梳理逻辑思路的时候,记录下关键点,这类关键点通常是条件语句,如if的条件,循环的条件,迭代停止的条件等。

  下面把代码贴在下边,欢迎大家给出不同实现。

  

	public static void main(String[] args) {
		int[] data={100,50,20,10,5,1};//人民币面值,纸币
		int[] count={0,0,0,0,0,0};
		int goal=550;//目标计算金额
		//==========计算各面值的数量========================================
		for(int i=0;i<data.length;i++){
			if(i!=0){
				goal=goal-data[i-1]*count[i-1];//计算上一面值的零头
			}
			for(int j=0;data[i]*j<=goal;j++){
				count[i]=j;
			}
		}
		//==========输出面值及对应数量========================================
		for(int i:data){
			System.out.print(i+"\t");
		}
		System.out.println();
		for(int i:count){
			System.out.print(i+"\t");
		}
	}

   原文地址

 

分享到:
评论

相关推荐

    最少硬币问题 王晓东版

    对于任意钱数,设计一个用最少硬币找钱的方法 数据输入:由文件input.txt提供输入数据,文件的第一行中只有一个整数给出n的值,第二行起每行2个数,分别是T[j]和cion[j].最后一行是要找的钱数m。 解题思路:可以...

    算法分析与设计 最少硬币问题

    在这个问题中,状态可以表示为d[i],代表找零i元时所需的最少硬币数。初始状态d[0]为0,因为不需要任何硬币找零0元。 接下来,我们可以使用动态规划的思想来构建解决方案。动态规划的核心是将大问题分解为小问题,...

    动态规划-最少硬币问题

    ### 动态规划——最少硬币问题解析 #### 一、背景介绍 在计算机科学领域,动态规划(Dynamic Programming)是一种高效求解多阶段决策问题的方法。它通过将原问题分解为相互重叠的子问题,并自底向上或自顶向下地...

    最少零钱问题,最少硬币问题

    最少零钱问题,最少硬币问题,动态规划算法,找零钱问题,

    最少硬币问题

    最少硬币问题,运行通过。问题描述: 设有n 种不同面值的硬币,各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins[1:n]中。对任意钱数0≤m≤20001,设计一...

    动态规划解最少硬币问题

    ### 动态规划解决最少硬币问题 #### 知识点概述 - **最少硬币问题**:给定一组面额不同的硬币以及一个总金额,目标是使用最少数量的硬币来凑出该总金额。 - **动态规划**:一种解决多阶段决策过程最优化问题的方法...

    贪心算法——最少硬币找钱

    ### 贪心算法在最少硬币找零问题中的应用 #### 一、问题背景及定义 在实际生活中,我们经常遇到需要找零的情况。如何用最少数量的硬币完成找零?这个问题不仅关乎日常生活中的便利性,也是计算机科学领域内一个...

    最少硬币问题 动态规划法

    设计算法求解最少硬币问题,并编程实现,超市找零钱时,找钱数最少的方法

    最少硬币问题动态规划

    算法分析 关于动态规划的最少硬币问题的代码,

    算法设计与分析-最少硬币问题

    ### 算法设计与分析:最少硬币问题解析 #### 问题背景 在实际生活中,我们经常需要解决“找零”问题,即如何用最少数量的硬币组合成一个特定金额的问题。这类问题通常可以通过动态规划算法进行高效求解。本篇文章...

    用贪心算法实现购物找零(支付+找零使用最少硬币数)

    这个方案用的硬币个数最少。 您的任务:对于给定的各种面值的硬币个数和付款金额,计算使用硬币个数最少的交易方案。 输入 有若干行测试数据。每一行有6个整数a5、a4、a3、a2、a1、a0和1个有2位小数的实数money,...

    算法最少硬币问题题目

    【最少硬币问题】是一种经典的动态规划问题,它在计算机科学和算法分析中具有重要的地位。此问题的主要目标是找出用最少数量的硬币来组成指定的金额,这些硬币有多种不同的面值。在给出的题目中,我们被提供了硬币的...

    C语言贪心算法求解最少硬币问题源程序.zip

    贪心算法求解最少硬币问题C语言程序,问题描述:给顾客找零钱时,收银处有1元,5角和1角硬币若干,如何用最少数量的硬币找够零钱? 算法思想:比如要找给顾客2元9角钱,首先计算1元最多可以有多少枚,即2枚,减去2元,还...

    最少硬币找零算法

    本算法通过动态规划的方式解决最少硬币找零问题,不仅确保了算法的时间效率,还提供了最优解。 #### 问题描述 假设我们有 _n_ 种不同面值的硬币,每种硬币的面值分别存储在数组 _T_[1:_n_] 中。现在我们需要使用...

    最少硬币问题.note

    最少硬币问题.note

    最少硬币问题 动态规划

    最少硬币问题 动态规划动态规划动态规划动态规划动态规划v

    贪心算法硬币问题_硬币问题_贪心算法硬币_

    这个问题通常描述为:给定不同面额的硬币,如1元、5元、10元等,目标是用最少的硬币数量凑出指定的总金额。我们可以从以下几个方面详细探讨这个问题: 1. **问题定义**:硬币问题的核心在于寻找最小硬币组合来达成...

    硬币兑换问题的动态规划求解算法

    硬币兑换问题是指:给定一些面值不同的硬币,如何使用这些硬币来兑换某个金额的钱,而使得所需硬币的数量最少。这个问题是一个经典的动态规划问题。 在解决这个问题时,我们可以使用动态规划的思想来求解。在动态...

    最少硬币算法

    如果使用了这种面值的硬币,那么问题转化为凑足金额`j`所需的最少硬币数加上1(即使用了一枚这种面值的硬币)。如果这种方法得到的硬币数比已有的少,则更新状态数组`c[j+T[i]]`的值。 #### 三、算法设计与实现 ...

Global site tag (gtag.js) - Google Analytics