首页 > 试题广场 >

找零

[编程题]找零
  • 热度指数：29354 时间限制：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%的数据，。
算法知识视频讲解
添加回答
自由的小白头像 自由的小白
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)
dragonlogin头像 dragonlogin 
#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)
201909011536359头像 201909011536359 
#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)
BestBlade头像 BestBlade 
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)
Java
石秀官头像 石秀官 
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/C++
0b100001101000头像 0b100001101000
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)
C/C++
macl1012头像 macl1012
动态规划：找零问题

#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)
Java
Nakangzi头像 Nakangzi
老老实实动态规划，要注意的是此处应该是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)
Java
只是而已头像 只是而已
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)
C/C++
持盾、の猫头像 持盾、の猫 
#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)
EnvyEvil头像 EnvyEvil 
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)
heimingsheng头像 heimingsheng
#简单的背包问题
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)
C/C++
nbgao头像 nbgao 
#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)
Java
咽喉上的刀头像 咽喉上的刀
Java解答： 
import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int n = 1024 - N;
        int n1 = n/64;
        int n2 = n%64/16;
        int n3 = n%64%16/4;
        int n4 = n%64%16%4/1;
        int sum = n1+n2+n3+n4;
        System.out.println(sum);
    }
}

编辑于 2019-08-02 19:34:38 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 模拟 算法工程师 测试工程师 PHP工程师 字节跳动 2019 数学 Java工程师
上传者：小小
难度：
146条回答 20383浏览

热门推荐

通过挑战的用户

查看代码

相关试题

找零

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号