我一直在练习算法,我发现一个花了几周,仍然无法解决。我不能拿出一个完整的算法,但我一直在努力的想法,我写了到目前为止的代码是:在笛卡儿坐标系中找到最接近的点,并移动到另一个点上?
注:的我共享综合性的问题的原因是不恩龙的问题,而我可能首先误解了问题的主要观点。
问题
一个PropBot只能作出两种截然不同的走势。它可以是移动10厘米转发,或转向右边45度。这些单独运动中的每一个都需要秒的时间。
输入
你的模块有两个输入:在该PropBot希望得到尽可能接近地平面上的点的笛卡尔坐标,可以用来做的最大秒数这个。在导航开始时,机器人位于原点,指向+ x方向。秒数将是0到24之间的整数,包括0和24。期望的目的地点的x和y坐标将是-100和100之间的实数,包括端点在内。输入文件中的第一个条目将是测试 个案的数量,t(0 < t≤100)。在这行之后是t行,每行包含三个由空格分隔的条目。第一个条目将是PropBot必须接近该点的秒数。第二个条目是该点的x坐标,第三个条目是该点的y坐标。
输出
你的程序必须返回目标点和最近点的机器人可以在规定时间内到达之间的距离。您的结果应至少包含小数点左侧的一位数字,小数点右侧的正确六位数字。为了消除影响结果舍入误差的机会,我们已经构建了测试数据,以便在第七位的真实结果的小数点右边是从来没有一个4或5
采样输入
24 5.0 5.0
9 7.0 17.0
样本输出
0.502525
< - 如何?
0.100505
OK
Java代码
枚举方向
public enum Direction {
EAST(1), N_EAST(2), NORTH(3), N_WEST(4), WEST(5), S_WEST(6), SOUTH(7), S_EAST(8);
private int direction;
private int index;
Direction(){
direction = 1;
index = 0;
}
Direction(int dir){
direction = dir;
}
int getDirection(){
return direction;
}
public int incrementDir(){
if(direction > 1 && direction <= 8){
direction = 8 - index++;
// Rotate towards right side
}
else if(direction == 1){
direction = 8;
index = 1;
}
return direction;
}
}
摘要 - Calculation.java
import java.awt.Point;
public abstract class Calculation {
public static Direction getDir(Point p){
int line = getCloseLine(p);
switch (line) {
case 1:
return Direction.EAST;
case 2:
return Direction.N_EAST;
// 2nd Quadrant
case 3:
return Direction.NORTH;
case 4:
return Direction.N_WEST;
// 3rd Quadrant
case 5:
return Direction.WEST;
case 6:
return Direction.S_WEST;
// 4th Quadrant
case 7:
return Direction.SOUTH;
case 8:
return Direction.S_EAST;
default:
return Direction.EAST;
}
}
public static int getSelectedLine(Point p){
int a = getCloseLine(p);
return a;
}
public static int getQuadrant(Point target) {
double x = target.getX();
double y = target.getY();
if (x > 0 && y > 0)
return 1;
else if (x < 0 && y > 0)
return 2;
else if (x < 0 && y < 0)
return 3;
else if (x > 0 && y < 0)
return 4;
// Means point lies on an Axis not in any Quadrant
return -1;
}
public static int getAxis(Point target) {
double x = target.getX();
double y = target.getY();
if (x > 0 && y == 0)
return 1;
else if (x == 0 && y > 0)
return 2;
else if (x < 0 && y == 0)
return 3;
else if (x == 0 && y < 0)
return 4;
else if(x == 0 && y == 0)
return 0;
return -1;
}
public static double getAngle(Point v2) {
double d = v2.getY()/v2.getX();
double ang = Math.toDegrees(Math.atan(d));
return ang;
}
public static int getSector(Point point) {
double angle = getAngle(point);
int quad = getQuadrant(point);
if(quad == -1)
return -1;
switch (quad) {
case 1:
if (angle < 45.0)
return 1;
else
return 2;
case 2:
if (angle < -45.0)
return 3;
else
return 4;
case 3:
if (angle < 45.0)
return 5;
else
return 6;
case 4:
if (angle < -45.0)
return 7;
else
return 8;
}
return -1;
}
public static int getCloseLine(Point p) {
int sec = getSector(p);
double angle = getAngle(p);
System.out.println("ANGLE : " + angle);
if(sec == -1){
int axis = getAxis(p);
switch(axis){
case 1:
return 1;
case 2:
return 3;
case 3:
return 5;
case 4:
return 7;
case 0:
return 0;
}
}
switch (sec) {
case 1:
if (angle < 22.5)
return 1;
else
return 2;
case 2:
if (angle < 67.5)
return 2;
else
return 3;
// 2nd Quadrant
case 3:
if (angle < -67.5)
return 3;
else
return 4;
case 4:
if (angle < -22.5)
return 4;
else
return 5;
// 3rd Quadrant
case 5:
if (angle < 22.5)
return 5;
else
return 6;
case 6:
if (angle < 67.5)
return 6;
else
return 7;
// 4th Quadrant
case 7:
if (angle < -67.5)
return 7;
else
return 8;
case 8:
if (angle < -22.5)
return 8;
else
return 1;
}
return -1;
}
}
Main.java
import java.awt.Point;
import java.util.Scanner;
public class Main {
public static void main(String[] args)
{
Scanner s = new Scanner(System.in);
int time = 0;
Point p = new Point(0, 0);
System.out.println("Enter time: ");
time = s.nextInt();
System.out.println(" X: ");
p.x = s.nextInt();
System.out.println(" Y: ");
p.y = s.nextInt();
if(!(time > 0 && time <= 24)){
s.close();
System.err.println("INPUT ERROR!");
return;
}
// Initialize bot facing +x direction
Bot b = new Bot(p, Direction.EAST);
int line = Calculation.getCloseLine(p);
while(time != 0 && b.getDirectionInt() != line){
// Rotate the face towards the point
b.rotate();
time--;
}
s.close();
}
}
Bot.java
import java.awt.Point;
public class Bot {
private Point location;
private Direction direction;
public Bot(){
location = new Point(0, 0);
direction = Direction.EAST;
}
public Bot(Point loc, Direction dir){
location = loc;
direction = dir;
}
public Point move(){
return location;
}
public int rotate(){
direction.incrementDir();
return direction.getDirection();
}
public int getDirectionInt(){
return direction.getDirection();
}
}
我的方法是笛卡尔平面分成部门,并得到一个壁橱线输入点和旋转机器人和然后继续前进。
第一期:我得到了如何评估第二个案例输出,但我对第一个案例输出没有任何意见。
线分布如下:
第二期:如果机器人移动对角(45度),然后可以水平或垂直移动,之后,它似乎为如果整个笛卡尔飞机已经移动并且我写的代码不再有效。
我的方法是否正确?如果是的话,我如何进一步改进? 如果我的方法错了?请提出一个更好的选择。
难道我们假设PropBot开始于(0,0)?我们假设坐标是以厘米为单位的吗?也就是说,(5,5)是否对应于原点右侧5厘米,上面5厘米? –
@JimMischel从(0,0)开始,确实是Bot面向+ x方向。单位是厘米也是,因为当你尝试用上述假设评估给定的输入时,你会得到给定的输出结果。这证明它以厘米为单位。 –
你试过回溯吗? 2^24似乎可以回溯。 – algrid