首页 > 试题广场 >

找零

[编程题]找零
  • 热度指数:28872 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币,以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为的商品,请问最少他会收到多少硬币?

输入描述:
一行,包含一个数N。


输出描述:
一行,包含一个数,表示最少收到的硬币数。
示例1

输入

200

输出

17

说明

花200,需要找零824块,找12个64元硬币,3个16元硬币,2个4元硬币即可。

备注:
对于100%的数据,
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//方法一,贪心,必然可以找清楚,从最大的开始找
int RecvNum(int num)
{
    int sum=0;//要找回的硬币数量
    int amount=64;
    for(int i=0;i<4;i++)//四种硬币
    {
        sum+=num/amount;//有多少个64元
        num%=amount;//找完64的硬币之后剩下的钱
        amount>>=2;//换下一个面值
    }
    return sum;
}

//方法二 使用动态规划 
//dp[i]:找i元钱最少需要多少硬币
//base: dp[0]=0;dp[1]=1
//状态转移方程:dp[i]=min(dp[i],dp[i-amount]+1);

//类比
//背包问题:装最少的东西将容量为1024-N的背包装满,每次可以装1/4/16/64
//爬楼梯问题:爬最少的次数爬完1024-N层楼梯,每次可以爬1/4/16/64层
int RecvNum_dp(int num)
{
    vector<int> dp(num+1,num+1);//都赋上最大值
    int amount[4]{1,4,16,64};
    //base
    dp[0]=0;dp[1]=1;
    for(int i=2;i<=num;i++)
    {
        for(int j=0;j<4;j++)
        {
            if(i>=amount[j])
                dp[i]=min(dp[i],dp[i-amount[j]]+1);
        }
    }
    return dp[num];
}



int main()
{
    int N;//花的钱
    cin>>N;
    cout<<RecvNum_dp(1024-N)<<endl;    
    return 0;
}
编辑于 2020-05-16 12:23:50 回复(5)
JAVA动态规划实现
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 输入
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()){
            // 计算需要组成多少钱
            int num = 1024 - scan.nextInt();
            // dp[i] 状态定义为找i元钱,需要的最少张数,从 0 - num 总共 num + 1种
            int[] dp = new int[num + 1];
            // 初始化dp数组,因为要找最小值,这里给每个位置赋最大值,即都是由1元组成的,即num/1
            for (int i = 0; i < dp.length; i++) {
                dp[i] = i;
            }
            // 定义钱的集合,方便遍历
            int[] money = {1, 4, 16, 64};

            // 状态转移方程 从 1 ~ num
            for (int i = 1; i <= num ; i++) {
                // dp[num]的最小值就是能组成它的前一步 + 1 和 本身进行比较
                for (int j = 0; j < money.length; j++) {
                    if (i - money[j] >= 0){
                        dp[i] = Math.min(dp[i - money[j]] + 1, dp[i]);
                    }
                }
            }

            System.out.println(dp[num]);
        }
    }
}


发表于 2019-09-16 09:17:18 回复(0)
#include <bits/stdc++.h>
using namespace std;
// 因为有面值 1 元, 所以可以用贪心
#define N 1024
int main() {
    int n;
    while (cin >> n) {
        n = N - n;
        int ans = 0;
        int p = 64;
        while (n != 0) {
            ans += n / p;
            n %= p;
            p >>= 2;
        }
        cout << ans <<endl;
    }
    return 0;
}

发表于 2019-10-17 12:51:26 回复(2)
这可能是这篇帖子下面最傻瓜的解法没有之一……🤣🤣🤣🤣🤣
N=int(input())
n=1024-N
a1,b1=n//64,n%64
a2,b2=b1//16,b1%16
a3,b3=b2//4,b2%4
print(a1+a2+a3+b3)


发表于 2019-08-08 11:24:23 回复(8)
#include <stdio.h>
int main(){
    int N,b=64,num=0;
	scanf("%d",&N);
	N=1024-N;
	while(N>0){
		num+=N/b;
		N%=b;
		b/=4;
	}
	printf("%d\n",num);
    return 0;
}

发表于 2019-10-02 15:17:02 回复(0)
int N;
int coins[] = { 64,16,4,1 };

int minCoins(int n) {
    int res = 0;
    int i = 0;
    while (n) {
        if (n >= coins[i]) {
            res += n / coins[i];
            n %= coins[i++];
        }
        else {
            i++;
        }
    }
    return res;
}

int main(){
    cin >> N;
    N = 1024 - N;
    cout << minCoins(N) << endl;
    return 0;
}

发表于 2021-03-24 18:32:21 回复(0)
import java.util.Scanner; //java.util为包名,Scanner为类名

public class Main
{
	public static void main(String[] args) // 切莫少了传入参数
	{
		Scanner input = new Scanner( System.in ); //使用前先导入Scanner类
        int N = input.nextInt(); //next() 为方法
        input.close();
        int Z = 1024-N;
        int n64 = Z/64;
        int S = Z-64*n64; // *不能少,和数学里的带分数的单项式不同
        int n16 = S/16;
        S = S-16*n16; //切莫重复定义,应用之前剩下的来减
        int n4 = S/4;
        S = S-4*n4;
        int NS = n64+n16+n4+S;
        System.out.println( NS ); //输出语句切莫和C语言搞混
	}
}

