程序設(shè)計(jì)實(shí)習(xí)第五講枚舉-資料下載頁
2024-09-28 16:56本頁面
【導(dǎo)讀】一種解決問題的方法。找不到一個數(shù)學(xué)公式，使得我們根據(jù)N就可以計(jì)算出。判斷N-K是否是素?cái)?shù)的問題又成了求小于N-K的全部。2是素?cái)?shù)，記為PRIM0. 大的最小素?cái)?shù)PRIMk+1。判斷猜測的答案是否正確。猜測的結(jié)果必須是前面的猜測中沒有出現(xiàn)過的。猜測的過程中要及早排除錯誤的答案。賽利有12枚銀幣。其中有11枚真幣和1枚假幣。看起來和真幣沒有區(qū)別，但是重量不同。于是他向朋友借了一架天平。如果賽利用一枚真幣與另一。枚銀幣比較，發(fā)現(xiàn)它比真幣輕或重，說明它是假幣。輸入有三行，每行表示一次稱量的結(jié)果。其中平衡狀態(tài)用``up'',``down'',或。``even''表示,分別為右端高、右端低和平衡。右的硬幣數(shù)總是相等的。據(jù)已經(jīng)保證三組稱量后答案唯一。數(shù)組下標(biāo)3代表3次稱量；行有6個按鈕，共5行。每個案例由5行組成，每一行包括6
【正文】 j ++ ) { a[i] = …。 a[j] = …。 } 二分查找函數(shù)： void *bsearch(const void *key, const void *base, size_t nelem, size_t width, int (_USERENTRY *fcmp)(const void *, const void *))。 查到返回地址，查不到返回空指針 參考程序 include include int r, c, n。 struct PLANT { int x, y。 }。 PLANT plants[5001]。 PLANT plant。 int myCompare( const void *ele1, const void *ele2 )； int searchPath(PLANT secPlant, int dX, int dY) 。 void main() { int i,j, dX, dY, pX, pY, steps, max = 2。 scanf(“%d%d”, amp。r, amp。c)。 //行數(shù)和列數(shù) , x方向是上下， y方向是左右 scanf(%d, amp。n)。 for (i = 0。 i n。 i++) scanf(%d%d, amp。plants[i].x, amp。plants[i].y)。 //將水稻按 x坐標(biāo)從小到大排序， x坐標(biāo)相同按 y從小到大排序 qsort(plants, n, sizeof(PLANT), myCompare)。 for (i = 0。 i n 2。 i++) //plants[i]是第一個點(diǎn) for ( j = i + 1。 j n 1 。 j++) { // plants[j]是第二個點(diǎn) dX = plants[ j ].x plants[i].x。 dY = plants[ j ].y plants[i].y。 pX = plants[ i ].x dX。 pY = plants[ i ].y dY。 if (pX = r amp。amp。 pX = 1 amp。amp。 pY = c amp。amp。 pY = 1) continue。 //第一點(diǎn)的前一點(diǎn)在稻田里，說明本次選的第 //二點(diǎn)導(dǎo)致的 x方向步長不合理（太小 )，取下一個點(diǎn)作為第二點(diǎn) if (plants[ i ].x + (max 1) * dX r) break。 //x方向過早越界了。說明本次選的第二點(diǎn)不成立。 //如果換下一個點(diǎn)作為第二點(diǎn)， x方向步長只會更大，更不成立，所以應(yīng)該 //認(rèn)為本次選的第一點(diǎn)必然是不成立的，那么取下一個點(diǎn)作為第一點(diǎn)再試 pY = plants[ i ].y + (max 1) * dY。 if ( pY c || pY 1) continue。 //y方向過早越界了，應(yīng)換一個點(diǎn)作為第二點(diǎn)再試 steps = searchPath(plants[ j ],dX,dY)。 //看看從這兩點(diǎn)出發(fā)，一共 //能走幾步 if (steps max) max = steps。 } if ( max == 2 ) max = 0。 printf(%d\n, max)。 } int myCompare( const void *ele1, const void *ele2 ) { PLANT *p1, *p2。 p1 = (PLANT*) ele1。 p2 = (PLANT*) ele2。 if ( p1x == p2x ) return(p1y p2y)。 return ( p1x p2x )。 } //判斷從 secPlant點(diǎn)開始，步長為 dx,dy，那么最多能走幾步 int searchPath(PLANT secPlant, int dX, int dY) { PLANT plant。 int steps。 = + dX。 = + dY。 steps = 2。 while ( = r amp。amp。 = 1 amp。amp。 = c amp。amp。 = 1) { if (!bsearch(amp。plant, plants, n, sizeof(PLANT), myCompare)) { //每一步都必須踩倒水稻才算合理，否則這就不是一條行走路徑 steps = 0。 break。 } += dX。 += dY。 steps++。 } return(steps)。 } 作業(yè) 1： POJ1166 ? 問題描述：有 9個時鐘，排成一個 3?3的矩陣。 現(xiàn)在需要用最少的移動，將 9個時鐘的指針都撥到 12點(diǎn)的位置。共允許有 9種不同的移動。如右表所示，每個移動會將若干個時鐘的指針沿順時針方向撥動 90度。 ? 輸入：從標(biāo)準(zhǔn)輸入設(shè)備讀入 9個整數(shù)，表示各時鐘指針的起始位置。 1=12點(diǎn)、 1=3點(diǎn)、 2=6點(diǎn)、 3=9點(diǎn)。 ? 輸出：輸出一個最短的移動序列，使得 9個時鐘的指針都指向 12點(diǎn)。按照移動的序號大小，輸出結(jié)果 移動 影響的時鐘 1 ABDE 2 ABC 3 BCEF 4 ADG 5 BDEFH 6 CFI 7 DEGH 8 GHI 9 EFHI ? 樣例輸入 3 3 0 2 2 2 2 1 2 ? 樣例輸出 4 5 8 9 作業(yè) 2： POJ1681 畫家問題
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1