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