สมมติว่าเรามีตารางอัตราแลกเปลี่ยนสกุลเงิน N x N หนึ่งตาราง เราต้องตรวจสอบว่ามีลำดับของการซื้อขายที่เราสามารถทำได้หรือไม่ ตอนนี้เริ่มต้นด้วยจำนวน A ของสกุลเงินใด ๆ เราสามารถจบลงด้วยจำนวนเงินที่มากกว่า A ของสกุลเงินนั้น ไม่มีค่าใช้จ่ายในการทำธุรกรรมและเรายังสามารถแลกเปลี่ยนปริมาณที่เป็นเศษส่วนได้อีกด้วย
ค่าที่รายการ [I, j] ในเมทริกซ์นี้แสดงถึงจำนวนสกุลเงิน j ที่เราสามารถซื้อได้ด้วยหน่วยสกุลเงิน i หนึ่งหน่วย ตอนนี้ให้พิจารณาสกุลเงิน 0 คือ USD 1 คือ CAD และ 2 คือ EUR เราสามารถทำการเก็งกำไรได้ดังต่อไปนี้ -
-
ขาย 1 CAD สำหรับ 0.65 EUR
-
ขาย 0.65 EUR ในราคา 0.7865 USD (0.65 * 1.21)
-
ขาย 0.7865 USD ในราคา 1.00672 CAD (0.65 * 1.21 * 1.28)
ดังนั้นหากอินพุตเป็นแบบ
| 1 | 1.28 | 0.82 |
| 0.78 | 1 | 0.65 |
| 1.21 | 1.55 | 1 |
แล้วผลลัพธ์จะเป็น True
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
สำหรับฉันในช่วง 0 ถึงขนาดของเมทริกซ์ ทำ
-
สำหรับ j ในช่วง 0 ถึงขนาดของเมทริกซ์[0] ให้ทำ
-
matrix[i,j] :=−log ค่าฐาน 2 ของ (เมทริกซ์[I, j])
-
-
-
v :=จำนวนแถวของเมทริกซ์
-
สำหรับ k ในช่วง 0 ถึง v ทำ
-
สำหรับผมอยู่ในช่วง 0 ถึง v ทำ
-
สำหรับ j ในช่วง 0 ถึง v ทำ
-
เมทริกซ์[I, j] :=ขั้นต่ำของเมทริกซ์[I, j] และ (เมทริกซ์[I, k] + เมทริกซ์[k,j])
-
-
-
-
คืนค่า True หากรายการใดในแนวทแยงของเมทริกซ์ไม่เป็นศูนย์
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
หลาม
import math class Solution: def solve(self, matrix): for i in range(len(matrix)): for j in range(len(matrix[0])): matrix[i][j] = −math.log(matrix[i][j], 2) v = len(matrix) for k in range(0, v): for i in range(0, v): for j in range(0, v): matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j]) return any(matrix[i][i] < 0 for i in range(len(matrix))) ob = Solution() matrix = [ [1, 1.28, 0.82], [0.78, 1, 0.65], [1.21, 1.55, 1] ] print(ob.solve(matrix))
อินพุต
matrix = [ [1, 1.28, 0.82], [0.78, 1, 0.65], [1.21, 1.55, 1] ]
ผลลัพธ์
True
