Python程式：查詢給定陣列中任意序列的最大大小，其中每對元素都滿足“友好”條件

假設我們有一個大小為n的序列nums。我們必須找到nums的子序列的最大大小，其中每對(p, q)都是友好對？當且僅當滿足以下至少一個條件時，一對被稱為友好對：1. p的不同質因數個數的奇偶性與q相同。例如，18有兩個不同的質因數：2和3。2. p的所有正因數之和的奇偶性與q相同。

因此，如果輸入類似於nums = [2,3,6,8]，則輸出將為3

為了解決這個問題，我們將遵循以下步驟：

n := nums的大小
定義三個空列表cnt、total、result
對於nums中的每個i，執行：
- count := 0, tot := 0
- prime := 一個新的列表
- 對於nums中的每個j，執行：
  - 如果(j mod k 對所有k在2到j的範圍內)為真，則
    - 將j插入prime的末尾
- 對於prime中的每個j，執行：
  - 如果i mod j為0，則
    - count := count + 1
- 如果count為偶數，則
  - 將'奇數'插入cnt的末尾
- 否則，
  - 將'偶數'插入cnt的末尾
- 對於1到i的每個j，執行：
  - 如果i mod j等於0，則
    - tot := tot + j
- 如果tot為奇數，則
  - 將'奇數'插入total的末尾
- 否則，
  - 將'偶數'插入total的末尾
對於0到n-2的每個i，執行：
- 對於i+1到n-1的每個j，執行：
  - 如果cnt[i]等於cnt[j]或total[i]等於total[j]，則
    - 將nums[i]插入result的末尾
    - 如果j等於n-2，則
      - 將nums[j]插入result的末尾
result := 從result的新集合中建立一個新的列表
返回result的大小

示例

讓我們看看下面的實現以更好地理解：

def solve(nums):
   n = len(nums)
   cnt = []
   total = []
   result = []
   for i in nums:
      count = 0
      tot = 0

      prime = []
      for j in nums:
         if all(j % k for k in range(2, j)) == True:
            prime.append(j)

      for j in prime:
         if i % j == 0:
            count += 1
      if count % 2:
         cnt.append('odd')
      else:
         cnt.append('even')

      for j in range(1,i+1):
         if i % j == 0:
            tot += j

      if tot % 2:
         total.append('odd')
      else:
         total.append('even')

   for i in range(n-1):
      for j in range(i+1, n):

         if cnt[i] == cnt[j] or total[i] == total[j]:
            result.append(nums[i])

            if j == n-1:
               result.append(nums[j])

   result = list(set(result))
   return len(result)

nums = [2,3,6,8]
print(solve(nums))

輸入

15, 3, 8

輸出

Arnab Chakraborty

更新於：2021年10月23日

199 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習