首页 > 代码库 > 1057: 有假币
1057: 有假币
1057: 有假币
时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte
总提交: 2844 测试通过:773
描述
居然有假币!!!
事情是这样的,现在猪肉涨了,但是农民的工资却不见涨啊,没钱怎么买猪肉啊。渊子这就去买猪肉,结果找来的零钱中有假币!!!可惜渊子一不小心把它混进了一堆真币里面去了。现在知道假币的重量比真币的质量要轻。给你一个天平,请用最快的时间把那个可恶的假币找出来。
输入
1≤n≤230,输入0结束程序。
输出
最少要称几次一定能把那个假币找出来。
样例输入
3
12
0
样例输出
1
3
提示
示例1中共有3枚硬币,所以任意取2个放天平上称量一下。
因为假币的重量比较轻。
- 如果天平不平衡,则较轻的那枚就是假币。
- 如果天平平衡,则说明这两枚硬币都是真的,而剩下那枚是假币。
考虑分3堆对该问题最优的特点
做法一:用到了 log 的用法
(int)( log (x) / log (3) )
#include <stdio.h> #include <math.h> int f(int x) { if(1 == x) return 0; else if(2 == x) return 1; else if(3 == x) return 1; else if(x == (pow(3, (int)( log (x) / log (3))))) return (log (x) / log (3)); else return (1 + (int)(log (x) / log (3))); }
做法2 就是让分3堆的数尽量平均
#include <stdio.h> int main() { int n; while(scanf("%d", &n), n != 0) { int count = 0; while(n != 0) { if(1 == n) break; else if(2 == n) { count += 1; break; } else if(3 == n) { count += 1; break; } else { switch(n % 3)//补充至3堆平均,既取原来分堆后最大的一堆 { case 0: n /= 3;break; case 1: n = (n + 2) / 3;break; case 2: n = (n + 1) / 3;break; } count++; } } printf("%d\n", count); } return 0; }
补充一个看到的函数
函数名: ceil
用 法: double ceil(double x);
功 能: 返回大于或者等于指定表达式的最小整数
头文件:math.h
中文名
ceil
用 法
double ceil
功 能
返回大于等于表达式的最小整数
头文件
math.h
对第一种解法的简化
#include<stdio.h> #include<math.h> int main() {
int n; while(scanf("%d",&n),n != 0) printf("%.0lf\n",ceil(log(n)/log(3.0)));//0.1f很重要 return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。