程序設(shè)計(jì)實(shí)習(xí)第五講枚舉(參考版)
2024-10-02 16:56本頁面
【正文】 ? 輸出：輸出一個最短的移動序列，使得 9個時鐘的指針都指向 12點(diǎn)。 ? 輸入：從標(biāo)準(zhǔn)輸入設(shè)備讀入 9個整數(shù)，表示各時鐘指針的起始位置。共允許有 9種不同的移動。 } 作業(yè) 1： POJ1166 ? 問題描述：有 9個時鐘，排成一個 3?3的矩陣。 steps++。 } += dX。plant, plants, n, sizeof(PLANT), myCompare)) { //每一步都必須踩倒水稻才算合理，否則這就不是一條行走路徑 steps = 0。amp。amp。amp。 steps = 2。 = + dX。 } //判斷從 secPlant點(diǎn)開始，步長為 dx,dy，那么最多能走幾步 int searchPath(PLANT secPlant, int dX, int dY) { PLANT plant。 if ( p1x == p2x ) return(p1y p2y)。 p1 = (PLANT*) ele1。 printf(%d\n, max)。 //看看從這兩點(diǎn)出發(fā)，一共 //能走幾步 if (steps max) max = steps。 if ( pY c || pY 1) continue。說明本次選的第二點(diǎn)不成立。 //第一點(diǎn)的前一點(diǎn)在稻田里，說明本次選的第 //二點(diǎn)導(dǎo)致的 x方向步長不合理（太小 )，取下一個點(diǎn)作為第二點(diǎn) if (plants[ i ].x + (max 1) * dX r) break。amp。amp。amp。 pY = plants[ i ].y dY。 dY = plants[ j ].y plants[i].y。 j n 1 。 i n 2。 //將水稻按 x坐標(biāo)從小到大排序， x坐標(biāo)相同按 y從小到大排序 qsort(plants, n, sizeof(PLANT), myCompare)。plants[i].x, amp。 i n。n)。c)。 scanf(“%d%d”, amp。 int myCompare( const void *ele1, const void *ele2 )； int searchPath(PLANT secPlant, int dX, int dY) 。 PLANT plants[5001]。 struct PLANT { int x, y。 } 二分查找函數(shù)： void *bsearch(const void *key, const void *base, size_t nelem, size_t width, int (_USERENTRY *fcmp)(const void *, const void *))。 j ++ ) { a[i] = …。 i n – 1 ) for( int j = i + 1。 ? 顯然方案 1更符合問題本身的描述 設(shè)計(jì)的算法要簡潔 ? 盡量使用 C++提供的函數(shù)完成計(jì)算的任務(wù)：猜測一條行走路徑時，需要從當(dāng)前位置 (X， Y)出發(fā)上時，看看(X + dX， Y + dY)位置的水稻水稻是否被踩踏 ? 方案 1：自己寫一段代碼，看看 (X + dX， Y + dY) 是否在數(shù)組 plants中 。 } plants[5000]。當(dāng)下列條件之一滿足時，這個猜測就不成立 ? 青蛙不能經(jīng)過一跳從稻田外跳到 (X1， Y1)上 ? 按照 (X1， Y1)、 (X2， Y2)確定的步長，從 (X1，Y1)出發(fā)，青蛙最多經(jīng)過 (MAXSTEPS 1)步，就會跳到稻田之外。 ? 樣例輸入 6 7 //6行 7列 1 4 2 1 6 6 4 2 2 5 2 6 2 7 3 4 6 1 6 2 2 3 6 3 6 4 6 5 6 7 ? 樣例輸出 7 解題思路 枚舉 ? 每條青蛙行走路徑中至少有 3棵水稻 ? 假設(shè)一只青蛙進(jìn)入稻田后踩踏的前兩棵水稻分別是 (X1， Y1)、 (X2， Y2)。 ? 程序輸出：從標(biāo)準(zhǔn)輸出設(shè)備上輸出一個整數(shù)。在剩下的 N行中，每行有兩個整數(shù)，分別是一顆被踩踏水稻的行號 (1~R)和列號 (1~C)，兩個整數(shù)用一個空格隔開。第一行上兩個整數(shù) R、 C，分別表示稻田中水稻的行數(shù)和列數(shù)， 1≤R、 C≤5000。而在一條青蛙行走路徑的直線上，也可能會有些被踩踏的水稻不屬于該行走路徑 ? ① 不是一條行走路徑：只有兩棵被踩踏的水稻 ? ② 是一條行走路徑，但不包括（ 2， 6）上的水道 ? ③ 不是一條行走路徑：雖然有 3棵被踩踏的水稻，但這三棵水稻之間的距離間隔不相等 ① ② ③ ? 請你寫一個程序，確定：在各條青蛙行走路徑中，踩踏水稻最多的那一條上，有多少顆水稻被踩踏。 ? 根據(jù)圖 4，農(nóng)民能夠構(gòu)造出青蛙穿越稻田時的行走路徑，并且只關(guān)心那些在穿越稻田時至少踩踏了 3棵水稻的青蛙。有些水稻可能被多只青蛙踩踏。而青蛙總是從稻田的一側(cè)跳進(jìn)稻田，然后沿著某條直線穿越稻田，從另一側(cè)跳出去 ? 如下圖所示，可能會有多只青蛙從稻田穿越。每只青蛙總是沿著一條直線跳越稻田，而且 每次跳躍的距離都相同 。每到晚上，這種青蛙會跳越稻田，從而踩踏稻子。 n 64。 //輸出解 break。 break。 k 6。 } bool bOk = true。 k ++ ) { //算出第 k行開關(guān)起作用后的結(jié)果 ApplySwitch( anPuzzle[k], anPuzzle[k+
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1