아이디어: 삼중항 -> 방향성 그래프 -> 두 노드의 경로 찾기 -> 행렬 곱셈 또는 Floyd-Warshal.

예를 들어 획득한 외환 가격은 다음과 같습니다.

첫 번째 줄은 1위안이 0.116파운드로 교환될 수 있음을 나타냅니다. 각 트리플 (c1, c2, r)은 두 개의 가중치 가장자리인 c1 -> c2 weighted r 및 c2 -> c1 weighted 1/r에 해당합니다. 이 인용문은 실제로 방향성 그래프를 제공합니다.

여기에서는 주어진 삼중항이 모순으로 이어지지 않고 방향 그래프가 연결되어 있다고 가정합니다(이해할 수 없음). 이 유향 그래프는 가중치 인접 행렬로 작성되었습니다.

행렬 요소 A[i,j]는 i 통화 1단위로 교환할 수 있는 j 통화 단위 수를 나타냅니다. 매트릭스의 0은 현재 환율을 알 수 없음을 나타냅니다.

행렬 곱셈

행렬을 곱하면A 이러한 0 요소를 점차적으로 제거할 수 있습니다. 그러나 일반적인 행렬 곱셈에서 내적을 계산하는 추가 작업은 "0보다 큰 첫 번째 숫자를 얻거나 그렇지 않은 경우 0을 얻습니다"라는 연산으로 대체되어야 합니다. 예: (1,2,3).(0,3,2) = first_positive(1*0, 2*3, 3*2) = 6.

A의 거듭제곱을 계산하려면 "환율 곱셈"을 사용하세요. A^k은 최대 k-1 단계로 변환된 환율 테이블을 나타내며 A^k에 0이 없을 때까지 계산이 계속됩니다. n 통화가 있는 경우 최대 A^(n-1)까지 계산됩니다.

A^3:

A^3의 첫 번째 줄을 보면 모든 통화의 위안화 가격 비교가 나와 있습니다. 두 통화의 비교는 RMB와의 비교 몫입니다. 따라서 실제로는 A의 첫 번째 행을 사용하여 처음부터 계산에 참여합니다. A[1] * A * ... * A (最多n-1次), 행의 모든 ​​요소가 0이 아닐 때까지 행 벡터와 행렬을 곱할 때마다. 이 계산의 복잡성은 O(n³)입니다.

플로이드-워샬

최단 경로 알고리즘 Floyd-Warshal에서 재귀 관계를 조정하면 이 질문의 환율 변환에도 사용할 수 있습니다. Floyd-Warshal의 복잡도는 Θ(n³)입니다. 따라서 행렬 곱셈이 더 빠를 수 있습니다.

두 알고리즘 모두 환율 행렬을 저장해야 하므로 공간 복잡도는 Θ(n²)입니다.

트리플 배열이 제공되면 x->y 환율 계산을 위한 최적 솔루션 생성: 방향 그래프 최단 경로 알고리즘

매번 다른 삼중 배열을 제공하는 경우 방향 그래프 경로 찾기 알고리즘이라는 하나의 결과만 얻으면 됩니다

튜플은 dict의 키로 사용될 수 있습니다

위 알고리즘 중 일부는 작성하기가 매우 복잡합니다. 간단한 알고리즘을 작성해 보겠습니다.

테스트 결과는 다음과 같습니다.

여기서 사용되는 것은 통화 이름의 고유성입니다. 두 통화는 함께 결합될 때 고유해야 합니다.