首页 > 试题广场 >

有假币

[编程题]有假币

热度指数：6411 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

居然有假币！现在猪肉涨了，但是农民的工资却不见涨啊，没钱怎么买猪肉啊。nowcoder这就去买猪肉，结果找来的零钱中有假币！！！可惜nowcoder 一不小心把它混进了一堆真币里面去了。只知道假币的重量比真币的质量要轻，给你一个天平（天平两端能容纳无限个硬币），请用最快的时间把那个可恶的假币找出来。

输入描述:

1≤n≤2^30,输入0结束程序。

输出描述:

最多要称几次一定能把那个假币找出来？

示例1

输入

3
12
0

输出

1
3

算法知识视频讲解

推荐

orgcheng

先枚举一些例子，找出其中规律：
对于 1个硬币，称量 0次
对于 2个硬币，称量 1次
对于 3个硬币，称量 1次

对于 4个硬币，称量 2次，先分成（2，2，0），第一次称量前两份（2，2），如果重量不一样，再次求出判断另外2个硬币需要称量的次数。

对于 5个硬币，称量 2次，先分成（2，2，1），第一次称量前两份（2，2），如果重量不一样，再次判断另外1个硬币需要称量的次数。

对于 6个硬币，称量 2次，先分成（2，2，2），第一次称量前两份（2，2），如果重量不一样，再次判断求出另外2个硬币需要称量的次数。

对于 7个硬币，称量 2次，先分成（3，3，1），第一次称量前两份（3，3），如果重量不一样，再次判断求出另外3个硬币需要称量的次数。

通过上面分析可以看出，对于要称量的硬币，每次称量前分成3份，要求前两份的个数不小于第三份。如果前两份重量是一样，那么假币在第三份中，这样就除去了2/3的硬币。
如果前两份重量不一样，那么假币在重量轻的一份中，这样也除去了2/3的硬币。

这样以来，称量一次除去了将近2/3的硬币，一直重复上面的分法，就可以很快求出称量次数。

import java.io.PrintStream;
import java.util.Scanner;

public class Main {
	public static Scanner in = new Scanner(System.in);
	public static PrintStream out = System.out;

	public static int findCoin(int n){
		if(n==1)
			return 0;
		if(n<=3)
			return 1;
		int metage,rest,times=0;
		// 3等分前，先加2，使得metage的值尽量大于rest
		// (metage,metage,rest)
		metage = (n+2)/3;
		rest = n-2*metage;

		times= 1 + findCoin(Math.max(metage, rest));
		return times;
	}
	public static void main(String[] args) {
		int n;
		while((n=in.nextInt()) > 0){
			out.println(findCoin(n));
		}
	}
}

编辑于 2015-08-18 23:46:50 回复(9)

ahac

#include <stdio.h>

int main()
{
    int n;
    while(scanf("%d",&n)&&n){
        if(n==1)
            printf("0\n");
        else if(n==2||n==3){
            printf("%d\n",1);
        }else{
            int j=1;
            while(n>3){
                if(n%3==0)
                    n/=3;
                else
                    n=n/3+1;
                j++;
            }
            printf("%d\n",j);
        }
    }
    return 0;
}

发表于 2015-12-20 11:48:09 回复(0)

C/C++

MarvelSuperMiracle

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


int main()
{
	unsigned n;
	while (~scanf("%u", &n)) {
        if (n==0) break;
		int result = (int)ceil(log(n) / log(3));//ceil是进一法取整
		printf("%d\n", result);
	}
	return 0;
}

发表于 2017-02-04 15:16:41 回复(1)

Java

MakeTutuGreatAgain

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            int n = sc.nextInt();
            if(n == 0) break;
            int count = 0;
            while (n >= 2){
                //Math.ceil向上取整,但是是double类型
                n = (int)Math.ceil((double)n/3);
                count++;
            }
            System.out.println(count);
        }
    }
}

发表于 2022-07-11 21:22:41 回复(0)

皮卡丘乒乓

//数学题太恶心了
#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int n;
    while(cin>>n)
    {
        if(n==0)
            break;
        int count = 0;
        int i=0;
        while(1)
        {
            if(pow(3,i)<n)
            {
                count++;
                i++;
            }
            else
            {
                break;
            }
            
        }
        cout<<count<<endl;
    }
    return 0;
}

编辑于 2021-08-05 22:18:13 回复(0)

C/C++

WZ_Dale

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int n;
    while(cin >> n){
        if(n == 0){
            continue;
        }
        int count = 0;
        while(n >= 2){
            ++count;
            if(n % 3){
                //不可以整除则取最差情况：特别的一份是 n/3 + 1个金币
                n = n / 3 + 1;
            }
            else{
                //可以整除在直接整除，能够获取到一份
                n /= 3;
            }
        }
        cout << count << endl;
    }
    return 0;
}

