Problem 190 Circle Through Three Points，通過三點的圓

ACM 190 的題目是讀取三個點的座標，利用這三個點算出圓的公式。
假設讀取點為 P1、P2、P3，在這裡的算法是求出兩條分別垂直於P1P2連線與P1P3連線的直線方程式，L12與L13，如上圖所示。

求L12時，先求出P1P2連線的中點，再求出L12的斜率。

中點座標分別為 C12x = (P1x+P2x)/2, C12y = (P1y+P2y)/2，

斜率為 m12 = -(P2x-P1x)/(P2y-P1y)。

所以 L12 的直線公式為 y = m12 * (x - C12x) + C12y

L13 的計算方式類似，L13 的直線公式為 y = m13 * (x - C13x) + C13y

這時就可以求L12與L13兩條線的交點，這個交點 C 就是圓心。

求解L12與L13 聯立方程式，得圓心座標(x, y)

x = (C13y-C12y-m13*C13x+m12*C12x) / (m12-m13)
y = m12 * (x-C12x) + C12y

半徑 r 為 (x,y) 到 (P1x,P1y) 的距離。
這部份的C語言程式碼如下：

c12x = (x1+x2)/2;
c12y = (y1+y2)/2;
c13x = (x1+x3)/2;
c13y = (y1+y3)/2;
cx = (c13y-c12y-m13*c13x+m12*c12x)/(m12-m13);
cy = m12*(cx-c12x)+c12y;
r = dist(cx,cy,x1,y1);
printf("(x %c %.3f)^2 + ", cx>=0?'-':'+', cx>=0?cx:-cx);
printf("(y %c %.3f)^2 = %.3f^2\n", cy>=0?'-':'+', cy>=0?cy:-cy, r);
printf("x^2 + y^2 %c %.3fx", cx>=0?'-':'+', cx>=0?2*cx:-2*cx);
printf(" %c %.3fy", cy>=0?'-':'+', cy>=0?2*cy:-2*cy);
e1 = cx*cx + cy*cy -r*r;
printf(" %c %.3f = 0\n\n", e1>=0?'+':'-', e1>=0?e1:-e1);

要特別注意的是斜率的計算，因為遇到P1P2或P1P3為水平線時，其垂直線的斜率會有除以零的錯誤，所以這裡用了交換的方式，換成另外一個點。m12的C語言程式碼如下，m13也用類似的方法。

if (y2==y1)
{
    temp = x1;
    x1 = x3;
    x3 = temp;
    temp = y1;
    y1 = y3;
    y3 = temp;
}
m12 = -(x2-x1)/(y2-y1);

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

Problem 216 Getting in Line，連線作業

這個問題有點像是銷售員旅行問題(Travelling Salesman Problem, TSP)，但是不用回到出發點，也就是不用將最後一點與第一點再連接，解決 TSP 的方法很多，這裡的題目特別點出最多只有八台電腦要連結，所以可能的解答只有 8! = 40320 種方法，所以最簡單的方式就是將每個可能的答案都算出來，將最小的解答顯示出來，就OK啦。
在這裡，我又用到了回溯的方法，在C語言主程式中的初始呼叫如下：

for (i=0;i<n;i++)
{
    computer[0] = i;
    makeConn(0);
}

然後，makeConn(0)會去呼叫makeConn(1)，呼叫前先將連線的 computer[1]也設定下一個，因為不能重複，所以要用 i_in_conn 來處理，等到了makeConn(7)，表示八台電腦都設完了，就計算一下連線長度，再將最小的解答儲存，這樣就可以了。 makeConn 回溯的程式碼如下，這裡的 minlength, opttour, computer 都是全域變數：

void makeConn(int level)
{
    int i, j, i_in_conn;
    double len;
    if (level == n-1)
    {
        len = connLength(); /* your function to calculate the connection length */
        if (minlength > len)
        {
            minlength = len;
            for (j=0;j<n;j++)
                opttour[j] = computer[j];
        }
    }
    else
    {
        for (i=0;i<n;i++)
        {
            i_in_conn = 0;
            for (j=0;j<=level;j++)
                if (computer[j]==i)
                    i_in_conn = 1;
            if (!i_in_conn)
            {
                computer[level+1] = i;
                makeConn(level+1);
            }
        }
    }
}

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

Problem 127 "Accordian" Patience，風琴手撲克牌遊戲

這題的ACM題目是個撲克牌遊戲，看起來有點複雜，本來想用人工方式，按照他所說的規則玩一下。後來想到，愈複雜的規則，如果電腦跑對了，就一定是對的。人跑對了，還不見得是對的，因為人眼睛有時會看不清楚。
題目是你攤開一列 52 張撲克牌，從左邊開始看，任何一張牌和它的左邊(或左邊第三張)的花色(或數字)相同，就拿起來，放在左邊(或左邊第三張)那張牌的上面。每次都只看最上面那張，每放完一張牌，要把空位(如果有空位)補起來，並從頭來過。
如果有多張牌可以拿起，每次優先拿起最左邊的那張。如果可以放在左邊，也可以放在左邊第三張，則選擇放在左邊第三張上面。記住，每放一張，都要從頭來過。
本解題的虛擬碼如下：

step 1: do
step 2:    look through the 2~52 cards
step 3:       compare i card with (i-3) card
step 4:       if the two cards match color or rank
step 5:          move i card to the top of (i-3) card
step 6:          if i is empty, move the rest cards to its left side
step 7:          go back to step 2
step 8: until no more moving cards.

這題很適合運用C語言的結構，程式碼如下

typedef struct
{
    int num;
    char card[52][3];
} CardPile;
CardPile p[52];

一堆牌有 52 個位置(p[52])，每個位置可以放 52 張牌(p[i][0]為第i個位置的第一張)，同時有個計數器(p[i].num第i個位置的牌數)。
比較i 與 i-3 位置的牌，如下列程式碼，如果條件符合，將 i 疊的牌放到 i-3 那疊上面，清除 i 疊的值，同時更新兩疊的數量，如果第 i 疊數量是零，則要移動所有後面的牌。最後的 break 是用來進行從頭開始檢視的動作。

if (i>2 && (p[i].card[p[i].num-1][0]==p[i-3].card[p[i-3].num-1][0] ||
     p[i].card[p[i].num-1][1]==p[i-3].card[p[i-3].num-1][1]))
   strcpy(p[i-3].card[p[i-3].num], p[i].card[p[i].num-1]);
   strcpy(p[i].card[p[i].num-1], "");
   p[i].num--;
   p[i-3].num++;
   if (p[i].num==0)
   {
      for (j=i;j<51;j++)
      {
        p[j].num = p[j+1].num;
        for (k=0;k<p[j+1].num;k++)
        {
            strcpy(p[j].card[k], p[j+1].card[k]);
            strcpy(p[j+1].card[k], "");
        }
        p[j+1].num = 0;
      }
   }
   break;
}

簡單地修改上述的程式碼可以用來比較 i 與 i-1 兩疊牌的內容。
最後別忘了，一疊牌以上是用複數 piles 來顯示。
p127題目連結
回ACM題庫目錄
回首頁

Problem 105 The Skyline Problem，天際線問題

這個題目我之前使用邏輯方式企圖解算，可是總有些問題無法解決。記得有找到一個建議，使用height[10000]來紀錄每一個點的高度，今天總算有點時間，解解看，果然很方便。
以下的C語言程式碼是在讀入每個建築資訊後，用來修訂每一個點的建築高度，其中l, h, r 是讀取的輸入值。

for (i=l;i<r;i++)
    if (height[i] < h)
        height[i] = h;

讀完後，直接從高度current = 0開始，只要高度有變化，就列印出座標點與高度，很容易就做完了。程式碼如下：

if (height[i] != current)
{
   current = height[i]; 
   /* print a space if not the first output */
   printf("%d %d", i, current);
}

要注意有 presentation error問題，因為輸出不可以隨便加空白。
p105題目連結
回ACM題庫目錄
回首頁

Problem 10469 To Carry or not to Carry，進位或不進位

題目中所顯示的加法器，因為有錯誤，所以無法產生進位的動作。題目有兩個例子，一個是0100與0110的相加，結果為0010。另一個6+9=15的例子，是0110+1001=1111，所以綜合起來，這個加法器其實是個 XOR 的計算器。所以程式的輸出只要顯示 a^b 兩個數字 XOR 的結果，只不過題目提醒是要用 32 位元的 unsigned，因此宣告與讀取時，要使用 unsigned。
整個程式核心內容只有三行，不是開玩笑，真的就三行。C語言程式碼如下：

unsigned a, b;
while (scanf("%u%u", &a, &b)==2)
    printf("%u\n", a ^ b);

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

Problem 10034 Freckles 雀斑

這題是標準的最小伸展樹(Minimum Spanning Tree)問題(或稱為最小生成樹)，可以使用 Prim 或 Kruskal 演算法來解決，不需要自己再發明什麼新的方法。

這裡使用 Prim 的演算法，參考蔡宗翰譯的「演算法--使用C++虛擬碼」書中(碁峯資訊，2004年)，第四章貪婪演算法的方式，很快就可以完成。
在讀取雀斑輸入值之座標點後，你必須自行製作 W 距離矩陣，W 是全域變數，提供 prim 函數使用。另一個全域變數 F ，用來存放解答中相連的點。
prim 函數如下：

void prim(int m)
{
    int i,j,k,vnear;
    int nearest[SIZE];
    float distance[SIZE], Dmin;
    for (i=1; i<m; i++)
    {
        nearest[i] = 0; /* Start from v0 */
        distance[i] = W[0][i];
    }
    for (k=1;k<m;k++)
    {
        Dmin = inf;
        for (i=1;i<m;i++)
            if (0<=distance[i] && distance[i]<Dmin)
            {
                Dmin = distance[i];
                vnear = i;
            }
        F[k][0] = vnear;
        F[k][1] = nearest[vnear];
        
        distance[vnear] = -1;
        for (i=1;i<m;i++)
            if (W[i][vnear] < distance[i])
            {
                distance[i] = W[i][vnear];
                nearest[i] = vnear;
            }
    }
}

當完成10034 Freckles，ACM 10147 Highways (高速公路)與 ACM 10397 Connect the Campus(連接校園) 這兩題就可以順便輕鬆的解題了。
p10034題目連結
回ACM題庫目錄
回首頁

Problem 119 Greedy Gift Givers 貪心的送禮者

這題目中，每次送禮者最多十人，每個人送出一個數字的金額，平均分配給指定的人。題目的要求在計算每個送禮者到底是收了多少錢，或付出多少錢。
題目說是貪心的送禮者，就是說你要斤斤計較，到底誰賺誰賠，所以多收了就賺到了，少收了就賠了，那斤斤計較的過程就顯得有點貪心，這樣說，對嗎？管它的，寫程式吧。

這個ACM 題目是練習C語言結構的好機會，程式的結構定義如下，name是名字，mget是淨收入。

typedef struct
{
    char name[20];
    int mget;
} person;

由於輸入格式中，並未告知有多少案例，題目所列的示範是兩個案例，因此程式可以用

while (scanf("%d", &n)!= EOF)

來判斷是否還有下一個案例。
每次執行前，別忘了將所有人的變數設定為初設值。
在讀取每個人的付出時，就可以先計算每個人的淨支出，別忘了不能整除時，要將餘數留著，C語言程式碼如下所示。

