Chương trình Python tìm số phép toán đóng gói thanh kim loại vào container

Giả sử ta phải vận chuyển các thanh kim loại kích thước khác nhau. Container chỉ chứa thanh độ dài 1. Cho n thanh với độ dài trong danh sách. Phải cắt chia tất cả thanh thành đơn vị kích thước 1. Sau đó đóng gói vào container tốn 1 phép toán. Tìm tổng số phép toán.

Ví dụ: input_arr = [6, 3, 7], kết quả 22:

• Thanh 6 → 10 phép toán
• Thanh 3 → 4 phép toán
• Thanh 7 → 8 phép toán

Giải thuật

Sử dụng phân tích thừa số nguyên tố và tính tổng theo quy tắc đặc biệt.

1. Hàm prime_find(input_num): sàng Eratosthenes tìm số nguyên tố
2. Hàm chính solve(input_arr):
   • prime_nums := prime_find(10^6 + 100)
   • result := 0
   • Với mỗi value trong input_arr:
     • result += value
     • Phân tích value thành thừa số nguyên tố f_list
     • temp := 1
     • Với mỗi p_num trong f_list duyệt ngược:
       • result += temp
       • temp *= p_num
   • Trả về result

Ví dụ

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]:
            result += temp
            temp *= p_num
    return result

if __name__ == "__main__":
    print(solve([6, 3, 7]))

Input

[6, 3, 7]

Output

22