2008年5月24日 星期六

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"。
*/

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

2008年5月22日 星期四

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

2008年5月10日 星期六

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

2008年5月2日 星期五

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}};

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