scanf("%s%d%d", givename, &give_amount, &m);
if (strcmp(givename, P[k].name)==0)
{
    if (m!=0)
        P[k].mget -= give_amount;
    if (m!=0)
        P[k].mget += give_amount%m;
}

然後，讀取付給哪些人，使用 strcmp 進行姓名字串的比較，比較輸出為 0 時，表示兩個字串相等，這時就可以將那個人的收入進行累加，程式如下。

if (strcmp(getname, P[k].name)==0)
    P[k].mget += give_amount / m;

其實，程式是很簡單的，但是要注意一種狀況，就是有付出金額，分配人員的數量是零的情形，也就是上述程式碼 m 為零的情形，因為題目也沒說會有設定分配人數是零的情形 (很詐)，如果沒考慮這點，上傳就會收到 wrong answer，這種情形最ㄐㄧㄢˋ，誰曉得是為什麼錯。
另外，要注意輸出的案例與案例之間要空一行。
p119題目連結
回ACM題庫目錄
回首頁

如何進行指標 (pointer) 的傳址呼叫(call by reference) (下)

這篇文章介紹函數的傳址呼叫，本文的內容是關於指標變數存放位址的改變。

為什麼要改變指標存放的位址呢，這是個很好的問題，平時在主程式中使用 p = &i;就可以改變其位址值，但是我們要藉著函數呼叫來改變其內容，用途呢?例如你用函數傳入指標來取得新的變數的位址(例如：dequeue(v)呼叫)。但是，有一點要注意的是，指標的值，就像一般整數 int 的值，他們都是屬於傳值呼叫(call by value)的。沒錯，指標也是傳值呼叫。

在下列的C語言範例程式中，modify 收到一個指標 v，然後試著去改變其本身所存放的值，你可以從執行結果看到，ptr的值完全沒有改變，這是當然的，傳值呼叫嗎。要改變其值，必須使用傳址呼叫，所以在 modify2 函數中，注意到了嗎，傳進去的是 int **p ，因為傳進來的是指標變數本身所在的位址，而 **p 表示這個位址中的位址中的值是整數。還可以懂吧。

因此呼叫時，必須傳入指標變數本身的位址，如下所示：

modify2(&ptr);

從執行的結果可以看出，指標的值被函數改變了，好玩吧。

#include <stdio.h>
#include <stdlib.h>

int x=8;
void modify(int *v)
{
    v = &x;
}
void modify2(int **p)
{
    *p = &x;
}

int main(void)
{
    int i = 5, *ptr;
    ptr = &i;

    printf("Before: ptr=%p, *ptr=%d\n", ptr, *ptr);
    modify(ptr);
    printf("After: ptr=%p, *ptr=%d\n", ptr, *ptr);
    printf("Before: ptr=%p, *ptr=%d\n", ptr, *ptr);
    modify2(&ptr);
    printf("After: ptr=%p, *ptr=%d\n", ptr, *ptr);

    return 0;
}

程式的執行結果如下：

Before: ptr=0022FF74, *ptr=5
After: ptr=0022FF74, *ptr=5
Before: ptr=0022FF74, *ptr=5
After: ptr=00402000, *ptr=8

如何進行指標 (pointer) 的傳址呼叫(call by reference) (上)

這篇文章介紹函數的傳址呼叫，第一段是利用指標來改變其所指到位址的內容，
傳遞的是指標所存放的地址。第二段是改變指標變數所存放的位址，傳遞的是指標本身的所在的位址。

指標的所存放的內容是地址，通常是其他值的地址。
常見的宣告會告知其內容的地址中所存放值的型態，例如

int *ptr;

這表示ptr的內容地址所指到的地方存放著一個型態為 int 的值。
又例如

void *ptr;

這表示ptr的內容是一個地址，其地址中的值的型態尚未特別指出，暫時空著，
等到後來要用時，必須藉著 cast 的方式來表示其所指值的型態。

指標常用在函數的傳址呼叫(call by reference)，在下列的範例中，
函數 modify 傳入一個指標 p，而 *p=100;表示將100放入p所指的位址中。

所以當指標的地址是其他變數的位址時，自然就可以用相同的方式，
透過函數的傳址呼叫來改變其他變數的值。在第二段的modify 函數呼叫前，
我們使用 ptr = &i; 讓ptr 存放著 i 的位址，所以當呼叫modify(ptr);後，i 的值就被改變了。

#include <stdio.h>
#include <stdlib.h>

void modify(int *p)
{
  *p = 100;
}

int main(void)
{
  int i, *ptr;
  pp = &x;
  i = 5;

  printf("Before: i=%d\n", i);
  modify(&i);
  printf("After: i=%d\n", i);

  printf("Before: ptr=%p, *ptr=%d\n", ptr, *ptr);
  i = 20;
  ptr = &i;
  modify(ptr);
  printf("After: ptr=%p, *ptr=%d, &i=%p, i=%d\n", ptr, *ptr, &i, i);

  return 0;
}

程式的執行結果如下：

   Before: i=5
   After: i=100
   Before: ptr=0022FFA8, *ptr=0
   After: ptr=0022FF70, *ptr=100, &i=0022FF70, i=100

在第二段的內容中，將說明指標變數內容位址的改變方式。

C 程式設計期末作業，解題練習：解答

這個題目看起來複雜，其實不算難。有幾個關卡要解決，首先是要能讀入所有的佈雷資訊，使用二維字元陣列(亦稱為一維字串陣列)讀取檔案內容，然後逐一的判斷是要列印"*"或數字。下列的C語言程式碼逐一的檢討字元，看是要列印"*"或數字。

if (mine[i][j]=='.')
   fprintf(fptr2, "%d", calcMineNumber(i,j));
else
   fprintf(fptr2, "*");

這裡的calcMineNumber(i,j)是一個函數，負責計算第 i 列和第 j 行的週遭八個位置有多少是雷。其C語言完成碼如下。

int calcMineNumber(int i, int j)
{
    int sum=0;
    sum += addMine(i-1, j-1);
    sum += addMine(i-1, j);
    sum += addMine(i-1, j+1);
    sum += addMine(i, j-1);
    sum += addMine(i, j+1);
    sum += addMine(i+1, j-1);
    sum += addMine(i+1, j);
    sum += addMine(i+1, j+1);
    return sum;
}

這個函數的概念簡單清楚，只是加總外圍八個位置的佈雷情形。至於i,j合理與否並不考慮，這種模組式的考慮，可以將問題拆解成容易理解的程度。
這時addMine就是決定i,j是否合理的地方，其C語言程式碼如下。

int addMine(int i, int j)
{
    if (i<0||j<0||i>=row||j>=column)
        return 0;
    if (mine[i][j]=='*')
        return 1;
    else
        return 0;
    return 0;
}

希望大家在完成這個題目後，對問題的模組化能有進一步的體會。
期末作業題目
回到作業目錄
回到首頁

小考十 解答

這題以C語言練習使用命令列語法，最常見的主程式輸入參數如下，argc是參數的數量，argv是參數的值，為一維字串陣列，或看成二維字元陣列。

int main(int argc, char *argv[])

程式一開始必須要能判斷參數數量是否正確，否則程式會產生錯誤的情形。
獲得的參數可以使用atof轉換成double，及atoi轉換成int，剩下的部份就簡單了，C語言程式碼解答如下，請參考。
解答A:

r = atof(argv[1]);
printf("Area of circle is %f\n", PI*r*r);
printf("Perimeter of circle is %f\n", 2*PI*r);

解答B:

n = atoi(argv[1]);
for (i=1; i<=n;i++)
    sum += i*i*i;
printf("Sum is %d\n", sum);

小考十題目
返回小考目錄
回到首頁

小考九(A) 解答

用C語言以二進位方式存入整數陣列，在PC Windows作業系統使用Dev-C++時，每個整數是四個位元組，而"Knowledge is power"有17個字元，因此必須存入五個整數，第一個整數的四個位元組用字串讀出來後，必須是"Know"，也就是十六進位的 4B 6E 6F 77，因為檔案中的整數位元組在被讀出時，是以反序方式進行，所以其整數值為776F6E4B，也就是2003791435，因此寫入時，就是寫入2003791435。
用相同的方法算出五個整數值，然後用二進位的方式寫入檔案quiz9.bin。
C語言主程式的全部程式碼如下，請參考。

 FILE *fptr;
 char str[80];
 int num[5] = {2003791435, 1734632812, 1936269413, 2003791904, 29285};
 fptr = fopen("quiz9.bin", "wb");
 fwrite(num, sizeof(int), 5, fptr);
 fclose(fptr);
 fptr = fopen("quiz9.bin", "r");
 fread(str, sizeof(char), 80, fptr);
 fclose(fptr); 
 printf("%s\n", str); 

小考九(A)題目
返回小考目錄
回到首頁

小考十 題目

/* C programming Quiz 10 */
/*
題目
(A) 利用命令列引數接受一個 double r，以計算並列印出圓的面積與周長。
(B) 利用命令列引數接受一個整數n，以計算1*1*1+2*2*2+3*3*3+...+n*n*n的和，並列印出結果。
*/

解答下載
返回小考目錄
回到首頁

因應 UVa Online Judge 在IExplorer 的變形

看來UVa Online Judge 目前只支援 Firefox，在 IExplorer的畫面變的很擁擠。

為繼續使用UVa Online Judge，因應之道有二
一、安裝Firefox。
二、安裝 Ubuntu 到 Windows 上的 VirtualBox ，使用 Ubuntu 上的 Firefox 。
這篇的內容在教你完成第二個方法。
-------------------------------------------------------------

安裝 Ubuntu 到 VirtualBox 的步驟

主要內容：
VirtualBox 安裝於Windows環境 (Windows host)，Ubuntu安裝於VirtualBox中 (Linux guest)。

基本需求：
目前的實驗中，1GB的RAM，4GB的硬碟空間，應該是綽綽有餘。

安裝步驟：

一、下載：

(一)用Google找到VirtualBox 的網頁，按Download，點選 Binaries(all platforms)，目前的版本為VirtualBox 1.5.6。下載時，Platform選Windows x86，Language不動，預設為 Multi-language，勾選同意版權條款(I agree to the VirtualBox 1.5.6 License Agreement )，接著就可以下載安裝了。

(二)用Google找到Ubuntu的網頁，並在完成安裝VirtualBox後，參考http://wiki.ubuntu.org.tw/index.php/Ubuntu7.10Install在Virtual中安裝Ubuntu。

二、安裝設定VirtualBox：

(一)安裝完成VirtualBox，要先設定一個虛擬磁碟，在[檔案]->[虛擬磁碟管理器]的[硬碟]分頁中，新增一個約4GB的虛擬硬碟，可以選動態擴充映像檔或固定大小都可以。

(二)新增一個虛擬機器(Virtual machine)，名稱自訂，作業系統類別選 Linux 2.6。接下來為設定記憶體，256MB或512MB皆可，如果你的記憶體只有 1GB，建議你虛擬機器設定256MB。再下一步為選定硬碟檔，就是稍早在前一個步驟中設定的 .vdi 檔。

(三)完成設定後，在視窗的左邊就出現了一台虛擬機器，你可以選擇它，然後按：設定值，會出現如下畫面：

