【蓝桥杯】C语言常见高级算法

🌸个人主页：Yang-ai-cao

📕系列专栏：蓝桥杯    C语言

   🍍博学而日参省乎己，知明而行无过矣

目录

🌸个人主页：Yang-ai-cao

📕系列专栏：蓝桥杯    C语言

🍍博学而日参省乎己，知明而行无过矣

一、动态规划（Dynamic Programming）

例子：斐波那契数列

动态规划解法

例子：0-1 背包问题

动态规划解法

二、贪心算法（Greedy Algorithm）

例子：活动选择问题

贪心算法解法

三、回溯算法（Backtracking）

例子：N皇后问题

回溯算法解法

四、分治算法（Divide and Conquer）

例子：归并排序（Merge Sort）

五、图算法（Graph Algorithms）

例子：Dijkstra 算法（单源最短路径）

贪心算法（Greedy Algorithm）

例子：霍夫曼编码（Huffman Coding）

总结

---

一、动态规划（Dynamic Programming）

例子：斐波那契数列

动态规划解法

#include <stdio.h>// 计算斐波那契数列的第 n 项
int fib(int n) {// 创建一个数组来存储斐波那契数列int f[n+1];f[0] = 0;  // 第 0 项是 0f[1] = 1;  // 第 1 项是 1// 通过迭代计算第 n 项for (int i = 2; i <= n; i++) {f[i] = f[i-1] + f[i-2];  // 当前项等于前两项之和}return f[n];  // 返回第 n 项
}int main() {int n = 10;  // 计算第 10 项printf("Fibonacci number is %d\n", fib(n));  // 输出结果return 0;
}

例子：0-1 背包问题

动态规划解法

#include <stdio.h>// 返回两个整数中的最大值
int max(int a, int b) { return (a > b) ? a : b; }// 解决 0-1 背包问题
int knapSack(int W, int wt[], int val[], int n) {// 创建一个二维数组 K，用于存储子问题的解int K[n+1][W+1];// 填充 K 表for (int i = 0; i <= n; i++) {for (int w = 0; w <= W; w++) {if (i == 0 || w == 0) {K[i][w] = 0;  // 基本情况：没有物品或容量为 0} else if (wt[i-1] <= w) {// 选择当前物品或不选择当前物品，取最大值K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);} else {K[i][w] = K[i-1][w];  // 当前物品不能放入背包}}}return K[n][W];  // 返回最大价值
}int main() {int val[] = {60, 100, 120};  // 物品的价值int wt[] = {10, 20, 30};     // 物品的重量int W = 50;                  // 背包的容量int n = sizeof(val)/sizeof(val[0]);  // 物品的数量printf("Maximum value in Knapsack = %d\n", knapSack(W, wt, val, n));  // 输出结果return 0;
}

二、贪心算法（Greedy Algorithm）

例子：活动选择问题

贪心算法解法

#include <stdio.h>// 打印最大数量的可选活动
void printMaxActivities(int s[], int f[], int n) {int i = 0;  // 第一个活动总是被选择printf("Selected activities: %d ", i);// 选择其余活动for (int j = 1; j < n; j++) {if (s[j] >= f[i]) {  // 如果当前活动的开始时间大于等于上一个活动的结束时间printf("%d ", j);i = j;  // 更新上一个被选择活动的索引}}printf("\n");
}int main() {int s[] = {1, 3, 0, 5, 8, 5};  // 活动的开始时间int f[] = {2, 4, 6, 7, 9, 9};  // 活动的结束时间int n = sizeof(s)/sizeof(s[0]);  // 活动的数量printMaxActivities(s, f, n);  // 输出结果return 0;
}

三、回溯算法（Backtracking）

例子：N皇后问题

回溯算法解法

#include <stdio.h>
#include <stdbool.h>#define N 4  // 棋盘大小// 打印棋盘
void printSolution(int board[N][N]) {for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {printf(" %d ", board[i][j]);}printf("\n");}
}// 检查在 board[row][col] 放置皇后是否安全
bool isSafe(int board[N][N], int row, int col) {int i, j;// 检查当前行的左侧for (i = 0; i < col; i++)if (board[row][i])return false;// 检查左上对角线for (i = row, j = col; i >= 0 && j >= 0; i--, j--)if (board[i][j])return false;// 检查左下对角线for (i = row, j = col; j >= 0 && i < N; i++, j--)if (board[i][j])return false;return true;
}// 递归解决 N 皇后问题
bool solveNQUtil(int board[N][N], int col) {if (col >= N)  // 所有皇后已放置return true;for (int i = 0; i < N; i++) {if (isSafe(board, i, col)) {  // 检查放置在 board[i][col] 是否安全board[i][col] = 1;  // 放置皇后if (solveNQUtil(board, col + 1))  // 递归放置其余皇后return true;board[i][col] = 0;  // 回溯：移除皇后}}return false;  // 如果无法放置皇后
}// 解决 N 皇后问题
bool solveNQ() {int board[N][N] = { {0, 0, 0, 0},{0, 0, 0, 0},{0, 0, 0, 0},{0, 0, 0, 0} };if (solveNQUtil(board, 0) == false) {printf("Solution does not exist");return false;}printSolution(board);  // 打印解决方案return true;
}int main() {solveNQ();  // 解决问题return 0;
}

