我一直在練習算法,我發現一個花了幾周,仍然無法解決。我不能拿出一個完整的算法,但我一直在努力的想法,我寫了到目前爲止的代碼是:在笛卡兒座標系中找到最接近的點,並移動到另一個點上?
注:的我共享綜合性的問題的原因是不恩龍的問題,而我可能首先誤解了問題的主要觀點。
問題
一個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