2011年6月26日 星期日

Problem 11244 Counting Stars,星星 ? 物體 ?

此題利用深度優先搜尋法即可解決問題。重點 C 語言程式碼如下:
struct map
{
    char line[104];
}data[104];


void findStar(int i, int j)
{
    isOne ++;
    data[i].line[j] = '.';
    
    if (i - 1 >= 0 && j - 1 >= 0 && data[i - 1].line[j - 1] == '*')
       findStar(i - 1, j - 1);
    if (j - 1 >= 0 && data[i].line[j - 1] == '*')
       findStar(i, j - 1);
    if (i + 1 < r && j - 1 >= 0 && data[i + 1].line[j - 1] == '*')
       findStar(i + 1, j - 1);
       
    if (i - 1 >= 0 && data[i - 1].line[j] == '*')
       findStar(i - 1, j);
    if (i + 1 < r && data[i + 1].line[j] == '*')
       findStar(i + 1, j);    
       
    if (i - 1 >= 0 && j + 1 < c && data[i - 1].line[j + 1] == '*')
       findStar(i - 1, j + 1);    
    if (j + 1 < c && data[i].line[j + 1] == '*')
       findStar(i, j + 1);    
    if (i + 1 < r && j + 1 < c && data[i + 1].line[j + 1] == '*')
       findStar(i + 1, j + 1);
}
而主程式內需如此呼叫:
for (i = 0; i < r; i ++)
{
    for (j = 0; j < c; j ++)
    {
        isOne = 0;
        if (data[i].line[j] == '*') findStar(i, j);
        if (isOne == 1) count ++;
    }
}
打完收假。
By David.K

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

2011年6月25日 星期六

Problem 10852 Less Prime,最小質數

此題先建立質數表 prime_table[] 後,利用以下 C 語言程式碼判斷即可:
j = 0;
while(prime_table[++ j] * 2 <= n);
p10852 問題連結 ACM 題庫目錄 回到首頁

Problem 10579 Fibonacci Numbers,超大費氏級數

此題需要利用大數相加即可, line 為 1001,len 由各位去拿捏這尺寸需要多少才夠,記得要宣告 int fn[line][len];。
重點 C 語言程式碼如下:
void createFn()
{
    int i, j, k;
    fn[0][0] = 0;
    fn[1][0] = 1;
    for(i = 2 ; i < line ; i ++)
    {
        for(j = 0 ; j < len ; j ++)
        {
            fn[i][j] += fn[i - 1][j] + fn[i - 2][j];
            if(fn[i][j] > 9)
            {
                fn[i][j + 1] += fn[i][j] / 10;
                fn[i][j] %= 10;
            }
        }
    }
}
By David.K

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