求解一道编程题，马的智障

题目如图，希望提供思路，最好有代码(c语言)图片

c语言 编程 c++

7个回答

按赞数排序

思路就是递归，
1，先判断大小，由于从n到K和从K到N是一样的时间，(假设N 2.递归算法，实际上就是2种情况，nk/2
3.n>K/2的情况下又分为两点，(n-(n-k/2))*2 或者是 k-n 两种时间比较哪种更优，如果K不是偶数的减一，在做这个运算，之后再加一步
4.N<k/2情况，递归这个函数，function（n,k/2）
完整的思路体系，代码估计就是10行左右，

qq_29594393
当作看不见 回复cheng_feng_xiao_zhan: 你还有更好的解决方案？
大约 4 年之前 回复
cheng_feng_xiao_zhan
乘风晓栈 8点是马，1点是草，1跳2跳4跳8？
大约 4 年之前 回复

先取判断nk大小，然后再判断(假设此时取n > k) n >(k/2)？，如果是则n＝n*2(且每循环一次时间t＋＋)；
若否，则设temp ＝ k － n，t ＝ t＋temp

若N<=K
思路是递归，判断N<=(K-N)则递归跳并计算步数
否则跳出递归走到目的地
（在最后一次跳时判断N与K的距离过N/2则跳，否则走）
若N>K
K<N/2时（若能会跳到终点则跳到0点）后走到K
否则一直走到K

分开来看好理解，但有相同代码，可以合一优化，或单独写一个Util

裸的bfs，O(n)。附上辣鸡代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
//--container
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
const int up=100000;
//--
#define clr(a) memset(a,0,sizeof(a))
bool bd[100001];
void cl(){
    int n,k;queue<pi>qe;scanf("%d %d",&n,&k);
    for(clr(bd),qe.push(pi(n,0));qe.front().first!=k;){
        pi t=qe.front();qe.pop();
        if(t.first-1>=0&&!bd[t.first-1])qe.push(pi(t.first-1,t.second+1)),bd[t.first-1]=1;
        if(t.first+1<=up&&!bd[t.first+1])qe.push(pi(t.first+1,t.second+1)),bd[t.first+1]=1;
        if(t.first*2<=up&&!bd[t.first*2])qe.push(pi(t.first*2,t.second+1)),bd[t.first*2]=1;
    }
    printf("%d\n",qe.front().second);
};
int main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    cl();
    return 0;
};
u012345506
wynist 回复qq_32794157: 出错的数据是什么？
大约 4 年之前 回复
qq_32794157
接骨木go 运行出错，貌似是指针越界了
大约 4 年之前 回复

import java.util.Scanner;
public class StupidHorse {
public static void main(String[] args) {
//测试
Scanner x=new Scanner(System.in);
System.out.println("请输入一个小花的起始位置n以及萝卜位置k；（0=<n<=100000;0=<k<=100000）:");
int n=x.nextInt();
int k=x.nextInt();
System.out.println("起始位置为"+n);
System.out.println("萝卜位置为"+k);
minTime(n,k);
minTime2(n, k);
}
//策略一：
public static void minTime(int n,int k){
if(n==0||n==1){
//起点为0或1，一直走到黑
System.out.println(k-n);
}else{
//定义s路程。最短时间必然是“先跳后走”。
int s = Math.abs(k-n);

        //两种case：跳过终点，再往回走到终点；跳至终点前，然后走向终点。
        int x = s/n + s%n;
        int y = s/n+1 + (s/n+1)*n-s;

        //判断两种场景的最优解，输出。
        if(x>=y){
            System.out.println(y);
        }else{
            System.out.println(x);
        }
    }
}
//策略二：
public static void minTime2(int n,int k){
    if(n==0||n==1){
        //起点为0或1，一直走到黑
        System.out.println(k-n);
    }else{
        //定义s路程。最短时间必然是“先跳后走”。
        int s = Math.abs(k-n);

        //两种case：跳过终点，再往回走到终点；跳至终点前，然后走向终点。最优解判断依据取余和n的一半做比较。
        int x=0;
        if(s%n<=n/2){
            x = s/n + s%n;
        }else{
            x = s/n+1 + (s/n+1)*n-s;
        }

        //判断两种场景的最优解，输出。
        System.out.println(x);
    }
}

}

http://write.blog.csdn.net/postlist

Csdn user default icon
插入链接
本地上传 网络图片
上传中...
上传图片
插入图片
抄袭、复制答案，以达到刷声望分或其他目的的行为，在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了！
我要提问
立即提问
相关内容推荐