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

题目如图,希望提供思路,最好有代码(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问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