首页 > 试题广场 >

小招喵跑步

[编程题]小招喵跑步
  • 热度指数:10141 时间限制: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

输入

3

输出

3
非递归,牛客测试通过

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)
更多回答
利用递归算法
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)
/*单序列的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)
/*
参考答案;动态规划
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)
逆向思维,从终点到原点需要的最少步数
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)
由于都是从原点出发,根据对称性,无论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)
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    n = abs(n);
    int dp[n+1];
    dp[0] = 0;
    dp[1] = 1;
    for(int i=2;i<=n;i++){
        if(i & 1)
            dp[i] = min(dp[i-1], dp[(i+1)/2]+1) + 1;
        else
            dp[i] = min(dp[i-1], dp[i/2]) + 1;
    }
    printf("%d\n", dp[n]);
    return 0;
}

发表于 2020-10-21 00:27:13 回复(0)
利用动态规划可以简单解决问题
能跳到一个点无非就三种方法:

1.数轴上向前走一步,即n=n+1 
2.数轴上向后走一步,即n=n-1 
3.数轴上使劲跳跃到当前点的两倍,即n=2*n

所以取dp上的 前后一个点及n/2 上可以+1步就跳到该点。取到该点的最小步数时,记得+1 放到 n*2上(规则3.数轴上使劲跳跃到当前点的两倍,即n=2*n

#include <iostream>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#include<math.h>
//#include<

using namespace std;

int main()
{

    int num;
    while(cin>>num)
    {
        num = abs(num);
        vector<long long>dp(2*(num+1),2*num);
        if(num  == 0)
            dp[0] = 0;
        else {
            dp[0] = 1;
            dp[1] = 1;
        }
        //    dp[2] = 2;

        for(int i =2;i<=num;i++)
        {
            if(i%2==0)
                dp[i] = min(dp[i/2]+1,dp[i]);
            dp[i] = min(dp[i-1]+1,dp[i]);
            dp[i] = min(dp[i],dp[i+1]+1);
            dp[i*2] = dp[i]+1;
        }

        cout<<dp[num]<<endl;
    }
    return 0;
}





发表于 2019-08-14 15:13:56 回复(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)
#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 回复(5)
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)
#include <stdio.h>

int digui(int data)
{
    if(data==1)
        return 1;
    else if(data==2)
        return 2;
    else if(data%2==0 && data!=0)
        return 1+digui(data/2);
    else if(data%2!=0)
        return 1+digui(data-1);
    else
        return 0;
}

int digui2(int data)
{
    if(data==-1)
        return 1;
    else if(data==-2)
        return 2;
    else if(data%2==0 && data!=0)
        return 1+digui2(data/2);
    else if(data%2!=0)
        return 1+digui2(data+1);
    else
        return 0;
}

int main()
{
    int data;
    scanf("%d",&data);
    int i;
    if(data>=0)
        i=digui(data);
    else
        i=digui2(data);
    printf("%d\n",i);
    return 0;
}

//很好奇你们是怎么通过的,我同样以递归的形式写的代码,当数据为1980时,输出错误18,最简单为14
发表于 2023-11-02 00:27:16 回复(0)
x = int(input())
i = 0
x = abs(x)
while x != 0:
    if x % 2 == 0:
        x = x/2
        i += 1
    elif x % 4 == 3 and x != 3:
        x += 1
        i += 1
    elif x % 4 == 1:
        x -= 1
        i += 1
    else:
        x = 0
        i += 3
print(i)

# 笨比算法 考拉兹猜想的变形

发表于 2022-11-10 23:50:34 回复(0)
class Solution:
#     最少需要考虑两倍走法
    def minSteps(self, x: int) -> int:
        if x == 0&nbs***bsp;x == 1:
            return x
        
        if x < 0:
            x = (-1) * x
        
        dp = [x] * (x + 1)
        dp[0] = 0
        dp [1] = 1
        
        for i in range(2, x + 1):
            if i % 2 == 0:
                dp[i] = dp[i // 2] + 1   # 就算整除也会变成浮点数
            else:
                dp[i] = min(dp[(i + 1) // 2] + 2, dp[(i - 1) // 2] + 2)
                
        return dp[-1]
    
if __name__ == '__main__':
    x = int(input())
    my_solution = Solution()
    result = my_solution.minSteps(x)
    print(result)

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

int main() {
    int n; cin >> n; n = abs(n);
    if (n == 0) { cout << 0; return 0; }
    int dp[n];
    dp[0] = 0; dp[1] = 1; dp[2] = 2;
    for (int i=3; i<=n; i++) {
        if (i % 2 != 0) {   // 奇数位置:三种位置
            dp[i] = min(dp[i-1]+1, dp[(i-1)/2]+2);
            dp[i] = min(dp[i], dp[(i+1)/2]+2);
        } else {   // 偶数位置:只需要一种
            dp[i] = dp[i/2] + 1;
        }
    }
    cout << dp[n] << endl;
    return 0;
}

发表于 2022-05-25 10:50:21 回复(0)
#include<iostream>
#include<queue>
#include<cstdio>
#include<unordered_set>
using namespace std;
int main(){
    int x;
    cin >> x;
    queue<int> q;
    unordered_set<int> s;
    q.push(0);
    s.insert(0);
    int step = 0;
    while(!q.empty()){
        int sz = q.size();
        while(sz--){
            int t = q.front();
            if(t == x){
                //printf("nmsl\n");
                printf("%d",step);
                return  0;
            }
            q.pop();
            if(s.find(t + 1) == s.end()){
                q.push(t+1);
                s.insert(t+1);
            }
            if(s.find(t-1) == s.end()){
                q.push(t-1);
                s.insert(t-1);
            }
            if(s.find(2*t) == s.end()){
                q.push(2*t);
                s.insert(2*t);
            }
        }
        step++;
    }
}
BFS也可以做
发表于 2022-02-07 21:01:54 回复(0)
import java.util.*;
public class Main{
    /*public static void main(String[] args){//BFS
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        if(x==0){
            System.out.println(0);
            return;
        }
        LinkedList<Integer> list = new LinkedList<Integer>();
        list.add(0);
        int step = 0;
        while(true){
            step++;
            int size = list.size();
            for(int i=0;i<size;i++){
                int tmp = list.pop();
                if(tmp+1!=x){
                    list.add(tmp+1);
                }else{
                    System.out.println(step);
                    return;
                }
                if(tmp-1!=x){
                    list.add(tmp-1);
                }else{
                    System.out.println(step);
                    return;
                }
                if(tmp*2!=x){
                    list.add(tmp*2);
                }else{
                    System.out.println(step);
                    return;
                }
            }
        }
    }*/
    public static void main(String[] args){//dp
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        if(x==0){
            System.out.println(0);
            return;
        }
        if(x<0)x=-x;
        int[] dp = new int[x+1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i=2;i<=x;i++){
            if(i%2==0){
                dp[i]=dp[i/2]+1;
            }else{
                dp[i]=Math.min(dp[i-1]+1,dp[(i+1)/2]+2);
            }
        }
        System.out.println(dp[x]);
    }
}

