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

输出

3

更新于：2021年10月23日

199 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告