首页 > 代码库 > 蓝桥杯——说好的进阶之砝码称重(贪心算法)
蓝桥杯——说好的进阶之砝码称重(贪心算法)
5个砝码
用天平称重时,我们希望用尽可能少的砝码组合称出尽可能多的重量。
如果只有5个砝码,重量分别是1,3,9,27,81。则它们可以组合称出1到121之间任意整数重量(砝码允许放在左右两个盘中)。
本题目要求编程实现:对用户给定的重量,给出砝码组合方案。
例如:
用户输入:
5
程序输出:
9-3-1
用户输入:
19
程序输出:
27-9+1
要求程序输出的组合总是大数在前小数在后。
用天平称重时,我们希望用尽可能少的砝码组合称出尽可能多的重量。
如果只有5个砝码,重量分别是1,3,9,27,81。则它们可以组合称出1到121之间任意整数重量(砝码允许放在左右两个盘中)。
本题目要求编程实现:对用户给定的重量,给出砝码组合方案。
例如:
用户输入:
5
程序输出:
9-3-1
用户输入:
19
程序输出:
27-9+1
要求程序输出的组合总是大数在前小数在后。
可以假设用户的输入的数字符合范围1~121。
public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner = new Scanner(System.in); cal(Integer.parseInt(scanner.nextLine())); } static void cal(int n) { int[] iarr = new int[] { 1, 3, 9, 27, 81 }; int[] tarr = new int[] { 1, 4, 13, 40, 121 }; int mark=0; //符号 int i; while (n > 0) { for (i = 0; i < tarr.length; i++) { if (n <= tarr[i]) { break; } } //想要什么,满足它即可 //满足 if(mark==0) { n -= iarr[i]; System.out.print(iarr[i]);//第一个肯定为+ 特殊处理 } if(mark==1){ n -= iarr[i]; System.out.print("+"+iarr[i]); } if(mark==-1) { n=-n+iarr[i]; System.out.print("-"+iarr[i]); } //想要 //得到一个数之后,想要+ mark=1; if(n>0) { mark=1; } else if(n<0) { //得到之后想要负数 n=-n;//大小取绝对值 mark=-1;//标记符号 想要- mark=-1; } } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。