【筆記】名題精選百則-題意整理

名題精選百則，實有107組題目敘述/參考答案
不過如果嚴格地去除重複的部分應該是92道問題
(例如「列出所有子集」、「列出所有子集－字典順序」是一道問題，
「奇數階魔方陣」、「單偶數階魔方陣」、「雙偶數階魔方陣」也視為一樣的問題)

為求督促自己理解之效
這裡將所有題目的「題意」整理後，茲列表如下：



第一部分：序曲
1.最長平台：有一排序過的陣列，定義平台是幾個連續相同數字的區間，問最長平台有哪些
2.支配值數目：有兩排序過的陣列f[],g[]，存在f[i]>g[j]是為支配，問總共有幾對滿足條件的(i,j)
3.等值數目：有兩排序過的陣列f[],g[]，單陣列內不會有重複元素，問有幾組f[i]=g[j]
4.兩陣列最短距離：有兩排序過的陣列f[],g[]，求|f[i]-g[j]|的最小值
5.等值首尾和：正整數陣列x[]有n個元素編號0...n-1，問存在多少組(i,j)滿足sigma(0...i)=sigma(j...n-1)

第二部分：數字問題
6.Armstrong數：三位數abc滿足a^3 + b^3 + c^3 = abc是為Armstrong數，試求出所有的Armstrong數
7.數值字謎：VINGT+CINQ+CINQ=TRENTE，不同字母是不同的數且V,C,T不是0，求各字母代表的值
8.求質數：找出前N個質數
9.篩法、線性篩法：找出介於2...N之間的所有質數(我認為這和8是略有不同的)
10.因數分解：將一個正整數所有的質因數找出來
11.數值自乘遞歸解、非遞歸解：給正整數m,n，求m^n
12.Fibonacci數非遞歸解、快速解：定義f(1)=f(2)=1，f(n)=f(n-2)+f(n-1)，求f(n)
13.擴充Fibonacci數：定義f(0)=f(1)=1，f(n)=x(f(n-2))+y(f(n-1))，求f(n)
14.二項式係數加法解、快速解：求n個物件取r個的方法數(即求C(n,r))
15.階乘算法、快速解：求N!
16.連續整數的固定和：正整數n，正整數對(i,j)滿足1<=i,j<n，問有多少種(i,j)可以滿足n=sigma(i,j)

第三部分：排列、組合和集合
17.列出所有子集、字典順序：列出{1,2,3,...,n}的所有子集(含空集)
18.產生Gray碼：承17，按照Gray碼的順序列出所有子集(Gray碼是2^n個有n位二進制數組成，相鄰兩項只有一個bit不同的數列)
19.產生所有排列旋轉法、字典順序：列出n個元素的所有排列
20.所有K個元素的子集：將n個元素的集合{1,2,3,...,n}中含有k個元素的子集合，用字典順序列出來
21.集合的所有分割方式：所謂集合S的分割是有若干(p)個子集，(S1,S2,...,Sp)聯集是S，但任兩Si,Sj交集皆為空集。列出所有分割方式
22.整數的所有不同分割數目：求一個正整數n有幾種分解方法，例如4=3+1=2+2=2+1+1=1+1+1+1(不同順序算相同的方式)
23.整數的分割方式：承22，把所有可能的分割方法列出來

第四部分：搜尋
24.尋找足碼：有排序好的整數陣列x[]，元素皆不相同，問是否有元素滿足x[i]=i
25.尋找固定的和：對給定的值d以及兩個陣列x[]與y[]，找出滿足x[i]+y[j]=d的(i,j)
26.無限式搜尋：有一排序好的陣列，不知道有多少元素、末端填滿了「無限」值(也不知道這個值是多少)，找出陣列中是否有元素x
27.尋找極小值：有一循環排序的陣列x[]，即對某個x[i]具有x[0]<x[1]<...<x[i-1]以及x[i]<x[i+1]<...<x[n]<x[0](例如8,10,14,15,2,6)，找出這個陣列的最小值
28.兩個陣列的中位數：兩個排序好的陣列x[],y[]，找出x[]和y[]合併後的中位數
29.尋找中間值：整數陣列x[]滿足|x[i]-x[i+1]|<=1並且x[0]<x[n-1]，請找出是否有給定的數字a(保證x[0]<=a<=x[n-1])
30.三個陣列的共同元素：有三個排序好的陣列，找出值最小的共同元素
31.尋找最大與次大元素：給一陣列求最大值與次大值
32.搜尋矩陣：有大小n*n的矩陣M，所有元素都滿足M(i,j)<M(i,j+1)且M(i,j)<M(i+1,j)，換言之所有元素會小於右邊或下方的元素。找出M裡面是否含有K
33.表示或兩個數平方和：已知正整數R，找出所有滿足x^2+y^2=R的正整數對(x,y)
34.最大方塊區域：有一方陣以及給定值K，找出最大的一個正方形子區域裡所有的元素都是K

