首页 > 试题广场 >

牛牛打响指

[编程题]牛牛打响指

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

牛牛在地上捡到了一个手套，他带上手套发现眼前出现了很多个小人，当他打一下响指，这些小人的数量就会发生以下变化：如果小人原本的数量是偶数那么数量就会变成一半，如果小人原本的数量是奇数那么数量就会加一。现在牛牛想考考你，他要打多少次响指，才能让小人的数量变成1。

输入描述:

每个输入包含一个测试用例。
输入的第一行包括一个正整数，表示一开始小人的数量N(1<=N<=10^100)。

输出描述:

对于每个用例，在单独的一行中输出牛牛需要打多少次响指才能让小人的数量变成1。

示例1

输入

输出

算法知识视频讲解

zevyu

#include <iostream>
#include<vector>

using namespace std;
int main()
{
uint32_t N[128] = { 0 };
char temp;
int begin = 0, end = 0, res = 0;
while (scanf("%c", &temp))
{
if (temp == '\n')
break;
N[end] = temp - '0';
end++;
}
while (!(begin == end - 1 && N[end - 1] == 1))
{
if (N[end - 1] & 1)
{
N[end - 1]++;
res++;
}
int flag = 0, tempV = 0;
res++;
for (int i = begin; i < end; i++)
{
tempV = N[i] + flag * 10;
flag = tempV & 1;
N[i] = tempV >> 1;
}
if (N[begin] == 0)begin++;
}
cout << res;
return 0;

}

关于+1进位时只在最低位进位，下图大致计算了进位次数，可以保证最低位不会溢出。

编辑于 2018-06-25 09:19:03 回复(6)

为啥要起名字

while True:
try:
num=int(raw_input().strip())
if num==1:
print(0)
else:
count=0
while True:
if num%2==0:
num=num//2
count+=1
else:
num+=1
count+=1
if num==1:
break
print(count)
except:
break

发表于 2018-05-28 09:39:39 回复(0)

Python

pein531

这个题用python可以直接模拟

n = int(input())
step = 0
while n > 1:
    if n&1:
        n = (n + 1) >> 1
        step += 2
    else:
        n >>= 1
        step += 1
print(step)

发表于 2023-02-07 15:06:58 回复(0)

biamgo

n = input()
s = bin(n)[2:]
ans = len(s) - 1 + s.strip("0").count("0")
if s.count("1") > 1:
    ans += 2
print ans

编辑于 2018-08-02 20:07:54 回复(2)

Java

luckyxue

import java.util.Scanner;
import java.math.BigInteger;
public class Main {
//    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
//        BigInteger bi = new BigInteger(sc.nextLine());
//        int count = 0;
//        BigInteger two = new BigInteger("2");
//        while (!bi.equals(BigInteger.ONE)) {
//            if (bi.remainder(two).equals(BigInteger.ZERO)) {
//                bi = bi.divide(two);
//            } else {
//                bi = bi.add(BigInteger.ONE);
//            }
//            count++;
//        }
//        System.out.println(count);
//    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String str = sc.next();
            String bin = new BigInteger(str).toString(2);
            int len = bin.length();
            int count = 0;
            for (int i = len - 1; i >= 0; i--) {
                if (bin.charAt(i) == '1') {
                    for (int j = 0; j < i; j++) {
                        if (bin.charAt(j) == '0') {
                            count++;
                        }
                    }
                    break;
                }
            }
            if (bin.length() == 1) {
                System.out.println(0);
            } else {
                System.out.println(len + count + 1);
            }
        }
    }
}

发表于 2018-06-06 19:54:42 回复(1)

麦垛上的守望者

有一个9XXXXX，一大串，18位数，我算出来是86，牛客说答案是89

郁闷，，，这玩意，我总不能手动验证吧

想不通哪里有问题

import java.util.Scanner;

/**
* 牛牛在地上捡到了一个手套，他带上手套发现眼前出现了很多个小人，当他打一下响指，这些小人的数量就会发生以下变化：如果小人原本的数量是偶数那么数量就会变成一半，如果小人原本的数量是奇数那么数量就会加一。现在牛牛想考考你，他要打多少次响指，才能让小人的数量变成1。
输入描述:
每个输入包含一个测试用例。
输入的第一行包括一个正整数，表示一开始小人的数量N(1<=N<=10^100)。

输出描述:
对于每个用例，在单独的一行中输出牛牛需要打多少次响指才能让小人的数量变成1。

输入例子1:
10000

输出例子1:
20

* @author kafka
*
*/
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        double n = Double.parseDouble(scanner.next()) ;
        int cnt=0;
        while(n>1){
            if(n%2==1)
                n+=1;
            else
                n/=2;
            cnt++;
        }
        System.out.println(cnt);
        scanner.close();
    }
}

发表于 2018-05-25 16:57:06 回复(4)

灵外＆棂外

#coding:utf-8

i=raw_input()
try:
i=int(i)
j=0
while i!=1:
if i%2==1:
i=i+1
else:
i=i/2
j=j+1
print j
except:
print None

发表于 2018-05-25 16:11:07 回复(0)

鬼祟

import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        // 创建字符串缓冲区对象
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int score = 0;
        while(num!=1){
            if(num%2==0){
                num/=2;
            }else{
                num++;
            }
            score++;
        }
        System.out.println(score);
    }

}

为什么我的代码通过率只有百分之60

发表于 2018-05-25 15:53:46 回复(1)

uing

import java.math.BigInteger;
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    BigInteger bi= new BigInteger(sc.nextLine());
    System.out.println(times(bi));        
}

private static int times(BigInteger num) {
    int times= 0;
    BigInteger t = new BigInteger("2");
    while (!num.equals(BigInteger.ONE)) {
        if (num.remainder(t).equals(BigInteger.ZERO)) {
            num=num.divide(t);
        }
        else {
            num=num.add(BigInteger.ONE);
        }
        times++;
    }
    return times;
}

}

发表于 2018-05-25 14:47:00 回复(0)