Ugly Numbers（醜數）Dynamic Programming（動态規劃

所謂的醜數是指隻包含質因子2、3和5的數。例如前10個醜數分别為 1, 2, 3, 4, 5, 6, 8, 9, 10, 12. 然後要求求得第n個醜數。

解決此問題主要有兩個問題：暴力求解，即挨個找醜數，直到找到第n個，另一種方法就是使用動态規劃。

1.簡單方法

要檢查數字是否為醜數，将該數字除以2、3和5的最大可除幂。如果數字變為1，則它是醜陋的數字，否則不是。例如，讓我們看看如何檢查300是否為醜數。 2的最大可除幂是4，将300除以4後得到75。3的最大可除幂是3，将75除以3後得到25。5的最大可除幂是25，将25除以25後得到1 由于最後得到1，是以300是醜數。代碼如下

class Solution{
//将a除b的最大整數倍
 public int maxDivide(int a, int b)
    {
        while (a % b == 0)
        {
            a = a / b;
        }
        return a;
    }
   //判斷 number是否為醜數
    public int isUgly(int number)
    {
        number = maxDivide(number,2);
        number = maxDivide(number,3);
        number = maxDivide(number,5);
        return (number == 1)? 1 : 0;
    }
    //得到第n個醜數
    public int getUglyNo(int n)
    {
        int i = 1;
        int count = 1;
        while (n > count)
        {
            i++;
            if(isUgly(i) == 1)
            {
                count++;
            }       
        }
         return i;
    }
 }
           

1. 動态規劃

   因為每個數字隻能除以2、3、5，是以一種檢視序的方法是将序列分成三組，如下所示：

   （1）1×2、2×2、3×2、4×2、5×2，…

   （2）1×3、2×3、3×3、4×3、5×3，…

   （3）1×5、2×5、3×5、4×5、5×5，…

   我們可以發現每個子序列都是醜數序列本身（1、2、3、4、5，…）乘以2、3、5。然後我們使用類似的歸并方法作為歸并排序，從三個序列中擷取每個醜數 子序列。 每一步我們都選擇最小的一步，然後再向前邁一步。

public class UglyNumber {
   public int getNthUglyNumber(int n)
   {
       int ugly[] = new int[n];
       int i2 = 0;
       int i3 = 0;
       int i5 = 0;
       int next_mul_of_2 = 2;
       int next_mul_of_3 = 3;
       int next_mul_of_5 = 5;
       int next_ugly_num = 1;
       ugly[0] = 1;
       for(int i = 1; i < n; i++)
       {
           next_ugly_num = Math.min(next_mul_of_2,Math.min(next_mul_of_3,next_mul_of_5));
           ugly[i] = next_ugly_num;
           if(next_ugly_num == next_mul_of_2)
           {
               i2 = i2 + 1；
               next_mul_of_2 = ugly[i2] * 2;
           }
           if(next_ugly_num == next_mul_of_3)
           {
               i3 = i3 + 1;
               next_mul_of_3 = ugly[i3] * 3;
           }
           if(next_ugly_num == next_mul_of_5)
           {
               i5 = i5 + 1;
               next_mul_of_5 = ugly[i5]*5;
           }
       }
       return next_ugly_num;
   }
}
           

下面是工作方式的示範，求第150個醜數

initialize
   ugly[] =  | 1 |
   i2 =  i3 = i5 = 0;

First iteration
   ugly[1] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
            = Min(2, 3, 5)
            = 2
   ugly[] =  | 1 | 2 |
   i2 = 1,  i3 = i5 = 0  (i2 got incremented ) 

Second iteration
    ugly[2] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
             = Min(4, 3, 5)
             = 3
    ugly[] =  | 1 | 2 | 3 |
    i2 = 1,  i3 =  1, i5 = 0  (i3 got incremented ) 

Third iteration
    ugly[3] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
             = Min(4, 6, 5)
             = 4
    ugly[] =  | 1 | 2 | 3 |  4 |
    i2 = 2,  i3 =  1, i5 = 0  (i2 got incremented )

Fourth iteration
    ugly[4] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
              = Min(6, 6, 5)
              = 5
    ugly[] =  | 1 | 2 | 3 |  4 | 5 |
    i2 = 2,  i3 =  1, i5 = 1  (i5 got incremented )

Fifth iteration
    ugly[4] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
              = Min(6, 6, 10)
              = 6
    ugly[] =  | 1 | 2 | 3 |  4 | 5 | 6 |
    i2 = 3,  i3 =  2, i5 = 1  (i2 and i3 got incremented )

Will continue same way till I < 150