내가이 전에 요청했다 알고하지만 난 사람이 정말 쉬운 방법으로 나에게 이것을 설명 할 수있을 것입니다 희망 그래서 나는Java : 1 차원 그래프에서 구멍을 찾는 방법은 무엇입니까?
.... 답변에서 문제점 아무것도 만들 수 없습니다 :
을남자가 무한 길이의 벽 앞에 서 있습니다. 벽의 다른쪽에는 그가 가려고하는 마을이 있습니다. 벽의 어느 곳에서나 문이 있고 그 사람은 왼쪽이나 오른쪽으로 갈 수 있습니다.
선형 런타임이있는 알고리즘을 작성해야하는데이 문제를 해결할 수 없습니다 ... 어떤 도움도 대단히 감사합니다!
답변을 제공하지 않고 힌트를주는 방법을 모르는 경우.
당신은 "무한히 왼쪽"으로 갈 수 없다는 것을 알고 있습니다. 그러면 실패 할 때까지 문을 찾을 때까지 계속됩니다. 그거야.
문을 전혀 찾으려면 약간 왼쪽으로 가야하고, 다시 돌아가서 시작으로 돌아가서 오른쪽으로 조금 가면서 크고 큰 비트로 반복하십시오.
질문은 "비트"의 크기를 늘려서 전체 런타임, 즉 모든 "비트"의 합계가 문을 찾을 수있을만큼 커야한다고 생각할 수 있습니까? , 선형입니까?
당신은 이미 매번 1 씩 증가하면 복잡성이 너무 큽니다 (O (n^2) 실제로 지수가 아니라 너무 큽니다)라고 말한 적이 있습니다. 그러니 더 나은 진행을 찾으십시오. 더 좋은 진행과 결과를 가져올 것입니다.
그가 잘못한 길을 간다면 무한한 시간을 할애 할 수 있기 때문에 가능하지 않습니다. 그가 텔레포트 할 수 있다면 쉽습니다. N 미터마다 시작점의 반대쪽으로 텔레포트하고 N 미터를 검색 한 다음 다시 텔레포트하고 반복 할 수 있습니다. 이것은 선형 검색이됩니다.
나는 OP가 왼쪽이나 오른쪽으로 움직일 수 있다고 가정하고 있습니다. 한 걸음 물러 난 후에는 더 이상 오른쪽으로 나아갈 수 없습니다. – Bart
남자가 좌우로 번갈아 가면서 간격이 증가하면 그는 결국 게이트를 쳐야합니다. 그러나 이것이 "선형 런타임"을 준수하는지는 알 수 없습니다. 여기
무슨 뜻인지의 예입니다1. he goes 1 km left
2. he goes 2 km right, being 1 km right of where he started
3. he goes 3 km left, being 2 km left of where he started
4. he goes 4 km right, being 2 km right of where he started
5. he goes 6 km left, being 4 km left of where he started
6. he goes 8 km right, being 4 km right of where he started
이 알고리즘에 대한 내 생각이지만, 나는 가능한 많은 최적화가 확신합니다.
런타임이 거리에 비례하면 선형이 아닙니다. 여기서 O (n²) 시간이 필요합니다. –
그는 양쪽을 시도해야합니다. 그러나, 그가 각 방향으로 일정한 길이만큼만 움직인다면, 그것은 "화가 Schlemiel"문제가 될 것입니다. 그는 지수 함수로 각 방향으로 걷는 새로운 길이를 늘려야하므로 어림 쇄 탐색 시간이 선형이됩니다. 세부 사항과 복잡성 공식으로 변환하는 방법을 연습해야합니다.
첫 번째 생각은 사람이 Archimedean spiral의 원래 위치를 중심으로 이동한다는 것입니다. 구멍이 나선형의 연속 된 두 회전 사이의 거리보다 크다고 가정하면, 남자는 결국 그것을 발견 할 것입니다.
또한 답변을 살펴보십시오 this question
나선의 길이는 반경에서도 여전히 2 차입니다. 나선을 1 차원으로 평평하게하면 이것이 크게 변하지 않을 것이라고 생각합니다. –
@ Paŭlo Ebermann : 사실. 그러나, 벽은 양방향이며, 나는 덜 - 2 차적인 방식으로 그것을 탐구하는 방법을 생각할 수 없다. 나선형은 실제로 한 번만 각 벽의 위치 (직교 좌표 또는 극좌표의 관점에서)를 탐색하는 트릭입니다. – MarcoS
OP는 1 차원 그래프를 지정했습니다. 나는 그 벽이 바닥에서 수직으로 뻗어 나가고 있으며, 그 사람이 왼쪽이나 오른쪽으로 걷고 바닥에서 문을 찾는다는 생각이 있다고 생각합니다. – Cephron
이 숙제입니까? 이 경우 태그를 붙이십시오. 지금까지 무엇을 시도 했습니까? 그리고 이미 이에 대한 꽤 좋은 답변이 있습니다. 너는 무엇을 이해하지 못 했는가? – Bart
이 문제의 시간 단위는 무엇입니까? 한 걸음?또는 같은 방향으로 임의의 수의 단계가 있습니까? –
네, 숙제 태그를 만들었습니다. 한 방향으로 가면 영원히 탐색 할 수있는 기회가 있기 때문에 왼쪽과 오른쪽으로 번갈아 가야한다는 것을 이해합니다. 그래서 나는 한 걸음 더 왼쪽으로 두 걸음 가고 오른쪽으로 ... 그런 다음 당신은 기하 급수적 인 런타임을 얻습니다. 누군가는 당신이 지수 나선형을 사용해야한다고 썼지 만 그 의미가 거의 또는 전혀 모른다. – Chris