首页 > 试题广场 >

小招喵跑步

[编程题]小招喵跑步

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

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

输入描述:

小招喵想去的位置x

输出描述:

小招喵最少需要的步数

示例1

输入

输出

算法知识视频讲解

Java

pein531

由于都是从原点出发，根据对称性，无论x是正数还是负数都是一样的。利用递归从x反推至原点，如果当前位置是偶数，就除以2，否则就通过+1（右移一步）或-1（左移一步）变成偶数位置后再除以2。这样的策略下，得到的步数一定是最少的。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int x = Integer.parseInt(br.readLine());
        if(x == 0){
            System.out.println(x);
        }else{
            System.out.println(dfs((long)Math.abs(x)));
        }
    }
    
    private static long dfs(long x) {
        if(x == 0){
            return 0;
        }else if(x <= 2){
            return x;
        }
        if((x & 1) == 0){
            return dfs(x >> 1) + 1;
        }else{
            return Math.min(dfs((x - 1) >> 1) + 2, dfs((x + 1) >> 1) + 2);
        }
    }
}

发表于 2022-01-19 11:39:01 回复(0)

Java

lmz9509

/*
参考答案；动态规划
dp[i]表示到达i点的最少步数。
最少就需要考虑两倍的走法
状态转移：
当前位置能被二整除，dp[i] = dp[i/2]+1;
当前位置不能被二整除，dp[i] = min(dp[i-1],dp[i+1/2]+1) + 1

dp[i+1/2]+1这个表示后移一步，比如说i=5,那么可以有dp[4] + 1,也可以有dp[6]+1,
而这里的dp[6]很显然是个偶数，那他的步数就一定是dp[3]+1
*/
import java.math.*;
import java.lang.Math;
import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader((new InputStreamReader(System.in)));
        int x = Integer.parseInt(br.readLine());
        if(x < 0){
            x = -x;
        }
        if(x == 0){
            System.out.println(0);
            return;
        }
        int[] step = new int[x+1];
        step[0] = 0;
        step[1] = 1;
        for(int i = 2; i < x + 1; i++){
            if(i % 2 == 0){
                step[i] = step[i/2]+1;
            }else{
                step[i] = Math.min(step[i -1], step[(i+1)/2]+ 1) + 1;
            }
        }
        System.out.println(step[x]);
    }
}

发表于 2020-06-17 20:35:30 回复(0)

Java

分为若干范围广

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)