处女座的砝码-数学推论

本文主要是介绍处女座的砝码-数学推论，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：https://ac.nowcoder.com/acm/contest/327/C
来源：牛客网

处女座的砝码

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

处女座热爱做物理实验，为了实验，处女座必须要精确的知道物品的质量。处女座准备自己设计一套砝码，每一个砝码都是正整数，这套砝码必须能够精确测量出n以内所有正整数的质量，处女座想要知道至少需要多少个砝码。你可以在天平的任意一边放置砝码。

输入描述:
 
一行，一个正整数n

1<=n<=101000

输出描述:
一个整数，表示最少的砝码数。
示例1

输入
20
输出
4
说明
你可以选择1，2，6，11
1=1
2=2
3=1+2
4=6-2
5=6-1
6=6
7=6+1
8=6+2
9=6+2+1
10=11-1
11=11
12=11+1
13=11+2
14=11+2+1
15=11+6-2
16=11+6-1
17=11+6
18=11+6+1
19=11+6+2
20=11+6+2+1

假设有K个砝码，然后可以称出不大于 $\frac{3^{k+1}-1}{2}$ 重量的所有重量

所以有满足 $3^{k+1}<2*n+1$ ,输出的是最后一个满足条件的k

也就是满足 $3^{k}<2*n+1$ ，的下一个k

C++如果没有大数模板的话，需要用Python 或者Java的大数进行操作

This is the code：

//java


import java.math.BigInteger;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner cin =new Scanner(System.in);String str=cin.next();BigInteger n=(new BigInteger(str));n=n.multiply(new BigInteger("2"));n=n.add(new BigInteger("1"));BigInteger thr=new BigInteger("3");int ans=1;while(true) {if(thr.pow(ans).compareTo(n)<0)++ans;elsebreak;}System.out.println(ans);cin.close();}}

这篇关于处女座的砝码-数学推论的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！