2008年4月24日 星期四

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

2008年4月16日 星期三

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

2008年4月15日 星期二

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

2008年4月14日 星期一

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)題目
返回小考目錄
回到首頁

2008年4月9日 星期三

小考六(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)題目
返回小考目錄
回到首頁

2008年4月4日 星期五

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

2008年4月3日 星期四

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

2008年4月2日 星期三

如何學好C語言─王伯倫

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

liangk

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

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


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


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



資一甲,王伯倫