发表于 2020-07-16 21:03:07 回复(0)

SupritYoung

https://blog.csdn.net/a1097304791/article/details/84261191

详细题解

发表于 2018-11-19 22:14:35 回复(0)

SKT.RUO

#include<stdio.h>
int main() 
{
	int n;
	while (scanf("%d", &n),n) 
	{
		int count = 0;
		while (n>1)
		{
			n = n / 3 + 1 - (n % 3 ^ 3) / 3;
			count++;
		}
		printf("%d\n", count);
	}
	return 0;
}

发表于 2017-08-04 17:20:25 回复(2)

hestyle

$\color{blue}解题思路：$
一看到这道题，我首先想到的是一个猜数游戏，就是随机生成[1,1000]之间的一个数，你每次报错一个猜想值，只告诉你你猜的数是比随机数大还是小，每次根据反馈调整猜的数值，直到猜中为止。玩过的都知道，折半查找是最快的，比如将[1,1000]分为[1,500]、[500,1000]，第一次猜500，如果大了就猜250，否则猜750。这样按照折半的规则猜，最多需要 log2n向上取整次。

对于这道题，我已开始的思路也是折半查找，把n分成两堆，如果n不是偶数，就分成(n - 1) / 2。但这种思路并不是最优的，无法通过所有测试。
我们首先来看前面几个示例：

当n = 1时，不需要再称了，它就是假币，总共需要0次
当n = 2时，1、1放天平两端，轻的就是假币，总共需要1次
当n = 3时，随机抽出2个放到天平两端，如果天平平衡，则剩下1个就是假币，
    否则天平中较轻的是假币，总共需要1次
当n = 4时，分成1、1、2，天平秤1、1，注意题目要求最短时间，
    并且是次数最大的情况，也就是我们需要考虑最坏的情况，第一次1、1重量相等，
    接着我们把2分开称，总共需要2次
当n = 5时，分成2、2、1，天平秤2、2，同样考虑最坏的情况，2、2重量相等，
    接着我们把2分开称，总共需要2次
当n = 6时，分成2、2、2，天平秤2、2，同样考虑最坏的情况，不管如何，还需要
    把2分开称，总共需要2次
当n = 7时，分成2、2、3，天平先称2、2，考虑最坏的情况，重量相等，接着我们就需要
    按照n = 3的最优情况称，总共需要2次
...

其中有一个规则，我们每次把n分成是3堆，
    如果n % 3 == 0,分成 n/3、 n/3、 n/3三堆， 剩下 n/3
    如果n % 3 == 1,分成 n/3、 n/3、1 + (n/3)三堆，最坏剩下 1 + (n/3)
    如果n % 3 == 2,分成 n/3、 1 + (n/3)、1 + (n/3)三堆，最坏剩下 1 + (n/3)

$\color{blue}代码实现：$

#include <iostream>
using namespace std;

int main() {
    int n = 0;
    //scanf返回值为正确输入数据的变量个数，当一个变量都没有成功获取数据时，此时返回-1
    while (scanf("%d", &n) != - 1) {
        if (n == 0) {
            break;
        }
        int count = 0;
        while (n > 1) {
            count += 1;
            //每次取1/3,如果不能整除3，有两种情况
            //剩余1个，分成 1/3 、1/3 、1 + (1/3) ，两个1/3放入天平两端，
            //剩余2个，分成 1/3 、1 + (1/3) 、 1 + (1/3)，两个1 + (1/3)放入天平两端
            //由于题目要求最快的时间，并且是求最多的次数，因此取每次剩余的最大值 1 + (1/3)
            n = n / 3 + (n % 3 > 0);
        }
        printf("%d\n", count);
    }
    return 0;
}
————————————————
版权声明：本文为CSDN博主「hestyle」的原创文章，遵循 CC 4.0 BY 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://hestyle.blog.csdn.net/article/details/104689962

发表于 2020-03-06 10:26:22 回复(1)

不徐不疾

从小往前推导，一次称量最多能找出3枚硬币中的假币，二次称量最多能找到9枚......

#include<iostream>
using namespace std;
int main()
{
    int N;
    while(cin>>N&&N)
    {
        int ans=0;
        long long sum=1;
        while(sum<N)
        {
            sum*=3;
            ans++;
        }
        cout<<ans<<endl;
    }
    return 0;
}

发表于 2019-05-09 21:03:01 回复(0)

Yohifo

#include <iostream>

using namespace std;

int main()
{
    int n = 0;
    while(cin >> n && n != 0)
    {
        //因为天平只有两端，所以至多可以均分为三堆
        //假若不可均分为三堆，则优先分为 2n + m 的模式，其中 m 要尽可能的小
        int num = 0;
        while(n > 1)
        {
            if(n % 3 == 0)
                n /= 3;
            else
                n = ((n / 3) + 1);    //寻求最优解

            num++;
        }

        cout << num << endl;
    }

    return 0;
}