四、分治算法（Divide and Conquer）

例子：归并排序（Merge Sort）

#include <stdio.h>// 合并两个子数组
void merge(int arr[], int l, int m, int r) {int n1 = m - l + 1; // 左子数组的大小int n2 = r - m; // 右子数组的大小int L[n1], R[n2]; // 临时数组// 复制数据到临时数组 L[] 和 R[]for (int i = 0; i < n1; i++)L[i] = arr[l + i];for (int j = 0; j < n2; j++)R[j] = arr[m + 1 + j];// 合并临时数组到 arr[l..r]int i = 0, j = 0, k = l;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}// 复制 L[] 剩余元素while (i < n1) {arr[k] = L[i];i++;k++;}// 复制 R[] 剩余元素while (j < n2) {arr[k] = R[j];j++;k++;}
}// 归并排序
void mergeSort(int arr[], int l, int r) {if (l < r) {int m = l + (r - l) / 2; // 找到中点mergeSort(arr, l, m); // 排序左半部分mergeSort(arr, m + 1, r); // 排序右半部分merge(arr, l, m, r); // 合并已排序的部分}
}// 打印数组
void printArray(int A[], int size) {for (int i = 0; i < size; i++)printf("%d ", A[i]);printf("\n");
}int main() {int arr[] = {12, 11, 13, 5, 6, 7};int arr_size = sizeof(arr) / sizeof(arr[0]);printf("Given array is \n");printArray(arr, arr_size);mergeSort(arr, 0, arr_size - 1);printf("\nSorted array is \n");printArray(arr, arr_size);return 0;
}

五、图算法（Graph Algorithms）

例子：Dijkstra 算法（单源最短路径）

#include <stdio.h>
#include <limits.h>
#include <stdbool.h>#define V 9 // 顶点数量// 找到最小距离的顶点
int minDistance(int dist[], bool sptSet[]) {int min = INT_MAX, min_index;for (int v = 0; v < V; v++)if (sptSet[v] == false && dist[v] <= min)min = dist[v], min_index = v;return min_index;
}// 打印解
void printSolution(int dist[], int n) {printf("Vertex \t Distance from Source\n");for (int i = 0; i < V; i++)printf("%d \t\t %d\n", i, dist[i]);
}// Dijkstra 算法
void dijkstra(int graph[V][V], int src) {int dist[V]; // 最短距离数组bool sptSet[V]; // sptSet[i] 为 true 表示顶点 i 已包含在最短路径树中// 初始化所有距离为无穷大，sptSet[] 为 falsefor (int i = 0; i < V; i++)dist[i] = INT_MAX, sptSet[i] = false;dist[src] = 0; // 源顶点距离为 0for (int count = 0; count < V - 1; count++) {int u = minDistance(dist, sptSet); // 选取最小距离顶点sptSet[u] = true; // 标记为已处理for (int v = 0; v < V; v++)if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v])dist[v] = dist[u] + graph[u][v]; // 更新距离}printSolution(dist, V); // 打印结果
}int main() {int graph[V][V] = { {0, 4, 0, 0, 0, 0, 0, 8, 0},{4, 0, 8, 0, 0, 0, 0, 11, 0},{0, 8, 0, 7, 0, 4, 0, 0, 2},{0, 0, 7, 0, 9, 14, 0, 0, 0},{0, 0, 0, 9, 0, 10, 0, 0, 0},{0, 0, 4, 14, 10, 0, 2, 0, 0},{0, 0, 0, 0, 0, 2, 0, 1, 6},{8, 11, 0, 0, 0, 0, 1, 0, 7},{0, 0, 2, 0, 0, 0, 6, 7, 0} };dijkstra(graph, 0); // 调用 Dijkstra 算法return 0;
}

贪心算法（Greedy Algorithm）

例子：霍夫曼编码（Huffman Coding）

#include <stdio.h>
#include <stdlib.h>#define MAX_TREE_HT 100// 最小堆节点
struct MinHeapNode {char data; // 字符unsigned freq; // 频率struct MinHeapNode *left, *right; // 左右子节点
};// 最小堆
struct MinHeap {unsigned size; // 当前大小unsigned capacity; // 容量struct MinHeapNode **array; // 数组指针
};// 创建新节点
struct MinHeapNode* newNode(char data, unsigned freq) {struct MinHeapNode* temp = (struct MinHeapNode*)malloc(sizeof(struct MinHeapNode));temp->left = temp->right = NULL;temp->data = data;temp->freq = freq;return temp;
}// 创建最小堆
struct MinHeap* createMinHeap(unsigned capacity) {struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap));minHeap->size = 0;minHeap->capacity = capacity;minHeap->array = (struct MinHeapNode**)malloc(minHeap->capacity * sizeof(struct MinHeapNode*));return minHeap;
}// 交换两个最小堆节点
void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b) {struct MinHeapNode* t = *a;*a = *b;*b = t;
}// 最小堆化
void minHeapify(struct MinHeap* minHeap, int idx) {int smallest = idx;int left = 2 * idx + 1;int right = 2 * idx + 2;if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq)smallest = left;if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]->freq)smallest = right;if (smallest != idx) {swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);minHeapify(minHeap, smallest);}
}// 检查是否只有一个元素
int isSizeOne(struct MinHeap* minHeap) {return (minHeap->size == 1);
}// 提取最小值节点
struct MinHeapNode* extractMin(struct MinHeap* minHeap) {struct MinHeapNode* temp = minHeap->array[0];minHeap->array[0] = minHeap->array[minHeap->size - 1];--minHeap->size;minHeapify(minHeap, 0);return temp;
}// 插入节点到最小堆
void insertMinHeap(struct MinHeap* minHeap, struct MinHeapNode* minHeapNode) {++minHeap->size;int i = minHeap->size - 1;while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) {minHeap->array[i] = minHeap->array[(i - 1) / 2];i = (i - 1) / 2;}minHeap->array[i] = minHeapNode;
}// 构建最小堆
void buildMinHeap(struct MinHeap* minHeap) {int n = minHeap->size - 1;for (int i = (n - 1) / 2; i >= 0; --i)minHeapify(minHeap, i);
}// 打印数组
void printArr(int arr[], int n) {for (int i = 0; i < n; ++i)printf("%d", arr[i]);printf("\n");
}// 检查是否是叶子节点
int isLeaf(struct MinHeapNode* root) {return !(root->left) && !(root->right);
}// 创建并构建最小堆
struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) {struct MinHeap* minHeap = createMinHeap(size);for (int i = 0; i < size; ++i)minHeap->array[i] = newNode(data[i], freq[i]);minHeap->size = size;buildMinHeap(minHeap);return minHeap;
}// 构建霍夫曼树
struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) {struct MinHeapNode *left, *right, *top;struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size);while (!isSizeOne(minHeap)) {left = extractMin(minHeap);right = extractMin(minHeap);top = newNode('$', left->freq + right->freq);top->left = left;top->right = right;insertMinHeap(minHeap, top);}return extractMin(minHeap);
}// 打印霍夫曼编码
void printCodes(struct MinHeapNode* root, int arr[], int top) {if (root->left) {arr[top] = 0;printCodes(root->left, arr, top + 1);}if (root->right) {arr[top] = 1;printCodes(root->right, arr, top + 1);}if (isLeaf(root)) {printf("%c: ", root->data);printArr(arr, top);}
}// 霍夫曼编码
void HuffmanCodes(char data[], int freq[], int size) {struct MinHeapNode* root = buildHuffmanTree(data, freq, size);int arr[MAX_TREE_HT], top = 0;printCodes(root, arr, top);
}int main() {char arr[] = {'a', 'b', 'c', 'd', 'e', 'f'};int freq[] = {5, 9, 12, 13, 16, 45};int size = sizeof(arr) / sizeof(arr[0]);HuffmanCodes(arr, freq, size); // 调用霍夫曼编码return 0;
}

总结

• 分治算法通过递归地将问题分解为子问题，解决这些子问题然后合并其解，适用于排序、搜索等问题。
• 图算法如Dijkstra算法，通过逐步扩展最短路径树，找到图中从单个源到所有其他顶点的最短路径。
• 贪心算法如霍夫曼编码，通过每一步选择局部最优解，最终构建出全局最优解，适用于数据压缩等问题。
• 贪心算法每一步都选择当前最优的选择，适用于能够通过局部最优达到全局最优的问题。
• 回溯算法系统地搜索所有可能的解，通过尝试构建解并在不满足条件时回溯，适用于需要探索所有可能解的问题。
• 动态规划通过存储子问题的解来避免重复计算，适用于有重叠子问题和最优子结构的问题。