Số Xấu (Ugly Numbers)

Giới thiệu

Số xấu (ugly number) là số chỉ có thừa số nguyên tố 2, 3, 5. Tìm số xấu thứ n (1 được coi là số xấu đầu tiên).

Đầu vào và Đầu ra

Đầu vào: n = 10
Đầu ra: Số xấu thứ 10 là 12 (dãy: 1,2,3,4,5,6,8,9,10,12).

Thuật toán Quy hoạch động

Duy trì ba con trỏ i2, i3, i5 chỉ đến số xấu tiếp theo nhân với 2,3,5. Mỗi bước lấy min(next2, next3, next5) làm số xấu mới, cập nhật con trỏ tương ứng.

getUglyNumbers(n)
Begin
    uglyNum[0..n-1]
    i2=i3=i5=0
    next2=2, next3=3, next5=5
    next=1; uglyNum[0]=1
    for i=1 to n-1 do
        next = min(next2, next3, next5)
        uglyNum[i] = next
        if next == next2 then i2++; next2 = uglyNum[i2]*2
        if next == next3 then i3++; next3 = uglyNum[i3]*3
        if next == next5 then i5++; next5 = uglyNum[i5]*5
    done
    return next
End

Ví dụ C++

#include <iostream>
using namespace std;

int min3(int x, int y, int z) {
    if (x < y) return (x < z) ? x : z;
    else return (y < z) ? y : z;
}

int getUglyNum(int n) {
    int uglyNum[n];
    int i2=0, i3=0, i5=0;
    int next2=2, next3=3, next5=5;
    int next=1;
    uglyNum[0]=1;
    for (int i=1; i> n;
    cout << n << "th Ugly number: " << getUglyNum(n) << endl;
    return 0;
}

Kết quả

Nhập thứ tự: 10
10th Ugly number: 12