[UVa]136:Ugly Numbers

這題要算第1500個Ugly Number是誰，
假設我現在要算第N項，
那麼我就找前面這N-1項中找出：
「乘2會大於第N-1項的那項」以及「乘3會大於第N-1項的那項」還有「乘5會大於第N-1項的那項」。
找出來後比較他們三個的大小，
最小的就是第N項。

接著要找N+1項，
我再從前N項中一樣找出：
「乘2會大於第N項的那項」以及「乘3會大於第N項的那項」還有「乘5會大於第N項的那項」。
那其實你再找「乘2會大於第N項的那項」，
你可以從「乘2會大於第N-1項的那項」開始往後搜，
就不用再從第0項開始搜。
找「乘3會大於第N項的那項」還有「乘5會大於第N項的那項」也可以比照辦理、以此類推。

這樣就可以很快速的找到第1500個Ugly Number了。^^

[C](0.020)

	#include<stdio.h>
	#define min( a, b ) ( (a < b)? a : b )
	int main()
	{
	int uglynumbers[1505] = {1};
	int m2 = 0, m3 = 0, m5 = 0;
	int i = 1;
	int pre_n = 1;
	for( i = 1 ; i < 1500 ; i++ )
	{
	for( ; m2 < i ; m2++ )
	if( uglynumbers[m2]*2 > pre_n )
	break;
	for( ; m3 < i ; m3++ )
	if( uglynumbers[m3]*3 > pre_n )
	break;
	for( ; m5 < i ; m5++ )
	if( uglynumbers[m5]*5 > pre_n )
	break;
	pre_n = min( uglynumbers[m5]*5, min( uglynumbers[m2]*2 , uglynumbers[m3]*3 ) );
	uglynumbers[i] = pre_n;
	}
	printf( "The 1500'th ugly number is %d.\n", uglynumbers[1499] );
	system( "pause" );
	return 0;
	}

view raw UVa136.c hosted with ❤ by GitHub