一、问题描述
你有一架天平。现在你要设计一套砝码,使得利用这些砝码可以称出任意小于等于 N 的正整数重量。
那么这套砝码最少需要包含多少个砝码?
注意砝码可以放在天平两边。
输入包含一个正整数 N。
输出一个整数代表答案。
7
3
二、解析
用贪心的思想来解决这个问题:尽可能在增加砝码时使得砝码的重量最大。
要称重量为 1,需要砝码 1
重量为 2,增加砝码 3(使增加的砝码尽可能的大,所以不是 1 和 2 )
- 1 3 可以同时称 ‘1’=1,‘2’+1=3,‘3’=3,‘4’=3+1 ;
所以下一个是5,增加砝码 9(尽可能的大)
- 1 3 9 可以同时称(除去 1 和 3 能称的):
‘5’+3+1=9,‘6’+3=9,‘7’+3=9+1,‘8’+1=9,‘9’=9
‘10’=9+1,‘11’+1=9+3,‘12’=9+3,‘13’=1+3+9
下一个是14,增加砝码几呢?
- n - w
1 - 3
2 - 1 3
5 - 1 3 9
大胆推测一下(或者接着演算),下一个增加的砝码是 9*3=27
由上面演算可知增加的砝码每次乘以三,
可测量的数字为上一轮的 n+w;
三、代码
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
int n=1;
int w=1;
int ans=1;
while((n+w)<N) {
n+=w;
w*=3;
ans++;
}
System.out.println(ans);
}