小蓝有 30 个数，在这些数中取出两个序号不同的数，有多少种取法取出的两个数的乘积大于等于 2022

问题描述

小蓝有 30 个数，分别为：99, 22, 51, 63, 72, 61, 20, 88, 40, 21, 63, 30, 11, 18, 99, 12, 93, 16, 7, 53, 64, 9, 28, 84, 34, 96, 52, 82, 51, 77 。
小蓝可以在这些数中取出两个序号不同的数，共有 30*29/2=435 种取法。
请问这 435 种取法中，有多少种取法取出的两个数的乘积大于等于 2022 。

答案提交

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

我的解题

分析

如果说直接解出这道题的话很简单，两个索引遍历一下，判断是否大于等于 2022，然后计数输出就行了。

但是呢，考虑到如果出了编程题，会限制运行时间、使用内存，那么就得对其进行性能优化了。

以下是我的思考：

1. 先进行降序排序，覆盖原来的列表。
2. 依旧需要两个索引遍历列表，但是遍历的右边界我们让它动态变化：引入变量 right，起始的时候就是取列表长度减一，在外层循环中右边界就是 right，内层循环便是 right+1；为什么需要让其动态变化呢？试着思考：是否存在一种情况，右索引变化的时候与左索引的数的乘积小于 2022 并且右索引没有到达右边界，这时右索引就不需要再进行下去了，没有必要，因为这是降序列表，右索引继续下去值仍然小于 2022，索引跳出内层右索引的循环进行下一轮外层循环。
3. 上述的判断二者乘积大于 2022 条件后需要引入一个变量计数，最后需要输出，这是我们需要的结果。

编程

细思的代码优化，平均总运行时长小于 1ms，大概在 900 微秒左右。（Python3.11.8 版本解释器）

# 定义一个包含数字的列表
num_lis = [99, 22, 51, 63, 72, 61, 20, 88, 40, 21, 63, 30, 11, 18, 99, 12, 93, 16, 7, 53, 64, 9, 28, 84, 34, 96, 52, 82, 51, 77]
# 进行降序排序
num_lis = sorted(num_lis, reverse=True)
count = 0
# 引入一个变量，记录右边界
right = len(num_lis) - 1
# 遍历列表中的每一个元素，使用变量 i 来索引
for i in range(0, right):
    # 遍历从 i+1 到 right 的元素，使用变量 j 来索引
    for j in range(i+1, right+1):
        # 判断乘积是否大于等于 2022
        if num_lis[i] * num_lis[j] >= 2022:
            count += 1
        else:
            # 乘积小于2022，更新 right 的值为 j，并跳出内层循环
            right = j
            break
# 输出 count 的值，即满足条件的数的个数
print(count)

思考了一下，想到左索引的下标不一定需要遍历到右边界减一，应当充分考虑到二数乘积为 2022，则如果二数大小相等，则应当是 int(sqrt(2022))，所以左索引只需要遍历到大于等于 int(sqrt(2022)) 的数即可。

以下是优化后的代码：

import math
# 定义一个包含数字的列表
num_lis = [99, 22, 51, 63, 72, 61, 20, 88, 40, 21, 63, 30, 11, 18, 99, 12, 93, 16, 7, 53, 64, 9, 28, 84, 34, 96, 52, 82, 51, 77]
# 进行降序排序
num_lis = sorted(num_lis, reverse=True)
count = 0
# 引入一个变量，记录右索引的右边界
right = len(num_lis) - 1
# 引入一个变量，记录左索引的右边界
left = [i for i,num in enumerate(num_lis) if num >= int(math.sqrt(2022))]
# 遍历列表中的每一个元素，使用变量 i 来索引
for i in range(0, left[-1]+1):
    # 遍历从 i+1 到 right 的元素，使用变量 j 来索引
    for j in range(i+1, right+1):
        # 判断乘积是否大于等于 2022
        if num_lis[i] * num_lis[j] >= 2022:
            count += 1
        else:
            # 乘积小于2022，更新 right 的值为 j，并跳出内层循环
            right = j
            break
# 输出 count 的值，即满足条件的数的个数
print(count)

运行时间 1ms 左右，运行结果也是 189 。

AI 解题

qwen-max

提问

请用Python解决以下问题，要求极致的代码性能优化：

小蓝有 30 个数，分别为：99, 22, 51, 63, 72, 61, 20, 88, 40, 21, 63, 30, 11, 18, 99, 12, 93, 16, 7, 53, 64, 9, 28, 84, 34, 96, 52, 82, 51, 77 。

小蓝可以在这些数中取出两个序号不同的数，共有 30*29/2=435 种取法。

请问这 435 种取法中，有多少种取法取出的两个数的乘积大于等于 2022 。

回答

为了实现高性能计算，我们可以使用NumPy库来进行向量化操作。以下是一个优化的解决方案：

import numpy as np

# 小蓝的30个数
numbers = np.array([99, 22, 51, 63, 72, 61, 20, 88, 40, 21, 63, 30, 11, 18, 99, 12, 93, 16, 7, 53, 64, 9, 28, 84, 34, 96, 52, 82, 51, 77])

# 使用numpy计算所有可能的组合及其乘积
combinations = np.outer(numbers, numbers)
valid_combinations = combinations[np.triu_indices_from(combinations, k=1)]  # 取上三角部分（不包括对角线）以排除重复组合

# 计算乘积大于等于2022的组合数量
count = np.sum(valid_combinations >= 2022)

print("共有", count, "种取法取出的两个数的乘积大于等于2022")

注意：这个方法在处理大数据集时非常高效，但对于较小的数据集（如这里的30个数），其优势可能并不明显，因为数组创建和遍历的开销相对于数据量来说较大。如果数据量确实很小，可以考虑使用纯Python列表推导式或双层循环来求解。但在实际应用中，尤其是处理大规模数据时，优先考虑向量化运算能显著提升性能。

我的评价：运行结果是 189 没错，6 行代码解决问题？！！！现在的大模型不要太离谱啊！用的还是向量法。运行时间 1ms 左右，厉害的嘞。

讯飞星火 V3.0

提问

请用Python解决以下问题，要求极致的代码性能优化：

小蓝有 30 个数，分别为：99, 22, 51, 63, 72, 61, 20, 88, 40, 21, 63, 30, 11, 18, 99, 12, 93, 16, 7, 53, 64, 9, 28, 84, 34, 96, 52, 82, 51, 77 。

小蓝可以在这些数中取出两个序号不同的数，共有 30*29/2=435 种取法。

请问这 435 种取法中，有多少种取法取出的两个数的乘积大于等于 2022 。

回答

def count_ways(nums, target):
    count = 0
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] * nums[j] >= target:
                count += 1
    return count

nums = [99, 22, 51, 63, 72, 61, 20, 88, 40, 21, 63, 30, 11, 18, 99, 12, 93, 16, 7, 53, 64, 9, 28, 84, 34, 96, 52, 82, 51, 77]
target = 2022
result = count_ways(nums, target)
print(result)

我的评价：运行结果 189，看了看代码并没有什么特别的，就是常规操作，不过封装成函数了。

总结

看了看几个大模型给出代码，想到了几个算法：双指针、向量法（大受震撼）……

其它几个大模型没给出来的是结果有错……

不过通义确实牛，深深震撼到了 。

---

存档地址：https://www.yuque.com/worthstudy/study/sdsx459ulgzcgi4o