這時候選擇光碟，畫面如下，必須掛載光碟並選擇已經下載的ISO映像檔，至於其他的部份可以自己選定，例如設定使用軟碟、音效、網路、序列埠和USB等，等安裝完Ubuntu後，就可以使用這些硬體資源，分享資料夾部份，後面會再介紹。


(四)啟動虛擬機器，由於你的光碟是掛載著Ubuntu的映像檔，所以會直接由該光碟開機。開機之後的畫面會很快完成，任你感覺有了另一個作業系統在VirtualBox中執行，但是這真的只是執行而已，還沒有安裝Ubuntu，此時桌面會有一個Install的光碟檔案圖像，你必須點兩下進行安裝Ubuntu的工作。整個執行的步驟應該是非常簡單的，因為你使用的硬碟是虛擬硬碟，有關各項細節的設定，請參考安裝說明。建議使用英文語言，這樣在shell畫面時，資料夾會比較方便處理。其實中文也OK啦。

(五)重新啟動Ubuntu，記住你再重新啟動前，先將光碟掛載改成正常的光碟機，否則你會被問要如何開機。(如果沒有將Ubuntu的安裝iso檔卸載，你仍然可以選擇從硬碟開機。)之後，你必須輸入使用者帳號密碼，就可以進入Ubuntu畫面，如果你有記體體不足的問題，請先關掉佔用大量記憶體的程式(例如iexplorer)。

(六)在Ubuntu的Applications下選Accessories，選Terminal。這個Terminal的程式，就像Windows環境中的命令執行單元。請執行

sudo apt-get install build-essential

這個指令是讓你以管理員的身分，執行安裝程式發展環境的指令，他會再問你一次密碼，安裝完成後，你就可以編輯一個簡單的C語言程式 test.c，然後使用 gcc test.c -o test 來編譯，並用 ./test來執行。

(七)安裝 Guest Additions，這是個功能擴充的檔案，可以在Google code中下載，檔名為VirtualBox_OSE_GuestAdditions-1.5.4-0.exe。請先關閉你的虛擬機器與VirtualBox在安裝這個擴充檔。安裝完畢後，重新將VirtualBox的Ubuntu開機，你會感覺這個VirtualBox好用多了，此時，在Ubuntu的視窗最外層的工具列中，選[裝置]->[安裝客端額外功能]。你會在Ubuntu桌面發現一個光碟掛載檔，這時你必須在terminal中使用

cd /cdrom
sudo ./VBoxLinuxAdditions.run

指令安裝，安裝完，重開機。這樣你的外掛就有了。裝這個外掛的原因是要能與Windows進行檔案分享。

(八)在Ubuntu的視窗最外層的工具列中，選[裝置]->[分享資料夾]，如下畫面。此時你可以按右上角的新增來設定新的分享資料夾。這裡的名稱，要先記住。另外你也可以設定此資料夾紙能讓Ubuntu唯讀。

然後回到Terminal，使用指令 sudo mount -t vboxsf temp /home/liangk/D_TEMP，這裡的temp是分享資料夾的名稱，D_TEMP則是在Ubuntu中新建的資料夾。完成之後，Ubuntu和Windows就可以分享資料，以上圖為例，Windows使用D:\temp，而Ubuntu使用D_TEMP，其實這兩個資料夾是同一個。
　

C 程式設計期末作業，解題練習

作業內容：
本作業將使用C語言進行踩地雷遊戲的數字計算。

大部分的人都玩過踩地雷的遊戲，遊戲的開始是在一個M*N的陣列中佈有許多地雷，你必須將佈有地雷的地方插一個旗子，在沒有地雷的地方，填入這個格字的週遭(即上下左右斜上斜下等八個格子)佈有地雷的數字。下圖為Windows作業系統所附的遊戲畫面。在這個作業中，題目的輸入格式如下。題目中的 '*' 表示是地雷，'.' 表示不是地雷。題目第一列的兩個整數分別表示地雷矩陣的大小，亦即列數與行數。

17 36
*..*.**..........*.....*.........*..
.......*.....*.*......*.....*...**..
...**...............*...*.....*.....
........*...........*......**.*.....
.......*.....**..........*.....*..*.
...**............*...*.*.*.....*....
*...*.....**.*.*..*........*...**...
*...............*....*.....*........
.................*..*...........*...
....*...............**...**...*.....
*..**..*..*...........*.*....*.*...*
..**......*..........*.*.**...**....
.*.....*.............*..*...*.....*.
...*..**...*.*.**.....*......**.*.*.
....*.*.....*............**.........
..*...........*.*..*.**..*....**.**.
.*.*..**..**.....*...*...........*..

作業的輸出是以C語言計算所有非地雷點的週遭地雷數。有地雷的地方仍然印著 '*' ，沒地雷的地方則印著其週遭的地雷數。上述例題的答案如下所示。

*11*2**2100011212*10012*100111013*20
1123433*10001*2*211112*32101*212**20
001**112210011211002*312*11334*32210
00122112*10012210002*201222**3*31111
0012211*21001**1111122213*32223*21*1
111**211112233422*211*2*3*31103*4211
*213*20001**2*2*33*12231213*202**100
*201110001222122*3222*10002*20133200
11011100000000012*12*42012321112*100
1113*211111100001112**222**112*32111
*23**21*12*20000000134*3*5421*5*201*
23**312222*2000000002*4*4**223**2122
1*43213*2122212221002*43*322*44423*2
112*23**201*3*2**10012*223222**2*3*2
0123*3*31012*334321123322**113443432
12*32333112322*2*22*3**12*3101**3**1
1*3*11**11**11122*213*31111001223*31

解答下載
回到作業目錄
回到首頁

96 試題一

ISBN(International Standard Book Number)是一種世界共通的書籍編碼方法，世界上任何一本書籍之出版，皆有著唯一的一組ISBN碼。此碼由十個位數組成，每一位數可以為0~9的任何一個數字，或者為X，代表此位數為10；試寫出一個程式來判斷所輸入的ISBN碼是否為合法的。其判斷方法如下，首先，將此ISBN碼的十個位數分開，自左而右依次為第一位數，第二位數至第十位數，接著進行第一次的累加，使得第二位數成為第一位數到第二位數的和，第三位數為第一位數到第三位數的累加和，第十位數為第一位數到第十位數的累加和；進行完第一次的累加和後，接著再依照相同之方法進行第二次的累加動作，我們稱此時最後所求得之累加和為此ISBN碼之識別碼，倘若此識別碼為11的倍數，則此ISBN碼為合法的，故請輸出YES，反之請輸出NO。注意：為便於識別，在此ISBN碼中可能會插入'-'符號，此符號不具任何意義，可以直接忽略它。例如，若輸入之ISBN碼為013-162-959X，則其運算之過成如下表所示：

 ISBN碼      0 1 3  1  6  2  9  5   9  10(X)
第一次累加和  0 1 4  5 11 13 22 27  36  46
第二次累加和  0 1 5 10 21 34 56 83 119 165

經由計算可得其識別碼為165，乃是11之倍數，故此為一合法之ISBN碼，因此應該要輸出YES於螢幕上。

試題一解答
試題目錄
回到首頁

小考九(A) 題目

/* C programming Quiz 9A */
/*
題目
請儲存一組整數陣列，以二進位檔案模式寫入至"quiz9.bin"，並以純文字檔案模式讀出字串，並列印字串，讀出與列印的字串必須為"Knowledge is power"。
*/

解答下載
返回小考目錄
回到首頁

96 試題二

實踐大學高雄校區資管系96學年程式設計比賽試題

題二：亂數產生器

運用電腦進行模擬時經常用到亂數，產生虛擬亂數的方法之一是使用下列的公式

seed(x+1) = [seed(x) + STEP] % MOD

%是計算餘數。
此一公式可以產生0到MOD-1之間的數，這個公式有個問題，就是產生的亂數會週而復始，有相同的序列。減少這種情形必須慎選STEP和MOD兩數，以產生較佳的平均分配亂數，值在0與MOD-1間。

例如，如果STEP=3且MOD=5，這個公式將產生0、3、1、4、2的重複循環，每次循環，所有0到MOD-1之間的數字都會出現。此公式的一個特性是如果每次seed(x)都產生相同seed(x+1)，則每次循環都會產生平均分佈的虛擬亂數。

如果STEP=15且MOD=20，這個公式將產生0、15、10、5的重覆序列(如果seed設定不是零，則啟始值不從零開始)。這個STEP和MOD選擇就很糟，因為不是0和MOD-1之間的每個數字都出現。
你的程式就是決定是否選定的STEP和MOD會產生平均分配的虛擬亂數。
輸入值
每一行數入一對整數STEP和MOD，且 1 <= STEP, MOD <= 100,000
輸出值
每一行輸出包含STEP值佔1~10格向右調整，MOD值佔11~20格向右調整，印出Good Choice或Bad Choice從第25格開始，向左調整。當這個亂數產生了MOD個亂數時，包括了0至MOD-1之間的每個數字，則印出Good Choice，否則印出Bad Choice。在每個測試輸出後，你應該再列印一個空行。
範例輸入

3 5
15 20
63923 99999

範例輸出

         3         5     Good Choice
        15       20     Bad Choice
     63923     99999     Good Choice

試題二解答(即ACM problem 408解答)
試題目錄
回到首頁

Problem 408 Uniform Generator，平均隨機亂數產生器

這個題目要求每個亂數範圍內的數字若只出現一次，就是好的選擇。我直接想到用陣列來存放每個數字出現的次數，但是陣列要大到100000這麼大，使用C語言時，這就不是個好的辦法。後來我用了土方法，全部亂數產生一次(100000個對電腦來說，一下子就做完了)，所有數字加總的結果與公式做比對(公式就是上底加下底乘高除二)，不相等就是Bad choice。這個做法上傳ACM裁判系統後，也過關了。
重點C語言程式碼如下：

for (i=0;i<mod-1;i++)
{
    seed = (seed+step)%mod;
    sum += (double)seed;
}
if (((double)mod-1)*mod/2.0!=sum)
    isBad = 1;

程式設計比賽題目二
p408題目連結
回ACM題庫目錄
回首頁

C 程式設計作業八，結構使用

作業內容：
本作業將計算兩個圓的交點。

輸入的值為兩個圓的圓心及半徑，輸出為兩個圓的交點座標。你必須使用下列的結構

typedef struct
{
   double x, y;
} Point;

typedef struct
{
   Point center;
   double r;
} Circle;

輸入值的順序為 x1 y1 r1 x2 y2 r2，前三個數字為第一個圓的圓心(x1, y1)與半徑(r1)，後三個數字為第二個圓的圓心(x2, y2)與半徑(r2)，輸出的值為兩個交點的座標，精確度為兩位小數點，如果無交點，則印出 No cross points.

輸入範例：

1 0 2 -1 0 2
1 0 1 -1 0 1
1 0 0.5 -1 0 1

輸出範例：

The cross points are (0.00,1.73) and (0.00,-1.73).
The cross points is (0.00,0.00).
No cross points.

作業提示：
一、使用Google搜尋「兩圓交點」，以尋找公式求解。
二、或下載兩圓交點公式說明
解答下載
回到作業目錄
回到首頁

小考八(B) 解答

這題C語言小考重點在結構的練習，透過函數的呼叫來完成。C語言在主程式中使用函數如下

    printf("本月壽星學生為\n");
    happy_birthday(student, 5); 
    printf("全班平均成績最佳者為 %s\n", student[max_grade(student)].name);

函數完成的部份，其C語言程式碼如下：

void happy_birthday(struct data st[], int month)
{
    int i;
    for (i=0;i<8;i++)
        if (st[i].birthday.mm == month)
            printf("%s\n", st[i].name); 
} 
int max_grade(struct data st[])
{
    int i, index=0;
    float temp, max_avg=(st[0].eng+st[0].chi+st[0].math)/3.0;
    for (i=1;i<8;i++)
    { 
        temp=(st[i].eng+st[i].chi+st[i].math)/3.0;
        if (max_avg < temp)
        { 
            max_avg=temp; 
            index=i;
        } 
    } 
    return index; 
}

程式中可以定義一個SIZE以取代數字8。
陣列元素的取用 st[i].math 與 (st+i)->math 是相同的。
小考八(A)題目
返回小考目錄
回到首頁

小考八(A) 解答

這題C語言小考重點在結構的練習，透過函數的呼叫來完成。C語言在主程式中使用函數如下

printf("英文成績最佳的學生為 %s\n", student[max_eng(student)].name); 
printf("A 班數學平均成績為 %.2f\n", avg_math(student, 'A')); 
printf("B 班數學平均成績為 %.2f\n", avg_math(student, 'B'));

函數完成的部份，其C語言程式碼如下：

int max_eng(struct data st[])
{
    int i, index=0, max=st[0].eng;
    for (i=1;i<8;i++)
        if (max < st[i].eng)
        { 
            max=st[i].eng; 
            index=i;
        } 
    return index; 
} 
float avg_math(struct data st[], char ch)
{
    float sum=0;
    int i, total=0; 
    for (i=0;i<8;i++)
        if (st[i].classNo==ch)
        { 
            sum += st[i].math; 
            total++;
        } 
    return sum/total; 
} 

程式中可以定義一個SIZE以取代數字8。
陣列元素的取用 st[i].math 與 (st+i)->math 是相同的。
小考八(A)題目
返回小考目錄
回到首頁

C 程式設計作業七，指標之使用：解題

這題的重點是要熟悉指標的應用，但也只是簡單的指標。或許以後讀到C語言指標比實際自己用指標的機會還多，加上Java, VB, c#都不用指標，看到的機會也會變少，但是這種存放資料位址的觀念卻是每個程式語言都會用到的。
題目中有一個要注意的地方，就是在x1或y1為零的地方是沒有花的，所以計算起始點時要加入考量。xi,yi是for迴圈的起始點，如果可以整除10，則得到零，所以在 (test)?(true_result):(false_result) 的語法中，在x1不為零且可以整除時(相反則為X1為零或不可整除時)，由x1/10起算花的數目。
以下是C語言函數calcRose的解答。

void calcRose(int x1, int y1, int x2, int y2, int *rnum, int *ynum)
{
    int i, j, xi, yi;
    
    xi = x1%10||x1==0?x1/10+1:x1/10;
    yi = y1%10||y1==0?y1/10+1:y1/10;
    for (i=xi;i<=x2/10;i++)
        for (j=yi;j<=y2/10;j++)
            if (i%2)
                if (j%2)
                    (*ynum)++;
                else
                    (*rnum)++;
            else
                if (j%2)
                    (*rnum)++;
                else
                    (*ynum)++;
}

作業七題目
回到作業目錄
回到首頁

小考八(B) 題目

/* C Programming Quiz 8B */
/*
題目：
有一個表示學生國英數成績結構陣列如后所附。
請完成二個函數，其原型分別為
void happy_birthday(struct data [], int);
int max_grade(struct data []);
其功能可以
(1)列印某月份生日的學生姓名；
(2)傳回全班平均成績最高的學生的索引值 。
請完成函數，並依題目輸出要求，測試函數，
印出結果。
題目輸入：
八個學生資料如后所附。
題目輸出：
(1)印出本月壽星的學生姓名
(2)印出全班平均成績最高的學生姓名
*/

struct day
{
    int yy, mm, dd; /* 年、月、日 */ 
};
struct data
{
    char name[20];  /* 姓名 */ 
    struct day birthday;  /* 生日 */ 
    int chi, math, eng;   /* 國文、數學 與 英文成績 */ 
};
struct data student[8] = {{"Marry Hu", {77, 2, 3}, 89, 90, 79},
                              {"Tom Chen", {78, 12, 13}, 79, 69, 88},
                              {"Billy Wu", {77, 1, 30}, 81, 54, 66},
                              {"John Hsu", {77, 7, 22}, 69, 49, 70},
                              {"Tim Huang", {77, 3, 8}, 90, 62, 83},
                              {"Marry Chen", {78, 5, 27}, 78, 93, 91},
                              {"Tomas Chu", {77, 5, 18}, 80, 50, 68},
                              {"Ann Wang", {77, 9, 21}, 66, 79, 78}};

解答下載
返回小考目錄
回到首頁

小考八(A) 題目

/* C programming Quiz 8A */
/*
題目
有一個表示學生英數成績結構陣列如后所附。
請完成二個函數，其原型分別為
int max_eng(struct data []);
float avg_math(struct data [], char);
其功能可以
(1)傳回英文成績最佳學生的索引值；
(2)傳回某班數學平均成績 。
請完成函數，並依題目輸出要求，測試函數，
印出結果。

題目輸入：
八個學生資料如后所附。
題目輸出：
(1)印出英文成績最佳的學生
(2)印出 A 班和 B 班學生的數學平均成績
*/

struct day
{
    int yy, mm, dd; /* 年、月、日 */ 
};
struct data
{
    char name[20];  /* 姓名 */ 
    char classNo;   /* 班別 */ 
    struct day birthday;  /* 生日 */ 
    int math, eng;   /* 數學 與 英文成績 */ 
};
struct data student[8] = {{"Marry Hu", 'A', {77, 2, 3}, 89, 90},
                              {"Tom Chen", 'B', {78, 12, 13}, 79, 69},
                              {"Billy Wu", 'A', {77, 1, 30}, 81, 54},
                              {"John Hsu", 'A', {77, 7, 22}, 69, 49},
                              {"Tim Huang", 'B', {77, 3, 8}, 90, 62},
                              {"Marry Chen", 'B', {78, 6, 27}, 78, 93},
                              {"Tomas Chu", 'A', {77, 6, 18}, 80, 50},
                              {"Ann Wang", 'A', {77, 9, 21}, 66, 79}};

解答下載
返回小考目錄
回到首頁

Problem 369 Combinations，組合 C(n, m) 的計算

這題所要完成的C語言程式是計算組合，C(n, m)是指計算在n個物品中取出m個的方法數。如果寫成C(m, n)就表示m中取n的方法數。這題acm用的變數是以前者來表示。
題目中的數字範圍是 5 <= m <= n <= 100，組合的公式為
如果先算完N!，那結果就很難看了，因為答案將高達10的152次方，完成這麼大的數字乘法，就是一個挑戰。其實，這個題目可以不用這麼做。如果先化簡，那C語言的處理就會單純許多。例如，C(10, 7)或C(10, 3)是相等的，第一步的化簡可以變成(10*9*8)/(3*2*1)，第二步簡化時，分子分母再進一步相消，式子的計算就更簡單了，加上其題目都先告訴你答案會是小於32位元的整數，所以不用擔心數字太大。
首先，我們先進行第一步的化簡，算出分子項目數(與分母數相同)，並設定階乘的項目，C語言程式碼如下，其中Na是分子項陣列，Ma是分母項陣列：

aSize = (n-m > m) ? m : n-m;
for (i=0;i<aSize;i++)
{
   Na[i] = n-i;
   Ma[i] = i+1;
}

接者進行第二步的相消簡化，allOne為化簡為1的分母項數，nofactor為不能化簡的分母項數：

while (allOne<aSize && nofactor<aSize)
{
    nofactor = 0;
    for (i=0;i<aSize;i++)
    {
        j=1;
        allOne = 1;
        while (j<aSize)
        {
            if (Ma[j]==1)
                allOne++;
            else if (Na[i]%Ma[j]==0)
            {
                Na[i] /= Ma[j];
                Ma[j] = 1;
            }
            else
                nofactor++;
            j++;
        }
    }
}

最後再進行實際的乘除，即可算出成果。C語言程式碼可以輕鬆寫出。
p369題目連結
回ACM題庫目錄
回首頁

Problem 750 8 Queens Chess Problem，八個皇后的西洋棋問題

八個皇后的問題是演算法中最常見的問題，經常出現在回溯法(Backtracking)的範例中。在我們先前的ACM解題中，就出現過兩次，一次是在Problem 167 The Sultan's Successors，權位的繼承者，另一次就是前一個ACM解題：Problem 291 The House Of Santa Claus，聖誕老公公的房子。
回溯的一個重點使用遞迴呼叫，在C語言主程式中，使用

for (j=0;j<8;j++)
{
    column[0]=j;
    queens(0);
}

表示執行八次的queens(0)，這八次的執行都是從零開始，這裡的零代表著第一個皇后，這八次不一樣的地方在擺棋的方式，以column[0]=j;來表示第一列的皇后位置，八次，每次的第一列，皇后的位置都不一樣。所以這個題目的重點在以column[i]來代表第i列的皇后的位置，如果column[3]==5，表示第三列(row)的皇后放在第五行的位置。
在void queens(int i)的C語言函數中，只有下列簡單的內容

if (isPromising(i))
{
    if (i==7)
    {
        /* 這裡是排完八個皇后之後，要處理列印的地方 */
    }
    else
    {
        /* 這裡表示皇后沒放完，要繼續放 */
        for (j=0;j<7;j++)
        {
            column[i+1] = j;
            queens(i+1);
        }
    }
}

上面的C語言程式重點在promising(i)這個地方，因為如果這個皇后下下去之後，與其它皇后有所衝突，就表示 no promise了，也就是這一步下錯了，不用繼續向下處理，回頭吧。
這個題目要判斷是否promise有四個條件，任一條件成立都是 no promise
1. column[i]==column[k]，表示不同列的皇后在同一行。
2. abs(column[i]-column[k])==i-k ，表示兩個皇后在同一個斜線格上。
3. i==x-1&&column[i]!=y-1，表示與指定位置擺放的皇后，位置同列。
4. i!=x-1&&column[i]==y-1，表示與指定位置擺放的皇后，位置同行。

另外，我中了許多WA(Wrong answer)，因為題目的輸出要每個case都要有個兩行標頭，我以為全部就一個標頭即可，題目這裡倒是沒說的很清楚。
以下是輸入 4 7 後的答案

SOLN       COLUMN
 #      1 2 3 4 5 6 7 8

 1      3 1 7 5 8 2 4 6
 2      3 5 2 8 1 7 4 6
 3      3 7 2 8 5 1 4 6
 4      5 3 1 6 8 2 4 7
 5      5 7 1 3 8 6 4 2
 6      5 7 2 6 3 1 4 8
 7      6 3 1 8 5 2 4 7
 8      8 2 5 3 1 7 4 6

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

Problem 291 The House Of Santa Claus，聖誕老公公的房子

這個是小時候的遊戲，但我可沒玩過。題目要的答案是能筆不離紙的畫出下列圖形：
最後的輸出是將所有從點1出發的答案都列印出來。
我對這題的解法使用了回溯的方法，也就是和解八個皇后的方法一樣，請參考Problem 167 The Sultan's Successors，權位的繼承者。
畫圖的路徑一共有八條，所以會有九個點來敘述答案，不是範例中的八個數字，應該是九個。因此我使用

int path[PATHSIZE];

而PATHSIZE是9。在C語言主程式中呼叫

    path[0] = 0;
    Santa(0);

Santa是用來遞迴呼叫的C語言函數，完成細節如后。

void Santa(int i)
{
    int j;
    if (promising(i))
    {
        if (i==PATHSIZE-1)
        {
            for (j=0;j<PATHSIZE;j++)
                printf("%d", path[j]+1);
            printf("\n");
        }
        else
        {
            for (j=0;j<SIZE;j++)
            {
                path[i+1] = j;
                Santa(i+1);
            }
        }
    }
}

這個promising(i)決定要不要走下個點，有兩個基本考量
1. 不要走回自己，例如點3連到點3。
2. 不要走重複過的路，例如有了34，則34和43就不應該再出現在答案路徑中。
這個部份是訓練C語言程式設計邏輯的好機會，可以自己練習一下。
答案有44個，前五個是
123153452
123154352
123451352
123453152
123513452

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

C 程式設計作業七，指標之使用

作業內容：
有一天，小甜甜和他的同學到鄉下的奶奶家去玩，奶奶家有一個很大很大的玫瑰花園，種著各式各樣的玫瑰花，其中有一片玫瑰園種植著紅黃相間的玫瑰，排列整齊，非常好看。

這些黃白相間的玫瑰花每10公分的距離種一棵，小甜甜心理在想，隨便一個方塊中，會有多少棵玫瑰呢？

這次的作業，你要計算的是玫瑰的數量，在一個已知位置的矩形中，算出紅黃玫瑰各有多少棵。以下圖為例：

矩形左下角座標為(35, 35)，右上角座標為(95, 75)，算出的紅玫瑰有12棵，黃玫瑰也有12棵。

本作業基本要求如下：

1. 完成函數void calcRose( int, int, int, int, int *, int *)，輸入參數有六個，前四個整數為矩形座標，分別為x1, y1, x2, y2，而(x1, y1)為左下角，(x2, y2)為右上角座標。最後兩個參數為整數指摽，分別代表紅色與黃色玫瑰的數量。

2. 程式的輸入為四個整數，以空白格開，範圍在0~4000(含)之間，當四個值都是 0 時，則程式停止。

3. 程式的輸出為兩個整數，分別為紅色與黃色玫瑰的數量，各佔六格寬度。

4. 主程式呼叫calcRose函數，在求出玫瑰數量後，依格式輸出結果。

範例輸入：

35 35 95 75
30 20 50 30
1000 1005 1008 1055
0 0 0 0

範例輸出：

    12    12
     3     3
     3     2

作業提示：
使用 if (x1==0&&y1==0&&x2==0&&y2==0) break;來結束程式。

解答下載
回到作業目錄
回到首頁

小考六(D) 解答

C語言小考的題目主要在要求於50分中內完成程式，這題C語言答案的重點在函數的完成，函數解答的程式碼如下：

void reverseString(char str[])
{
    int i, len;
    len = strlen(str);
    for (i=len-1;i>=0;i--)
        printf("%c", str[i]);
    printf("\n");
}

反序列印的重點在找到最後一個字元，然後利用for迴圈來倒數，strlen是一個方便的函數，如果不用strlen，則必須從頭到尾去找到第一個結束字元 '\0'，再紀錄此時陣列的位置。
小考六(D)題目
返回小考目錄
回到首頁

小考六(D) 題目

/* C Programming, Quiz 6D */
/*
小考六題目：完成一個函數，reverseString，主程式中呼叫該函數。
函數輸入一個字串，列印出一個反序字串。例如：輸入
What a nice day!，輸出變成 !yad ecin a tahW。

函數輸入值：一個 char []
函數輸出值：一個 char []
題目輸入：一個字串
題目輸出：印出與輸入字串反序的字串
*/
解答下載
返回小考目錄
回到首頁

小考六(C) 解答

在C語言主程式中使用

printf("%d\n", getMinIndex(W));

即可列印出最小值的列索引值。
而getMinIndex函數之C語言程式碼如下：

int getMinIndex(int a[][COL])
{
    int i, j, rNo=0, minx;
    minx = a[0][0];
    for (i=0;i<ROW;i++)
        for (j=0;j<COL;j++)
            if (minx > a[i][j])
            {
                minx = a[i][j];
                rNo = i;
            }
    return rNo;
}

小考六(C)題目
返回小考目錄
回到首頁

Problem 10137 The Trip，旅遊分帳問題

這個旅遊分帳的問題雖然簡單，但是其中四捨五入的問題卻是非常重要。而問題所舉的第二個範例也能反映這個問題的核心。
這個問題說有一群學生出去遊玩，每個人先付一些集體需要的花費，例如車票、住宿、吃飯等，回來後大家再均攤。由於要算到「分」，就是小數的第二位，因此必須要處理四捨五入進位的問題。
我使用一個簡單的方法，就是讀進來的值乘100後再加總。再用C語言的floor來處理，程式如下

mean = floor(total/studNum+0.5)/100;

四捨五入進位後，所得的結果就會是這次旅遊每個人的平均花費。
因為一定會有一批人要再拿出一些錢，另一批人收回一些錢，題目問的是印出最小的交換金額，也就是在拿出來總額與收回去總額中取其小。重點程式碼如後：

for (i=0;i<studNum;i++)
{
    if (expense[i]>mean)
        pay1 += expense[i]-mean;
    if (expense[i]<mean)
        pay2 += mean-expense[i];
}
if (pay1<pay2)
    printf("$%.2f\n", pay1);
else
    printf("$%.2f\n", pay2);

這題非常適合C語言初學者練習解題用。
p10137 問題連結
ACM 題庫目錄
回到首頁

Problem 438 The Circumference of the Circle，求圓周長

過三點求圓
這是國中數學裡以三點形成一個圓，此三點不在一條線上。
分兩次任取兩點，畫出兩條線段，再求這兩條線段的中垂線相交於一點，就是圓心，這在平面上作圖是容易的事，但是要寫入程式中，必須將所有的公式算出來。
三點座標分別為 (x1,y1), (x2,y2), (x3,y3)。
首先算出任兩個線段的斜率，例如點1連點2線段(L_12)的斜率為(y2-y1)/(x2-x1)，點1連點3線段(L_13)的斜率為(y3-y1)/(x3-x1)，與這兩個線段垂直的斜率為

m_12 = -(x2-x1)/(y2-y1)，
m_13 = -(x3-x1)/(y3-y1)，

這兩個中垂線段分別通過L_12和L_13的中點 ((x1+x2)/2, (y1+y2)/2) 和 ((x1+x3)/2, (y1+y3)/2)

c12x = (x1+x2)/2;
c12y = (y1+y2)/2;
c13x = (x1+x3)/2;
c13y = (y1+y3)/2;

所以這兩個中垂線的公式為

y = m_12*(x - c12x) + c12y
y = m_13*(x - c13x) + c13y

因此求解這兩條線的交點，即得圓心座標(cx, cy)。解二元一次方程式，答案如下

cx = (c13y-c12y-m_13*c13x+m_12*c12x)/(m_12-m_13)
cy = m_12*(cx-c12x)+c12y

而半徑就是圓心到三點的距離

r = sqrt((x1-cx)*(x1-cx)+(y1-cy)*(y1-cy))

解題的C語言重點部分如下，必須注意取出任兩點線段時，如為垂直，會導致斜率的分母為零，簡單的方法，就是再取一點與其中一點對調。

if (y2==y1)
{
    temp = x1;
    x1 = x3;
    x3 = temp;
    temp = y1;
    y1 = y3;
    y3 = temp;
}
m_12 = -(x2-x1)/(y2-y1);
if (y3==y1)
{
    temp = x1;
    x1 = x2;
    x2 = temp;
    temp = y1;
    y1 = y2;
    y2 = temp;
}        
m_13 = -(x3-x1)/(y3-y1);
c12x = (x1+x2)/2;
c12y = (y1+y2)/2;
c13x = (x1+x3)/2;
c13y = (y1+y3)/2;
cx = (c13y-c12y-m_13*c13x+m_12*c12x)/(m_12-m_13);
cy = m_12*(cx-c12x)+c12y;
r = dist(cx,cy,x1,y1);
printf("%.2f\n", 2*PI*r);

這個題目的重點是要能化成公式，以套入C語言來解題。
注意：必須處理特殊狀況，例如分母為零時。
p438題目連結
回ACM題庫目錄
回首頁

如何學好C語言─王伯倫

這篇文章是目前就讀實踐大學高雄校區資管系的同學的學習心得與建議，學C語言經過一些努力，必有所成，這位同學已成為程式高手，讀完這篇，預祝所有C語言初學者能有所體會。

liangk

----------------------------------------------

想學好程式設計，很簡單，就是常去摸。一開始大家會對程式一無所知，所以會常常在寫作業時一直翻課本，看相似的範例怎麼寫的就依樣畫葫蘆照抄、拿光碟Copy範例，這些人注定學不好！一開始要學寫成是不看課本是非常痛苦的一件事，可是你必須訓練自己不要看課本，看看可以寫到什麼程度，再將不會的部分單獨挑出來自我訓練。平時沒事的時候就多看一下課本，多想。這樣對於自己絕對不會有壞處的！

而且請大家不要還沒開始學程式設計就認定自己是不會寫程式的人，寫程式並不會很困難，請各位平時有事沒事就多想，老師出了作業，先花幾分鐘去看一下題目，了解老師對程式的要求，把這個問題放在腦中，沒事就多想一下這個問題的邏輯、規則和自己想的方法的可行性。別想說這是很浪費時間的事！這是在訓練你們邏輯思考的能力！

不用問這樣做可不可以Pass，那種目標太小看你們了！相信照著我說的做，一定可以把程式設計這塊領域學的很棒的！

資一甲，王伯倫

小考六(C) 題目

/* C Programming, Quiz 6C */
/*
小考六題目：完成一個C語言函數，getMinIndex。
函數輸入一個 二維陣列，輸出最小值的列索引值

函數輸入值：一個 二維陣列。
函數輸出值：一個 int。
題目輸入：如下列陣列
題目輸出：印出小值的列索引值。
*/

#define ROW 4
#define COL 12

int W[ROW][COL] = {{ 41, 467, 334, 500, 169, 724, 478, 358, 962, 464, 705, 145}, 
             {281, 827, 961, 491, 995, 942, 827, 436, 391, 604, 902, 153},
             {673, 386,  21, 745, 924,  72, 270, 829, 777, 573,  97, 512},
             {313, 756, 321, 558, 646, 982, 481, 144, 196, 222, 129, 161}};
             
int main()
{
    return 0; 
} 

解答下載
返回小考目錄
回到首頁

Problem 10018 Reverse and Add，反轉再相加

這題是有關palindrome(迴轉字)的計算。
將輸入的數字倒轉過來，例如1234變成4321。然後與原數相加，產生新的數字。在重複相加的結果，如果數值倒轉過來與原數字相同，則這個數字就叫做palindrome(迴轉字)。
這題要列印出某輸入數字算成palindrome所需的加法次數及這個palindrome。
下列C語言程式碼是解答的重點部份，digitNum是輸入值的位數，reverse是倒轉過來的新數字，剩下來程式部分如相加、及判斷結束的條件應該很容易就OK了。

digitNum = floor(log10(num)+1);
for (j=digitNum-1; j>=0; j--)
{
    reverse += num%10 * (int)(pow(10,j)+0.001);
    num /= 10;
}

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

如何學好C語言─陳泳叡

這篇文章是目前就讀實踐大學高雄校區資管系的同學的學習心得與建議，學C語言經過一些努力，必有所成，這位同學已成為程式高手，讀完這篇，預祝所有C語言初學者能有所體會。

liangk

----------------------------------------------

如何學好C語言─陳泳叡
很多人一開始C語言沒有學好，到了後來覺醒了，想要開始好好學習。上課時很認真聽，卻有聽沒有懂，後來又放棄了。學習C語言我覺得剛開始學的一個月是打基礎最重要的時候，建議每天摸索個1~2小時或更多。

在一開始，我的練習方法是每個範例都先照著打一次，一開始照著打一定會有打錯的地方，例如可能忘了打”；”,那這時候就可以對照著課本檢查一次，看是錯在哪裡。接著你可以試著去改變一些變數，要本著實驗的精神去玩它。

雖然老師小考時是可以Open Book的，但是我覺得課本裡很多該背的還是要去背(例如：如何設立變數，迴圈的應用，函數的應用‧‧‧)，要是基本的東西沒背，考試的時候在那邊猛翻書，就算讓你翻到可以應用的範例好了，你也不見得會應用，而且老師出的小考考題是需要用到很多範例去組合的，試想腦袋裡一點東西都沒有，純粹靠翻課本找範例，這樣等你翻完課本我想大概也快要下課了吧!

學習C語言我覺得最主要的不是學習如何編寫程式碼，而是學習邏輯思考。寫程式都是要一步一步來的，要是一點邏輯概念都沒有，是很容易會忽略了某些條件而造成寫出來的程式不符合要求。

訓練邏輯我覺得梁老師一開始出的作業一，是最佳的訓練邏輯題目，如果是初學者一開始面對這個問題時，通常會覺得很痛苦，會覺得腦袋快轉不過來了，因此建議一開始先花一個禮拜的時間去想題目的邏輯和畫流程圖再花五天左右的時間去編寫程式碼(千萬不要到了要交作業的那禮拜才開始去動作業) ，流程圖對於初學者的幫助是很大的,能讓初學者省下很多的麻煩。

最後要告訴各位的是，作業一定要自己去寫，一開始一定會有很多地方都想不明白，當絞盡腦汁也無法解決問題的癥結在哪時，這時候就可以去問詢問老師，相信老師會本著熱誠的去教你，老師不會幫忙做作業但是他會說出你的作業的關鍵在哪裡,相信很快的問題一定可以迎刃而解，而且自我的水準也會有所提高。要是有空可以去老師的考古題網站去玩玩看那些題目，祝各位C語言都All Pass。

C++是一個奇跡，活著就是勇氣！C++是一段旅途，有磨礪就是人生！

電腦是死的，人是活的，希望大家是玩C語言，而不是被C語言玩。

資一甲，陳泳叡

C 程式設計作業六，陣列與字串之使用：解題

這題的C語言作業雖然是要做乘法，但是被乘數只有兩位數，所以，最簡單的作法是用加法來完成。也就是讀進來的第一個字串去累加，累加的次數由讀入的第二個數字決定。
完整的解答如下，我以add(prod, temp)函數呼叫來完成加法，使用addOn來處理進位。另外讀進來的數字字串最高位數是在str[0]的位置，所以轉成temp時要顛倒過來。digitNo是用來計算答案的位數，列印時前置的0才可以不用印出來。

#include <stdio.h>
#include <stdlib.h>

#define MSIZE 34

void multiply(int prod[], int multiplier[], int num);
void add(int prod[], int temp[]);
int main(void)
{
    int prod[MSIZE], temp[MSIZE];
    char str[MSIZE];
    int i, num, digitNo;
    
    while (1)
    {
        scanf("%s%d", str, &num);
        if (!strcmp(str,"0") && num==0)
            break;
        for (i=0;i<MSIZE;i++)
        {
            prod[i]=0;
            temp[i]=0;
        }
        for (i=strlen(str)-1;i>=0;i--)
            temp[strlen(str)-i-1] = str[i]-48;
/*            
        for (i=strlen(str)-1;i>=0;i--)
            printf("%d",temp[i]);
        printf("\n");
*/
        for (i=0;i<num;i++)
            add(prod, temp);
        digitNo = 0;
        for (i=MSIZE-1;i>=0;i--)
            if (prod[i]!=0)
            {
                digitNo = i;
                break;
            }
        for (i=digitNo;i>=0;i--)
            printf("%d",prod[i]);
        printf("\n");
    }


    return 0;
}

void add(int prod[], int temp[])
{
    int addOn=0, i;
    for (i=0;i<MSIZE;i++)
    {
        prod[i] = prod[i]+temp[i] + addOn;
        if (prod[i]>9)
        {
            prod[i] %= 10;
            addOn = 1;
        }
        else
            addOn = 0;
    }
}

作業六題目
回到作業目錄
回到首頁

Problem 10019 Funny Encryption Method，有趣的密碼編碼

這個ACM題目看起來又臭又長，其實只有兩個重點，將一個數字N，看成10進位與16進位的數字，然後分別進行10進位轉換2進位，與16進位轉換2進位，然後將這兩個二進位的數字中的 1 進行加總，再分別列印出來。
這兩個要求在C語言中可以用 stdlib.h中的itoa()輕易解決。在Dev C++中，用itoa(N, X1, 2)可以求得二進位字串。但是，ACM的裁判系統找不到itao函數，而產生compile error，這段過程是很令人氣結的。

解決之道是我自己再寫一個函數：srt2bin()，將數字字串s，經過以base為底換算成十進位後，再轉換成二進位的字串。存在字串 b 中。數字字元與一般整數型態轉換，必須加減 48 。

void str2bin(char s[], char b[], int base)
{
    int i, j, sum=0, prod, len=strlen(s);
    char temp[20];
    for (i=0;i<len;i++)
    {
        prod=1;
        for (j=len-i-1;j>0;j--)
            prod *= base;
        sum += prod * (s[i]-48);
    }
    i = 0;
    while (sum!=0)
    {
        b[i] = sum%2+48;
        sum /= 2;
        i++;
    }
    b[i] = '\0';
}

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

Problem 10035 Primary Arithmetic，小學算術

簡單的數學加法題目，非常適合C語言初學者，做為入門學習用。題目要求每次讀入兩個整數，求出兩數相加的過程中，產生了多少的進位。這種進位的數量可以用來決定這兩數相加的題目困難度。我想小學生的數學老師或許用的到吧。
程式的重點部份如下。雖然範例的數字是相同位數，可是真正的測試應該會有不同吧。迴圈中的兩個數字num1,num2每次都取出個位數，然後看addOne是否有產生進位的情形，有就記錄起來。迴圈的執行在兩個數都為0時停止。

        while (num1!=0 || num2!=0)
        {
            d1 = num1 % 10;
            d2 = num2 % 10;
            num1 /= 10;
            num2 /= 10;
            addOne = (d1+d2+addOne)/10;
            if (addOne==1)
                count++;
        }

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

Problem 10038 Jolly Jumpers，計算數列差

這個題目說的不是很明白，文中說明Jolly jumper是一個數列序列，內容包含了1到n-1之間的每一個數，可是題目所舉例之相鄰數字差的絕對值為連續的 3 2 1，所以會誤解說是不是要按大小排列，其實，題目中的Jolly jumper所指的1到n-1 之數列是要求，每一個數字都要有，但不用按序排，可以是任何排列。只是範例恰巧由大到小(八成是故意的)。
下列附上程式的重點內容，我用了一個整數陣列來存放這些差值，每個差值出現一次，就在該陣列的相關位置累進 1，算完後，只要看看這個陣列的每個值，如果都是 1，那就是Jolly，只要有 1 以外的數字，就不是Jolly。

for (i=0;i<seqNum-1;i++)
{
    scanf("%d",&x2);
    if (x1>x2)
        diff = x1-x2;
    else
        diff = x2-x1;
    x1 = x2;
    if (0<diff && diff<seqNum)
        n[diff]++;
    else
    {
        isJolly = 0;
    }
}

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

Problem 494 Kindergarten Counting Game，幼稚園算字遊戲

這題就像完成Office Word中計算字數的功能，這裡算的是英文字，所以只用ASCII值來判斷讀進來的字母是否為A-Z或a-z，只要是，就處於文字狀態，否則處於間隔狀態。只要狀態改變且進入文字狀態，wordCount就累進 1。重點程式碼如下

if ((str[i]>=65&&str[i]<=90) || (str[i]>=97&&str[i]<=122))
    isLetter = 1;
else
    isLetter = 0;
if (status != isLetter)
{
    if (isLetter==1)
        wordCount++;
    status = isLetter;
}

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

Problem 488 Triangle Wave，三角波形

這個題目非常適合初學 for 迴圈練習，難易程度比考試系列中的期末考(C)或期末考(D)還簡單，用到四個 for 迴圈，就解決了。
重點程式碼如下所示：

        scanf("%d%d", &, &freq);
        for (j=0; j<freq; j++)
        {
            if (first)
                first=0;
            else
                printf("\n");
            for (k=1;k<=amp;k++)
            {
                for (n=1;n<=k;n++)
                    printf("%d", k);
                printf("\n");
            }
            for (k=amp-1;k>=1;k--)
            {
                for (n=1;n<=k;n++)
                    printf("%d", k);
                printf("\n");
            }
        }

紅色部分是處理最後一行不列印換行的方法，也就是在一開始先決定不印，此後一律進行換行列印。
p488題目連結
回ACM題庫目錄
回首頁

Problem 913 Joana and the Odd Numbers，喬安娜與奇數

這是一個初學者練習解題的好機會，這個可愛的喬安娜愛玩奇數，所以排列了奇數如下：

 1
 3  5  7
 9 11 13 15 17
19 21 23 25 27 29 31

全部都是奇數，每一列的數量也是奇數，題目要求將最後面的三個數字相加後印出。
如果你要自己練習，請先不要看下面的解題經過。

解題過程：

行數  數字數量(n)  最後的值
1       1            (1) x 2 - 1
2       3            (1+3) x 2 - 1
3       5            (1+3+5) x 2 - 1
4       7            (1+3+5+7) x 2 - 1
5       9            (1+3+5+7+9) x 2 - 1
...
(n+1)/2  n            (1+3+...+n) x 2 - 1

所以最後的值，可以直接用公式 1+3+...+n = ((1+n)*(n+1)/2)/2
(上底為1，下底為n，高為(n+1)/2)
經過簡化：最後值的公式是(n+1)*(n+1)/2 -1
最後三個數字和為：((n+1)*(n+1)/2-3)*3
所以程式的重點如下：

    while (scanf("%d", &n)!=EOF)
    {
        a = (((long long)(n+1)/2)*((n+1)/2)*2-3)*3;
        printf("%lld\n", a);
    }

