题目_数学问题
用天平称重时,我们希望用尽可能
少
的砝码组合称出尽可能多
的重量。
如果有无限个砝码,重量分别
是1,3,9,27,81,……等3的指数幂
,
神奇之处在于用它们可以称出任意整数重量(砝码允许放在左右两个盘中)。
本题目要求编程实现:对用户给定的重量,给出砝码组合方案。
用户输入:
5
程序输出:
9-3-1
用户输入:
19
程序输出:
27-9+1
要求程序输出的组合总是大数在前小数在后。
可以假设用户的输入的数字符合范围1~121。
分析
1, 3, 9, 27, 81,……
3^0,3^1,3^2,3^3,3^4,……
题目中描述 三的指数幂 提示并联想到用3进制
解决问题。
我们先假设为二进制:
二进制转换
: 每位(0\1)乘以2的0、1、2..次方
例如:5
其二进制是 101 >> 12^2+02^1+1*2^0=4+0+1
砝码一遍 放 4 1 即可
如果是 19 其二进制为(10011)(16+2+1)
| 16 | 8 | 4 | 2 | 1 |
| --- | --- | --- | --- | --- |
|1|0|0|1|1|
一边放 16 2 1 即可
那么换三进制来说
三进制类转换
每位(0\1\2)乘以3的0、1、2..次方
进制从右边开始算 27 9 3 1
19 就是 201
>> 23^2+13^0
5 就是 12
>> 1*3^1+2^3^0
但是 1代表要取一个重量为3的砝码,2代表要取两个重量为1的砝码,但是题目说明是 分别 所以不能重用
同时也说做砝码数最少 重量最大 且为左右砝码盘 可以相互抵消
再以5为例 我们放砝码 组合方式是(9 -3 -1)
所以 我们再把 5的三进制变一下
(1,2) +1 =(2,3)
因为三进制逢3进1 所以=(3,0) 我们再减一个1 = (2,-1) 但是2 还是没法表示2
(选两个不允许)
把其中的2转换 左盘和右盘 (1,-1,-1) 从两个放一个盘 到 更大的放到一个盘 减去小的
手算一下 结果还是一样是5 怎么理解2 的这一步呢 类比 2进制 左移 倍数扩大 然后 再减去一半
想明白了 就感觉很妙
手算想一下也就明白啦 或者看代码哈
再举例 7 =(2,1) 把2向前进一位 =(1,-1,1) 即 (9,-3,1)
所以 现在转换到了
代码
package BlueCup.Six_MathQuestion;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Case1_天平称重 {
//
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int N = cin.nextInt();
convert(N);//转特殊三进制
}
private static void convert(int N) {
//转换三进制
final String x = Integer.toString(N, 3);
//翻转 字符数组 到着算可能越界 所有翻转从左到右
char[] arr = new StringBuilder(x).reverse().toString().toCharArray();//翻转
//容器处理之后的 0 -1 1
List<Integer> list=new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
if(arr[i]=='2') {
list.add(0, -1);//-1 插到开头
if (i == arr.length - 1) {//到尽头
list.add(0, 1);//最后一个字符 插入1 因为是尽头 没进位了
} else {
++arr[i + 1];//否则下一位+1
}
}else if(arr[i]=='3'){
list.add(0,0);
//更高位进1
if(i==arr.length-1){
list.add(0,1);
}else{
++arr[i+1];
}
}else{
list.add(0,arr[i]-'0');//不是0、就是1
}
}
StringBuilder sb = new StringBuilder();//注意是逆序 进制
for (int i = 0; i < list.size(); i++) {
if (list.get(i) == 1) sb.append("+").append((int) Math.pow(3, list.size() - i - 1));
if (list.get(i) == -1) sb.append("-").append((int) Math.pow(3, list.size() - i - 1));
//0直接pass咯
}
//因为结果的第一位一定是 正的 所以我能把它符号丢掉
System.out.println(sb.substring(1));
}
}
感觉
这道题消化及整理 撸代码 共耗时1h30min qaq
理解 上的的障碍 就是 那个进制转换 顺便复习了一下 进制运算 哈哈不亏
看完之后思路就很清晰了。 然后 一个字 妙啊~~

参考文献
https://baike.baidu.com/item/%E4%B8%89%E8%BF%9B%E5%88%B6/6151952
[2]巧用进制:
https://blog.csdn.net/weixin_43336281/article/details/89305300
本文地址:https://dxoca.cn/Algorithm/178.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。