2010年5月11日 星期二

Problem 11621 Small Factors,最小因數

要先求出只有 2 和 3 因數的數值,將這些數值排序, C 語言程式碼如下:
int factor[1000] = {0}, index = 0, tmp, sIndex = 0;
void create()
{
int k;
long long int i, j;
for (i = 1; i < 2147483648LL; i *= 2)
for (j = 1; j < 2147483648LL; j *= 3)
{
if (i * j > 2147483648LL) break;
factor[index ++] = i * j;
for (k = index - 1; k >= 1; k --)
{
if (factor[k] < factor[k - 1])
{
tmp = factor[k];
factor[k] = factor[k - 1];
factor[k - 1] = tmp;
}
else break;
}
}
}

再來讀入一個 n 值,再 factor 陣列找出大於此數的最小數值,所以我們用「二分搜尋法」來實作,C 語言程式碼如下:
void location(int x, int low, int high)
{
sIndex = 0;
if (low > high) {sIndex = (low + high) / 2 + 1; return ;}
else
{
int mid = 0;
mid = (low + high) / 2;
if (x == factor[mid]) {sIndex = mid; return ;}
else if (x < factor[mid]) location(x, low, mid - 1);
else location(x, mid + 1, high);
}
}

最後,只需在主程式呼叫:
location(n, 0, index - 1);
printf("%d\n", factor[sIndex]);

By David.K

p11621題目連結
回ACM題庫目錄
回首頁

沒有留言: