Số xấu là những số có thừa số nguyên tố là 2, 3 hoặc 5. Từ 1 đến 15, có 11 số xấu là 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15. Các số 7 , 11, 13 không xấu vì chúng là số nguyên tố. Số 14 không xấu vì trong hệ số nguyên tố của nó, số 7 sẽ xuất hiện. Vì vậy, giả sử chúng ta muốn kiểm tra số thứ 10 xấu xí. Giá trị sẽ là 12.
Hãy cùng chúng tôi xem thuật toán sau để có ý tưởng -
Thuật toán
getUglyNumbers (n)
Đầu vào - Số lượng điều khoản.
Đầu ra - Tìm số xấu thứ n.
Begin define array named uglyNum of size n i2 := 0, i3 := 0, i5 := 0 next2mul := 2, next3mul := 3, next5Mul := 5 next := 1 ugluNum[0] := 1 for i := 1 to n, do next := minimum of next2Mul, next3Mul and next5Mul uglyNum[i] := next if next = next2Mul, then i2 := i2 + 1 next2mul := uglyNum[i2] * 2 if next = next3Mul, then i3 := i3 + 1 next3mul := uglyNum[i3] * 3 if next = next5Mul, then i5 := i5 + 1 next5mul := uglyNum[i5] * 5 done return next End
Ví dụ (C ++)
# include<iostream>
using namespace std;
int min(int x, int y, int z){ //find smallest among three numbers
if(x < y){
if(x < z)
return x;
else
return z;
}
else{
if(y < z)
return y;
else
return z;
}
}
int getUglyNum(int n){
int uglyNum[n]; // To store ugly numbers
int i2 = 0, i3 = 0, i5 = 0;
//find next multiple as 1*2, 1*3, 1*5
int next2mul = 2;
int next3mul = 3;
int next5mul = 5;
int next = 1; //initially the ugly number is 1
uglyNum[0] = 1;
for (int i=1; i<n; i++){
next = min(next2mul, next3mul, next5mul); //find next ugly number
uglyNum[i] = next;
if (next == next2mul){
i2++; //increase iterator of ugly numbers whose factor is 2
next2mul = uglyNum[i2]*2;
}
if (next == next3mul){
i3++; //increase iterator of ugly numbers whose factor is 3
next3mul = uglyNum[i3]*3;
}
if (next == next5mul){
i5++; //increase iterator of ugly numbers whose factor is 5
next5mul = uglyNum[i5]*5;
}
}
return next; //the nth ugly number
}
int main(){
int n;
cout << "Enter term: "; cin >> n;
cout << n << "th Ugly number is: " << getUglyNum(n)<< endl;
} Đầu vào
10
Đầu ra
Enter term: 10 10th Ugly number is: 12