发表于 2020-08-13 15:42:47 回复(0)

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int Fast_Jump(int x)
{
    if(x < 0)
        x = -x;
    if(x < 4)  return x;
    vector<int> dp(x+1);
    dp[0]=0, dp[1]=1, dp[2]=2, dp[3]=3;
    for(int i=4; i<=x; i++)
    {
        if(i%2 == 0)
            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;
    cin>>x;
    int count = Fast_Jump(x);
    cout<<count<<endl;
    return 0;}
为什么vector<int> dp(x+1)可以,直接定义int dp[x+1]就会报错,必须要先初始化吗
发表于 2020-08-06 19:43:21 回复(0)
分享一个很好理解,但是内存占用比较大的AC代码
动态规划一直是我的软肋,但是动态规划的题必然可以用其他方法来做。
本题我用的是广搜,事实上广搜在很多动态规划问题都能用到,但是相比动态规划效率不高,但是对于我这种动态规划的小白来说真是救命稻草,尤其是在笔试中,能AC才是王道。
我的思想就是用广搜算法列出所有可能性,最先满足要求的就是最优解,用队列的方式实现广搜对小白来说很友好,广搜其实就是类似于二叉树的树型结构,向下扩散,每一条路径就代表了一种可能性,代码简单而且好理解。
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int x;
    cin>>x;
    queue<int> q;
    q.push(0);
    int count=0;
    while(!q.empty())
    {
        int len=q.size();
        while(len--)
        {
            int temp=q.front();
            if(temp==x)
            {
                cout<<count<<endl;
                return 0;
            }
            q.pop();
            q.push(temp+1);
            q.push(temp-1);
            q.push(2*temp);
        }
        count++;
    }
    return 0;
}


编辑于 2020-07-24 10:45:36 回复(0)
#include<iostream>
(720)#include<set>
using namespace std;
int main(){
    int x,res=0;
    cin>>x;
    if(x<0)
        x=x*(-1);
    set<int> a,b;
    set<int>::iterator iter;
    a.insert(x);
    while(a.count(0)==0){
        for(iter=a.begin();iter!=a.end();iter++){
            if((*iter)%2==0)
                b.insert((*iter)/2);
            else{
                b.insert((*iter)-1);
                b.insert((*iter)+1);
            }
        }
        a=b;
        res++;
    }
    cout<<res<<endl;
    return 0;
}
计算从x开始到达0的情况:
(1)如果中间值为偶数,必定÷2
(2)如果中间值为奇数,则-1或+1
(3)只要有0出现,则说明最短的路径找到了。
发表于 2020-03-03 10:40:21 回复(0)