Thuật toán tìm số Armstrong trong Python

Lap trinh c++ Python

Số Armstrong là gì?

Số Armstrong là một số tự nhiên mà tổng lập phương các chữ số của nó bằng chính nó. Ví dụ, số 153 là một số Armstrong vì 1^3 + 5^3 + 3^3 = 153.

Thuật toán tìm số Armstrong

Dưới đây là hai thuật toán phổ biến để tìm các số Armstrong:

  1. Thuật toán Brute Force (Vét cạn):
    • Bước 1: Lặp qua tất cả các số từ 1 đến n.
    • Bước 2: Đối với mỗi số, phân tách các chữ số và tính tổng lập phương của chúng.
    • Bước 3: So sánh tổng với số ban đầu. Nếu bằng nhau, in ra số đó là số Armstrong.
    • Bước 4: Lặp lại các bước trên cho các số tiếp theo cho đến khi đạt đến số n.
  2. Thuật toán Optimized (Tối ưu hóa):
    • Bước 1: Xác định số chữ số của số n.
    • Bước 2: Lặp qua tất cả các số từ 1 đến n.
    • Bước 3: Đối với mỗi số, phân tách các chữ số và tính tổng lập phương của chúng.
    • Bước 4: So sánh tổng với số ban đầu. Nếu bằng nhau, in ra số đó là số Armstrong.
    • Bước 5: Lặp lại các bước trên cho các số tiếp theo cho đến khi đạt đến số n.

Thuật toán tối ưu hóa trên là cải tiến của phương pháp vét cạn bằng cách xác định số chữ số trước và chỉ lặp qua các số có số chữ số tương ứng. Điều này giúp giảm thiểu số lượng lặp lại cần thiết và tăng tốc độ thực thi thuật toán.

Cài đặt Thuật toán Brute Force (Vét cạn)

def is_armstrong_number(n):
    num_str = str(n)
    num_digits = len(num_str)
    armstrong_sum = 0
    
    for digit in num_str:
        armstrong_sum += int(digit) ** num_digits
    
    if armstrong_sum == n:
        return True
    else:
        return False

# Kiểm tra các số từ 1 đến 1000
for i in range(1, 1001):
    if is_armstrong_number(i):
        print(i)

Cài đặt Thuật toán Optimized (Tối ưu hóa)

def is_armstrong_number(n):
    num_str = str(n)
    num_digits = len(num_str)
    armstrong_sum = 0
    
    for digit in num_str:
        armstrong_sum += int(digit) ** num_digits
    
    if armstrong_sum == n:
        return True
    else:
        return False

def find_armstrong_numbers(n):
    for i in range(1, n+1):
        if is_armstrong_number(i):
            print(i)

# Tìm các số Armstrong trong khoảng từ 1 đến 1000
find_armstrong_numbers(1000)

Cả hai thuật toán trên đều sử dụng phương pháp phân tách các chữ số của số và tính tổng lập phương. Thuật toán tối ưu hóa giúp giảm số lần lặp qua các số không cần thiết, tăng tốc độ thực thi thuật toán.

Độ phức tạp

Độ phức tạp của hai thuật toán tìm số Armstrong:

  1. Thuật toán Brute Force:
    • Độ phức tạp thời gian: O(n * d), trong đó n là số lượng số cần kiểm tra và d là số chữ số lớn nhất trong các số đó. Vì với mỗi số, chúng ta phải phân tách và tính tổng lập phương của các chữ số.
    • Độ phức tạp không gian: O(1), vì thuật toán không sử dụng bất kỳ cấu trúc dữ liệu bổ sung.
  2. Thuật toán Optimized:
    • Độ phức tạp thời gian: O(n * k), trong đó n là số lượng số cần kiểm tra và k là số chữ số của số lớn nhất trong các số đó. Bước xác định số chữ số tốn O(k) và vòng lặp chạy từ 1 đến n.
    • Độ phức tạp không gian: O(1), vì thuật toán không sử dụng bất kỳ cấu trúc dữ liệu bổ sung.

Tổng quát, cả hai thuật toán có độ phức tạp tương tự, tuy nhiên thuật toán Optimized có thể chạy nhanh hơn trong các trường hợp số lượng số cần kiểm tra lớn hoặc số chữ số của số lớn nhất lớn.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *