C語言考古題 & C的解題 -- 程式設計學習入門

學習程式設計，語法固然重要，也是許多程式設計課程的教學重點。但是看的懂 C ，不見得會用 C 來解決問題(Problem solving)，所以學會解題是重點中的重點。學習C語言的不二法門，就是從寫程式解題開始，這裡的考古題由淺而深，循序漸進，對初學者甚有助益。 ACM 協會針對每年程式設計比賽的練習需求，建立一個線上的題庫與評分系統，希望藉由題庫練習的機會，在此心得分享，讓有心學習程式解題的人，能有個溝通成長的橋樑。

2010年2月26日星期五

Problem 483 Word Scramble，字的顛倒

Problem 483 是要讀入一個字後，將字串反轉印出。也是簡單的一題。

一開始宣告 char 陣列，一個讀入整行字串，一個讀入字，如同以下程式碼：

char str[MAXLEN], word[200];

接著一個字元依序讀入到 word 陣列，當讀到空白或者換行，則將 word 反轉印出：

while (gets(str))
{
    for (i = 0, j = 0;str[i] ; i ++)
    {
        if (str[i] != ' ')
        {
            word[j] = str[i];
            j ++;
        }
        else
        {
            for (k = j - 1; k >= 0; k --)
                printf("%c", word[k]);
            printf(" ");    
            j = 0;      
        }   
    }
    for (k = j - 1; k >= 0; k --)
        printf("%c", word[k]);
    printf("\n");         
}

By David.K

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

2010年2月25日星期四

Problem 482 Permutation Arrays，索引陣列

此題為簡單題，只是針對索引印出所對應的值就OK了。

首先可以先建立一個結構，如同以下程式碼：

#define MAXLEN 100000

int indexArray[MAXLEN];
int iAIndex; 

struct FloatStr
{
    char f[200];    
};
struct FloatStr fS[MAXLEN];

接下來將索引值記錄下來，放入 indexArray 陣列中：

iAIndex = 0;
while (1)
{
    scanf("%d", &m);
    indexArray[iAIndex] = m;
    iAIndex ++;
    ch = getchar();
    if (ch == '\n') break;
}

再將它記錄索引值的放入 fS 結構陣列中，再依序的印出：


while (1)
{
    scanf("%s", fS[indexArray[j] - 1].f);
    j ++;
    ch = getchar();
    if (ch == '\n') break;
}

for (j = 0; j < iAIndex; j ++)
    printf("%s\n", fS[j].f );

By David.K

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

Problem 446 Kibbles `n' Bits `n' Bits `n' Bits，十六進位的運算

此題是要輸入兩個 16 進位的數，依照運算子做相加或相減的運算後，輸出以 2 進位顯示兩數，以 10 進位顯示運算結果。

首先宣告三個 char 以讀入所要使用的資料，如同以下程式碼：

char hexOne[4], hexTwo[4], op;
scanf("%s %c %s", hexOne, &op, hexTwo);

讀入後，我將它轉成 10 進位，使用兩個整數(h1、h2)接收：

sizeOne = strlen(hexOne), sizeTwo = strlen(hexTwo);
int h1 = 0, h2 = 0, i, k, sum = 0;
for (i = sizeOne - 1, k = 1; i >= 0; i --, k *= 16)
    h1 += wordJudge(hexOne[i]) * k;
for (i = sizeTwo - 1, k = 1; i >= 0; i --, k *= 16)
    h2 += wordJudge(hexTwo[i]) * k;

wordJudge 函式：

int wordJudge(char hex)
{
    if (hex == 'A') return 10;
    else if (hex == 'B') return 11;
    else if (hex == 'C') return 12;
    else if (hex == 'D') return 13;
    else if (hex == 'E') return 14;
    else if (hex == 'F') return 15;
    else return (hex - '0');
}

接著使用函式將它轉成 2 近位後輸出：

void printBinary(int n)
{
     int i;
     for (i = 4096; i >= 1; i /= 2)
         if (n / i) printf("%d", n / i), n %= i;
         else printf("0");     
}

至於判斷加或減，又怎麼輸出，就交給你們去寫了。

By David.K

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

2010年2月23日星期二

Problem 587 There's treasure everywhere!，找尋寶藏

假設你現在手上有一張藏寶圖，通常他會要你東南西北選一個方向走個幾步，再換個方向走，一直走到寶藏之所在地，你必須依照它給的指示去尋找寶藏。

現在你有一張這種藏寶圖，你必須馬上算出寶藏所在地，以及你到寶藏所在地之最短距離。開始以(0,0)做為起點，數字為移動格數，東西南北以英文字母 E、W、S、N 表示。例如輸入 4S.，也就是寶藏所在地在(0,-4)，距離為 4。

此題以 double 定義 x、y 兩變數為目前所在地，當你初始化兩變數時，必須使它等於 1e-8(或更小的數)，因為假設你定義 x = 0, y = 0;後，接著再去算乘法，會有誤差。

以下為主程式程式碼：

int caseNum = 0;
while (gets(str))
{
    if (str[0] == 'E') break;
    p.x = 1e-12, p.y = 1e-12;  
    int i, fIndex = 0;
    double nowSteps = 1e-12;
    char nowFace[2];
    for (i = 0; str[i]; i ++)
    {
        if (str[i] >= '0' && str[i] <= '9')
           nowSteps *= 10.0 ,nowSteps += str[i] - '0';
        else if (isalpha(str[i]))
           nowFace[fIndex] = str[i], fIndex ++; 
        else
        {
           if (fIndex == 1)
              moveLinear (nowFace[fIndex - 1], nowSteps);
           else
              moveSlash (nowFace, nowSteps);
           fIndex = 0;
           nowSteps = 1e-12;   
        }
    }
    
    printf("Map #%d\n", ++caseNum);
    printf("The treasure is located at (%.3lf,%.3lf).\n",p.x, p.y);
    printf("The distance to the treasure is %.3lf.\n\n",sqrt(p.x*p.x + p.y*p.y));
}

而函式以及結構程式碼如下：

#define MAXLEN 250
char str[MAXLEN] = {"\0"};
struct Point
{
    double x, y;   
};
struct Point p;
void moveLinear (char f, double steps)
{
    if (f == 'N') p.y += steps;
    else if (f == 'E') p.x += steps;  
    else if (f == 'W') p.x -= steps;
    else if (f == 'S')p.y -= steps;
}
void moveSlash (char f[], double steps)
{
    int i; 
    steps *= sqrt(2) / 2; 
    for (i = 0; f[i]; i ++)
        moveLinear(f[i] , steps);
}

By David.K

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

2010年2月19日星期五

Problem 530 Binomial Showdown，C 的值

Problem 530 是輸入兩數 n 和 m 值後，算出

。

假設 n = 8, m = 3，則可以知道 8!/ (5! * 3!)，也就是說，可以看成 8*7*6 / 1*2*3，依照 m 的大小來看，分母是從 8 乘到 6，分子就是從 1 乘到 3。但是在這個例子中，m 若大於 4，就要將 n - m再回傳給 m，因為

，所以這種情況會導致你WA。

以下是主程式程式碼：

int n, m, i;
double total;
while (1)
{
   total = 1;
   scanf("%d %d", &n, &m);
   if (n == 0 && m == 0) break;
   if(m > n/2) m = n - m;
   for (i = 1; i <= m; i ++)
       total *= ((double)n - (double)i + 1) / (double)i;
   printf("%.0f\n", total);    
}

By David.K

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

2010年2月18日星期四

Problem 880 Cantor Fractions，對映關係

Problem 880 此題需要用到等差級數的概念。

i 值	分子	分母	項
1	1	1	1
2	2	1	2
3	1	2	2
4	3	1	3
5	2	2	3
6	1	3
...	...	...	...
...	...	...	...

以上表是分析 Cantor 數的一些關聯，可以發現分母一直在做循環，只是每次多加了 1，從 1、1,2、1,2,3、1,2,3,4....等等；分子也是一樣，但它是顛倒的，1、2,1、3,2,1、4,3,2,1....等等。這就是等差級數的項數，好比說我們要找第 6 個 Cantor fraction，也就是 i = 6，則 S_n = 6，則 n = 3，我們就知道 6 是在 1,2,3 這個循環裡。就算用 5 也一樣， n = 2.701(無條件進位) = 3。

所以我們可以來推導公式：

              S_n = i
       n*(n+1)/2 = i
         n*(n+1) = i*2
n²+n+(1/4)-(1/4) = i*2
      (n+(1/2))² = i*2+(1/4)
               n = (i*2+0.25)^1/2-0.5

以上結果化為程式碼如下：

if (scanf("%lld", &i) < 1) break;
n = (long long int)ceil(sqrt(i * 2 + 0.25) - 0.5 );

如此一來，i 是第幾項也都知道了，接著只須算出它前一個項的總和，再去和 i 相減即可算出分母，分母既然算出來了，分子也就不難算了，請參考以下程式碼：

sN = (n-1) * n / 2;
printf("%lld/%lld\n", abs((i - sN) - (n+1)), i - sN);

abs 函式的程式碼：

long long int abs (long long int n)
{
    return n > 0? n:-n; 
}

By David.K

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

2010年2月17日星期三

Problem 847 A multiplication game，Stan 和 Ollie 的遊戲

Problem 847 此題是史丹和歐力的遊戲，兩人選定一個數 n 後，將 p = 1 使用 2 到 9 之間的任一數累乘，而史丹先開始再換歐力，如此輪流，當 p 累乘到大於 n 時，則為此人獲勝。

這題的解法就是在 n = 1 - 9 時為史丹贏、n = 10 - 18 為歐力贏、n = 19 - 162 為史丹贏、n = 163 - 324 為歐力贏....。也就是說，當史丹決定乘數時，p 用 9 乘，看它有沒有大於 n，如果有大於 n，就是史丹贏；當為歐力決定乘數時，p 用 2 乘，看它有沒有大於 n，如果有大於 n，就是歐力贏。

以下為此題重點程式碼：

if (scanf("%lld", &n) < 1) break;
p = 1; i = 1;
while (1)
{
    if (i % 2) p *= 9;
    else p *= 2;
    if (p >= n) 
    {
        if (i % 2) printf("Stan wins.\n");
        else printf("Ollie wins.\n");
        break;
    }
    i ++;  
}

By David.K

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

Problem 948 Fibonaccimal Base，費氏級數進位

Problem 948 是要寫一個「十進位」轉成「費氏級數進位」的程式。

首先這要先求出費氏級數擺入陣列，大概宣告 39 個就夠了，依照 f(1) = 1、f(2) = 2，當 n > 2時，f(n) = f(n-1) + f(n-2)，則程式碼如下：

int fib[39] = {0};

void getFib()
{
     int i;
     fib[0] = 1, fib[1] = 2;
     for (i = 2; i < 39; i ++)
         fib[i] = fib[i - 1] + fib[i - 2];
}

只須再程式一開始呼叫 getFib() 函式，就會建立 Fib 的表出來。而主程式中只須將輸入的數值去除每一個 Fib 的數值看它是否為 1，為 1 就印出 1，沒有就印出 0，而程式碼如下：

int n, i, m, j, isPut;
getFib();
scanf("%d", &n);
for (i = 0; i < n; i++)
{
    scanf("%d", &m);
    printf("%d = ", m);
    isPut = 0;
    for (j = 38; j >= 0;j --)
    {
        if ((m / fib[j]) == 1)
        {
            printf("1");
            m %= fib[j];   
            isPut = 1;   
        }
        else if (isPut && (m / fib[j]) == 0)
            printf("0");     
    }
    printf(" (fib)\n");
}

By David.K

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

2010年2月16日星期二

Problem 900 Brick Wall Patterns，模型組合次數

Problem 900 也是需要用費氏(Fibonacci)級數的概念。

此題與 11069 的概念相同，當 f(1) = 1、f(2) = 2，當 n > 2時， f(n) = f(n-1) + f(n-2)。

以下為主程式程式碼：

int i, n;
brick[0] = 1, brick[1] = 2;
for (i = 2; i < MAXLEN; i ++)
    brick[i] = brick[i - 1] + brick[i - 2];
while (1) 
{
    scanf("%d", &n);
    if (n == 0) break;
    printf("%d\n", brick[n - 1]);  
}

By David.K

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

Problem 10499 The Land of Justice，利潤

Problem 10499 是假設賣一個球形商品以它的表面積來算價格，當它切平等的切割成數塊，利潤會是原本的多少。

此題只須想一下就可以了。一個球體表面積為 4*pi*r²，當球體分割成 n 塊後，每一塊分割的球體一定都會多一個完整的圓面積，此圓面積為 pi*r²，所以除了不分割外，可以推導公式當 n > 1時， n*pi*r² / 4*pi*r² = n / 4 = n * 0.25。
也就是說每分成 n 塊，就會多增加 25% 的利潤。

以下為主程式程式碼：

while (1)
{
    long long n;
    scanf("%ld", &n);

    if (n < 0L) { break; }

    if (n == 1L) { printf("0%%\n"); }
    else        { printf("%ld%%\n", n * 25); }
}

By David.K

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

2010年2月11日星期四

Problem 10815 Andy's First Dictionary，詞彙

Problem 10815 此題需將輸入的一段文章，接著我們必須紀錄它詞彙並由 a - z 排序輸出。

此題我還是用一個結構(struct)去解決它，將這結構宣告一個長度為 5000 的陣列後，儲存所有出現過的詞。我一開始使用 ctype.h 的 isalpha() 判斷是否為英文字母，如果是，就一直擷取出來放入一個暫存的 char 陣列，如果擷取到非字母或者是結尾符號 '\0'，就將字加入結構陣列，順便判斷是否重複，以及排序。

以下是結構的設定：

#define MAXLEN 5000
struct Word
{
    char word[20];
};
struct Word w[MAXLEN];
struct Word wRecode, change;

以下是主程式區段程式碼：

char str[200] = {"\0"};
while (gets(str))
{
    
    j = 0; int isWord = 0;
    for (i = 0; str[i]; i ++)
    {
        if (isalpha(str[i]))
        {
            wRecode.word[j] = tolower(str[i]);
            j ++;
            isWord = 1;
            continue; 
        }
        else if (isWord)
        {
            insert();
            j = 0, isWord = 0; 
            memset(wRecode.word, 0, strlen(wRecode.word));
        }
    }
    if (isWord && str[i + 1] == '\0')
        insert(), j = 0, isWord = 0, memset(wRecode.word, 0, strlen(wRecode.word));
    memset(str, 0, strlen(str));    
        
}

以下是 insert() 函式程式碼：

void insert ()
{
    int isRepeat = 0,i; 
    for (i = 0; i < index; i++)
        if (strcmp(wRecode.word, w[i].word) == 0)
            isRepeat = 1;
    if (!isRepeat)
    {
        w[index] = wRecode, index ++; 
        for (i = index - 1; i >= 1; i --)
        {
            if (strcmp(w[i].word, w[i - 1].word) == -1)
            {
               change = w[i];
               w[i] = w[i - 1];
               w[i - 1] = change;
            }
        }
    }       
}

By David.K

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

2010年2月10日星期三

Problem 170 Clock Patience，紙牌遊戲

Problem 170 此題最大的問題就是它的敘述有誤，它說是依照 A 順時針發到 Q，再發 K。真正的發牌順序是先發 K，再從 Q 逆時針發到 A。而最上面的牌是第一列的牌，最下面的牌是第四列的牌。除此之外就沒有問題了，可是題目敘述搞成這樣，讓人霧煞煞，真是"奇牌"。

例如：
TS QC 8S 8D QH 2D 3H KH 9H 2H TH KS KC
9D JH 7H JD 2S QS TD 2C 4H 5H AD 4D 5D
6D 4S 9S 5S 7S JS 8H 3D 8C 3S 4C 6S 9C
AS 7C AH 6H KD JC 7D AC 5C TC QD 6C 3C
而 K 堆牌由上而下為 TS、9D、6D、AS，Q 堆牌由上而下為 QC、JH、4S、7C，以此類推。再來，如果輸出向上翻的牌數為個位數，前面要加 0。

一開始先建立一個結構(struct)，為以下程式碼：

struct Poker
{
    char points;
    char color;
    int isExist;
};
struct Poker p[13][4];

再依次將牌擺入陣列之中：

