数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Python程序：计算将多个金属棒装入容器所需的步骤数
假设我们需要运输几根不同尺寸的金属棒。但运输容器长度有限，只能容纳长度为1的金属棒。我们有n根金属棒，它们的长度已知。为了将所有金属棒放入容器，我们必须切割并分割所有金属棒，使其长度为单位长度。然后，我们将所有金属棒放入容器，这算作一次操作。我们需要找到必须对金属棒执行的操作次数。
例如，如果输入为 input_arr = [6, 3, 7]，则输出为 22
将长度为6的金属棒分割成长度为1的金属棒，需要执行10次操作。
将长度为3的金属棒分割成长度为1的金属棒，需要执行4次操作。
将长度为7的金属棒分割成长度为1的金属棒，需要执行8次操作。
为了解决这个问题，我们将遵循以下步骤：
定义一个函数 prime_find()。它将接收输入 input_num
prime_check := 一个新列表，大小为 floor((input_num-1)/2)，包含值为True的元素
对于 p_num 从 3 到 floor(sqrt(input_num)) + 1，步长为 2，执行以下操作：
如果 prime_check[floor((p_num-3)/2)] 不为零，则
对于 prime_check 中从 floor((p_num^2-3)/2) 到 p_num 的每个元素，执行以下操作：
prime_check[element] := 一个新列表，大小为 (floor(((input_num-p_num^2)/(2*p_num)) + 1))，包含值为False的元素
对于 i 从 0 到 floor((input_num - 1) / 2)，执行以下操作：
- 如果 prime_check[i] 为 True：
返回一个包含值 2 + 2 * i + 3 的列表
- 如果 prime_check[i] 为 True：
在主函数中，执行以下操作：
- prime_nums := prime_find(10^6 + 100)
- result := 0
- 对于 input_arr 中的每个值，执行以下操作：
- result := result + value
- f_list := 一个新列表
- 对于 prime_nums 中的每个 p_num，执行以下操作：
- 当 value % p_num == 0 时，执行以下操作：
- 将 p_num 添加到 f_list 的末尾
- value := floor(value / p_num)
- 如果 p_num^2 > value，则
- 如果 value > 1，则
- 将 value 添加到 f_list 的末尾
- 退出循环
- 如果 value > 1，则
- 当 value % p_num == 0 时，执行以下操作：
- temp := 1
- 对于 f_list 中的每个 p_num（逆序），执行以下操作：
- result := result + temp
- temp := temp * p_num
- 返回 result
示例
让我们来看下面的实现来更好地理解：
from math import floor,sqrt def prime_find(input_num): prime_check = [True]*((input_num-1)//2) for p_num in range(3,floor(sqrt(input_num))+1,2): if prime_check[(p_num-3)//2]: prime_check[(p_num**2-3)//2::p_num] = [False] * ((input_num-p_num**2)//(2*p_num) + 1) return [2]+[2*i+3 for i in range((input_num - 1) // 2) if prime_check[i]] def solve(input_arr): prime_nums = prime_find(10**6+100) result = 0 for value in input_arr: result += value f_list = [] for p_num in prime_nums: while value % p_num == 0: f_list.append(p_num) value //= p_num if p_num**2 > value: if value > 1: f_list.append(value) break temp = 1 for p_num in f_list[-1::-1]: result += temp temp *= p_num return result if __name__ == "__main__": print(solve([6, 3, 7]))
输入
[6, 3, 7]
输出
22
更新于：2021年5月18日
浏览量：160
广告