在编程的世界里,计算能力是基石之一。无论是算法设计、数据分析还是系统优化,计算都是不可或缺的技能。以下是一些精心挑选的练习题,它们将帮助你提升编程计算能力,让你成为真正的计算高手。
1. 基础算法练习
1.1 排序算法
题目描述:实现一个函数,输入一个整数数组,返回一个排序后的数组。
算法选择:冒泡排序、选择排序、插入排序、快速排序等。
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
# 测试
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))
1.2 查找算法
题目描述:在一个有序数组中查找一个特定元素的位置。
算法选择:线性查找、二分查找。
def binary_search(arr, x):
low = 0
high = len(arr) - 1
mid = 0
while low <= high:
mid = (high + low) // 2
if arr[mid] < x:
low = mid + 1
elif arr[mid] > x:
high = mid - 1
else:
return mid
return -1
# 测试
print(binary_search([1, 3, 5, 7, 9], 7)) # 输出:3
2. 数学计算练习
2.1 最大公约数
题目描述:实现一个函数,计算两个正整数的最大公约数。
算法选择:辗转相除法。
def gcd(a, b):
while b:
a, b = b, a % b
return a
# 测试
print(gcd(60, 48)) # 输出:12
2.2 斐波那契数列
题目描述:实现一个函数,计算斐波那契数列的第 n 项。
算法选择:递归、循环。
def fibonacci(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
# 测试
print(fibonacci(10)) # 输出:55
3. 数据结构与算法练习
3.1 链表操作
题目描述:实现一个链表,并支持插入、删除和查找操作。
数据结构:单链表、双向链表。
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def insert_node(head, val):
new_node = ListNode(val)
if not head:
return new_node
current = head
while current.next:
current = current.next
current.next = new_node
return head
# 测试
head = ListNode(1)
head = insert_node(head, 2)
head = insert_node(head, 3)
print(head.val, head.next.val, head.next.next.val) # 输出:1 2 3
3.2 图的遍历
题目描述:实现一个图,并支持深度优先搜索(DFS)和广度优先搜索(BFS)。
数据结构:邻接表。
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def dfs(self, v, visited):
visited.add(v)
print(v, end=' ')
for i in self.graph[v]:
if i not in visited:
self.dfs(i, visited)
def bfs(self, start):
visited = set()
queue = []
visited.add(start)
queue.append(start)
while queue:
s = queue.pop(0)
print(s, end=' ')
for i in self.graph[s]:
if i not in visited:
queue.append(i)
visited.add(i)
# 测试
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)
print("DFS: ")
g.dfs(2)
print("\nBFS: ")
g.bfs(2)
通过以上练习题,你可以逐步提升自己的编程计算能力。记住,多练习、多思考,才能在编程的道路上越走越远。