a 必須宣告為 long long
做這一題時，我的Dev C++無法列印出正確的 long long答案，找了很多說法，我採用了其中的一個說法，那就是，你的電腦印不出來，不代表ACM線上裁判系統也印不出來，所以，上傳後，居然就過了。呵呵。
913題目連結
回ACM題庫目錄
回首頁

C 程式設計作業六，陣列與字串之使用

作業內容：
你會乘法嗎？當然會。每個人小學就開始學九九乘法表。

電腦也會乘法，你跟電腦比賽過嗎？當然電腦瞬間就可以算出來了。可是電腦在精確度方面是有限制的。int 變數型態通常是四個位元組，計有32個位元，所以能代表數字的範圍為−2,147,483,648 ~ +2,147,483,647。double 變數型態所能代表的範圍比 int 大，可高達10的16次方，即10,000,000,000,000,000。

這次的作業，你要處理的是兩個整數的相乘，第一個整數的範圍在0~ 10^32(10的32次方)，第二個整數的範圍是0~99。

例如，999,999,999,999,999,999,999,999 x 11，得到的答案是 10,999,999,999,999,999,999,999,989

本作業基本要求如下：

1. 每次讀取兩個值，進行相乘運算後，印出乘積。

2. 當輸入的兩個值都是 0 時，則程式停止。

3. 必須使用陣列。

3. 必須製作函數，以呼叫進行運算。

範例輸入：

999999999999999999999999 11
0 99
12345678901234567890 0
12345678901234567890 11
98765432109876543210111222333 58
11111111111111111111111111111 99
999999999999999999999999999999 99
0 0

範例輸出：

10999999999999999999999989
0
0
135802467913580246790
5728395062372839506186450895314
1099999999999999999999999999989
98999999999999999999999999999901

作業提示：
使用scanf 讀取 %s%d，再將第一個讀取的字串，轉存成陣列，以計算乘積。

解答下載
回到作業目錄
回到首頁

Problem 160 Factors and Factorials，因數與階乘

我喜歡這輸入值的限制，居然是 2 到 100。
這題是說一種特大數字的表示方法，就是用其質因數的次數來表示。這裡應用的範圍是 2 到 100的階乘值。
經過小小的計算，我先把100以內的質數算出來，然後宣告一個質數的陣列，如下

int prime[25] = {2,3,5,7,11,13,17,19,23,29,31,37,41,
    43,47,53,59,61,67,71,73,79,83,89,97};

接下來計算所有 2 到 100每個數的質因數表示方法，也就是說，每個數字都有一個質因數的陣列表示方法，這個資料在後來處理階乘時，只要將階乘中乘數的每個質因數陣列相加，答案就出來了。

    int primeTable[101][25]={0};
    for (i=2;i<=100;i++)
    {
        k = i;
        j=0;
        while (k>=2)
        {
            if (k%prime[j]==0)
            {
                primeTable[i][j]++;
                k /= prime[j];
            }
            else
                j++;
        }
    }

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

Problem 167 The Sultan's Successors，權位的繼承者

這個題目的重點在你會不會解西洋棋的八個皇后問題。也就時在西洋棋盤(8x8)上，放八個皇后，八個皇后互不侵犯，誰也不能吃誰。如果學過演算法，這個題目應該不算難。在蔡宗翰譯的「演算法--使用C++虛擬碼」書中(碁峯資訊，2004年)，第五章介紹回溯方法的應用。所以只要完成該n-queen的程式碼，就可以將所有八個皇后全部的編排位置排出來，排出來之後，再以題目提供的數字，將皇后所佔領的格子中的數字加總，將最大的加總保留下來，並印出，就大功告成了。

主程式呼叫的部份如下，BSIZE為8。queens是將皇后在第一列的位置排出來後，進行呼叫，其中也用到了遞迴。

for (j=0;j<BSIZE;j++)
{
   column[0]=j;
   queens(0);
}
printf("%5d\n", max);

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

Problem 151 Power Crisis，紐西蘭電力危機

這題的簡化版就是95年度的作業五，因為要每隔一個固定的數字作為停電的規則，這個數字在作業五中是固定在5, 6, 7, 8四個數字，且停電區是固定17個區，而原題目是輸入一個13到100之間的數作為停電區，並算出要隔多少，才能讓第13區排在停電順序的最後一個。下方是主要的程式碼，其實蠻短的。

            powerOff[0] = 0;
            currentOff = 0;
            downSeq[0] = currentOff;
            for (i=1;i<area;i++) {
                count = 0;
                while (count < m) {
                    currentOff++;
                    if (currentOff>=area)
                        currentOff = 0;
                    if (powerOff[currentOff]==1)
                        count++;
                }
                powerOff[currentOff]=0;
                downSeq[i] = currentOff;
            }

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

Problem 11326 Laser Pointer，雷射光筆

這題用到三角函數，首先雷射光射出的第一個落點，在射出角度大於arctan(W/L)時，會在對面(長L)的鏡子上。雷射行進的距離為 a = W/sin(e)，水平平移的距離為 len = W/tan(e)，只要累積的水平平移不超過L，表示會有一次反彈。最後落在寬 W 的出口時，可以用lastw = (L-累積平移)*tan(e)算門上的落點，這時要注意反彈次數是奇或偶，這個最後落點 lastw 可以用畢式(高商)定理算 B。重要部份程式顯示如下：

        len = W/tan(e*M_PI/180);
        while (len+dist<L)
        {
            dist += len;
            A += W/sin(e*M_PI/180);
            len = W/tan(e*M_PI/180);
            j++;
        }
        A += (L-dist)/cos(e*M_PI/180);
        lastw = (L-dist)*tan(e*M_PI/180);
        if (j%2==1)
            B = sqrt((W-lastw)*(W-lastw)+L*L);
        else
            B = sqrt(lastw*lastw+L*L);

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

Problem 10300 Ecological Premium，生態保育補助

題目介紹了德國農夫在畜養動物時，對環保裝備使用進行費用補助。輸入的題目每個農夫有三個數字，分別是畜牧面積x、動物數量y、環保程度z。根據文中的敘述，計算補助的方式為(x/y)*z*y，沒錯，y消掉後，公式就是x*z，因此這題幾乎是不用花腦筋，就可以做出來。全部答案如下。

int main(void)
{
    int caseNum, farmNum, i, j;
    double area, animal, degree, budget;
    scanf("%d", &caseNum);
    for (i=0;i<caseNum;i++)
    {
        scanf("%d", &farmNum);
        budget = 0;
        for (j=0;j<farmNum;j++)
        {
            scanf("%lf%lf%lf", &area, &animal, °ree);
            budget += area*degree;
        }
        printf("%.0f\n", budget);
    }
    return 0;
}

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

Problem 834 Continued Fractions，連續的整數加分數

又是一個用到遞迴的題目，這題一開始是 A 除以 B，求得餘數 C 後，再來 B 除以 C，每次這樣除下去，答案就出來了。遞迴要停在餘數為 1 或 0 時，餘數1，表示找到最後的 1/x，餘數0，表示可以整除，就等於找到了 1/x。下列只有first是全域變數，專為列印時使用。

void compFraction(int n, int d)
{
    int quo, remainder;
    quo = n/d;
    remainder = n%d;
    if (first)
    {
        first=0;
        printf("%d;", quo);
    }
    else
        printf("%d,", quo);
    if (remainder!=1 && remainder!=0)
        compFraction(d, remainder);
    else
        printf("%d]\n", d);
}

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

Problem 993 Product of digits，位數的乘積

這題的意思是給你一個數字N，N是另一個數字Q中的所有個別位數的乘積，例如N=10，則Q可以是25，或52，題目要求Q是最小的。所以我就從 9 到 1 ，算他的因數，一次抽一個，按這種方式排列後，其數字會變的最小。需要注意的特殊狀況是，質因數有大於10的情形，這種數字就沒有答案了。這題又用到了遞迴的技巧，遞迴真是好用，只需要注意停止呼叫的條件，遞迴可以省很多事。遞迴函數如下，其中Q[10]是全域變數。

void compFactor(int n, int idx)
{
    int i;
    for (i=9;i>=1;i--)
        if (n%i==0)
        {
            Q[idx] = i;
            n /= i;
            break;
        }
    if (i!=1)
        compFactor(n, idx+1);
    else if (n!=1)
        Q[idx]=-1;
}

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

Problem 10013 Super long sums，位數超長的加總

又被多印一個換行給退回了。
這回跟問題10062一樣，要注意在最後一行是不可以多一個換行的。
這題也用到了問題619中的add函數，不過輸入的陣列是用char來宣告。

char n1[SIZE], n2[SIZE];

SIZE是1000000，如果用short來宣告，會超過其限制，程式會當掉。另外，讀取時，不能直接讀進陣列，因為%d是讀進四個bytes的整數，所以會蓋掉前面陣列的值。我用

scanf("%d%d", &temp1, &temp2);
n1[j] = temp1;
n2[j] = temp2;

來讀取資料。
雖然輸入時有給數字長度，但是處理時，要多給一位，因為有可能兩數相加後會有進位的情形。
p10013題目連結
回ACM題庫目錄
回首頁

Problem 10055 Hashmat the brave warrior，勇敢的戰士Hashmat

題目真好聽，不是嗎。
這題是 ACM 裡面最最最容易的一題。乍看之下，2^32剛好超過C語言的int精確度範圍，不能用int。那就用double囉，double的數字精確度達2^52，所以非常夠用。不要忘了在scanf使用 %lf 來讀取，使用 %.0f 來省去小數的輸出，全部的程式解答如下：

int main(void)
{
    double n1, n2;
    while (scanf("%lf%lf", &n1, &n2)!=EOF)
        printf("%.0f\n", fabs(n1-n2));
    return 0;
}

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

Problem 10062 Tell me the frequencies，告訴我字母次數

這題就是所說的不明不白型，因為結尾多一個換行是錯的，所以輸出方式必須在一開始用

if (first)
   first=0;
else
   printf("\n");

另外，不能用scanf，只要用幾個空白鍵(ASCII=32)測試一下，你就知道scanf是讀不了空白字元的，用gets是OK的。
這題是實作結構(struct)的良好範例。

    struct tuple
    {
        char letter;
        int freq;
    } ansStat[MAXASCII], temp;

在做排序時很方便，可以整組字元與次數一起排序，在統計字元次數時也很方便，就是
ansStat[strInput[i]-32].freq++;

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

Problem 619 Numerically Speaking，數字與文字轉換處理

題目真的不難，但是卻囉唆的要死。
這其實是一個26進位的系統，從1-26，以a-z來代表，不是0-25。我用了p324中的乘法函數，稍作修改，另外也增加了加、減、除等三個函數，用來處理以short陣列所代表的大型數字之加減乘除。
因為常用到以26為底的指數，所以一開始就先利用乘法函數，將26的1~20次方的數字先儲存起來，後來再計算時就會很快。這題有許多字串轉數字陣列的地方，我想或許有更快的方法，不用轉來轉去。另外，也許有一些處理大數字的函式庫可以呼叫應用，但我想自己寫會快些，反正乘法函數已經有了，其他的就類似，甚至更簡單。
這題有個簡單的地方，就是範例做的出來，上傳應該一次就OK，不像有的題目，完成範例不見得上傳就一定會過。像那種題目就很令人睹爛，也不知道錯在哪裡。
下面列出了乘法與減法的函數。