char str[40];  
int i, j, nIndex, k = 0, isTurn, turnCount;
char ch, nowPoints, nowColor;  
for (i = 0 ; i < 4; i ++)
{
    memset(str, 0, strlen(str));
    gets(str);
    if (str[0] == '#') break;
    j = 0;
    while (str[j] != '\0')
    {
        if (j % 3 == 0)
            ch = str[j]; 
        else if (j % 3 == 1)
        {
            p[(j-1)/3][k].points = ch;
            p[(j-1)/3][k].color = str[j];
            p[(j-1)/3][k].isExist = 1;
        }
        j ++;  
    }
    k ++;
}
if (str[0] == '#') break;

接下來，只須將 K 堆第一個牌記錄下來，以上面的例子來看為 TS，將它的 isExist 變為 0，再去尋找 T 堆牌的第一張牌 8S，判斷它的 isExist 為不為 1，若不為 1 再看第二張牌，但它為 1，所以再去尋找 8 堆牌的第一張牌，如此如此找下去，當找到四張牌 isExist 都是 0 時，就印出目前紀錄的牌就可以了。

By David.K

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

2010年2月8日星期一

Problem 10922 2 the 9s，9 的倍數

Problem 10922 此題要輸入一個 n 值後，判斷它是否為 9 的倍數以及它的 9-degree。

本來我還看不懂這題的意思，所以我就上網去找這題的資料，發現原來是將此數的所有位數相加後除以 9 ，若是小於 10 ，則結束；若不小於 10 ，則要繼續將 n/9 的所有位數相加後再除以 9，再判斷下去。
例如：999999999999999999999 (21個9)，相加後等於189，不小於10，而189 mod 9也等於 0，則可先知道它是 9 的倍數，189 相加後等於 21，不小於10 ，再相加後等於 3，此值小於10，則結束。f(999999999999999999999) = f(189) = f(21) = f(3)，總共做了三次，所以 degree 為 3。

當我了解這個原則後，就寫出來了。

以下是函式程式碼：

int degree()
{ 
 int len = strlen(tmp), n = 0, i;
 for(i = 0;i < len; i ++)
  n += tmp[i] - '0';
 sprintf(tmp, "%d", n); 
 return n;
}

By David.K

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

2010年2月7日星期日

Problem 11000 Bee，蜜蜂的數量

Problem 11000 此題是說一隻母蜂一年會生下一隻公蜂，而公蜂則會生下一隻公蜂和一隻母蜂，然後死掉。問你 n 年後會有幾隻蜜蜂，而其中這些蜜蜂，又有幾隻是公蜂。

此題只要算它前幾個結果，並找出其中的關係，其實不難。公蜂的數量從 0 年算起數量的變化為：0 -> 1 -> 2 -> 4 -> 7 -> ...；而母蜂的數量從 0 年算起數量的變化為：1 -> 1 -> 2 -> 3 -> 5 -> ...。可以發現，當年的公蜂數量是去年公蜂和母蜂加總，而母蜂的數量是去年和前年的母蜂加總，有了這個關係，就很好寫了。

以下是主程式區塊程式碼：

long n, i;
scanf("%ld", &n);
if (n < 0) break;
long female[2], recode, male = 0,total = 0;
female[0] = 0, female[1] = 1;
if(n == 0)
{
    printf("0 1\n");
    continue;
}
else
    for(i=1 ; i<=n ; i++)
    {
        male = female[1] + male;     
        recode = female[1] ,female[1] += female[0], female[0] = recode;
        total = male + female[1];  
    }
printf("%ld %ld\n", male, total);

By David.K

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

2010年2月6日星期六

Problem 145 Gondwanaland Telecom，電話收費

Problem 145 設定了一個收費表，用通話距離以及通話時段區分不同的收費價格，給你一段時間，要計算出個時段所用的分鐘數，以及通話費。

這題只要想得出方法來算個時段的分鐘數，就可以解得出來了，跨夜時段比較難算，其他大概就沒有甚麼問題了。

以下是主程式程式碼：

struct Converse
{
    char charge, telephone[8];
    int sHour, sMin, eHour, eMin;
};
void getTime (int sH, int sM, int eH, int eM);
struct Converse c;
float charging[5][3] = { {0.10, 0.06, 0.02},
                         {0.25, 0.15, 0.05},
                         {0.53, 0.33, 0.13},
                         {0.87, 0.47, 0.17},
                         {1.44, 0.80, 0.30} };
int dayTime, eveningTime, nightTime;                         
int main()
{   
    while (1)
    {
        scanf("%c",&c.charge);
        if (c.charge == '#') break;
        scanf("%s %d %d %d %d",c.telephone ,&c.sHour ,&c.sMin ,&c.eHour ,&c.eMin);
        int chargeIndex = c.charge - 'A';
        dayTime = 0, eveningTime = 0, nightTime = 0;
        
        if(c.sHour >= c.eHour && c.sMin >=  c.eMin)
            getTime(c.sHour, c.sMin, 24, 0) ,getTime(0, 0, c.eHour, c.eMin);
        else
            getTime(c.sHour, c.sMin, c.eHour, c.eMin);

        float money = (float)(dayTime * charging[chargeIndex][0]) + 
                      (float)(eveningTime*charging[chargeIndex][1]) +
                      (float)(nightTime*charging[chargeIndex][2]);

        printf("%10s%6d%6d%6d%3c%8.2f\n", c.telephone, dayTime, eveningTime, nightTime, c.charge, money);
        char ch = getchar();
    }    
    return 0;
}

接下來 getTime 函式就交給大家去寫了。

By David.K

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

2010年2月5日星期五

Problem 130 Roman Roulette，生死遊戲

Problem 130 此題是要算出從第幾個位置開始數，才會讓你存活下來。

一開始我設了兩個整數陣列，依照給予的 n 值做為陣列的長度，如同以下程式碼設定以及初始化：

int isLife[n], NO[n];
for (s = 0; s < n; s ++)
    isLife[s] = 1, NO[s] = s + 1;

isLife 陣列為是否有存活，NO 陣列為人的編號。因為殺掉第一個人後就要交換位置，所以我用 isLife[NO[nowSite] - 1] (nowSite 為目前位置)來判斷這個人有沒有死亡。再來，讓 nowSite 持續累加，等於 n 時則變 0，再設定一個整數 count，當 nowSite 這位置的人存活時累加 count，而 count mod (k-1) 時若等於 0 時，則表示在 NO[nowSite] 這個編號的人即將被殺，也就是 isLife[NO[nowSite] - 1] = 0。在這指令之後，就要做交換位置的動作，而找到要交換位置的人，跟上面的做法雷同，程式碼貼在以下，給大家參考，但我相信還有更好的方法。

以下為主程式區段程式碼：

for (i = 0; i < n; i ++)
{
    for (s = 0; s < n; s ++)
        isLife[s] = 1, NO[s] = s + 1;
    int nowSite = i, count = 0, nowLife = n;
    while (nowLife != 1)
    {
        nowSite ++;
        if (nowSite == n)
            nowSite = 0;
        if (isLife[NO[nowSite] - 1])
        {
           count ++;
           if (count % (k-1) == 0)
           {      
               isLife[NO[nowSite] - 1] = 0;
               nowLife --, count = 0;
               if (nowLife == 1) break;
               int changeSite = nowSite, r;
               while (1)
               {
                   changeSite ++;
                   if (changeSite == n)
                       changeSite = 0;
                   if (isLife[NO[changeSite] - 1])
                   {
                       count ++;
                       if (count % k == 0)
                       {
                           r = NO[nowSite];
                           NO[nowSite] = NO[changeSite];
                           NO[changeSite] = r;
                           count = 0;
                           while (1)
                           {
                               nowSite ++;
                               if (nowSite == n)
                                   nowSite = 0;
                               if (isLife[NO[nowSite] - 1])
                                   break;
                           }
                           break; 
                       }
                   }        
               }
           }    
        }   
    }
    if (isLife[0])
    {
        printf("%d\n", i + 1);
        break;              
    }
}

By David.K

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

2010年2月4日星期四

Problem 118 Mutant Flatworld Explorers，機器人的移動

Problem 118 此題需要輸入一個矩形的大小，而給定機器人初始位置後，下一些指令使它轉動或移動，當它走出矩形之外就會消失，在消失之前，機器人會在此點上做「標記」，以防下一個機器人走到此點再次消失。

這題我一開始就先設計一個結構(struct)，裡面紀錄 x 座標和 y 座標和它面向什麼方向，這有兩個地方會用到這個結構，一個是「機器人」，另一個是「標記」，如同以下程式碼：

