首页 > 代码库 > 1057: 有假币

1057: 有假币

2024-07-01 21:06:03   226人阅读

 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　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;
}


联系
我们