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

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


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

输入

3

输出

3

12个回答

添加回答
#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)
/**
 * 小招喵跑步
 * 小招喵喜欢在数轴上跑来跑去,假设它现在站在点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)
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)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <climits>
#include <queue>
using namespace std;

// 考虑用bfs找最短路径的做法,类似于单源最短路径求解
// 每次遍历一点,把从当前点,一步可达达的点的距离都更新,如果可达点距离更新了
// 则把他们入队,最终迭代直到队为空
// 考虑当前点一步可达,有几种情况,前进一步,后退一步,当前点*2的点
// 每种情况如果点合法,并且最短距离可以更新,则把此点入队

class Solution {
public:
    int minStep(int n);
};

int Solution::minStep(int n) {

    if (n < 0)
        n = (-1) * n;

    vector<int> distance(n+1, INT_MAX);
    distance[0] = 0;
    queue<int> q; q.push(0);

    while (!q.empty()) {
        int idx = q.front();
        q.pop();

        if (idx + 1 <= n) {
            if (distance[idx + 1] > distance[idx] + 1) {
                distance[idx + 1] = distance[idx] + 1;
                q.push(idx + 1);
            }
        }

        if (idx * 2 <= n) {
            if (distance[idx * 2] > distance[idx] + 1) {
                distance[idx * 2] = distance[idx] + 1;
                q.push(idx * 2);
            }
        }
        if (idx - 1 >= 0) {
            if (distance[idx - 1] > distance[idx] + 1) {
                distance[idx - 1] = distance[idx] + 1;
                q.push(idx - 1);
            }
        }
    }
    return distance[n];
}

int main(void) {
    Solution solu;
    int pos;
    while (cin >> pos) {
        cout << solu.minStep(pos) << endl;
    }
    return 0;
}
编辑于 2018-09-02 15:05:55 回复(0)
def func(n):
    n=abs(n)
    if n<=3:return n
    else:
        if n%2==0:
            return func(n//2)+1
        else:
            return func(n//2)+2 if func(n//2)<func(n//2+1) else func(n//2+1)+2
print(func(int(input())))

编辑于 2018-08-26 12:47:39 回复(0)
#include <cstdio>
#include <cstdlib>
int min(int a, int b){     if (a <= b)         return a;     else         return b;
}
int Steps(int x){     //int result;     if (x < 0)         x = -1 * x;     if (x == 0)         return 0;     if (x == 1)         return 1;     if (x == 2)         return 2;     if (x % 2 == 0)         return Steps(x / 2) + 1;     else{         int num1 = Steps((x + 1) / 2) + 2;         int num2 = Steps((x - 1) / 2) + 2;         return min(num1, num2);     }
}
int main(){     int x;     scanf("%d", &x);     int result = 0;     result = Steps(x);     printf("%d", result);     system("pause");     return 0;
}

发表于 2018-08-24 15:19:39 回复(0)
#include <bits/stdc++.h>
using namespace std;

int minstep;

//当前位置,当前走的步数,目标位置,上一条指令
void dfs(int pos, int count, int target, int lastcom)
{
    if (pos > target || pos < 0)//走出界失败
        return;
    if (pos == 0 && count > 0)//原地走失败
        return;
    if (count > minstep)//走的步数比当前最小步还大,失败
        return;
    if (pos == target)//成功
    {
        minstep = min(minstep, count);
        return;
    }

    if (lastcom != -1)//如果上一条指令后退,没必要前进
        dfs(pos + 1, count + 1, target, 1);
    if (lastcom != 1)//如果上一条指令前进,没必要后退
        dfs(pos - 1, count + 1, target, -1);
    dfs(pos * 2, count + 1, target, 2);
}

int main()
{
    int n;
    cin >> n;
    minstep = abs(n);
    dfs(0, 0, abs(n), 0);
    cout << minstep << endl;

    return 0;
}
编辑于 2018-08-22 21:29:40 回复(0)

import java.util.Arrays;
import java.util.Scanner;
public class Main {
    static int dp(int start, int x, int count) {
        int[][] dp = null;
        if (x < 0) {
            dp = new int[(-x) + 1][count + 1];
        } else {
            dp = new int[x + 1][count + 1];
        }
        //套路,用动态规划做,
        for (int i = dp.length - 2; i >= 0; i--)
            dp[i][0] = Integer.MAX_VALUE;
        for (int j = 1; j < dp[0].length; j++) {
            for (int i = dp.length - 2; i >= 0; i--) {
                int cur_count = Integer.MAX_VALUE;
                if (dp[i + 1][j - 1] != Integer.MAX_VALUE)
                    cur_count = dp[i + 1][j - 1] + 1;
                if (i - 1 >= 0 && dp[i - 1][j - 1] != Integer.MAX_VALUE)
                    cur_count = Math.min(cur_count, dp[i - 1][j - 1] + 1);
                if (2 * i < dp.length && dp[2 * i][j - 1] != Integer.MAX_VALUE)
                    cur_count = Math.min(cur_count, dp[2 * i][j - 1] + 1);
                dp[i][j] = cur_count;
            }
        }
        return dp[start][dp[0].length - 1];
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scanner = new Scanner(System.in);
        int x = scanner.nextInt();
        if (x < 0) {
            System.out.println(dp(0, x, (-x) - 0));
        } else {
            System.out.println(dp(0, x, x - 0));
        }
    }
}

发表于 2018-08-19 10:56:01 回复(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群

扫描二维码,关注牛客网公众号

  • 公司地址:北京市朝阳区大屯路东金泉时代3-808北京牛客科技有限公司
  • 联系方式:010-60728802(电话) admin@nowcoder.com
  • 牛客科技©2018 All rights reserved
  • 京ICP备14055008号-4
  • 京公网安备 11010502036488号