#define MAX 100
struct Robots
{
    int x;
    int y;
    char face;   
};
struct Robots r;
struct Robots scent[MAX];

接著，機器人的動作我分成「轉動」和「移動」兩個部分，所以我分兩個函式去做它，在寫這些這兩個函式之前，需要先寫一個函式判斷機器人有沒有走出矩形之外，如同以下程式碼：

int isInSite (int x, int y)
{
    // topX 和 topY 為右上角頂點。
    if (topX >= x && x >= 0 && topY >= y && y >= 0) 
       return 1;
    return 0;
}

主程式中，在讀入機器人指令為 'F' 則跳入 move() 函式；讀入指令不為 'F'，則跳入 changeFace(char ch) 函式，以下為主程式區段程式碼：

gets(str);
for (i = 0; str[i];i ++)
{
    if (!inSite) break;
    if (str[i] == '\n') break;
    if (str[i] == 'F') inSite = move();
    else changeFace(str[i]);
}

以下為 move() 和 changeFace(char ch) 函式程式碼：

void changeFace (char ch)
{
    if (ch == 'R')
        if (r.face == 'N') r.face = 'E';
        else if (r.face == 'E') r.face = 'S';
        else if (r.face == 'S') r.face = 'W';
        else r.face = 'N';
    else 
        if (r.face == 'N') r.face = 'W';
        else if (r.face == 'W') r.face = 'S';
        else if (r.face == 'S') r.face = 'E';
        else r.face = 'N'; 
}

int move ()
{
    int i, isInScent = 0;
    if (r.face == 'N') r.y ++;    
    else if (r.face == 'E') r.x ++;  
    else if (r.face == 'S') r.y --;
    else r.x --;
    
    if (isInSite(r.x, r.y))
       return 1;
    else
    {
       if (r.face == 'N') r.y --;
       else if (r.face == 'E') r.x --;  
       else if (r.face == 'S') r.y ++;
       else r.x ++;
       for (i = 0; i < index; i ++)
           if (scent[i].x == r.x && scent[i].y == r.y)
           {
              isInScent = 1;
              break;
           } 
       if (isInScent)    
          return 1;
       else
       {       
          scent[index].x = r.x, scent[index].y = r.y, index ++;
          return 0;
       }
    } 
}

如此一來，上傳後雖然有一些小錯誤，但修正後還是過了。

By David.K

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

Problem 107 The Cat in the Hat，等比級數的運算

Problem 107 此題是輸入貓的高度以及牠最後工作的貓數量，請你算出牠所有貓高度總和以及最後沒工作的貓數量。

此題是一個簡單的等比級數運算，找它的例子來看不難發現，其實就是要解 rⁿ = 125 and (r+1)ⁿ = 216，簡化兩式後，log_n125 = log_(n+1)216，接下來程式就很好寫了。

以下是主程式區塊提示：

int n = 0, p = 0;
scanf("%d %d", &catH, &catWorkCount);
if (catH == 0 || catWorkCount == 0) break;
if (catH == 1 && catWorkCount == 1)
    printf("%d %d\n", 0, 1);
else if (catH == 1)
    printf("1 %d\n", catWorkCount);
else
{
    ...
    ...
    ...
}

By David.K

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

2010年2月3日星期三

Problem 10550 Combination Lock，轉動多少角度

Problem 10550 此題是輸入刻度開始位置、第一個密碼、第二個密碼、第三個密碼，接著請你算出要開鎖的話，需轉動多少角度。

仔細觀察鎖的構造，不難發現它如果順時針轉，對於刻度則是逆時針轉；反之，則相反。所以只須設定幾個條件即可求出答案。

以下為主程式區段程式碼：

scanf("%d %d %d %d",&startNum, &pw1, &pw2, &pw3);
if (startNum == 0 && pw1 == 0 && pw2 == 0 && pw3 == 0) break;
sum = 720 + 360;

if (startNum >= pw1) sum += (startNum - pw1) * 9;
else if (startNum < pw1) sum += (startNum + 40 - pw1) * 9;

if (pw1 > pw2) sum += (40 - pw1 + pw2) * 9;
else if (pw1 <= pw2) sum += (pw2 - pw1) * 9;

