좌표에서 좌표로의 재귀 경로

StackOverflow https://stackoverflow.com/questions/2231772

  •  19-09-2019
  •  | 
  •  

문제

나는 일하고있다 자바 수업에 대한 과제와 나는이 문제를 해결하는 방법을 잘 모를 것입니다. 나는 그것이 나를 위해 완성되기를 원하지 않지만 올바른 방향으로 시작하게합니다. 나는 프로그램의 재귀 부분이 대부분 확실하지 않습니다. 나는 프로그래밍에 능숙하지 않습니다.

문제:

북동쪽 경로는 위로 올라가서 2 차원 그리드에서 얻습니다. 예를 들어, 아래 그림에는 1,0에서 0,1의 두 가지 경로가 있습니다. 첫 번째는 (1,0), (0,0), (0,1)이고 두 번째는 (1,0), (1,1), (0,1)입니다. (0,1)에서 다른 지점까지의 북동쪽 경로가 없습니다. 또한 (1,1)에서 (0,1)까지 북동쪽 경로가 하나 있습니다. 숫자 (그리드의 크기 - 10 이하)와 시작 위치 및 엔딩 위치를 취하고 모든 "북동부"경로를 재귀 적으로 계산하는 프로그램을 작성해야합니다.

0,0 0,1

1,0 1,1

Prog2.dat 파일로 읽고 있습니다

그리드 크기로 먼저 읽은 다음 시작 좌표와 마무리 좌표로 읽습니다. 예를 들어:

5

3 0

1 3

하나의 파일이어야하므로 방법을 사용하겠습니다. 누군가 나를 시작하거나 이미 게시 한 비슷한 질문으로 나를 지시 할 수 있다면 감사하겠습니다.

도움이 되었습니까?

해결책

재귀와 관련된 한 가지 해결책은 목적지에 가장 가까워 질 경로에서 다음 지점을 찾는 것입니다. 그 지점이 있으면 동일한 방법을 사용하여 다음으로 가장 가까운 지점을 파악하십시오. 이 과정 (또는 재귀)은 목적지에 도착했을 때 종료됩니다.

당신은 다음과 같은 일을 시도 할 수 있습니다.

void getNextPoint(Point start, Point end, Path currentPath) {
    //if start == end, then you're done with the recursion
    //and you have a valid path

    //if you can move east from start to get closer to end
    //Point next = east of start
    //append next to the currentPath
    //then call getNextPoint(next, end, currentPath)

    //if you can move north from start to get closer to end
    //Point next = north of start
    //append next to currentPath
    //then call getNextPoint(next, end, currentPath)
}

나는 많은 세부 사항을 생략하여 자신을 위해 더 많은 것을 알아낼 수 있지만 재귀 사용에 대한 한 가지 방법입니다. 본질적으로, 당신은 길을 구축하고 있습니다. 당신은 당신의 경로를 관리하는 방법을 알아 내야하지만, 경로를 밀고 포인트를 튀어 나와서 포인트를 팝업 할 수 있어야 할 가능성이 있습니다.

다른 팁

이것은 도움이 될 수 있습니다 :

http://en.wikipedia.org/wiki/binomial_theorem

읽기 시작하십시오 파스칼의 삼각형.

주어진 시작 위치 (x0, y0) 및 주어진 결말 위치 (x1, y1)의 경우, 그리드에서 북쪽 또는 동쪽으로 이동하는 것으로 제한하면 최소 길이의 경로는 정확하게 (x1-x0) 단계로 구성됩니다. 동쪽과 (Y1-Y0)는 어느 순서로 북쪽으로 향합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top