算法练习题之抓住那头牛

在搜索Trie树内容的时候，在一个OJ答题网站“百练”看到一道题感觉还蛮有意思的，所以就自己写了一下，用java写的，下面贴出来：

农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0<=N<=100000)，牛位于点K(0<=K<=100000)。农夫有两种移动方式：

5 17

4

上代码：

package p1;

import java.util.Scanner;

public class AcmTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		System.out.println("输入");
		Scanner in = new Scanner(System.in);
		int farmer = in.nextInt();
		int cow = in.nextInt();
		if(farmer<0 || farmer>100000 || cow<0 || cow>100000){
			System.out.println("输入无效！");
		}else{
			System.out.println(getMinTime(farmer,cow));
		}
	}
	
	//计算最少时间
	public static int getMinTime(int f, int c)
	{
		//如果牛的坐标小于农夫，则可以做交换便于处理，结果一致
		if(f > c){
			int temp;
			temp = c;
			c = f;
			f = temp;
		}
		int time = 0;
		int f1 = 0,f2 = 0;	//f1是指先以X+1,X-1运动方式进行，f2是指先以X->2X运动方式进行
		int long1,long2;	//long1是指运动超过牛之后坐标差，long2是指运动后没有超过牛的坐标差
		while(4*f < c){
			if(2*f >c)
				break;
			f = 2*f;	//执行x到2x的运动方式
			time++;
		}
		if((f1 = 2*f) >c && isBeyond(f1)){
			long1 = f1 - c;	//超过之后的距离
			long2 = long1/2;	//可以进行2x运动的调整次数
			if((f2 = 2*(f-long2)) <= c){
				time = time+long2 + 1;	//运动时间
			}
		}else{
			f1 = 2*f;
			long1 = c - f1;
			long2 = long1/2;
			f2 = 2*(f+long2);
			time = time+long2+1;
		}
		//以农夫跟牛的坐标重合为成功
		if(c % 2 != 0)
			time++;
		return time;
	}
	//判断农夫是否出界
	public static boolean isBeyond(int f){
		if(f<0 || f>100000){
			return false;
		}else{
			return true;
		}
	}
}

最后

以上就是开放月饼为你收集整理的算法练习题之抓住那头牛的全部内容，希望文章能够帮你解决算法练习题之抓住那头牛所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。