公告版位

目前分類:演算法 (19)

瀏覽方式: 標題列表 簡短摘要

簡介

選擇排序法(Selection Sort)是排序演算法的一種,也是一種簡單容易理解的演算法,其概念是反覆從未排序的數列中取出最小的元素,加入到另一個的數列,結果即為已排序的數列。運算流程如下:

文章標籤

emn178 發表在 痞客邦 PIXNET 留言(1) 人氣()

簡介

插入排序法(Insertion Sort)是排序演算法的一種,他是一種簡單容易理解的排序演算法,其概念是利用另一個數列來存放已排序部分,逐一取出未排序數列中元素,從已排序數列由後往前找到適當的位置插入。運算流程如下:

文章標籤

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()

簡介

氣泡排序法(Bubble Sort)是最容易理解和實作的一種排序演算法,也翻譯作冒泡排序法。由於它很容易學習,所以也是許多演算法課程中第一個學習的排序演算法。

文章標籤

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()

簡介

排序(Sorting)演算法是常用到的一種演算法,顧名思義他是用來將資料依據特定的規則做排序後輸出;既然稱為排序就會有一個比較順序的依據,例如數字就比較數值大小、字串則依ASCII字母順序或者物件會有自定義的規則。一般沒有特別指定的話,輸出是以遞增排序為準。

文章標籤

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()

簡介

先來描述一下問題,這裡以下樓梯為例:

文章標籤

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()

How to find the missing integer in an array.

題目的詳細條件是,未排序的n個連續整數中少了一個,要找出是哪一個,例如:3, 6, 9, 7, 8, 4,連續整數範圍為3-9,少了5。

文章標籤

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()

How to find second largest number in array.

How to find kth largest number in array.

文章標籤

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()

How to sum the Integers from 1 to N.

說明

文章標籤

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()

How to find out the largest one of the two numbers without judgement statements.

max(a, b)...正解,這題題目限制不能用if, switch或? :的語法,但沒說不能用math的max。

文章標籤

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()

How to swap two variables without using a temporary variable.

解法

文章標籤

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()

簡介

費波那西數列(Fibonacci),又稱費氏數列、黃金分割數列等很多譯名,由西方的數學家費波那西使用兔子問題來描述這個數列,以下引用Wiki:

文章標籤

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()

簡介

Dynamic Programming中文譯作動態規劃,動態規劃類似Divide and Conquer,一個問題的答案來相依於子問題,常用來解決最佳解的問題。與Divide and Conquer不同的地方在於,動態規劃多使用了memoization的機制,將處理過的子問題答案記錄下來,避免重複計算,因此在子問題重疊的時候應該使用動態規劃;Divide and Conquer通常使用遞迴(Top-Down)來處理,轉成迭代法(Bottom-up)來解並不容易,故使用動態規劃則可以解決重覆計算並保留遞迴思考的優點。

文章標籤

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()

簡介

Iterative Method中文翻譯作迭代法或疊代法,而在數學領域和電腦程式領域的定義有些不同,數學領域的迭代法指的是無法使用公式一次求解,而須反覆運算求出近似解;而在電腦程式雖然亦有反覆運算的含義,但一般指的是迴圈解。

文章標籤

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()

簡介

最大子序列(Maximum Subarray或稱作Maximum Subsequence)為在一個具有正負數陣列當中,找出一段連續的元素總和最大,這個問題又分為一定要取值或可不取。實作方法有很多種,這裡說明四種實作方法,分別為暴力法、改良式暴力法、Divide and Conquer和Kadane's演算法(Dynamic Programming),其中Kadane's實作取值和可不取值兩種版本,其他為一定要取值版本。

文章標籤

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()

簡介

二元搜索法(Binary Search)又稱折半搜索,搜索演算法的一種,可使用Divide and Conquer或直接使用迴圈來實作,搜索的目標資料必須是已經排序過的(以小到大排序為例)。其概念是每次挑選中間位置的資料來比對,若該資料小於目標值,則縮小範圍為左半部,反之亦然;因此使用這個方法每次比對後都可以濾掉一半的資料,以增快搜索速度。過程依以下步驟進行:

文章標籤

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()

簡介

快速排序法是排序演算法的一種,使用Divide and Conquer的演算法來實作。其概念是從數列中挑選一個基準點,大於基準的放一邊,小於的放一邊,如此循環最後可完成排序。過程依照以下步驟進行(遞增為例):

文章標籤

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()

簡介

合併排序法(或稱歸併排序法),是排序演算法的一種,使用Divide and Conquer的演算法來實作。排序時需要額外的空間來處理,過程依照以下步驟進行:

文章標籤

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()

簡介

也翻譯作漢諾塔,這是根據一個傳說演變而成的題目,題目的規則如下:

文章標籤

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()

簡介

Divide and conquer中文翻作分治法,概念如字面上的意義,將問題先切分成小問題後再解決,再將結果合併求出原始問題的答案。

文章標籤

emn178 發表在 痞客邦 PIXNET 留言(0) 人氣()