if (pw2 >= pw3) sum += (pw2 - pw3) * 9;
else if (pw2 <= pw3) sum += (40 - pw3 + pw2) * 9;

By David.K

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

2010年2月2日星期二

Problem 10473 Simple Base Conversion，數值轉換

Problem 10473 此題是若輸入為一10進位數，則輸出它的16進位數；若輸入一16進位數，則輸出它的10進位數；若輸入負值，則結束。

此題只需用簡單的格式化輸出即可。以字串讀入輸入數值，若為負值，只需判斷索引為 0 的字元是否為字元 "-" (減號)；若為16進位數，只需判斷索引為 0 的字元是否為字元 "0"；以上判斷都為否時，則此數為10進位數。

當讀進10進位數時使用 %d 讀取，使用 0x%X 輸出( %x 為無號的十六進位整數)；讀進16進位數時使用 %x 讀取，使用 %d 輸出即可。

以下為主程式程式碼：

int i, n;
char str[10];
while (1)
{
   scanf ("%s", str);
   if (str[0] == '-') break;
   else if (str[0] != '0')
      sscanf(str ,"%d" ,&n), printf("0x%X\n", n);
   else
      sscanf(str ,"%x" ,&n), printf("%d\n", n);
}   
return 0;

By David.K

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

訂閱：文章 (Atom)

考古題-小考系列	考古題-作業系列	成功學習C語言-感想短文
ACM比賽題庫解題	程式設計比賽(95)	C#程式語言教學
Crystal Report 教學

C語言考古題 & C的解題 -- 程式設計學習入門

網頁

2010年2月26日星期五

Problem 483 Word Scramble，字的顛倒

2010年2月25日星期四

Problem 482 Permutation Arrays，索引陣列

Problem 446 Kibbles `n' Bits `n' Bits `n' Bits，十六進位的運算

2010年2月23日星期二

Problem 587 There's treasure everywhere!，找尋寶藏

2010年2月19日星期五

Problem 530 Binomial Showdown，C 的值

2010年2月18日星期四

Problem 880 Cantor Fractions，對映關係

2010年2月17日星期三

Problem 847 A multiplication game，Stan 和 Ollie 的遊戲

Problem 948 Fibonaccimal Base，費氏級數進位

2010年2月16日星期二

Problem 900 Brick Wall Patterns，模型組合次數

Problem 10499 The Land of Justice，利潤

2010年2月11日星期四

Problem 10815 Andy's First Dictionary，詞彙

2010年2月10日星期三

Problem 170 Clock Patience，紙牌遊戲

2010年2月8日星期一

Problem 10922 2 the 9s，9 的倍數

2010年2月7日星期日

Problem 11000 Bee，蜜蜂的數量

2010年2月6日星期六

Problem 145 Gondwanaland Telecom，電話收費

2010年2月5日星期五

Problem 130 Roman Roulette，生死遊戲

2010年2月4日星期四

Problem 118 Mutant Flatworld Explorers，機器人的移動

Problem 107 The Cat in the Hat，等比級數的運算

2010年2月3日星期三

Problem 10550 Combination Lock，轉動多少角度

2010年2月2日星期二

Problem 10473 Simple Base Conversion，數值轉換

C語言與C#語言分類目錄

網頁

2010年2月26日 星期五

2010年2月25日 星期四

2010年2月23日 星期二

2010年2月19日 星期五

2010年2月18日 星期四

2010年2月17日 星期三

2010年2月16日 星期二

2010年2月11日 星期四

2010年2月10日 星期三

2010年2月8日 星期一

2010年2月7日 星期日

2010年2月6日 星期六

2010年2月5日 星期五

2010年2月4日 星期四

2010年2月3日 星期三

2010年2月2日 星期二

C語言與C#語言分類目錄

2010年2月26日星期五

2010年2月25日星期四

2010年2月23日星期二

2010年2月19日星期五

2010年2月18日星期四

2010年2月17日星期三

2010年2月16日星期二

2010年2月11日星期四

2010年2月10日星期三

2010年2月8日星期一

2010年2月7日星期日

2010年2月6日星期六

2010年2月5日星期五

2010年2月4日星期四

2010年2月3日星期三

2010年2月2日星期二