一行,包含一个数N。
一行,包含一个数,表示最少收到的硬币数。
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; }
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]); } } }
#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; }
#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; }
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; }
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语言搞混 } }
#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)
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]); } } }