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