首页 > 试题广场 > 小招喵跑步
[编程题]小招喵跑步
小招喵喜欢在数轴上跑来跑去,假设它现在站在点n处,它只会3种走法,分别是:
1.数轴上向前走一步,即n=n+1 
2.数轴上向后走一步,即n=n-1 
3.数轴上使劲跳跃到当前点的两倍,即n=2*n
现在小招喵在原点,即n=0,它想去点x处,快帮小招喵算算最快的走法需要多少步?

输入描述:
小招喵想去的位置x


输出描述:
小招喵最少需要的步数
示例1

输入

3

输出

3

7个回答

添加回答
/**
 * 小招喵跑步
 * 小招喵喜欢在数轴上跑来跑去,假设它现在站在点n处,它只会3种走法,分别是:
 * 1.数轴上向前走一步,即n=n+1
 * 2.数轴上向后走一步,即n=n-1
 * 3.数轴上使劲跳跃到当前点的两倍,即n=2*n
 * 现在小招喵在原点,即n=0,它想去点x处,快帮小招喵算算最快的走法需要多少步?
 * 输入描述:
 * 小招喵想去的位置x
 * 输出描述:
 * 小招喵最少需要的步数
 * 输入例子1:
 * 3
 * 输出例子1:
 * 3
 */
public class RunningCat {

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int x = scanner.nextInt();
        System.out.println(countQuickSteps(x));
    }

    private static long countQuickSteps(long x) {
        if (x < 0)
            x = -x;
        long quickSteps;
        if (x == 0)
            return 0;
        if (x == 1)
            return 1;
        if (x == 2)
            return  2;
        if (x % 2 == 0){
            quickSteps = countQuickSteps(x/2) + 1;
        }else {
            long q1 = countQuickSteps((x+1) / 2) + 2;
            long q2 = countQuickSteps((x-1) / 2) + 2;

            quickSteps = Math.min(q1,q2);
        }
        return quickSteps;
    }


}
发表于 2018-08-14 23:26:56 回复(0)
#include <iostream>
#include <vector>
 
using namespace std;
 
// 想到位置x处
int process(int x) {
    if (x < 2) {
        return x;
    }
    vector<int> dp(x + 1);
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= x; ++i) {
        if (i % 2 == 0) { // 能整除 // 必然跳更快
            dp[i] = 1 + min(dp[i-1], dp[i / 2]);
        } else {
            dp[i] = 1 + min(dp[i-1], 1 + dp[(i + 1) / 2]);
        }
    }
    return dp[x];
}
 
int main() {
    int x = 0;
    while (cin >> x) {
        cout << process(abs(x)) << endl;
    }
    return 0;
}

发表于 2018-08-10 08:26:13 回复(4)
def count(n):
    if n<0:
        n = -n
    if n==0:
        return 0
    if n==1:
        return 1
    if n%2==0:
        return count(n//2)+1
    else:
        r1 = count((n+1)//2)+2
        r2 = count((n-1)//2)+2
        return min(r1,r2)

发表于 2018-08-09 16:38:14 回复(0)
非递归,牛客测试通过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
importjava.util.Scanner;
 
publicclassMain{
    publicstaticvoidmain(String[] args){
        Scanner sc=newScanner(System.in);
        inttar=sc.nextInt();
        System.out.println(count(tar));
    }
     
    staticint[] c(intx){
        intk=0,i=0,j=1;
        while(x!=0){
            if((x&j)==1)i++;
            k++;
            x>>=1;
        }
        returnnewint[]{k,i};
    }
     
    staticintcount(intt){
        if(t<0)t=-t;
        if(t==0)return0;
        int[] c=c(t);
        intA=c[0]+c[1]-1;
        intM=c[0]+c((int)(Math.pow(2, c[0])-t))[1]+1;
        returnMath.min(A, M);
    }
}


发表于 2018-08-10 14:30:15 回复(0)
def jump(n):
    n = abs(n)
    if((n//2)<=1):
        return n
    if(n%2 == 0 ):
        return count(n//2)+1
    else:
        return count((n-1)//2)+2

自测通过,但不知道如何在牛客上正确测试

发表于 2018-08-10 11:32:19 回复(0)
#include <iostream>
using namespace std;

int main()
{
    int step = 0;
    int i,j;
    int temp=2;
    int x;
    cin>>x;
    temp = x;
    if(temp < 0)
        temp = -temp;
    for(i=0;temp>0;)
    {
        if(temp%2 == 0 || temp == 1)
        {
            temp = temp/2;
            i++;
        }
        else if ((temp+1) % 16 == 0)
        {
            temp = temp + 1;
            i++;
        }
        else
        {
            temp = (temp-1)/2;
            i += 2;
        }
    }
    step = i;
    cout<<step;
    return 0;
}

#我是从x来倒着回到0的,思路其实就是一步可以跳的就跳,是奇数不能跳就减,即往后走一步。以上
#是基本思路,但严格按照:遇到奇数就减,会出现问题,因为当一个奇数加一可以被16整除的时候,
#加一获得一个偶数可以让其连续跳几步,相比于减一获得一个偶数,会少走一步,所以需要判断一下
#是否是加一和减一。
发表于 2018-08-10 09:45:42 回复(1)

    var n = parseInt(line);
    console.log(jump(n));
    function jump(n) {
        if (n < 0) {
            n = -n;
        }
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n % 2 == 0) {
            return jump(n / 2) + 1;
        } else {
            let count1 = jump(Math.floor(n / 2)) + 2;
            let count2 = jump(Math.ceil(n / 2)) + 2;
            return Math.min(count1, count2);
        }
    }

发表于 2018-08-09 17:01:13 回复(0)
牛客网,程序员必备求职神器
QQ群:169195721
微 信:www_nowcoder_com 关注
微 博:牛客网 关注

扫一扫,把题目装进口袋