Problem 879 Circuit Nets，電絡網

同 793 Network Connections，在此不贅述。

By David.K

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

Problem 793 Network Connections，網絡連接

此題使用 Dijkstra 演算法即可解決。

Dijkstra 演算法可以參考：http://zh.wikipedia.org/wiki/%E8%BF%AA%E7%A7%91%E6%96%AF%E5%BD%BB%E7%AE%97%E6%B3%95

By David.K

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

Problem 10116 Robot Motion 機器人運動

這題其實也只要多建立一個相同大小的陣列紀錄步數以及重複步數值就可以了。

#define row 12
#define col 12

int step, r, c;

char motion[row][col];
int record[row][col];

void move(int x, int y)
{
   int i, j;
    record[x][y] = step ++;
    
    switch (motion[x][y])
 {
        case 'N':
            x --;
            break;
        case 'E':
            y ++;
            break;
        case 'W':
            y --;
            break;
        case 'S':
            x ++;
            break;
    }
    
    if (x < 0 || x >= r || y < 0 || y >= c)
    {
        printf("%d step(s) to exit\n", step - 1);
        return;
 }   
    if (record[x][y] != -1 )
    {
        int k = step - record[x][y];
     printf("%d step(s) before a loop of %d step(s)\n", step - k - 1, k);
  return;  
 }
 move(x, y);
 
}

最後在主程式內傳入開始的 x, y 座標即可。

By David.K

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

Problem 12019 Doom's Day Algorithm

先對 Doom's Day 做解釋。

這個神奇的方法就叫做 "Doomsday Algorithm"，詳細的原理就是… 每一年的二月的最後一天 (2/28 或 2/29)，和 4/4、6/6、8/8、10/10、12/12，和 9/5、5/9、7/11、11/7 (記憶口訣是 "我在 7-11 的工作時間是朝 9 晚 5″)，和 3/7 (二月最後一天的一星期後)，和 1/3 (西元年不可被 4 整除) 或 1/4 (可以被 4 整除)，這些日子的星期都是一樣的，這一天叫做 Doomsday，而上面這些日子就是一年中每個月的基準日，只要配合簡單的餘數運算就可以求出今年其他日子是星期幾啦。

但是如果要算其他年份，例如說去年的 Doomsday，怎麼辦呢 ? 因為 365 除以 7 會餘 1，也就是說每一個平常年 Doomsday 會跳一天，而閏年則會跳兩天；這樣一天，其他年份的 Doomsday 也就可以求出來，所以上面的算法也可以引申到其他年份啦。對於 19XX 年來說還有另一個速算法：先記住 1900 年的 Doomsday 是星期三；然後把 XX/12 的商和餘數，以及餘數除以 4 所得的商數，把這三個數字加起來以後，再除以 7，所得的餘數就是該年份 Doomsday 和星期三的相差數了。例如說 1937 年，XX = 37，37 / 12 商是 3 餘數是 1，1 /4 的商是 0，3 + 1 + 0 = 4，星期三再加 4 天就是星期天，也就是說 1937 年的 Doomsday 是星期天。

可是上面只有對 19xx 年有效啊，能推廣到其他的世紀去嗎 ? 其實是可以的，只要知道了該世紀的基準日就可以算了。經由觀察可以得知各世紀的 Doomsday 是以 "五三二日" 的循環在輪替，也就是說 1900 年是星期三，則 1800 年就是前一個，也就是星期五，而 2000 年就是星期二了。這就是世紀基準日的速記法。有了該世紀的基準日的話，就可以套用上一段所說的算法來計算該世紀任一天的星期了。

不過說實在的，上面這些步驟也確實太麻煩啦 !! 所以下面就有人發明了速算法：一樣是要先知道每個月的 Doomsday 基準日是那一天，然後算出你要求的日期和基準日差幾天，再把上面講的年份的那三個數字加起來，就加上該世紀 Doomsday 的星期，就是所求的那天是星期幾了。舉例來說，1937/7/7 (七七事變) 是星期幾呢 ? 先前提過，7/11 是 Doomsday，所以 7/7 就是 -4 的差距；37/12=3…1，1/4=0，-4 + 3 + 1 + 0 = 0；而 1900 年的 Doomsday 是星期三，再加上 0 天的差距，就是告訴我們 1937/7/7 是星期三。

以上引用自 http://blog.ijliao.info/archives/2004/04/07/321/

因為我們已經知道年份為 2011，而 2011 年 Doomsday 為星期一，其實也只要用一個陣列來加加減減就好了

char week[7][10] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
int month[13] = {-1 ,3, 28, 7, 4, 9, 6, 11, 8, 5, 10, 7, 12};

int find(int m, int d)
{
    int index = (d - month[m]) % 7;
    index = index % 7 < 0 ? index + 7: index;
    printf("%s\n", week[index]);
}

讀入月份和日期，呼叫 find(m, d) 即可。
By David.K

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

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題庫目錄
回首頁

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題庫目錄
回首頁