資訊處理 95 年程式設計概要考古題

設輸入為一串整數數列，請從中找出一個長度最長的遞增子串列，當此子串列不唯 一時，選取其中和最大的子串列。例如：當輸入串列為9、15、7、6、11、12、4 時， 輸出為9、11、12 。請以C、C++、JAVA 或VB（Visual Basic）中任一程式語言作 答。（20 分）

請撰寫一函式（function）：int inverse (int x)。此函數被呼叫時會根據傳入之四位數 正整數變數x（大小範圍為1000<= x <=9999）的內含值，傳回與x 相反順序的數字。 （15 分） 例如：若int x = 3467; int k = inverse (x); 則整數變數k 的內含值將為7643 若int x = 2730; int k = inverse (x); 則整數變數k 的內含值將為372

請利用迴圈控制指令，由外部資料檔讀入欲反轉字串，將此字串反轉後，印出此字 串。請以C、C++、JAVA 或VB（Visual Basic）中任一程式語言作答。（20 分）

請利用第一題的inverse (x)函式，撰寫一程式解決下列問題：所有的四位數整數中存 在某些四位數整數乘以一個個位數整數之後會變成該四位數相反順序的數字。 例如：2178×4=8712 請撰寫一程式找出所有符合上述條件的四位數及所對應的個位數，並於螢幕上印出。 （20 分）

數學上有一種費氏級數（Fibonacci numbers），其定義如下： ⎩ ⎨ ⎧ > − + − = = 2 ), 2 ( )1 ( 2 ,1 ,1 ) ( n if n Fib n Fib n if n Fib 請說明產生n = 500 的費氏級數適合使用遞迴（recursive）演算法或疊代（iteration） 演算法？寫出你的答案與理由。（20 分）

假設已存在一實數亂數函數float random ( )可以傳回一大於等於零且小於1 的實數 （亦即0 <= random ( ) < 1）。利用此函數，請撰寫另一函數int RND (int m, int n)可以 傳回一介於m～n 之間的整數亂數（亦即m <=RND (m,n) <= n）。（15 分） 例如：int k = RND (10,20); 則傳回之整數亂數必介於10～20 之間

請由小至大列出下述函數之複雜度：1000000, nlogn, n2, (3/2)n, loglogn, n2logn。寫出 你的答案與理由。（20 分）

請利用第三題的RND (m,n)函式，撰寫一程式可以產生二十組10～50 的亂數（彼此 不可以相同）存入一整數矩陣a 中，然後將此二十組亂數印在螢幕上。（30 分） 注意：此二十組亂數彼此不可以相同。

考慮下列程式片段： S1: procedure P(L) /* L 為一串數字*/ S2: 若L 的長度為2，則return 此二數字之和 S3: L1 = L 的前半部分 /* if L=1234, L1=12 */ S4: L2 = L 的後半部分 /* if L=1234, L2=34 */ S5: L3 =將L 分成四部分，第2 及第3 部分之組合/* if L=1234, L3=23 */ S6: return (P(L1)+P(L2)+P(L3)) 若L=87654321（長度為8），則最後return 之結果為何？（20 分）

請撰寫一遞迴函式（recursive function）：int OddSUM (int a[] , int n)。能計算出有n 個元素的整數陣列a 中所有奇數元素的總和。（20 分） 注意：必須以遞迴方式撰寫。 例如：int a[3]; a[0]=3; a[1]= 4; a[2]=7; int k=OddSUM (a[],3); 則k 將等於10