void multiply(short prod[], short multiplier[], int num)
{
    short tempSum[DSIZE];
    int digitNum, addOn, temp, i, j;
    
    for (i=0;i<DSIZE;i++)
        tempSum[i] = 0;
    for (i=0;i<DSIZE;i++)
    {
        temp = num * multiplier[i];
        digitNum = floor(log10(temp)+1);
        addOn = 0;
        for (j=i;j<i+digitNum;j++)
        {
            tempSum[j] += temp%10 + addOn;
            if (tempSum[j]>9)
            {
                tempSum[j] %= 10;
                addOn = 1;
            }
            else
                addOn = 0;
            temp /= 10;
        }
        if (addOn==1)
            tempSum[j]++;
    }
    for (i=0;i<DSIZE;i++)
        prod[i] = tempSum[i];
}
int minus(short diff[], short temp[])
{
    int minusOn, len=0, i;
    for (i=DSIZE-1;i>=0;i--)
    {
        if (diff[i]-temp[i]<0)
            return 0;
        else if (diff[i]-temp[i]>0)
        {
            len = i+1;
            break;
        }
    }
    minusOn = 0;
    for (i=0;i<DSIZE;i++)
    {
        diff[i] = diff[i] - temp[i] + 10 - minusOn;
        if (diff[i]>=10)
        {
            diff[i] %= 10;
            minusOn = 0;
        }
        else          
            minusOn = 1;
    }
    return 1;
}

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

Problem 617 Nonstop Travel，回家一路綠燈

這題是要從時速30哩到60哩之間，算出所有可以在回家時，一路綠燈的速度。每個人偶爾都會經歷一路綠燈的經驗，解這題時，我卻沒有一路綠燈。首先是列印解答時，格式的要求有點龜毛，要考慮好幾種不同的可能，要兼顧頭尾、「-」、「, 」等情形，所以這題非常適合作為if-else的邏輯練習，做完會很有成就感。其次是fmod與一般%餘數運算的差異，改用fmod後，一下就過關了。
我用到結構，因為在參數傳遞時，只要將指標傳過去，比較簡潔。結構如下：

struct traffic
{
    float distance;
    int green, yellow, red;
};

下列是函數呼叫，用來檢驗速度sp在某燈號下的紅黃綠燈。記得要用fmod，一下就過了。

int checkLight(int sp, struct traffic *lptr)
{
    float tm; /* in second */
    float lightTime;
    int cycleTime;
    tm = lptr->distance/sp*3600;
    cycleTime = lptr->green + lptr->yellow + lptr->red;
    lightTime = fmod(tm, cycleTime);
    if (lightTime>lptr->green + lptr->yellow)
        return 1;
    else
        return 0;
}

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

Problem 324 Factorial Frequencies，階乘的數字頻率

這題要先計算小於等於366的階乘，然後再算出答案中各個數字出現的頻率。因為366!的解答位數有781個，因此乘積必須另外處理，我使用一個782大小的short陣列，下列是處理一次相乘的運算過程，digitNum是目前乘積的位數，quotient是乘數，m是被乘數，因為m <= 366，所以只需要一個大小為四的陣列暫放單次乘積，所有乘積的再加總到 tempQuotient，最後再將tempQuotient 取代 quotient。

    for (i=0;i<digitNum;i++)
    {
        temp = m * quotient[i];
        tempSingleQuotient[0] = temp%10;
        tempSingleQuotient[1] = (temp/10)%10;
        tempSingleQuotient[2] = (temp/100)%10;
        tempSingleQuotient[3] = temp/1000;
        addOn = 0;
        for (j=i;j<i+4;j++)
        {
            tempQuotient[j] += tempSingleQuotient[j-i] + addOn;
            if (tempQuotient[j]>9)
            {
                tempQuotient[j] %= 10;
                addOn = 1;
            }
            else
                addOn = 0;
        }
        if (addOn==1)
            tempQuotient[j]++;
    }

366!的答案參考如下：

91881110952544960192121764120652021400905804187746451946753698409678048465888630
95597762591294093025991679067056119532289819154031153412626361004655299317292397
49179412498318319018148586317535633967317457727070935401134984115987016231538802
10775515745441503394546772632592927414904702786529187586181553191933821765407560
99231912808304474174078456156193961001478398647954868692612278257154615836148475
87497304417332305563008204883785367990054205910511284539407194719244320847853070
01945328184598553156206617049504666959657009975517485204759412277436981211121307
99760005290512978278155471280205501581277410145813062661991385483143379923345195
40643216551834035171686893165020312665044431520399360000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000

輸出結果為：

366! --
   (0)  160    (1)   93    (2)   58    (3)   60    (4)   74
   (5)   81    (6)   58    (7)   64    (8)   59    (9)   74

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

Problem 326 Extrapolation Using a Difference Table，用差分表算外差

這題的差分表並不是真的要你宣告一個很大的陣列來儲存差分表，根據他最後的提示，似乎會給你一個很大的 k 值，如果你將每個值都存起來，可能就會有記憶體消耗的問題。
我的作法是先將每一行的最後一個值算出來，存在一個全域變數的陣列中，並使用遞迴呼叫來做解算。因為題目說最多只有10個值，所以遞迴所用的陣列大小10個就夠用。在下面的例子中，lastValue和m_index都是全域變數，每呼叫一次，就計算一行的差分值，然後只要將最後的一個值存起來，放入lastValue中就OK了。

void compDiff(int eArray[], int size)
{
    int ary[10]={0}, i;
    if (size==2)
    {
        m_index++;
        lastValue[m_index] = eArray[1]-eArray[0];
    }
    else
    {
        for (i=1;i<size;i++)
            ary[i-1] = eArray[i]-eArray[i-1];
        m_index++;
        lastValue[m_index] = ary[i-2];
        compDiff(ary,size-1);
    }
}

每一行最後的值算完後，再重複k次，每次再更新lastValue的每個值，使用
lastValue[j] += lastValue[j+1];
這樣就大功告成了。
p326題目連結
回ACM題庫目錄
回首頁

Problem 263 Number Chains，數字鏈

這個題目適合剛學C語言的人來練習，其中數字轉變成最大或最小值的方法，只要用簡單的Bubble Sort就可以了。這題的挑戰點在如何判斷輸入的數字是幾位數，當將輸入值拆成一個一個的個數後，最後面一定會有剩下 0 的情形，所以將陣列大小減去最後剩下多少零，就可以判斷位數了。參考下列程式片斷，如果digit[i]!=0，則位數i+1就出來了。

    i = 9;
    while (i>=0)
    {
        if (digit[i]!=0)
        {
            size = i+1;
            break;
        }
        i--;
    }

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

C 程式設計期末作業，解題練習：解答

/* C Programming, final project */
#include <stdio.h>
#include <stdlib.h>

int getSortedNum(int, int);
int numInChain(int, int);
int chain[1000];
int main(void)
{
    int num, size, idx;
    int bigNum, smallNum;
    while (1)
    {
        scanf("%d", &num);
        if (num==0)
            break;
        printf("Original number was %d\n", num);
        idx = 0;
        do
        {
            bigNum = getSortedNum(num,1);
            smallNum = getSortedNum(num,-1);
            chain[idx] = bigNum - smallNum;
            num = chain[idx];
            printf("%d - %d = %d\n", bigNum, smallNum, chain[idx]);
            idx++;
        } while (!numInChain(chain[idx-1], idx-2));
        printf("Chain length %d\n\n",idx);
    }

    return 0;
}

int getSortedNum(int num, int order)
{
    int digit[10]={0};
    int i, j, temp, size=0;
    
    for (i=0; i<10; i++)
    {
        digit[i] = num%10;
        num /= 10;
    }
    i = 9;
    while (i>=0)
    {
        if (digit[i]!=0)
        {
            size = i+1;
            break;
        }
        i--;
    }
    if (order == 1)
    {
        for (i=0;i<size-1;i++)
            for (j=i; j<size; j++)
                if (digit[i]<digit[j])
                {
                    temp = digit[i];
                    digit[i] = digit[j];
                    digit[j] = temp;
                }
    }
    else if (order == -1)
    {
        for (i=0;i<size-1;i++)
            for (j=i; j<size; j++)
                if (digit[i]>digit[j])
                {
                    temp = digit[i];
                    digit[i] = digit[j];
                    digit[j] = temp;
                }
    }
    temp = digit[0];
    for (i=1;i<size;i++)
    {
        temp *= 10;
        temp += digit[i];
    }
    return temp;
}

int numInChain(int newNum, int idx)
{
    int i;
    for (i=0;i<=idx;i++)
        if (newNum == chain[i])
            return 1;
    return 0;
}

作業五題目
回到首頁

期末考(D)題目：解答

#include <stdio.h>
#include <stdlib.h>

void print_tri(int);
int main(void)
{
    int n;
    printf("Enter a positive number: ");
    scanf("%d", &n);
    print_tri(n);
    
    system("pause");
    return 0;
}

void print_tri(int n)
{
    int i,j;
    for (i=0;i<=n;i++)
    {
        for (j=0;j<i;j++)
            printf(" ");
        for (j=2*n+1;j>2*i;j--)
        {
            printf("%d", j);
        }
        printf("\n");
    }
}

期末考(D)題目
返回小考目錄
回到首頁

期末考(D)題目

/* C Programming, final exam D */
/*
期末考題目：完成一個 print_tri 函數，以列印排列的數字，
            若輸入值為 n ，則第一列印出2n+1到 1 的數，
            第二列印出2n+1到 3 的數，依此類推，最後
            一列只印出2n+1，列印時以等腰倒三角形形式
            印出。例如輸入 4 時，輸出
            
            987654321
             9876543
              98765
               987
                9 

            輸入 1 時，輸出
            
            321
             3
                
函數輸入值：一個 int。 
函數輸出值： 無。 
題目輸入：一個大於等於 0 的整數 
題目輸出：印出等腰倒三角形。 
*/

解答下載
返回小考目錄
回到首頁

期末考(C)題目：解答

#include <stdio.h>
#include <stdlib.h>

void print_tri(int);
int main(void)
{
    int n;
    printf("Enter a positive number: ");
    scanf("%d", &n);
    print_tri(n);
    
    system("pause");
    return 0;
}

void print_tri(int n)
{
    int i,j;
    for (i=0;i<n;i++)
    {
        for (j=0;j<i;j++)
            printf(" ");
        for (j=n;j>i;j--)
        {
            printf("%d", j);
        }
        printf("\n");
    }
}

期末考(C)題目
返回小考目錄
回到首頁

期末考(C)題目

/* C Programming, final exam A */
/*
期末考題目：完成一個 print_tri 函數，以列印排列的數字。例如輸入 6 
            時，輸出
              654321
             65432
              6543
               654
                65
                 6 

            輸入 4 時，輸出
              4321
             432
              43
               4
                
函數輸入值：一個 int。 
函數輸出值： 無。 
題目輸入：一個整數 
題目輸出：印出倒三角形。 
*/

解答下載
返回小考目錄
回到首頁