資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學從 Python 中 gcd() 函式中找到原始數字
假設我們有一個數組 A，其中給出了另一個數組中每對元素的最大公約數 (GCD)，我們需要找到用於計算給定 GCD 陣列的原始數字。
因此，如果輸入類似於 A = [6, 1, 1, 13]，則輸出將為 [13, 6]，因為 gcd(13, 13) 為 13，gcd(13, 6) 為 1，gcd(6, 13) 為 1，gcd(6, 6) 為 6
為了解決這個問題，我們將遵循以下步驟：
n := A 的大小
將陣列 A 按降序排序
occurrence := 一個大小為 A[0] 並填充為 0 的陣列
對於 i 從 0 到 n，執行：
occurrence[A[i]] := occurrence[A[i]] + 1
size := n 的平方根的整數部分
res := 一個大小與 A 相同並填充為 0 的陣列
l := 0
對於 i 從 0 到 n，執行：
如果 occurrence[A[i]] > 0，則：
res[l] := A[i]
occurrence[res[l]] := occurrence[res[l]] - 1
l := l + 1
對於 j 從 0 到 l，執行：
如果 i 不等於 j，則：
g := gcd(A[i], res[j])
occurrence[g] := occurrence[g] - 2
返回 res[從索引 0 到 size]
示例
讓我們來看下面的實現以更好地理解：
from math import sqrt, gcd def get_actual_array(A): n = len(A) A.sort(reverse = True) occurrence = [0 for i in range(A[0] + 1)] for i in range(n): occurrence[A[i]] += 1 size = int(sqrt(n)) res = [0 for i in range(len(A))] l = 0 for i in range(n): if (occurrence[A[i]] > 0): res[l] = A[i] occurrence[res[l]] -= 1 l += 1 for j in range(l): if (i != j): g = gcd(A[i], res[j]) occurrence[g] -= 2 return res[:size] A = [6, 1, 1, 13] print(get_actual_array(A))
輸入
[6, 1, 1, 13]
輸出
[13, 6]
更新於：2020年8月25日
156 次瀏覽
廣告