第五部分：排序(這章很像教科書的筆法)
35.二分插入法：基於插入排序法，作一個二分插入的程式
36.Shell法：作一個ShellSort的程式
37.快速排列法、保持等值原來順序、非遞歸堆疊法：作一個QuickSort的程式，進一步讓它能穩定排序、不用遞歸不用堆疊
38.求中位數：在不排序的前提下，找出一個陣列的中位數
39.堆積法、改良堆積法：作一個HeapSort的程式
40.合併法：作一個MergeSort的程式
41.桶子法：作一個BucketSort的程式
42.單一重複元素排序：對只有少數幾個值不同的陣列，發展一個較快的排序程式。
43.均勻重複元素排序：對少數幾種數均勻出線的陣列，發展一個較快的排序程式。
44.堆積式合併：在記憶體有限的情形下，將數個很大的陣列排序好。(就是外排序)
45.檢查陣列元素是否相異：已知一陣列，把重複出現的相同元素去到只剩一個
46.陣列中和為零的段落：一整數陣列元素全相異，找出是否有子陣列元素和為零
47.平面上的極大點：定義如果兩個座標點(x,y)與(a,b)，如果x>=a且y>=b我們說(x,y)支配了(a,b)。給一點集合，找出不被任何點支配的點(極大點)的數目
48.宴地中訪問數目的極大值：宴會中有n位賓客，他們分別在Xi時刻到達、Yi時刻離開，問整場宴會同時最多有幾個人在場？
49.包含在其他區間中間的區間：給n組互為相異的區間[ai,bi]，找出有哪些區間包含在別的區間裡(i被j包含即ai>=aj&&bi<=bj)

第六部分：字串
50.括號匹配問題：給一個括號序列，報告哪幾個括號是多餘的
51.轉換成後繼式寫法：讀入一個運算式，將它轉換成後序式
52.計算前置式寫法：承上，將中序式轉成前序式
53.KMP、BM法尋找字串：給兩字串T[],P[]，問P是否在T中出現？(或出現幾次)
54.所謂的h-序列：定義h-序列(1)只有'0'、(2)'1'緊接兩個h-序列。好比說0,100,10100,1100100都是h-序列。讀入一個字串判斷它是不是h-序列
55.尋找部分序列：給兩字串T[],P[]，問P是不是T的一個子序列
56.最長重複部分序列：給兩字串T[],P[]，定義P^i指的是把P的每個字寫i次(例如"abc"^2="aabbcc")，找出最大的i使得P^i是T的子序列
57.最長共同部分序列：找出最長的一個LCS並印出來
58.字串編修：有兩個字串s,t，我們可以(1)插入一個符號(2)刪除一個符號，問最少要做幾步才能把s變成t(最短編輯距離)
59.產生無連續重複部分的字串：產生由1,2,3構成、長度為n的字串，並且子串不能連續重複。例如12321,12312都算答案、12123卻不是(12相鄰)