发表于 2023-05-26 16:20:12 回复(0)

反对画饼的社畜很喜欢吃火锅

// write your code here cpp
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
while(cin>>n)
{
if(n==0)return 0;
n--;
int cnt=0;
while(n)
{
cnt++;
n/=3;
}
cout<<cnt<<endl;
}
return 0;
}

发表于 2022-11-18 21:01:26 回复(0)

牛客596330099号

// write your code here
import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNextInt())
{
int n=sc.nextInt();
if(n==0)
break;
int count=0;
//每次分三堆称最快天平平衡说明在未测量堆
//不平衡说明在轻堆每次都能排除两堆
while(n>=2)
//两颗以上才需称量
{
count++;
//因为计算最多称几次所以在不知道每次测量结果的情况下
//只能按照每次称量硬币最多的那一堆的情况计算最多称量次数
//因为分三堆所以每次仅可能多出0-2颗币如果多出一颗分给未称量堆
//多出两颗分别分给天平两侧无论是哪种情况较重堆都是n/3+1的情况
//所以只需要分有余币和无余币两种情况处理
if(n%3!=0)//有余币
n=n/3+1;
else//无余币
n/=3;
}
System.out.println(count);
}
}
}

发表于 2022-11-02 12:28:48 回复(0)

Java

来学习的小张

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            int n = in.nextInt();
            if(n == 0){
                return;
            }else if(n == 1){
                System.out.println(0);
            }else if(n == 2 || n == 3){
                System.out.println(1);
            }else {
                int count = 1;
                while(n > 3){
                    if(n % 3 == 0){
                        n /= 3; 
                    }else{
                       n = n / 3 +1;
                   }
                    count++;
                } 
                System.out.println(count);
            }
        }
    }
}

发表于 2022-05-06 09:36:04 回复(0)

一条余弦Cos

// write your code here cpp
// write your code here cpp
#include<stdio.h>
int main()
{
    int n;
    while(scanf("%d",&n),n)
    {
        int count=0;
        while(n>1)
        {
            n=n/3+1-(n%3^3)/3;
            count++;
        }
        printf("%d\n",count);
    }
    return 0;
}

发表于 2021-03-22 11:43:32 回复(0)

C/C++

牛客691469011号

/*
算法：称出结果三堆，类似2个树3个空隙，其坏币必在其中；
开始n==1 num=0;
n==2 num=1;
n==3 num=1;
n>3时每次找其在的1/3堆，即序号为n-2*n/3；
不难得出递归；
*/
#include<stdio.h>
long long int fun(long long int n)
{
    long long int sum=0;
    if(n==1) return sum;
    else if(n==2||n==3) return sum+1;
    else return 1+fun(n-2*n/3);

}
int main (void)
{
    long long int n;
    while(scanf("%lld",&n)!=EOF)
    {
if(n==0) break;
        printf("%lld\n",fun(n));
    }
return 0;
}

发表于 2020-11-14 23:11:30 回复(0)

阳光丿洒脱

#include<iostream>

using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        if(n == 0)
            break;
        int count = 0;
        while(n)
        {
            if(n == 1)
                break;
            if (n%3 == 0)
                n/=3;
            else
                n = n/3+1;
            count++;
        }
        cout<<count<<endl;
    }
    return 0;
}

发表于 2020-04-17 11:30:47 回复(0)

C/C++

不偷不抢安度因_

#include <stdio.h>
#include <stdlib.h>
 
int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        if(n == 0)
            break;
        int count = 0;
        while(n)
        {
            if(n == 1)
                break;
            if(n % 3 == 0)
                n /= 3;
            else
                n = n/3 + 1;
            count++;
        }
        printf("%d\n", count);
    }
}

编辑于 2020-03-03 18:24:55 回复(0)

AC好难

#include <stdio.h>
int main() {
    long n;
    int num;
    while (scanf("%ld", &n), n != 0)
    {
        num = 0;
        while (n > 1)
        {
            num++;
            n = n - n / 3 - (n - n / 3) / 2;
        }
        printf("%d\n", num);
    }
    
    return 0;
}

发表于 2019-04-12 23:22:25 回复(1)

価闙

import math

while True:
    try:
        n = int(input())
        if n==0:
            break
    except:
        pass

    print(math.ceil(math.log(n)/math.log(3)))

发表于 2019-02-12 15:30:24 回复(0)

Disconnect

def find(a):
con = 0
while a>1:
if a%3==1 or a%3==0:
a = a - a//3*2
con+=1
elif a%3==2:
a = a//3+1
con+=1
return con
try:
while True:
n = input()
n = int(n)
if n==0:
break
else:
print(find(n))
except:
pass

发表于 2018-12-01 23:43:50 回复(0)