頁籤選單縮合
題 名 | Recursively Divide-And-Conquer Algorithm and Implementations of Few Example=遞迴式分割與征服演算法及其實例程式設計 |
---|---|
作 者 | 施能裕; | 書刊名 | 南臺科技大學學報 |
卷 期 | 25 2001.03[民90.03] |
頁 次 | 頁117-122 |
分類號 | 310.153 |
關鍵詞 | 遞迴呼叫; 分割與征服演算法; 快速排序; Recursive; Divide-and-conquer; Quicksort; |
語 文 | 英文(English) |
中文摘要 | 副程式在執行過程中,呼叫本身或多個副程式相互呼叫形成一個循環我們稱為遞回呼叫。遞迴呼叫能化簡程式設計結構,但對於效率的增進則無幫助,雖然它是一個極重要的程式設計方式,但對於初學者來說卻是一件困難的事。 分割與征服演算法在理論電腦計算的領域�堿O一個很有趣,很重要的演算法。本篇文章主要在檢視使用分割與征服演算法來解決電腦科學上的幾個重要實例。並且,重要的是,分割與征服演算法本身是遞迴式的,也就是說,為了要解決一個問題,分割與征服演算法本身是遞迴式的,也就是說,為了要解決一個問題,分割與征服演算法將會遞迴的呼叫自己多次以解決許多輸入較小的新問題,但這些新問題的本質與原來的問題相同的。最後,我們就可以直接的解決一個小問題。更進一步的,將這些小問題的答案合併起來就得到原來問題的答案。分割與征服演算法用來解決合併排序,快速排序,以及Strassen’s矩陣相乘演算法都是非常有效率的。我將挑選幾個例子用Visual Basic語言來撰寫程式。 |
英文摘要 | Divide and conquer algorithm is an interesting topic among the theoretical computing area. The aim of this paper is to examine the use of divide and conquer algorithms for solving some important examples. Also, this divide-and-conquer algorithm is recursive itself, that, is, in order to solve a problem, the programs will call themselves recursively more and more times to solve almost the same problem except that the input size of the new problem is smaller than the original one. Finally, the latest problem is so easy that we could solve it directly. Furthermore, we have to combine these simple solutions together step by step and get a final solutions of the original problem. Divide and conquer algorithms have proved to be very effective to solve the merge sort, quicksort, Strassen’s fast matrix multiplication, the fast Fourier Transform, and binary search …etc. I pick some examples and implement the solutions using Visual Basic in the following sections. |
本系統中英文摘要資訊取自各篇刊載內容。