21 thoughts on “

  1. // yours
    logN   N       N 
      ∑   --- log ---
     i=1  2^i     2^i
    
    // correct
    logN       N       N 
      ∑   2^i --- log ---
     i=1      2^i     2^i
    
    = N log(N) + N log(N/2) + N log(N/4) + ... + N log(1)
    
    = O(NlogN)
    

    謝謝,煮完飯再來改。

  2. 請教版主,http://www.csie.ntnu.edu.tw/~u91029/Point2.html 的Closest Pair一欄中你提到最後一種方法是 O(N logN logN)的,但我認為應該是O(N logN)的。。原因在於某處,你可以檢索“依照Y座標排序。O(NlogN)”快速找到該處,這裡的N並沒有原來的N那麼大。。實際計算應該為O( ∑{i=1->logN} (N/(2^i)) log(N/(2^i)) ),可以證明這是O(N logN)的。
    最後祝願貴站越辦越好!

  3. 我不知道。不過谷歌知道。用關鍵字oscillator,資料比較多。
    https://www.google.com.tw/search?q=C%23+wave+oscillators+generator+source+code

    我有找到一個,不知道是不是你要的?
    https://github.com/ADeltaX/Audio-Physics

    聲音訊號處理最初是從電子學領域發展出來的,大家都是用電子電路製造聲音,幾乎所有算法都是畫成電路圖,到現在仍然如此。至於寫程式生產聲音訊號,非常冷門,資料很少。

    不知道你想要幹嘛。如果你想生產sine wave,程式碼很短,只有一兩行。如果你想播放聲音,高階語言python/java/c sharp/qt都有內建函式庫可用。這些東西比較基礎,跟語言特性無關。侷限在C#反而難找到原始碼。

  4. Jason 說:

    版主
    請教一下,你知道有沒有C#的Frequency Sound generate 原始碼?要做一些研究但都找不到

  5. Yu-Han 說:

    Topological Ordering 那節中的很普通的演算法應該叫 Kahn’s algorithm(https://en.wikipedia.org/wiki/Topological_sorting#Kahn.27s_algorithm)。 在Largest Empty Rectangle的窮舉法中最後一段,如果用了 summed area table 的技巧,應該可以變成 O((H*W)^2)。 https://en.wikipedia.org/wiki/Summed_area_table

  6. 剛剛想了一下,如果有人使用瀏覽器自選字型的功能的話,可能就有差別。那麼我還是補上好了,謝謝。

  7. CSS 在

     tag 的 font-family 部分,最好在結尾加一個 monospace,讓所有平臺都能看到正確的等寬字體
  8. 圖片是正確的。數據從3維降到2維,2維數據本來就是X和Y。
    看來這張圖片容易產生遐想,我再想一想怎麼編排好了。

  9. 章節標題加註 under construction! 都是草稿。因為 chordal graph 應用很少,不太要緊,所以我擱置兩年了,一直沒畫圖。

    這問題講起來可大可小。雖然不知道你對算法了解多少,不過我還是通盤的介紹一下吧。

    1.
    討論範圍姑且侷限在傳統的組合算法。其他方法的話,數學家有人用 spectral theory,工程方面是用 linear programming 和 evolutionary computation,學術前沿是用 deep learning。

    2.
    判斷這個graph是否為特殊類別。經典類別如tree、dag、chordal、planar等等。更詳細的類別,已經有一個網站整理了:http://www.graphclasses.org/

    3.
    圖上的邊可以分成有向的、無向的、混和的。

    4.
    圖上的邊可以分成有權重的、沒權重的。還可以分成整數的、實數的。

    5.
    環狀路徑可分成:自身不相交(cycle)、自身可相交(walk)。

    6.
    找最小環可以分成兩種:只找一個、找到全部。

    7.
    根據圖是否會隨時改變,分成兩種:靜態問題、動態查詢問題。

    8.
    答案精確度可以分成三種:精確解、近似解(答案誤差在一定範圍內)、隨機解(答案時對時錯)。

    9.
    又可以分為實務用途(教科書上教的那些都是)、理論用途(複雜度後面有很多 polylog sqrt min)。

    上面這些情況的排列組合有a^b種,而每種組合又有許多算法。很不幸的,大部分的算法,我都不懂,也不想懂,當然也就沒有整理到網站上。與你的問題最相關的,網站上只有這一篇:http://www.csie.ntnu.edu.tw/~u91029/Cycle.html#3

    想要計算學以外的方法也行。例如crowd sourcing:弄成一個趣味數學問題,找matrix67之類的數學科普作家合作,付點錢請他寫篇文,讓廣大網民幫你找。又例如物理實驗:製作管線,測量流量流速水壓之類的。這種點子隨便想都有,至於能不能實行又是另外一回事了。

    如果是我的話,大概會寄個信問一下jeff erickson或seth pettie的學生,看看他們對這問題有沒有興趣。不過要是缺乏一些好理由的話,人家應該不會理我。

  10. 詹先生 說:

    可能上面个问题那个问题可能这样问

    如何切割多边形好些

    上面的图 切割成2个图

    {1,4,3,7,6,5,1}
    {5,6,7,2}

    而忽略最大的环{1,2,3,4,1}

  11. 訪客 說:

    想問一下,Hidden Markov Model 中 Decoding Problem: Viterbi Algorithm 程式碼,第18、25行的「v」 是不是沒有宣告呢?

  12. 簡易結論:

    n就陣列長度啊。

    ——————————————

    詳細內容:

    float src[]/float dst[]是指聲音訊號。src是輸入,dst是輸出,它們是source與destination的縮寫。陣列處理、聲音處理當中,大家習慣採用這兩個單字。

    陣列數量是1。所以是單聲道(channel = 1)。

    陣列元素是32bit浮點數,數值是-1~+1。注意到原本聲音檔案儲存的是整數!16位元的情況下是-32768~+32767的整數,24位元的情況下是0~16777215的整數。一段同樣的聲音,採用不同位元深度,那麼數字範圍就不一樣,很難搞。因此大家處理聲音訊號的時候,習慣先做好標準化:將範圍中心位移至0、再除以最大值,最後變成-1~+1。C/C++語言當中,float變數是32bit,大致上足以精確地儲存「16位元訊號經過標準化」、「24位元訊號經過標準化」的結果。另外,JavaScript的Audio API就是這樣處理的。

    陣列長度是n,也就是訊號數量。另外,在C語言當中,n往往是指陣列長度,ijk往往是指陣列索引,可以說是眾人皆知的習俗了。另外,在C語言當中,傳遞陣列常見的寫法就是陣列後面補個陣列長度size_t num,你可以參考strncpy等等內建的字串處理函式。

    訊號的取樣頻率是sampling_rate。比方說,如果取樣頻率是sampling_rate = 48000Hz,換句話說一秒鐘有48000個訊號,那麼聲音的長度是n/sampling_rate秒。這個我可能要再改一下,因為大家習慣叫做fs而非sampling_rate。比方說matlab語言當中,就是用fs。

    簡諧波的頻率是f。這是要製造簡諧波的時候才需要用的參數。例如中音C的簡諧波就要設定為f=261.625565Hz,換句話說一秒鐘有261.625565次上下起伏,上下整個算一次。如果你的手指能動這麼快而且速度均勻,就能發出中音C。

    看起來我沒把聲音訊號的變數名稱定義清楚。一開始的名稱是pcm,後來忽然變成src和dst,又忽然冒出個n。我會修正一下、補點註解。

  13. IaoYu 說:

    您好,參考過您們網站裡關於audio的部份,我想請問一下全部程式碼(function)裡的參數n是什麼? 謝謝。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s