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

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


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

输入

3

输出

3

18个回答

添加回答
#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)
/*单序列的dp问题,在点n处三种方式,根据n的奇偶性来进行讨论
dp[i]:
1.当i是偶数,dp[i/2]+1
2.当i是奇数,dp[(i+1)/2]+2,dp[i-1]+1
3.每个位置先进行初始化,然后就是上面两种情况下多取一下Min
*/
#include <iostream>
#include <vector>
using namespace std;
class Solution{
public:
    int solve(int n){
        if(n<=3)
            return n;
        vector<int> dp(n+1,0);
        //先进行初始化
        dp[1]=1,dp[2]=2,dp[3]=3;
        for(int i=4;i<=n;++i){ //1,2,3不用进行讨论,无论如何就那么几步
            if(i%2==0)
                dp[i]=min(dp[i-1]+1,dp[i/2]+1);
            else
                dp[i]=min(dp[(i+1)/2]+2,dp[i-1]+1);
        }
        return dp[n];
    }
};
int main(){
    int n; //想去的位置
    cin>>n;
    if(n>=0 && n<3){
        cout<<n;
        return 0;
    }
    Solution sol;
    if(n<0)
        cout<<sol.solve(-n);
    else
        cout<<sol.solve(n);
    return 0;
}
/*对于dp的题,其实也是个惯式
1.单序列的dp,那么就是找i+1位置和i位置的联系
2.双序列的dp,那么就是一个二维vec存结果,那么无非就是dp[i][j]与dp[i-1][j],dp[i][j-1],dp[i-1][j-1]三者之间的联系
3.矩阵的dp,这个就比较简单了,直接顺着来即可
总结可以看我给出的各类的例子:
https://blog.csdn.net/qq_26896213/article/details/86507685
*/

发表于 2019-02-17 12:35:35 回复(2)
逆向思维,从终点到原点需要的最少步数
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int x = Math.abs(Integer.parseInt(br.readLine()));

        int res = 0;
        while (x != 0) {
            if (x % 2 == 0) x >>= 1;
            else x += ((x + 1) / 2 % 2 == 0 && x > 3) ? 1 : -1;
            res++;
        }
        System.out.println(res);
    }
}

编辑于 2019-01-24 12:45:51 回复(2)
/**
 * 小招喵跑步
 * 小招喵喜欢在数轴上跑来跑去,假设它现在站在点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)
利用递归算法
import java.util.Scanner;
public class Main {
    public static int  minstep(int x) {
        x=Math.abs(x);
        if (x==0)  return 0;
        if (x==1)  return 1;
        else if (x%2==0) {
            return minstep(x/2)+1;
        }
        else {
             return Math.min(minstep(x-1)+1,minstep(x+1)+1);
        }
    }
    public static void main(String[] args) {
       Scanner sc=new Scanner(System.in);
        System.out.println(minstep(sc.nextInt()));
    }
}


发表于 2019-04-01 01:47:34 回复(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 回复(1)
public class RunningCat { public static void main(String[] args){ Scanner scanner = new Scanner(System.in); int x = scanner.nextInt(); if (x < 0){ x = -x; } // 用数组保存一下前面的状态 int[] a = new int[x+1]; Arrays.fill(a,-1); a[0] = 0; a[1] = 1; a[2] = 2; System.out.println(countQuickSteps(x,a)); } private static int countQuickSteps(int x, int [] a) { if (a[x] != -1){ return a[x]; } int quickSteps; if (x % 2 == 0){ quickSteps = countQuickSteps(x/2, a) + 1; }else { int q1 = countQuickSteps((x+1) / 2, a) + 2; int q2 = countQuickSteps((x-1) / 2, a) + 2; quickSteps = Math.min(q1,q2); } return quickSteps; } }
发表于 2019-02-28 16:07:37 回复(0)
n=int(input())
def judge(x):
    if x<0:
        x=-x
    if x==0:
        return 0
    elif x==1:
        return 1
    else:
        if x%2==0:
            return judge(x//2)+1
      
        else:
            return min(judge(x//2+1)+2,judge(x//2)+2)
print(judge(n))

发表于 2019-02-27 15:50:00 回复(0)
动态规划做法

#include<iostream>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define MAX 10000000
int dp[10000];
int main() {
    int x;
    cin>>x;
    memset(dp,10000,sizeof(dp));
    dp[5000]=0;
    //dp[499]=dp[501]=dp[498]=dp[502]=1;
    int t;
    if (x<0) {
        for (int i=4999;i>=5000+x;i--) {
            if (i%2!=0) {
                dp[i]=min(dp[i-1],min(dp[i+1],dp[5000-(5000-i+1)/2]+1))+1;
            } else {
                dp[i]=min(dp[i-1]+1,min(dp[i+1]+1,dp[5000-(5000-i)/2]+1));
                //dp[i]=dp[i/2]+1;
            }
        }
    } else if (x>0) {
        for (int i=5001;i<=5000+x;i++) {
            if (i%2!=0) {
                dp[i]=min(dp[i-1],min(dp[i+1],dp[(i+1-5000)/2+5000])+1)+1;
            } else {
                dp[i]=min(dp[i-1],min(dp[i+1],dp[(i-5000)/2+5000]))+1;
                //dp[i]=dp[i/2]+1;
            }
        }
    }
    cout<<dp[5000+x]<<endl;
    return 0;
}

发表于 2019-02-03 00:48:34 回复(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)