C ++中的丑数

丑数是那些其主要因子为2、3或5的数字。从1到15,有11丑数1、2、3、4、5、6、8、9、10、12、15。数字7 ,11、13并不丑陋,因为它们是素数。数字14并不丑陋,因为它的主要因素是7。因此,假设我们要检查第十个丑陋的数字。该值为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;
   //查找下一个倍数为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