警告：本文內容可能影響您思考的樂趣，觀看前請三思 ---- 防雷頁 ---- 第一題： 解 4x4 的數獨，輸出其字典序最小的一組解，以及解的個數 一般看到數獨時，很容易會去思考能否用一般我們解數獨時的方法 但是這樣很難實作，畢竟要用一堆技巧交叉利用，也很容易漏掉或不小心寫錯 而難以 debug，因此這裡必須借助電腦的運算能力，使用笨一點的方法 加上所求為所有解，也就是說可能有多重解的情形，這在手寫上也是很不利的一點 一個最笨的想法是，在每一個空格填上 1~4 的數字，看會不會矛盾 對於不會矛盾的情形，去填下一個空格，矛盾就試其它數字，都試過了就回去改上一格 如果可以填到沒有空格可以填，那麼表示我們找到了一組可行解 這裡我們可以用遞迴的特性來解這一題 一開始我們先找出所有的空格，並建成一張表，假設表的大小是 n 則從 0 開始，對於每一個空格 i 試著填入 1~4 的數字，如果發現有數字可以填 那麼就填上去，並遞迴去填 i+1 格，直到 i==n 表示我們找到了一組解 所有可能都試過後，就 return 回去繼續試上一格，如此反覆即可得到所有解 可以想像成「以第 i 格填上 j 為前提的情形，嘗試第 i+1 格能夠填些什麼」 實際畫畫看可以得到一個樹狀的展開圖，這樣對於它的運作原理應該會清楚一點 至於每行、每列和每個 2x2 的小區域都必須有 1~4 且恰出現一次 可以對於每行、每列記錄 1~4 哪些數字出現過、哪些沒有，例如 row[i][j] = 1 表示第 i 列數字 j 出現過，而 row[i][j] = 0 表示第 i 列數字 j 沒出現過，等等，2x2 的小區域的話 會發現若座標用 0~3 則同一區域的格子，其 x/2 和 y/2 會相同 弄個圖幫助思考一下 0 1 2 3 0 A A B B 1 A A B B 2 C C D D 3 C C D D 所以用 block[i][j][k] 記錄 x/2=i, y/2=j 的小區域，k 是否出現過即可 注意在讀入時需注意，有可能出現 <0 或 >4 的數字，這種情況一律視為無解 也有可能一列或一行已被填了重覆的數字，這些情形也要注意一下 ---- 第二題 對一個只包含 +、- 運算子且係數、冪次均為整數的多項式微分 由於給的輸入並不保證降冪排序，所以要在分析並存下每一項微分後的結果 最後依冪次排序，排序的部份使用 qsort() 即可，困難的部份在於如何分析 這裡想辦法抓出每一項的共通點並想辦法切開它們 從字串的第一個字開始，要嘛是正負號，要嘛是數字 如果是數字那係數一定是正的，是正負號就記一下正負 接下來處理掉這個數字後，看數字的下一個符號為何 如果不是 x 就可以忽略，因為一定是常數項，微分後就不見了 如果是 x 那麼下一個字要嘛是^，要嘛是正負號 如果是正負號，因為沒有 ^ 所以可以認定它是和下一項連接的符號 恰可當作下一項係數正負的判斷依據，所以當作是下一項的東西 如果有 ^ 那麼接下來要嘛是正負號，要嘛是數字，之後就一定是和下一項連接的符號了 就這樣慢慢分析即可，每項都對它微分後存起來，最後對分析出來的資料排序 要小心有可能出現 x^0 這種東西 ---- 第三題 依 bmi 排序並輸出前十高者 bmi 算法：體重(kg) / 身高^2 (m) qsort() 一下，再輸出前十筆即可 比較方式的話，由於身高的單位轉換會抵消，所以可以不用管它 將 a/b 與 c/d 的比較轉換成 a*d, b*c 的比較也可以避免誤差的出現 一個比較好的方式是，每輸入一筆資料就把它和現有的資料比較，然後保留前十高的 在過程中無法保持在前十高的，拿掉也不影響結果 這樣每筆資料只要找到在現有資料中，自己是第幾高，就可以直接放在那個位置 其它比自己低的就往後挪一格，然後限制長度永遠 <= 10 即可，這樣效率是比較高的 ---- 第四題 用 出門 => 吃掉 dorayaki => 回家 => 出門 => 吃掉 dorayaki => 回家 => ... 的策略來吃 dorayaki 問最多可以吃多少個 所以吃掉每個 dorayaki 後，hp 的變化量是 -(2dis - g)，且能吃到的前提是 hp > dis 越遠的能吃的條件越高，變化量也越不利，因此先吃較近的銅鑼燒並不會比較差 也就是說，可能先吃近的銅鑼燒能導致可以吃較遠且原本吃不到的銅鑼燒 反之卻不可能，因為吃不到近的銅鑼燒就一定吃不到遠的銅鑼燒 所以從最近的開始吃，吃到沒 hp 可以吃下一個銅鑼燒為止即可 先算出距離並排序就可以了 ---- 第五題 以 a < z < b < ... 的順序來對字串排序 如果要硬寫會有點麻煩，不過這裡我們可以自己寫一個 strcmp() 用自己的方式比 為方便起見，可以先賦予每個字母一個 value，之後用這個 value 來比較字母大小 建表的方式可以如下： for(i='a', j='z', k=1; i<=j; i++, j--) { tbl[i] = k; k++; if(i != j) { tbl[j] = k; k++; } } 如此即可得到每個字母的 value，再以這 value 代替 ASCII 碼寫個自定的 strcmp() 就可以解決這題了，一樣使用 qsort() 排序即可 ---- 為直接 end 的人著想，安全起見，故留此文末防雷頁 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.91.122