广东建设基金管理有限公司网站,棠下手机网站建设电话,简洁中文网站模板下载,互联网营销常用网站在编程开发中#xff0c;算法是用于解决特定问题或完成特定任务的一组指令或过程。算法可以用任何编程语言表示#xff0c;可以像一系列基本操作一样简单#xff0c;也可以像涉及不同数据结构和逻辑的多步骤过程一样复杂。
算法的主要目标是接收输入、处理它并提供预期的输…在编程开发中算法是用于解决特定问题或完成特定任务的一组指令或过程。算法可以用任何编程语言表示可以像一系列基本操作一样简单也可以像涉及不同数据结构和逻辑的多步骤过程一样复杂。
算法的主要目标是接收输入、处理它并提供预期的输出。算法可以根据时间和空间复杂性、用于解决问题的技术以及解决问题的类型进行分类。算法的例子有排序、搜索、图形遍历、字符串操作、数学运算等等。
这些算法广泛用于各种应用程序程序员对它们有深刻的理解很重要所以我会尽力解释它们。
我们将要讨论的8大算法如下
1、排序算法
1).Quicksort
Quicksort 是一种分而治之的算法它从数组中选择一个“主元”元素然后根据其他元素是小于还是大于主元将它们分成两个子数组。然后对子数组进行递归排序。
def quicksort(arr):if len(arr) 1:return arrpivot arr[len(arr) // 2]left [x for x in arr if x pivot]middle [x for x in arr if x pivot]right [x for x in arr if x pivot]return quicksort(left) middle quicksort(right)print(quicksort([3,6,8,10,1,2,1]))
2).归并排序
归并排序算法是一种分而治之的算法它将一个数组一分为二对两半进行排序然后将它们归并在一起。
def merge_sort(arr):if len(arr) 1:return arrmid len(arr) // 2left merge_sort(arr[:mid])right merge_sort(arr[mid:])return merge(left, right)def merge(left, right):result []i 0j 0while i len(left) and j len(right):if left[i] right[j]:result.append(left[i])i 1else:result.append(right[j])j 1result left[i:]result right[j:]return result
print(merge_sort([3,6,8,10,1,2,1]))
3).堆排序
堆排序算法是一种基于比较的排序算法它将输入元素构建一个堆然后从堆中反复提取最大元素并将其放在排序后的输出数组的末尾。
def heap_sort(arr):n len(arr)for i in range(n, -1, -1):heapify(arr, n, i)for i in range(n-1, 0, -1):arr[i], arr[0] arr[0], arr[i]heapify(arr, i, 0)def heapify(arr, n, i):largest il 2 * i 1r 2 * i 2if l n and arr[i] arr[l]:largest lif r n and arr[largest] arr[r]:largest rif largest ! i:arr[i], arr[largest] arr[largest], arr[i]heapify(arr, n, largest)
print(heap_sort([3,6,8,10,1,2,1]))
2.搜索算法
1).二分搜索
二分搜索是一种从已排序的项目列表中查找项目的有效算法。它的工作原理是将要搜索的数组部分重复def binary_search(arr, x):
分成两半直到找到目标值。
def binary_search(arr, x):low 0high len(arr) - 1mid 0while low high:mid (high low) // 2if arr[mid] x:low mid 1elif arr[mid] x:high mid - 1else:return midreturn -1
print(binary_search([1,2,3,4,5,6,7], 4))
2).哈希表
哈希表是一种将键映射到值的数据结构使用哈希函数计算到桶或槽数组的索引从中可以找到所需的值。
class HashTable:def __init__(self):self.size 10self.keys [None] * self.sizeself.values [None] * self.sizedef put(self, key, data):index self.hash_function(key)while self.keys[index] is not None:if self.keys[index] key:self.values[index] data # updatereturnindex (index 1) % self.sizeself.keys[index] keyself.values[index] datadef get(self, key):index self.hash_function(key)while self.keys[index] is not None:if self.keys[index] key:return self.values[index]index (index 1) % self.sizereturn Nonedef hash_function(self, key):sum 0for pos in range(len(key)):sum sum ord(key[pos])return sum % self.sizet HashTable()
t.put(apple, 10)
t.put(orange, 20)
t.put(banana, 30)
print(t.get(orange))
3.图算法
1).Dijkstra 最短路径算法
Dijkstra 最短路径算法是一种寻找图中节点之间最短路径的算法。
import heapqdef dijkstra(graph, start):heap [(0, start)]visited set()while heap:(cost, v) heapq.heappop(heap)if v not in visited:visited.add(v)for u, c in graph[v].items():if u not in visited:heapq.heappush(heap, (cost c, u))return visitedgraph {A: {B: 2, C: 3},B: {D: 4, E: 5},C: {F: 6},D: {G: 7},E: {G: 8, H: 9},F: {H: 10},G: {},H: {}
}
print(dijkstra(graph, A))
4.动态规划
斐波那契数列
斐波那契数列是可以使用动态规划解决的问题的经典示例。
def fibonacci(n):if n 0:return 0elif n 1:return 1else:return fibonacci(n-1) fibonacci(n-2)print(fibonacci(10))
5.贪婪算法
霍夫曼编码
霍夫曼编码是一种无损数据压缩算法它使用贪婪算法为给定的一组符号构造前缀码。
from collections import Counter, namedtupledef huffman_encoding(data):Generates a Huffman encoded string of the input data# Create a frequency counter for the datafreq_counter Counter(data)# Create a namedtuple for the Huffman tree nodesHuffmanNode namedtuple(HuffmanNode, [char, freq])# Create a priority queue for the Huffman treepriority_queue PriorityQueue()# Add all characters to the priority queuefor char, freq in freq_counter.items():priority_queue.put(HuffmanNode(char, freq))# Combine nodes until only the root node remainswhile priority_queue.qsize() 1:left_node priority_queue.get()right_node priority_queue.get()combined_freq left_node.freq right_node.freqcombined_node HuffmanNode(None, combined_freq)priority_queue.put(combined_node)# Generate the Huffman code for each characterhuffman_code {}generate_code(priority_queue.get(), , huffman_code)# Encode the input dataencoded_data for char in data:encoded_data huffman_code[char]return encoded_data, huffman_code
print(huffman_encoding(aaaaabbbcccc))
6.分治法
归并排序上面已经解释过了
7.回溯
The N-Queens Problem这是一个可以使用回溯法解决的经典问题。目标是将 N 个问题放在 NxN 的棋盘上使得任何皇后都不能攻击任何其他皇后。
def solveNQueens(n):def could_place(row, col):# check if a queen can be placed on board[row][col]# check if this row is not under attack from any previous queen in that columnfor i in range(row):if board[i] col or abs(board[i] - col) abs(i - row):return Falsereturn Truedef backtrack(row0, count0):for col in range(n):if could_place(row, col):board[row] colif row 1 n:count 1else:count backtrack(row 1, count)return countboard [-1 for x in range(n)]return backtrack()
print(solveNQueens(4))
该算法开始将皇后放置在第一行并且对于每个放置的皇后它检查它是否受到任何先前皇后的攻击。
如果不是它将继续到下一行并重复该过程。如果将皇后置于受到攻击的位置算法会回溯并尝试不同的位置。这一直持续到所有皇后都被放置在棋盘上且没有任何相互攻击。
8.随机算法
随机快速排序随机选择主元的快速排序算法的一种变体。
import randomdef randomized_quicksort(arr):if len(arr) 1:return arrpivot random.choice(arr)left [x for x in arr if x pivot]middle [x for x in arr if x pivot]right [x for x in arr if x pivot]return randomized_quicksort(left) middle randomized_quicksort(right)print(randomized_quicksort([3,6,8,10,1,2,1]))
这些是每个程序员都应该熟悉的一些最常用的算法。了解这些算法与它的实现可以帮助程序员在设计和实现高效解决方案时做出更好的决策。
