ตัวเลขน่าเกลียดคือตัวเลขที่มีตัวประกอบเฉพาะคือ 2, 3 หรือ 5 จาก 1 ถึง 15 มี 11 ตัวน่าเกลียด 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15 ตัวเลข 7 , 11, 13 ไม่น่าเกลียดเพราะเป็นจำนวนเฉพาะ เลข 14 ไม่ได้น่าเกลียดเพราะเลข 7 จะมาในปัจจัยเฉพาะ สมมุติว่าเราต้องการตรวจสอบเลขน่าเกลียดตัวที่ 10 ค่าจะเป็น 12
ให้เราดูอัลกอริธึมต่อไปนี้เพื่อรับแนวคิด -
อัลกอริทึม
getUglyNumbers(n)
ป้อนข้อมูล − จำนวนเทอม
ผลผลิต − ค้นหาหมายเลขน่าเกลียดที่ 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
ตัวอย่าง (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;
} อินพุต
10
ผลลัพธ์
Enter term: 10 10th Ugly number is: 12
