最新消息:点击查看大S的省钱秘笈

Vijos P1361 天平称量 C语言版

Vijos题解 Slyar 73浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

描述 Description

有n个球,从外表上看不出差别,但有一个球比其他球重,其他N-1个球质量相等。请问:在地球上(MS废话),用天平最少称几次可以称出来?

输入格式 Input Format

一个自然数N(0<N<=2^24)

输出格式 Output Format

输出用天平最小的称量数m(m<30000)

Tip:天平称量问题,证明我不会。。。

天平称重,有两个托盘比较轻重,加上托盘外面,也就是每次称重有3个结果,就是ln3/ln2比特信息。n个球要知道其中一个不同的球,如果知道那个不同重量的球是轻还是重,找出来的话那就是n个结果中的一种,就是有ln(n)/ln2比特信息,假设我们要称k次,根据信息理论:k*ln3/ln2>=ln(n)/ln2,解得k>=ln(n)/ln3

学会2个函数:

floor(x)返回的是小于或等于x的最大整数。

ceil(x)返回的是大于x的最小整数。

另外还有一点是:

ln(x) 在C中是log(x)

lg(x) 在C中是log10(x)

#include <stdio.h>
#include <math.h>

int main(){
long n,m;
scanf("%d",&n);
m=ceil(log(n)/log(3));
printf("%d",m);
system("pause");
return 0;
}

转载请注明:Slyar Home » Vijos P1361 天平称量 C语言版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址