특정 작업을 사용하여 해당 와이어의 시작과 끝을 찾는 데 필요한 이동 횟수

Question

내 교수는 우리가 휴일에 생각할 문제를 주었지만 해결할 수있는 올바른 방법이 있는지 확신하지 못했습니다.

문제는 다음과 같습니다. 지점 A에서 지점 B로가는 N 개의 와이어 (1 ≤N ≤ 10^6)가 있지만 어느 와이어 끝이 어떤 와이어 시작에 해당하는지 알 수 없습니다. 점 A와 B

연결 와이어 사이

• 여행이 파악하는 방법은 세 가지가 있습니다. (이는 와이어의 서브 세트를 가져 와서 단 하나의 결말로 엔딩을 사용할 수 있도록 연결 함을 의미합니다)
• 전선이 연결되었는지 테스트합니다. (예를 들어, 일부 전선이 A 지점에 연결되어 있고 B 지점에서 연결된 케이블 중 하나에 전원이 공급되는 경우 연결되어있는 케이블도 볼 수 있습니다)

목표는 A와 B 사이에 필요한 최소 이동 횟수를 계산하는 것입니다.

예 우리는 2 개의 여행을 필요로하는 3 개의 철사를 위해 : 우리는 두 개의 철사를 연결하고 세 번째를 호출합니다. 그리고 다른 지점으로 여행하고 어떤 철사가 다른 두 전선에 연결되어 있지 않은지 테스트합니다. 그러면 A 와이어 여야합니다. 그런 다음 A를 다른 와이어와 연결하고 B 라하고 다시 여행합니다. 이제 우리는 A에 연결된 케이블을 찾아야합니다.이 케이블은 B이어야하며 세 번째 케이블은 C이어야합니다.

불행히도 일부 N의 경우 어떤 선이 어떤 것인지 예를 들어 알 수 없습니다. N = 2 인 경우 (N = 2가 유일한 경우). N = 1은 제로 이동을 의미합니다.

이 문제를 해결하는 방법에 대한 조언은 대단히 감사하겠습니다.

Answer 1

이렇게 전에 비슷한 퍼즐을 풀었습니다.

N> 2 인 경우 은 항상 2 번 이동하여 전선을 확인할 수 있습니다. 와이어의 홀수를 들어

---

(내가 예를 들어 5 사용)

A B C D E 
| | | | | 

| | | | | 
1 2 3 4 5 

는 먼저 다음과 같이 와이어를 연결합니다 (지금은 "번호"옆에있는 가정) :

A B C D E 
| | | | | 

|__| |__| | 
1 2 3 4 5 

그런 다음 "알파벳"쪽으로 이동하십시오. 다른 쪽 끝에 연결되어 있지 않은 것을 발견 할 수있는 하나의 와이어가 있어야합니다 (다른 쪽 끝의 전도도로 테스트). 그것은 A라고 가정합니다. 그러면 A가 5에 해당합니다.

그런 다음 연결된 끝에있는 쌍을 찾습니다. B-C와 D-E가 연결되어 있다고 가정 해 봅시다. 그런 다음 A-B, C-D를 연결하십시오. 이렇게하면 5에서 E로 이동하는 하나의 긴 와이어가 생깁니다.

A__B C__D E 
| | | | | 
\__________  
      \ 
|__| |__| | 
1 2 3 4 5 

"번호"면으로 돌아갑니다. 이면의 모든 연결을 끊으십시오.

A__B C__D E 
| | | | | 
\__________  
      \ 
| | | | | 
1 2 3 4 5 

그런 다음 어떤 전선이 5와 함께 작동하는지 테스트하십시오.3이라고 가정하면 3이 B에 해당한다는 것을 알게됩니다. 3-4가 원래 연결되어 있고 B-C가 쌍인 경우 4가 C에 해당한다는 것을 알게됩니다. 3-4를 다시 연결하십시오.

A__B C__D E 
| | | | | 
\___\__\___  
    \ \ \ 
| | |__| | 
1 2 3 4 5 

당신은 이상한 전선의 어떤 번호를 식별하기 위해이 방법을 사용할 수 있습니다 5 1 또는 2 행위의, 당신은 D에 해당하는 알고, E.

에 따라서 다른 참조.

---

와이어의 짝수를 들어,이 홀수 유사합니다

1 단계, 2 와이어 알파벳 옆으로

A B C D E F 
| | | | | | 

|__| |__| | | 
1 2 3 4 5 6 

여행 연결되지 않은이 같은 일을하지만, 떠나 시간이 경과하면 다른 전선에 전도되지 않는 2 개의 전선 (A와 F로 가정)을 찾아야합니다. 그 중 하나는 손대지 마십시오 (F로 가정). 홀수 방식으로 설명한대로 A와 E를 연결하십시오.

숫자로 돌아 가기 당신은 5 또는 6 일 (6 가정) 다른 와이어 수행되지 찾을 것입니다, 당신은 그래서, 당신은 6-F, 5-A를 확인

A__B C__D E F 
| | | | | | 
\__________ | 
      \ | 
|__| |__| | | 
1 2 3 4 5 6 

F.

에 해당 알고있다. 나머지는 위에서 설명한 홀수 번호의 경우입니다. 당신은, 적어도 하나 이상의 와이어를 반입 할 수, 또는하지 않는

---

그리고는 예, N = 2, 그들을 식별 할 수있는 방법은없는 것 같다 당신과 함께 다이오드 : P 실제로