iT邦幫忙

2022 iThome 鐵人賽

DAY 28
0
自我挑戰組

有事者·試競程(附帶每日演算法小謎題)系列 第 28

實作過才知道細節藏在哪裡

  • 分享至 

  • xImage
  •  

程式解題跟數學解題有個很類似的地方,當你以為你想通了,但實際寫下去才發現問題百出,掛一漏萬。尤其是需要比較細心雕琢的題目,它包含了許多子程式。而這些子程式在設計與使用的時候,如果使用的是現成的函式庫,必須要對該函式庫有一定的熟悉程度。否則的話很容易誤會其實作細節,因而導致找不到錯誤。

印象比較深刻的是 C++ STL 裡面的 nth_element(),還有 Java 的排序比較函數 (Comparator.compare)。nth_element 講究的是利用線性時間將第 k 個元素放入陣列中第 k 個位置。這個函式會需要三個迭代器參數:陣列開始位置、陣列結束位置、第k元素位置。但是你知道這三個參數傳入的順序是什麼嗎...在 IDE 沒有提供好的支援情形下,諸如此類的細節是非常容易忘記的...

Java 的排序比較函數與 C 的 qsort 排序比較函數雷同,都是比較兩個元素,而且接受三種回傳值:正整數、零、負整數。可是如果你只是將兩個數相加或相減便回傳,很有可能會造成整數溢位而最終導致排序崩壞。而這些經驗幾乎都不是聽過就記得住的,很多時候得在賽場上付出實際的代價才會印象深刻...

以程式解題比賽來說,最常見且最容易弄錯細節的題目,大概就屬二分搜尋法了。二分搜尋法基本上是百家爭鳴的狀態,各家有各家習慣的寫法。有時候已經寫習慣了其中一種,在看另一種寫法的時候,反而會無法調適過來。我自己是習慣全閉區間的 (通常大家比較推薦左閉右開區間的寫法)。我個人的習慣是在看這類型的程式碼的時候,先確定迴圈不變量 (到底我要找的東西在區間的什麼位置),然後看看跳出迴圈的時候是否總是因為同一個邊界改變而離開。


上一篇
解題的直覺與信念
下一篇
賽場上的心態
系列文
有事者·試競程(附帶每日演算法小謎題)30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言