发表于 2020-12-29 20:15:06 回复(0)
def solution(N):
    x = 1024 - N
    s = 0
    for _ in range(3):
        s += x & 3
        x = x >> 2
        if not x:
            break
    s += x
    return s

N = int(input())
print(solution(N))

发表于 2020-07-31 17:06:36 回复(0)
C:
#include <stdio.h>
int main(){
    int input, r, a, b, c;
    scanf("%d", &input);
    r = 1024 - input;
    a = r / 64;
    r = r % 64;
    b = r / 16;
    r = r % 16;
    c = r / 4;
    r = r % 4;
    printf("%d", a+b+c+r);
}
Python:
r = 1024-int(input())
a,r = divmod(r, 64)
b,r = divmod(r, 16)
c,r = divmod(r, 4)
print(a+b+c+r)





发表于 2020-04-06 21:28:17 回复(0)
a = 1024 - int(input())
m,p = [64,16,4,1],0
for i in m:
    a,p = a % i,p + a // i
print(p)

发表于 2020-03-19 17:14:19 回复(0)
动态规划:找零问题

#include <iostream>
#
include <vector>
using namespace std;

// 找零
int change(vector<int>& coins, int n) {
    vector<int> dp(n+1, n+1);
    // base case
    dp[0] = 0;
    dp[1] = 1;
    for(int i=1; i<=n; i++) {
        for(int coin : coins) {
            if(i-coin < 0) continue;
            dp[i] = min(dp[i], 1 + dp[i-coin]);
        }
    }
    return dp[n];
}

int main() {
    vector<int> coins = {64, 16, 4, 1};
    int N = 0;
    cin >> N;
    int res = change(coins, 1024-N);
    cout << res << endl;
    
    return 0;
}
发表于 2020-03-13 17:31:26 回复(0)
老老实实动态规划,要注意的是此处应该是1024减去商品价格才是要找的钱的总额
import java.util.*;
public class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = 1024-sc.nextInt();
            int[]coins={1,4,16,64};
            int max=n+1;
            int[]dp=new int[max+1];
            Arrays.fill(dp,max);
            dp[0]=0;
            for(int i=1;i<=n;i++){
                for(int coin:coins){
                    if(i>=coin)dp[i]=Math.min(dp[i],dp[i-coin]+1);
                }
            }
            System.out.println(dp[n]);
        }
    }
}

发表于 2020-03-07 17:20:00 回复(1)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc =new Scanner(System.in);
int n =1024-sc.nextInt();
int sum =0;
int count =64;
while (count>=1){
if (n%count==0){
sum+=n/count;
break;
}else {
sum+=n/count;
n=n%count;
count=count/4;
}
}
System.out.println(sum);

}

}

编辑于 2019-09-20 01:13:23 回复(0)
#include <iostream>
using namespace std;

int main() {
    int n; cin >> n; n = 1024 - n;
    int conis[4] = {1, 4, 16, 64};
    int ans = 0;
    for (int i=3; i>=0; i--) {
        ans += (n / conis[i]);
        n %= conis[i];
    }
    cout << ans << endl;
    return 0;
}

发表于 2019-09-12 21:23:49 回复(0)
#include <stdio.h>

int main()
{
    int N, n;
    scanf("%d", &N);
    N = 1024 - N;
    n = N/64 + N%64/16 + N%16/4 + N%4;
    printf("%d", n);
    return 0;
}

编辑于 2019-09-11 16:04:40 回复(0)
remaining_money = 1024 - int(input())
res = 0
for coin_unit in [64, 16, 4, 1]:  # 迭代对应 64 16 4 1
    res += remaining_money // coin_unit  # 累加由商代表的硬币枚数
    remaining_money %= coin_unit  # 将剩余的钱更新为余
print(res)


编辑于 2019-09-09 17:27:05 回复(0)
money  = 1024 - int(input())
output = 0
for i in [64,16,4,1]:
    output+=int(money/i)
    money = money%i
print(output)
😕
发表于 2019-09-05 13:47:58 回复(0)
#include <iostream>
using namespace std;
int main() {
    int N;
    cin >> N;
    int res = 0;
    N = 1024 - N;
    for (int i = 0; i < 3 && N > 0; ++i) {
        res += N % 4;
        N = N / 4;
    }
    cout << res + N << endl;
    return 0;
}

发表于 2019-08-24 14:00:55 回复(0)
#简单的背包问题
array = [1,4,16,64]
n = int(input())
m = 1024 - n
#要用array中的硬币找出m元的钱
dp = [100000 for i in range(m+1)]
dp[0] = 0
for i in range(m+1):
    for j in range(len(array)):
        if i - array[j] >= 0:
            dp[i] = min(dp[i],dp[i-array[j]] + 1)
print(dp[m])

发表于 2019-08-11 11:53:06 回复(0)
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N,s,cnt=0,a[4] = {64,16,4,1};
    cin>>N;
    s = 1024 - N;
    for(int i=0;i<4;i++){
        cnt += s/a[i];
        s %= a[i];
    }
    cout<<cnt<<endl;
    return 0;
}

发表于 2019-08-02 22:34:39 回复(0)