第七部分：其它問題
60.BUFFON丟針問題：有兩條距離為L的平行線，以及一根長度為D的針。將針任意投擲，問壓線的機率是多少？
61.三色旗問題：有個由1,2,3(紅,白,藍)構成的陣列，將它排序好。並且每個元素測試顏色只能作一次、不能開額外記憶體。
62.字串列整數的轉換：改寫atoi()函數，使得它能報告OVERFLOW、UNDERFLOW、NO_ERROR
63.整數類型別的極值：求出目前機器上各種整數型別的最大最小值。不能用sizeof、limits.h
64.無限位數算術：作一個支援正整數加法與乘法的大數運算程式
65.線性表示、對稱表示的矩陣相乘：(1)將二維陣列轉成用一維陣列表示、(2)將(1)的結果還原成二維陣列、(3)基於(1)結果的矩陣相乘，以及當矩陣對稱時的情形
66.找零錢問題：某國發行了a1,a2,a3,...,ak幾種不同面額的紙鈔，問如果有n元要怎麼兌換才能使紙鈔數最少。
67.背包問題：有n個物件，體積分別是k1,k2,...,kn，有個容量K的背包，問能不能選幾個物件出來使背包剛好放滿
68.最佳矩陣相乘順序：已知一連串矩陣的各維度容量，問最少要作幾次乘法才能算出這一列矩陣的連乘積
69.最短路徑問題：有矩陣D=[dij](dij>0)表示i地到j地的距離，如果沒路這個值就是無窮大(用0表示)。把任意兩個地點的最短距離以及行經路徑找出來
70.產生匹配括號的字串：產生所有由n個左括號以及n個右括號構成的合法字串
71.穩定伴侶問題：有n個男孩和n個女孩，男孩(女孩)都各自列出對n個女孩(男孩)的喜好排名1~n，找出一種穩定的配對方式。(如果「我喜歡你勝過我老婆」而且「你喜歡我勝過妳老公」會發生外遇，是為不穩定)
72.單調矩陣的極值：所謂單調矩陣是對每一列的最大值來說，位在上方的列極大會落在下方列極大的左邊。找出每一列極大值的位置
73.向量分類：對兩個都有n個量的向量X=[X1,X2,...,Xn]和Y=[Y1,Y2,...,Yn]來說，所謂同一類是X1=Y1,X2=Y2,...,Xn=Yn，各元素之間只有相同或不相同(不能比大小)，將同樣的向量分在一起

第八部分：遊戲問題
74.魔方陣(奇數、單偶、雙偶)：定義n階魔方陣是將正整數1~n^2填到n*n矩陣裡，並且直行橫列對角線和相等。試填魔方陣當(1)n是奇數、(2)n有2(2m+1)型、(3)n是4的倍數
75.N後問題公式解、遞歸解：在n*n的棋盤上擺n隻皇后(攻擊對角線直行橫列)，求使n後不互相攻擊的解
76.武士巡邏：在n*n棋盤上在給定起點座標放一隻騎士(走L型)，求一種路徑可以走完n*n格。(另：什麼時候能回到起點？)
77.環遊世界：給定的圖上找漢米頓迴路
78.一筆畫：給定的圖上找尤拉迴路
79.非遞歸河內之塔：求解河內塔問題所需的步驟，限定不能遞歸不能堆疊模擬
80.生命遊戲：模擬生命遊戲，棋盤上有一些細胞，每經過一回合：(1)細胞鄰居數<=1會太孤單死掉、(2)鄰居數>3會太擠死掉、(3)一個空格的鄰居數=3會原地生出新細胞

第九部分：終曲
81.等量正負號段落：陣列中有很多正數、零、負數，找出最長的段落使得正數和負數的數量一樣
82.尋找長方形：圓周上有若干個點，依順時鐘給出點間的正整數弧長，問此點集是否能選四個點劃出長方形
83.多邊形的直徑：給n個點連成的(任意)多邊形，定義當Pi和Pj連線是直徑有：(i...j連線總和)和(其它連線總和)差的絕對值最小，報告任一組直徑
84.機器人旋轉角度：給平面上n個點p1,p2,...,pn，機器人一開始在p1且面向正東方。機器人會延p2,p3,..,pn的路徑行走、最後回到p1面向正東方。每次機器人都會先逆時針旋轉面向下一個點、然後以直線移動到該點。問總計旋轉了幾個360度(點座標是整數、要求運算過程只用整數)
85.最大涵蓋距離：已知陣列x[]，有i<=j、定義如果x[j]涵蓋[i,j]、表示i...j每一個數字都小於等於x[j]的絕對值。求最大涵蓋距離
86.最大連續元素和：有整數陣列x[]，求一段連續和使其值最大。可以全部都不取(值為0)
87.最大連續元素積：承上，改為求連續元素相乘的積最大
88.尋找名人：有n個人和他們彼此之間認識或不認識的關係，所謂名人是「大家都認得他、他不認得任何人」的那個人。每次都只能問一個人a「你是否認識b」，用最少詢問找出是否有名人(自己認不認得自己並不重要)
89.投票問題：有n個人，他們每個人可以投票圈選一個人(不一定在n個人中)，問是否有候選人得票超過半數
90.尋找1對1函數：集合S={0,1,2,...,n}、以及給定函數f:S->S，找出一個最大的子集S'使f:S'->S'是一對一函數
91.尋找支配元素：整數陣列x[]，所謂x[i]的右支配元素是有j>i且x[j]>=x[i]，找出所有元素各自最靠近的右支配元素
92.最長遞增部分序列：求LIS的長度