尋找丑數(shù)

該算法非常直觀，代碼也非常簡(jiǎn)潔，但最大的問(wèn)題我們每個(gè)整數(shù)都需要計(jì)算。即使一個(gè)數(shù)字不是丑數(shù)，我們還是需要對(duì)它做求余數(shù)和除法操作。因此該算法很耗時(shí)。

???????? 接下來(lái)我們換一種思路來(lái)分析這個(gè)問(wèn)題，試圖只計(jì)算丑數(shù)，而不在非丑數(shù)的整數(shù)上花費(fèi)時(shí)間。根據(jù)丑數(shù)的定義，丑數(shù)應(yīng)該是另一個(gè)丑數(shù)乘以2、3或者5的結(jié)果（1除外）。因此我們可以創(chuàng)建一個(gè)數(shù)組，里面的數(shù)字是排好序的丑數(shù)。里面的每一個(gè)丑數(shù)是前面的丑數(shù)乘以2、3或者5得到的。

這種思路的關(guān)鍵在于怎樣確保數(shù)組里面的丑數(shù)是排好序的。我們假設(shè)數(shù)組中已經(jīng)有若干個(gè)丑數(shù)，排好序后存在數(shù)組中。我們把現(xiàn)有的最大丑數(shù)記做M?，F(xiàn)在我們來(lái)生成下一個(gè)丑數(shù)，該丑數(shù)肯定是前面某一個(gè)丑數(shù)乘以2、3或者5的結(jié)果。我們首先考慮把已有的每個(gè)丑數(shù)乘以2。在乘以2的時(shí)候，能得到若干個(gè)結(jié)果小于或等于M的。由于我們是按照順序生成的，小于或者等于M肯定已經(jīng)在數(shù)組中了，我們不需再次考慮；我們還會(huì)得到若干個(gè)大于M的結(jié)果，但我們只需要第一個(gè)大于M的結(jié)果，因?yàn)槲覀兿Ｍ髷?shù)是按從小到大順序生成的，其他更大的結(jié)果我們以后再說(shuō)。我們把得到的第一個(gè)乘以2后大于M的結(jié)果，記為M₂。同樣我們把已有的每一個(gè)丑數(shù)乘以3和5，能得到第一個(gè)大于M的結(jié)果M₃和M₅。那么下一個(gè)丑數(shù)應(yīng)該是M₂、M₃和M₅三個(gè)數(shù)的最小者。

前面我們分析的時(shí)候，提到把已有的每個(gè)丑數(shù)分別都乘以2、3和5，事實(shí)上是不需要的，因?yàn)橐延械某髷?shù)是按順序存在數(shù)組中的。對(duì)乘以2而言，肯定存在某一個(gè)丑數(shù)T₂，排在它之前的每一個(gè)丑數(shù)乘以2得到的結(jié)果都會(huì)小于已有最大的丑數(shù)，在它之后的每一個(gè)丑數(shù)乘以2得到的結(jié)果都會(huì)太大。我們只需要記下這個(gè)丑數(shù)的位置，同時(shí)每次生成新的丑數(shù)的時(shí)候，去更新這個(gè)T₂。對(duì)乘以3和5而言，存在著同樣的T₃和T₅。

#include 
using namespace std;
int Min(int num1, int num2, int num3)
{
	int min=(num1>n;
         cout<