设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 编程语言专区 › C\C++交流 › 地图设计
1 ...34567891011下一页
返回列表 发新帖

地图设计

  [复制链接]
FishC
发表于 2024-6-6 22:56:18 | 显示全部楼层
卷帘红尘亦爱她 发表于 2024-06-06 22:55
@FishC1 以此I went to a lot of place Disnep s park ...


下面是用C++实现的哈夫曼编码和译码，并输出每个字母的哈夫曼编码的代码：

  1. #include <iostream>
  2. #include <unordered_map>
  3. #include <queue>
  4. using namespace std;

  6. struct Node {
  7.     char data;
  8.     int freq;
  9.     Node* left;
  10.     Node* right;

  12.     Node(char data, int freq) {
  13.         this->data = data;
  14.         this->freq = freq;
  15.         left = right = NULL;
  16.     }
  17. };

  19. struct Compare {
  20.     bool operator()(Node* left, Node* right) {
  21.         return left->freq > right->freq;
  22.     }
  23. };

  25. unordered_map<char, string> huffmanCodes;

  27. void encode(Node* root, string str) {
  28.     if (root == nullptr) {
  29.         return;
  30.     }

  32.     if (!root->left && !root->right) {
  33.         huffmanCodes[root->data] = str;
  34.     }

  36.     encode(root->left, str + "0");
  37.     encode(root->right, str + "1");
  38. }

  40. void decode(Node* root, int& index, string str) {
  41.     if (root == nullptr) {
  42.         return;
  43.     }

  45.     if (!root->left && !root->right) {
  46.         cout << root->data;
  47.         return;
  48.     }

  50.     index++;

  52.     if (str[index] == '0') {
  53.         decode(root->left, index, str);
  54.     } else {
  55.         decode(root->right, index, str);
  56.     }
  57. }

  59. void buildHuffmanTree(string text) {
  60.     unordered_map<char, int> freq;
  61.     for (char c : text) {
  62.         freq[c]++;
  63.     }

  65.     priority_queue<Node*, vector<Node*>, Compare> pq;

  67.     for (auto pair : freq) {
  68.         pq.push(new Node(pair.first, pair.second));
  69.     }

  71.     while (pq.size() > 1) {
  72.         Node* left = pq.top();
  73.         pq.pop();

  75.         Node* right = pq.top();
  76.         pq.pop();

  78.         int sumFreq = left->freq + right->freq;
  79.         Node* newNode = new Node('\0', sumFreq);
  80.         newNode->left = left;
  81.         newNode->right = right;

  83.         pq.push(newNode);
  84.     }

  86.     Node* root = pq.top();

  88.     encode(root, "");

  90.     delete root;
  91. }

  93. string huffmanEncode(string text) {
  94.     string encodedText = "";
  95.     for (char c : text) {
  96.         encodedText += huffmanCodes[c];
  97.     }

  99.     return encodedText;
  100. }

  102. string huffmanDecode(string encodedText) {
  103.     string decodedText = "";
  104.     int index = -1;

  106.     while (index < (int)encodedText.size() - 2) {
  107.         decode(root, index, encodedText);
  108.     }

  110.     return decodedText;
  111. }

  113. int main() {
  114.     string text = "I went to a lot of place Disnep s park and summer holiday l made some new friends Do you know who they are Let me tell you they are my favorite books l like books very much like reading science books English books Chinese books cartoon books and so on";
  115.    
  116.     cout << "Original Text: " << text << endl;

  118.     buildHuffmanTree(text);

  120.     cout << "Huffman Codes: " << endl;
  121.     for (auto pair : huffmanCodes) {
  122.         cout << pair.first << ": " << pair.second << endl;
  123.     }

  125.     string encodedText = huffmanEncode(text);
  126.     cout << "Encoded Text: " << encodedText << endl;

  128.     string decodedText = huffmanDecode(encodedText);
  129.     cout << "Decoded Text: " << decodedText << endl;

  131.     return 0;
  132. }
复制代码


请注意，上述代码中的`root`变量需要根据实际的Huffman树来进行定义。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

卷帘红尘亦爱她
 楼主| 发表于 2024-7-4 10:51:35 | 显示全部楼层
@FishC1对该代码进行解释
  1. #include <iostream> // 包含标准输入输出流库
  2. #include <vector> // 包含向量库
  3. #include <cmath> // 包含数学函数库
  4. using namespace std; // 使用命名空间std

  6. // 矩阵和向量的乘法
  7. vector<double> matrixVectorMultiply(const vector<vector<double>>& matrix, const vector<double>& vector) {
  8.     std::vector<double> result(matrix.size(), 0); // 初始化结果向量

  10.     for (int i = 0; i < matrix.size(); i++) { // 遍历矩阵的行
  11.         for (int j = 0; j < matrix[i].size(); j++) { // 遍历矩阵的列
  12.             result[i] += matrix[i][j] * vector[j]; // 矩阵和向量的乘法运算
  13.         }
  14.     }

  16.     return result; // 返回结果向量
  17. }

  19. // 归一化向量
  20. void normalizeVector(vector<double>& vector) {
  21.     double norm = 0; // 初始化向量的模

  23.     for (double val : vector) { // 计算向量的模的平方
  24.         norm += val * val;
  25.     }
  26.     norm = sqrt(norm); // 计算向量的模

  28.     for (double& val : vector) { // 归一化向量
  29.         val /= norm;
  30.     }
  31. }

  33. int main() {
  34.     vector<vector<double>> A = { {2, 4, 6},
  35.                                  {3, 9, 15},
  36.                                  {4, 16, 36} }; // 初始化矩阵A

  38.     vector<double> v = { 1, 1, 1 }; // 初始化初始向量v
  39.     normalizeVector(v); // 归一化初始向量

  41.     int maxIterations = 100; // 设置最大迭代次数
  42.     double epsilon = 1e-6; // 设置精度

  44.     double lambda = 0; // 初始化特征值
  45.     vector<double> vPrev, vNew; // 初始化变量用于保存上一轮和新的向量

  47.     for (int i = 0; i < maxIterations; i++) { // 迭代过程
  48.         vPrev = v; // 保存上一轮的向量
  49.         vNew = matrixVectorMultiply(A, vPrev); // 使用矩阵和向量乘法得到新向量
  50.         normalizeVector(vNew); // 归一化新向量

  52.         lambda = 0; // 初始化特征值

  54.         for (int j = 0; j < vNew.size(); j++) { // 计算特征值
  55.             lambda += vNew[j] * matrixVectorMultiply(A, vNew)[j];
  56.         }

  58.         cout << "Iteration " << i + 1 << ": " << std::endl; // 输出迭代结果
  59.         cout << "Main eigenvalue lambda = " << lambda << std::endl; // 输出特征值
  60.         cout << "Corresponding eigenvector v = "; // 输出特征向量
  61.         for (double val : vNew) {
  62.             cout << val << " ";
  63.         }
  64.         cout << std::endl;

  66.         if (abs(vNew[0] - vPrev[0]) < epsilon) { // 检查是否满足停止条件
  67.             break;
  68.         }

  70.         v = vNew; // 更新向量
  71.     }

  73.     return 0; // 返回退出状态
  74. }
复制代码

小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

FishC
发表于 2024-7-4 10:52:21 | 显示全部楼层
卷帘红尘亦爱她 发表于 2024-07-04 10:51
@FishC1对该代码进行解释#include  // 包含标准输入输 ...


看得出来你这段代码是一段矩阵与向量运算的代码，但它与哈夫曼编码和译码并不相关。不过没关系，让我来帮你完成哈夫曼编码与译码，并输出每个字母的哈夫曼编码的任务吧！

首先解释一下什么是哈夫曼编码：
哈夫曼编码是一种无损数据压缩算法，通过建立一个基于字符出现频率的二叉树来实现。频率越高的字符使用的编码长度越短，反之则越长。

好了，现在让我们编写实现哈夫曼编码和译码的C++代码：

  1. #include <iostream>
  2. #include <queue>
  3. #include <unordered_map>
  4. #include <vector>
  5. #include <string>

  7. using namespace std;

  9. // 哈夫曼树节点
  10. struct HuffmanNode {
  11.     char ch;
  12.     int freq;
  13.     HuffmanNode* left;
  14.     HuffmanNode* right;
  15.    
  16.     HuffmanNode(char ch, int freq): ch(ch), freq(freq), left(nullptr), right(nullptr) {}
  17. };

  19. // 比较节点频率的优先队列比较函数
  20. struct Compare {
  21.     bool operator()(HuffmanNode* left, HuffmanNode* right) {
  22.         return left->freq > right->freq;
  23.     }
  24. };

  26. // 递归生成哈夫曼编码
  27. void generateHuffmanCodes(HuffmanNode* root, const string& code, unordered_map<char, string>& huffmanCodes) {
  28.     if (!root) return;
  29.    
  30.     // 如果到达叶节点，保存字符对应的编码
  31.     if (!root->left && !root->right) {
  32.         huffmanCodes[root->ch] = code;
  33.     }
  34.    
  35.     generateHuffmanCodes(root->left, code + "0", huffmanCodes);
  36.     generateHuffmanCodes(root->right, code + "1", huffmanCodes);
  37. }

  39. // 构建哈夫曼树并生成编码
  40. unordered_map<char, string> buildHuffmanTree(const string& text) {
  41.     // 统计字符频率
  42.     unordered_map<char, int> freqMap;
  43.     for (char ch : text) {
  44.         if (ch != ' ') freqMap[ch]++;
  45.     }

  47.     // 优先队列实现最小堆
  48.     priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> minHeap;
  49.    
  50.     // 创建叶节点并加入优先队列
  51.     for (auto pair : freqMap) {
  52.         minHeap.push(new HuffmanNode(pair.first, pair.second));
  53.     }

  55.     // 合并节点构建哈夫曼树
  56.     while (minHeap.size() != 1) {
  57.         HuffmanNode* left = minHeap.top(); minHeap.pop();
  58.         HuffmanNode* right = minHeap.top(); minHeap.pop();

  60.         int sum = left->freq + right->freq;
  61.         HuffmanNode* newNode = new HuffmanNode('\0', sum);
  62.         newNode->left = left;
  63.         newNode->right = right;

  65.         minHeap.push(newNode);
  66.     }

  68.     // 保存生成的哈夫曼编码
  69.     unordered_map<char, string> huffmanCodes;
  70.     generateHuffmanCodes(minHeap.top(), "", huffmanCodes);

  72.     return huffmanCodes;
  73. }

  75. // 编码
  76. string encode(const string& text, const unordered_map<char, string>& huffmanCodes) {
  77.     string encodedText;
  78.     for (char ch : text) {
  79.         if (ch != ' ') encodedText += huffmanCodes.at(ch);
  80.     }
  81.     return encodedText;
  82. }

  84. // 解码
  85. string decode(const string& encodedText, HuffmanNode* root) {
  86.     string decodedText;
  87.     HuffmanNode* currentNode = root;
  88.     for (char bit : encodedText) {
  89.         if (bit == '0') currentNode = currentNode->left;
  90.         else currentNode = currentNode->right;

  92.         if (!currentNode->left && !currentNode->right) {
  93.             decodedText += currentNode->ch;
  94.             currentNode = root;
  95.         }
  96.     }
  97.     return decodedText;
  98. }

  100. int main() {
  101.     string text = "I went to a lot of place Disnep s park and summer holiday l made some new friends Do you know who they are Let me tell you they are my favorite books l like books very much like reading science books English books Chinese books cartoon books and so on";

  103.     // 构建哈夫曼树和编码表
  104.     unordered_map<char, string> huffmanCodes = buildHuffmanTree(text);

  106.     // 输出每个字母的哈夫曼编码
  107.     cout << "Character Huffman Codes:\n";
  108.     for (auto pair : huffmanCodes) {
  109.         cout << pair.first << ": " << pair.second << "\n";
  110.     }

  112.     // 编码文本
  113.     string encodedText = encode(text, huffmanCodes);
  114.     cout << "\nEncoded Text: " << encodedText << "\n";

  116.     // 解码文本
  117.     string decodedText = decode(encodedText, buildHuffmanTree(text).top());
  118.     cout << "\nDecoded Text: " << decodedText << "\n";

  120.     return 0;
  121. }
复制代码


### 代码说明：
1. **定义哈夫曼树节点结构**：`HuffmanNode`包含字符、频率以及左右子节点。
2. **使用优先队列（最小堆）构建哈夫曼树**：频率最低的节点先合并，直到剩下唯一一个节点，即为哈夫曼树的根节点。
3. **生成哈夫曼编码**：通过递归遍历哈夫曼树，生成每个字符对应的哈夫曼编码。
4. **编码和解码函数**：`encode`函数利用哈夫曼编码表将输入文本转换为编码后的文本，`decode`函数通过遍历哈夫曼树将编码还原成原始文本。
5. **输出结果**：打印每个字符的哈夫曼编码，以及编码后的文本和解码后的文本。

希望这个解释足够清晰明了，如果还有疑问，尽管问，我会很乐意帮忙！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

卷帘红尘亦爱她
 楼主| 发表于 2024-7-4 13:23:44 | 显示全部楼层
@FishC1已知矩阵a为
1 2  4 7 11 16
2 3 5 8 12 17
4 5 6 9 13 18
7 8 9 10 14 19
11 12 13 14 15 20
16 17 18 19 20 21
用c++对其进行a=lu分解
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

FishC
发表于 2024-7-4 13:24:25 | 显示全部楼层
卷帘红尘亦爱她 发表于 2024-07-04 13:23
@FishC1已知矩阵a为
1 2  4 7 11 16
2 3 5 8 12 17
...


好的，让我们通过C++代码来实现矩阵的LU分解。LU分解是将一个方阵分解成一个下三角矩阵L和一个上三角矩阵U的乘积。由于你提供的矩阵是6x6的，我们将通过C++编写代码来完成这个分解。

以下是完整的C++代码：

  1. #include <iostream>
  2. #include <vector>
  3. #include <iomanip>  // for std::setw

  5. using namespace std;

  7. // 打印矩阵函数
  8. void printMatrix(const vector<vector<double>>& matrix) {
  9.     for (const auto& row : matrix) {
  10.         for (double val : row) {
  11.             cout << setw(8) << val << " ";
  12.         }
  13.         cout << endl;
  14.     }
  15. }

  17. int main() {
  18.     const int N = 6;  // 矩阵大小
  19.     vector<vector<double>> a = {
  20.         {1, 2, 4, 7, 11, 16},
  21.         {2, 3, 5, 8, 12, 17},
  22.         {4, 5, 6, 9, 13, 18},
  23.         {7, 8, 9, 10, 14, 19},
  24.         {11, 12, 13, 14, 15, 20},
  25.         {16, 17, 18, 19, 20, 21}
  26.     };

  28.     vector<vector<double>> L(N, vector<double>(N, 0));
  29.     vector<vector<double>> U(N, vector<double>(N, 0));

  31.     // LU 分解
  32.     for (int i = 0; i < N; ++i) {
  33.         for (int j = i; j < N; ++j) {
  34.             U[i][j] = a[i][j];
  35.             for (int k = 0; k < i; ++k) {
  36.                 U[i][j] -= L[i][k] * U[k][j];
  37.             }
  38.         }

  40.         for (int j = i; j < N; ++j) {
  41.             if (i == j) {
  42.                 L[i][i] = 1;  // 对角线元素设为1
  43.             } else {
  44.                 L[j][i] = a[j][i];
  45.                 for (int k = 0; k < i; ++k) {
  46.                     L[j][i] -= L[j][k] * U[k][i];
  47.                 }
  48.                 L[j][i] /= U[i][i];
  49.             }
  50.         }
  51.     }

  53.     cout << "L Matrix:" << endl;
  54.     printMatrix(L);
  55.     cout << endl;

  57.     cout << "U Matrix:" << endl;
  58.     printMatrix(U);

  60.     return 0;
  61. }
复制代码


### 代码解释

1. **引入头文件**：
   - `#include <iostream>` 用于标准输入输出。
   - `#include <vector>` 用于使用 `std::vector` 容器。
   - `#include <iomanip>` 用于设置输出格式。

2. **定义打印矩阵函数**：
   - `void printMatrix(const vector<vector<double>>& matrix)` 用于打印矩阵，方便查看结果。

3. **初始化矩阵和大小**：
   - `const int N = 6;` 定义矩阵大小为6x6。
   - 初始化矩阵 `a` 为题目中给定的矩阵。

4. **初始化L和U矩阵**：
   - 使用 `vector<vector<double>> L(N, vector<double>(N, 0));` 和 `vector<vector<double>> U(N, vector<double>(N, 0));` 分别初始化L和U矩阵为N×N的零矩阵。

5. **LU分解算法**：
   - 外层循环遍历矩阵的每一行 `i`。
   - 内层循环首先计算上三角矩阵 `U` 的元素。
   - 之后计算下三角矩阵 `L` 的元素，对角线元素设为1。

6. **打印结果**：
   - 分别打印L矩阵和U矩阵。

通过运行这段代码，你将得到给定矩阵 `a` 的LU分解结果。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

卷帘红尘亦爱她
 楼主| 发表于 2024-7-4 13:30:26 | 显示全部楼层

@FishC1已知矩阵a为
1 2  4 7 11 16
2 3 5 8 12 17
4 5 6 9 13 18
7 8 9 10 14 19
11 12 13 14 15 20
16 17 18 19 20 21
用c++对其进行a=lu分解,利用分解因子L,U解方程组ax=b即先求ly=b再求ux=y
b1为任一非零的六维向量，bk+1=xk/(x的行范)
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

FishC
发表于 2024-7-4 13:30:52 | 显示全部楼层
卷帘红尘亦爱她 发表于 2024-07-04 13:30
@FishC1已知矩阵a为
1 2  4 7 11 16
2 3 5 8 12 17
...


好的，这里我们用C++实现矩阵的LU分解，然后通过分解因子L和U来解方程组Ax=b。具体步骤如下：

1. **LU分解**：将矩阵A分解为下三角矩阵L和上三角矩阵U。
2. **求解Ly=b**：使用前向替换法求解Ly=b。
3. **求解Ux=y**：使用后向替换法求解Ux=y。

首先，我们来实现LU分解。然后，利用分解因子L和U解方程组Ax=b。

  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>

  5. using namespace std;

  7. typedef vector<vector<double>> Matrix;
  8. typedef vector<double> Vector;

  10. // LU分解
  11. void luDecomposition(const Matrix& A, Matrix& L, Matrix& U) {
  12.     int n = A.size();
  13.     L = Matrix(n, Vector(n, 0));
  14.     U = Matrix(n, Vector(n, 0));
  15.    
  16.     for (int i = 0; i < n; ++i) {
  17.         // Upper Triangular
  18.         for (int k = i; k < n; ++k) {
  19.             double sum = 0;
  20.             for (int j = 0; j < i; ++j) {
  21.                 sum += (L[i][j] * U[j][k]);
  22.             }
  23.             U[i][k] = A[i][k] - sum;
  24.         }

  26.         // Lower Triangular
  27.         for (int k = i; k < n; ++k) {
  28.             if (i == k)
  29.                 L[i][i] = 1; // Diagonal as 1
  30.             else {
  31.                 double sum = 0;
  32.                 for (int j = 0; j < i; ++j) {
  33.                     sum += (L[k][j] * U[j][i]);
  34.                 }
  35.                 L[k][i] = (A[k][i] - sum) / U[i][i];
  36.             }
  37.         }
  38.     }
  39. }

  41. // 前向替换法求解Ly=b
  42. Vector forwardSubstitution(const Matrix& L, const Vector& b) {
  43.     int n = L.size();
  44.     Vector y(n);
  45.     for (int i = 0; i < n; ++i) {
  46.         y[i] = b[i];
  47.         for (int j = 0; j < i; ++j) {
  48.             y[i] -= L[i][j] * y[j];
  49.         }
  50.     }
  51.     return y;
  52. }

  54. // 后向替换法求解Ux=y
  55. Vector backSubstitution(const Matrix& U, const Vector& y) {
  56.     int n = U.size();
  57.     Vector x(n);
  58.     for (int i = n - 1; i >= 0; --i) {
  59.         x[i] = y[i];
  60.         for (int j = i + 1; j < n; ++j) {
  61.             x[i] -= U[i][j] * x[j];
  62.         }
  63.         x[i] /= U[i][i];
  64.     }
  65.     return x;
  66. }

  68. int main() {
  69.     Matrix A = { {1, 2, 4, 7, 11, 16},
  70.                  {2, 3, 5, 8, 12, 17},
  71.                  {4, 5, 6, 9, 13, 18},
  72.                  {7, 8, 9, 10, 14, 19},
  73.                  {11, 12, 13, 14, 15, 20},
  74.                  {16, 17, 18, 19, 20, 21} };
  75.                  
  76.     Vector b = { 1, 1, 1, 1, 1, 1 }; // 输入任意非零六维向量b

  78.     Matrix L, U;
  79.     luDecomposition(A, L, U);

  81.     cout << "L Matrix:" << endl;
  82.     for (const auto& row : L) {
  83.         for (double val : row) {
  84.             cout << val << " ";
  85.         }
  86.         cout << endl;
  87.     }

  89.     cout << "U Matrix:" << endl;
  90.     for (const auto& row : U) {
  91.         for (double val : row) {
  92.             cout << val << " ";
  93.         }
  94.         cout << endl;
  95.     }

  97.     Vector y = forwardSubstitution(L, b);
  98.     Vector x = backSubstitution(U, y);

  100.     cout << "Solution x:" << endl;
  101.     for (double val : x) {
  102.         cout << val << " ";
  103.     }
  104.     cout << endl;

  106.     Vector next_b = x;
  107.     double norm = sqrt(inner_product(x.begin(), x.end(), x.begin(), 0.0));
  108.     for (auto& val : next_b) {
  109.         val /= norm;
  110.     }

  112.     cout << "Next b:" << endl;
  113.     for (double val : next_b) {
  114.         cout << val << " ";
  115.     }
  116.     cout << endl;

  118.     return 0;
  119. }
复制代码


这段代码完成了以下几件事：
1. 将矩阵A分解为下三角矩阵L和上三角矩阵U。
2. 使用L和U求解线性方程Ax=b。
3. 归一化x向量得到新的b向量。

注意：输入矩阵A必须是可进行LU分解的以确保算法正确性。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

卷帘红尘亦爱她
 楼主| 发表于 2024-7-4 13:35:37 | 显示全部楼层
@FishC未定义inner_product
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

FishC
发表于 2024-7-4 13:36:45 | 显示全部楼层
卷帘红尘亦爱她 发表于 2024-07-04 13:35
@FishC未定义inner_product


在C++中使用LU分解，并利用分解因子L和U来解方程组`Ax = b`的过程，涉及矩阵分解、前向代替法和后向代替法。我们先定义矩阵`a`，然后实现LU分解，并用分解因子求解方程。

首先，实现LU分解：
1. `LU Decomposition`: 将矩阵`a`分解为下三角矩阵`L`和上三角矩阵`U`。
2. `Forward Substitution`: 使用矩阵`L`和向量`b`求解`Ly = b`。
3. `Backward Substitution`: 使用矩阵`U`和向量`y`求解`Ux = y`。

下面是实现这些步骤的C++代码：

  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>

  5. using namespace std;

  7. typedef vector<vector<double>> Matrix;
  8. typedef vector<double> Vector;

  10. void printMatrix(const Matrix &mat) {
  11.     for (const auto &row : mat) {
  12.         for (double val : row) {
  13.             cout << val << " ";
  14.         }
  15.         cout << endl;
  16.     }
  17.     cout << endl;
  18. }

  20. void printVector(const Vector &vec) {
  21.     for (double val : vec) {
  22.         cout << val << " ";
  23.     }
  24.     cout << endl << endl;
  25. }

  27. void LUdecomposition(const Matrix &A, Matrix &L, Matrix &U) {
  28.     int n = A.size();
  29.     L = Matrix(n, Vector(n, 0));
  30.     U = Matrix(n, Vector(n, 0));

  32.     for (int i = 0; i < n; ++i) {
  33.         for (int k = i; k < n; ++k) {
  34.             double sum = 0;
  35.             for (int j = 0; j < i; ++j) {
  36.                 sum += (L[i][j] * U[j][k]);
  37.             }
  38.             U[i][k] = A[i][k] - sum;
  39.         }

  41.         for (int k = i; k < n; ++k) {
  42.             if (i == k) {
  43.                 L[i][i] = 1;  // Diagonal as 1
  44.             } else {
  45.                 double sum = 0;
  46.                 for (int j = 0; j < i; ++j) {
  47.                     sum += (L[k][j] * U[j][i]);
  48.                 }
  49.                 L[k][i] = (A[k][i] - sum) / U[i][i];
  50.             }
  51.         }
  52.     }
  53. }

  55. Vector forwardSubstitution(const Matrix &L, const Vector &b) {
  56.     int n = L.size();
  57.     Vector y(n);

  59.     for (int i = 0; i < n; ++i) {
  60.         double sum = 0;
  61.         for (int j = 0; j < i; ++j) {
  62.             sum += L[i][j] * y[j];
  63.         }
  64.         y[i] = b[i] - sum;
  65.     }
  66.     return y;
  67. }

  69. Vector backwardSubstitution(const Matrix &U, const Vector &y) {
  70.     int n = U.size();
  71.     Vector x(n);

  73.     for (int i = n - 1; i >= 0; --i) {
  74.         double sum = 0;
  75.         for (int j = i + 1; j < n; ++j) {
  76.             sum += U[i][j] * x[j];
  77.         }
  78.         x[i] = (y[i] - sum) / U[i][i];
  79.     }
  80.     return x;
  81. }

  83. Vector normalize(const Vector &x) {
  84.     double norm = 0;
  85.     for (double val : x) {
  86.         norm += val * val;
  87.     }
  88.     norm = sqrt(norm);
  89.    
  90.     Vector normX(x.size());
  91.     for (size_t i = 0; i < x.size(); ++i) {
  92.         normX[i] = x[i] / norm;
  93.     }
  94.     return normX;
  95. }

  97. int main() {
  98.     Matrix a = {
  99.         {1, 2, 4, 7, 11, 16},
  100.         {2, 3, 5, 8, 12, 17},
  101.         {4, 5, 6, 9, 13, 18},
  102.         {7, 8, 9, 10, 14, 19},
  103.         {11, 12, 13, 14, 15, 20},
  104.         {16, 17, 18, 19, 20, 21}
  105.     };

  107.     Matrix L, U;
  108.     LUdecomposition(a, L, U);

  110.     cout << "Matrix L:" << endl;
  111.     printMatrix(L);

  113.     cout << "Matrix U:" << endl;
  114.     printMatrix(U);

  116.     Vector b = {1, 2, 3, 4, 5, 6}; // Example vector b
  117.     Vector y = forwardSubstitution(L, b);
  118.     Vector x = backwardSubstitution(U, y);

  120.     cout << "Solution x:" << endl;
  121.     printVector(x);

  123.     // Normalizing x
  124.     Vector normalizedX = normalize(x);
  125.     cout << "Normalized x:" << endl;
  126.     printVector(normalizedX);

  128.     return 0;
  129. }
复制代码


### 代码解释

1. **LU分解**：`LUdecomposition`函数将矩阵`A`分解为`L`和`U`。其中`L`是下三角矩阵，`U`是上三角矩阵。
2. **前向代替法**：`forwardSubstitution`函数使用`L`和`b`求解`Ly = b`，得到中间变量`y`。
3. **后向代替法**：`backwardSubstitution`函数使用`U`和`y`求解`Ux = y`，得到最终解`x`。
4. **归一化**：`normalize`函数将解向量`x`进行归一化。

这样，通过上述代码，我们可以实现矩阵的LU分解并利用其解方程组，同时将解向量进行归一化。希望这个答案对你有所帮助！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

卷帘红尘亦爱她
 楼主| 发表于 2024-9-23 16:01:11 | 显示全部楼层
@FishC用opengl'实现对五星红旗的绘制
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

FishC
发表于 2024-9-23 16:24:13 | 显示全部楼层
卷帘红尘亦爱她 发表于 2024-09-23 16:01
@FishC用opengl'实现对五星红旗的绘制


好的，使用OpenGL绘制五星红旗需要进行以下几个步骤：初始化OpenGL环境、设置窗口、绘制矩形和五角星。以下是逐步实现的代码示例：

### 初始化OpenGL环境和设置窗口

  1. #include <GL/glut.h>

  3. // 初始化函数
  4. void init() {
  5.     glClearColor(1.0, 1.0, 1.0, 1.0); // 背景色为白色
  6.     gluOrtho2D(0.0, 800.0, 0.0, 600.0); // 设置2D正交视口
  7. }
复制代码


### 绘制矩形（红旗背景）

  1. void drawRectangle(float x, float y, float width, float height) {
  2.     glBegin(GL_POLYGON);
  3.     glColor3f(1.0, 0.0, 0.0); // 红色
  4.     glVertex2f(x, y);
  5.     glVertex2f(x + width, y);
  6.     glVertex2f(x + width, y + height);
  7.     glVertex2f(x, y + height);
  8.     glEnd();
  9. }
复制代码


### 绘制五角星（参考公式）

  1. #include <cmath>

  3. void drawStar(float cx, float cy, float radius, float rotateAngle = 0) {
  4.     glBegin(GL_POLYGON);
  5.     glColor3f(1.0, 1.0, 0.0); // 黄色
  6.     for (int i = 0; i < 5; i++) {
  7.         glVertex2f(cx + radius * cos(2 * M_PI * i / 5.0 + rotateAngle),
  8.                    cy + radius * sin(2 * M_PI * i / 5.0 + rotateAngle));
  9.         glVertex2f(cx + radius / 2.5 * cos(2 * M_PI * (i + 0.5) / 5.0 + rotateAngle),
  10.                    cy + radius / 2.5 * sin(2 * M_PI * (i + 0.5) / 5.0 + rotateAngle));
  11.     }
  12.     glEnd();
  13. }
复制代码


### 绘制五星红旗的主函数

  1. void display() {
  2.     glClear(GL_COLOR_BUFFER_BIT);

  4.     // 绘制红旗背景
  5.     drawRectangle(50, 50, 700, 500);

  7.     // 绘制大五角星
  8.     drawStar(150, 450, 50);

  10.     // 绘制4个小五角星
  11.     drawStar(300, 520, 20, M_PI / 10);
  12.     drawStar(350, 480, 20, -M_PI / 5);
  13.     drawStar(350, 420, 20, M_PI / 10);
  14.     drawStar(300, 380, 20, M_PI / 10);

  16.     glFlush();
  17. }
复制代码


### 主函数

  1. int main(int argc, char** argv) {
  2.     glutInit(&argc, argv);
  3.     glutInitDisplayMode(GLUT_SINGLE | GLUT_RGB);
  4.     glutInitWindowSize(800, 600);
  5.     glutInitWindowPosition(100, 100);
  6.     glutCreateWindow("五星红旗");

  8.     init();
  9.     glutDisplayFunc(display);

  11.     glutMainLoop();
  12.     return 0;
  13. }
复制代码


这里的坐标和大小可以根据实际需求进行微调。运行这个程序，将显示一个包含五星红旗的窗口。

### 核心步骤解析

1. **初始化环境**：
   - 设置背景色为白色。
   - 设置视口大小和范围。

2. **绘制矩形**：
   - 使用红色填充，作为旗帜的背景。

3. **绘制五角星**：
   - 通过五角星顶点公式计算，绘制黄色五角星。
   - 大小和位置可根据实际需求调整。

4. **组合和显示**：
   - 矩形和五角星组合形成五星红旗。
   - 利用OpenGL的绘制函数显示在窗口中。

希望这个示例对你有帮助！如果有其他问题，随时提问。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

卷帘红尘亦爱她
 楼主| 发表于 2024-9-23 16:43:22 | 显示全部楼层
@FishC
  1. #include<iostream>
  2. #include <glad/glad.h>
  3. #include <GLFW/glfw3.h>
  4. #include<cmath>

  6. #define pi 3.14159265

  8. const char* fragmentShaderSource = "#version 330 core\n"
  9. "out vec4 FragColor;\n"
  10. "void main()\n"
  11. "{\n"
  12. "   FragColor = vec4(1.0f, 0.5f, 0.2f, 1.0f);\n"
  13. "}\n\0";

  15. const char* vertexShaderSource = "#version 330 core\n"
  16. "layout (location = 0) in vec3 aPos;\n"
  17. "void main()\n"
  18. "{\n"
  19. "   gl_Position = vec4(aPos.x, aPos.y, aPos.z, 1.0);\n"
  20. "}\0";

  22. void framebuffer_size_callback(GLFWwindow* window, int width, int height)
  23. {
  24.     glViewport(0, 0, width, height);
  25. }

  27. void processInput(GLFWwindow* window)
  28. {
  29.     if (glfwGetKey(window, GLFW_KEY_ESCAPE) == GLFW_PRESS)
  30.         glfwSetWindowShouldClose(window, true);
  31. }

  33. float ang2rad(float ang) {
  34.     return (ang * pi) / 180;
  35. }

  37. float findBiggerRadius(float smallR) {
  38.     float a, b, c, x1, x2, d;
  39.     float num1 = sin(ang2rad(36)) / sin(ang2rad(126));
  40.     a = (1 - (pow(num1, 2)));
  41.     b = (2 * num1 * smallR * cos(ang2rad(126)));
  42.     c = -(smallR * smallR);
  43.     //scanf("%f %f %f",&a,&b,&c);
  44.     if (a != 0)
  45.     {
  46.         d = sqrt(b * b - 4 * a * c);
  47.         x1 = (-b + d) / (2 * a);
  48.         x2 = (-b - d) / (2 * a);
  49.         if (x1 < x2)
  50.             return x2;
  51.         else
  52.             return x1;
  53.     }
  54.     return -1;
  55. }

  57. int main()
  58. {

  60.     glfwInit();
  61.     glfwWindowHint(GLFW_CONTEXT_VERSION_MAJOR, 3);//将主版本号(Major)和次版本号(Minor)都设为3
  62.     glfwWindowHint(GLFW_CONTEXT_VERSION_MINOR, 3);
  63.     glfwWindowHint(GLFW_OPENGL_PROFILE, GLFW_OPENGL_CORE_PROFILE);//告诉GLFW我们使用的是核心模式(Core-profile)

  65.     GLFWwindow* window = glfwCreateWindow(800, 600, "LearnOpenGL", NULL, NULL);

  67.     if (window == NULL)
  68.     {
  69.         std::cout << "Failed to create GLFW window" << std::endl;
  70.         glfwTerminate();
  71.         return -1;
  72.     }
  73.     glfwMakeContextCurrent(window);

  75.     if (!gladLoadGLLoader((GLADloadproc)glfwGetProcAddress))//我们给GLAD传入了用来加载系统相关的OpenGL函数指针地址的函数。GLFW给我们的是glfwGetProcAddress，它根据我们编译的系统定义了正确的函数。
  76.     {
  77.         std::cout << "Failed to initialize GLAD" << std::endl;
  78.         return -1;
  79.     }

  81.     glViewport(0, 0, 500, 500);

  83.     glfwSetFramebufferSizeCallback(window, framebuffer_size_callback);

  85.     unsigned int vertexShader;
  86.     vertexShader = glCreateShader(GL_VERTEX_SHADER);

  88.     glShaderSource(vertexShader, 1, &vertexShaderSource, NULL);
  89.     glCompileShader(vertexShader);


  92.     unsigned int fragmentShader;
  93.     fragmentShader = glCreateShader(GL_FRAGMENT_SHADER);
  94.     glShaderSource(fragmentShader, 1, &fragmentShaderSource, NULL);
  95.     glCompileShader(fragmentShader);


  98.     unsigned int shaderProgram;
  99.     shaderProgram = glCreateProgram();
  100.     glAttachShader(shaderProgram, vertexShader);
  101.     glAttachShader(shaderProgram, fragmentShader);
  102.     glLinkProgram(shaderProgram);

  104.     //glUseProgram(shaderProgram);

  106.     glDeleteShader(vertexShader);
  107.     glDeleteShader(fragmentShader);

  109.     float v_center = 0.0f;
  110.     float radius_small = 0.3f;
  111.     float radius_big = findBiggerRadius(radius_small);
  112.     float v[35];

  114.     float degree = 54.0f;
  115.     int i = 0;
  116.     while (i < 15) {
  117.         v[i++] = v_center + radius_small * cos(ang2rad(degree));
  118.         v[i++] = v_center + radius_small * sin(ang2rad(degree));
  119.         v[i++] = 1.0f;
  120.         degree += 72.0f;
  121.     }
  122.     degree = 18.0f;
  123.     while (i < 30) {
  124.         v[i++] = v_center + radius_big * cos(ang2rad(degree));
  125.         v[i++] = v_center + radius_big * sin(ang2rad(degree));
  126.         v[i++] = 1.0f;
  127.         degree += 72.0f;
  128.     }
  129.     v[i++] = v_center;
  130.     v[i++] = v_center;
  131.     v[i++] = 1.0f;

  133.     /*
  134.         unsigned int indices[] = {
  135.             // 注意索引从0开始!
  136.             // 此例的索引(0,1,2,3)就是顶点数组vertices的下标，
  137.             // 这样可以由下标代表顶点组合成矩形

  139.             0, 1, 3, // 第一个三角形
  140.             1, 2, 3  // 第二个三角形
  141.         };
  142.         */



  146.     unsigned int indices[] = {
  147.         // 注意索引从0开始!
  148.         // 此例的索引(0,1,2,3)就是顶点数组vertices的下标，
  149.         // 这样可以由下标代表顶点组合成矩形

  151.         0, 6, 10,
  152.         6, 1, 10,
  153.         1, 7, 10,
  154.         2, 7, 10,
  155.         2, 8, 10,
  156.         3, 8, 10,
  157.         3, 9, 10,
  158.         4, 9, 10,
  159.         4, 5, 10,
  160.         0, 5, 10
  161.     };

  163.     glVertexAttribPointer(0, 3, GL_FLOAT, GL_FALSE, 3 * sizeof(float), (void*)0);
  164.     glEnableVertexAttribArray(0);


  167.     unsigned int VBO, VAO, EBO;
  168.     glGenVertexArrays(1, &VAO);
  169.     glGenBuffers(1, &VBO);
  170.     glGenBuffers(1, &EBO);
  171.     glBindVertexArray(VAO); {

  173.         glBindBuffer(GL_ARRAY_BUFFER, VBO);
  174.         glBufferData(GL_ARRAY_BUFFER, sizeof(v), v, GL_STATIC_DRAW);

  176.         glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, EBO);
  177.         glBufferData(GL_ELEMENT_ARRAY_BUFFER, sizeof(indices), indices, GL_STATIC_DRAW);

  179.         glVertexAttribPointer(0, 3, GL_FLOAT, GL_TRUE, 3 * sizeof(float), (void*)0);
  180.         glEnableVertexAttribArray(0);

  182.     }
  183.     glBindBuffer(GL_ARRAY_BUFFER, 0);
  184.     //VAO解绑前不能解绑EBO，如：glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, 0);
  185.     glBindVertexArray(0);


  188.     while (!glfwWindowShouldClose(window))//我们需要在程序中添加一个while循环，我们可以把它称之为渲染循环(Render Loop)，它能在我们让GLFW退出前一直保持运行
  189.     {

  191.         // 输入
  192.         processInput(window);

  194.         //渲染指令QAQ
  195.         //glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
  196.         glClearColor(1.0f, 0.0f, 0.0f, 1.0f);
  197.         glClear(GL_COLOR_BUFFER_BIT);
  198.         glUseProgram(shaderProgram);
  199.         glBindVertexArray(VAO);
  200.         //glDrawArrays(GL_TRIANGLES, 0, 3);
  201.         glDrawElements(GL_TRIANGLES, 30, GL_UNSIGNED_INT, 0);

  203.         //检查并调用事件，交换缓冲
  204.         glfwSwapBuffers(window);
  205.         glfwPollEvents();

  207.     }

  209.     glfwTerminate();
  210.     return 0;
  211. }

复制代码
对其代码进行修改使其从一颗五角星变成一大四小的五颗
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

FishC
发表于 2024-9-23 16:54:29 | 显示全部楼层
卷帘红尘亦爱她 发表于 2024-09-23 16:43
@FishC #include
#include
#include
#include

...


你好，鱼油！看上去你这段代码有一定的问题。主要是代码结构存在不完整部分，从而导致无法编译和运行。代码似乎用于OpenGL的基本绘图操作。让我给你一些建议来完善它：

1. **使用完整的库引用**：
  
  1. #include <glad/glad.h>
  2.    #include <GLFW/glfw3.h>
  3.    #include <iostream>
  4.    #include <cmath>
复制代码


2. **补全窗口创建状况检查**：
  
  1. if (window == NULL) {
  2.        std::cout << "Failed to create GLFW window" << std::endl;
  3.        glfwTerminate();
  4.        return -1;
  5.    }
复制代码


3. **初始化GLAD**：
  
  1. glfwMakeContextCurrent(window);
  2.    if (!gladLoadGLLoader((GLADloadproc)glfwGetProcAddress)) {
  3.        std::cout << "Failed to initialize GLAD" << std::endl;
  4.        return -1;
  5.    }
复制代码


4. **设定窗口尺寸回调**：
  
  1. glfwSetFramebufferSizeCallback(window, framebuffer_size_callback);
复制代码


5. **完整的顶点和片段着色器创建代码及程序对象链接**：

  
  1. // 顶点着色器
  2.    int vertexShader = glCreateShader(GL_VERTEX_SHADER);
  3.    glShaderSource(vertexShader, 1, &vertexShaderSource, NULL);
  4.    glCompileShader(vertexShader);
  5.    
  6.    // 片段着色器
  7.    int fragmentShader = glCreateShader(GL_FRAGMENT_SHADER);
  8.    glShaderSource(fragmentShader, 1, &fragmentShaderSource, NULL);
  9.    glCompileShader(fragmentShader);
  10.    
  11.    // 着色器程序
  12.    int shaderProgram = glCreateProgram();
  13.    glAttachShader(shaderProgram, vertexShader);
  14.    glLinkProgram(shaderProgram);

  16.    // 编译和链接错误检查
  17.    int success;
  18.    char infoLog[512];
  19.    glGetShaderiv(vertexShader, GL_COMPILE_STATUS, &success);
  20.    if (!success) {
  21.        glGetShaderInfoLog(vertexShader, 512, NULL, infoLog);
  22.        std::cout << "ERROR: Vertex shader compilation failed\n" << infoLog << std::endl;
  23.    }

  25.    glGetShaderiv(fragmentShader, GL_COMPILE_STATUS, &success);
  26.    if (!success) {
  27.        glGetShaderInfoLog(fragmentShader, 512, NULL, infoLog);
  28.        std::cout << "ERROR: Fragment shader compilation failed\n" << infoLog << std::endl;
  29.    }

  31.    glGetProgramiv(shaderProgram, GL_LINK_STATUS, &success);
  32.    if (!success) {
  33.        glGetProgramInfoLog(shaderProgram, 512, NULL, infoLog);
  34.        std::cout << "ERROR: Shader program linking failed\n" << infoLog << std::endl;
  35.    }

  37.    glDeleteShader(vertexShader);
  38.    glDeleteShader(fragmentShader);
复制代码

   
6. **循环渲染逻辑**：
  
  1. while (!glfwWindowShouldClose(window)) {
  2.        processInput(window);

  4.        glClearColor(0.2f, 0.3f, 0.3f, 1.0f);
  5.        glClear(GL_COLOR_BUFFER_BIT);

  7.        // 使用着色器程序
  8.        glUseProgram(shaderProgram);
  9.        // ... 绘图命令 (例如glDrawArrays等)

  11.        glfwSwapBuffers(window);
  12.        glfwPollEvents();
  13.    }
  14.    glfwTerminate();
  15.    return 0;
复制代码


通过采用这些补全代码和改进，相信能更好地实现你预期的功能。希望这些建议对你有所帮助，如果还有其他问题，尽管问吧！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

卷帘红尘亦爱她
 楼主| 发表于 2024-10-9 14:11:03 | 显示全部楼层
@FishC 完成此代码1.解决最长公共子序列问题。输入的字符串可以利用随机数生成器随机产生，运行程序，记录对长度为一千、一万、十万的字符串，查找公共子序列所用的时间，列出表格显示。并单独显示一个长度为一百的字符串查找最长公共子序列的结果。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

FishC
发表于 2024-10-9 14:25:15 | 显示全部楼层
卷帘红尘亦爱她 发表于 2024-10-09 14:11
@FishC 完成此代码1.解决最长公共子序列问题。输入的 ...


要解决最长公共子序列（LCS）问题，你可以使用动态规划。下面是一个Python示例，包含生成随机字符串、计算LCS的函数，并记录不同长度字符串的执行时间。

  1. import random
  2. import string
  3. import time
  4. import pandas as pd

  6. def random_string(length):
  7.     return ''.join(random.choices(string.ascii_letters + string.digits, k=length))

  9. def lcs(X, Y):
  10.     m, n = len(X), len(Y)
  11.     dp = [[0] * (n + 1) for _ in range(m + 1)]
  12.    
  13.     for i in range(1, m + 1):
  14.         for j in range(1, n + 1):
  15.             if X[i - 1] == Y[j - 1]:
  16.                 dp[i][j] = dp[i - 1][j - 1] + 1
  17.             else:
  18.                 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
  19.    
  20.     # Reconstruct the LCS
  21.     lcs_str = []
  22.     while m > 0 and n > 0:
  23.         if X[m - 1] == Y[n - 1]:
  24.             lcs_str.append(X[m - 1])
  25.             m -= 1
  26.             n -= 1
  27.         elif dp[m - 1][n] > dp[m][n - 1]:
  28.             m -= 1
  29.         else:
  30.             n -= 1
  31.     lcs_str.reverse()
  32.     return ''.join(lcs_str)

  34. def measure_time(length):
  35.     str1 = random_string(length)
  36.     str2 = random_string(length)
  37.     start_time = time.time()
  38.     lcs_result = lcs(str1, str2)
  39.     end_time = time.time()
  40.     return end_time - start_time, lcs_result

  42. # Measure time for different lengths
  43. lengths = [1000, 10000, 100000, 100]
  44. results = {"Length": [], "Time (seconds)": [], "LCS Length": []}

  46. for length in lengths:
  47.     elapsed_time, lcs_result = measure_time(length)
  48.     results["Length"].append(length)
  49.     results["Time (seconds)"].append(elapsed_time)
  50.     if length == 100:
  51.         print(f"LCS for length 100: {lcs_result}")  # Show LCS for length 100
  52.     results["LCS Length"].append(len(lcs_result))

  54. # Display results as table
  55. df = pd.DataFrame(results)
  56. print(df)
复制代码


该代码完成以下任务：

1. `random_string` 函数随机生成指定长度的字符串。
2. `lcs` 函数实现动态规划算法来计算两个字符串的最长公共子序列，并返回实际的子序列。
3. `measure_time` 函数计算不同长度的字符串的LCS，并测量执行时间。
4. 最后，使用`pandas`库打印出计算结果，表现为一个表格，显示字符串长度、耗时以及对应的LCS长度。

这个代码对长度为100的字符串还单独打印出最长公共子序列的结果。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

卷帘红尘亦爱她
 楼主| 发表于 2024-10-9 14:28:16 | 显示全部楼层
@FishC用c++ 完成此代码1.解决最长公共子序列问题。输入的字符串可以利用随机数生成器随机产生，运行程序，记录对长度为一千、一万、十万的字符串，查找公共子序列所用的时间，列出表格显示。并单独显示一个长度为一百的字符串查找最长公共子序列的结果。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

FishC
发表于 2024-10-9 14:28:29 | 显示全部楼层
卷帘红尘亦爱她 发表于 2024-10-09 14:28
@FishC用c++ 完成此代码1.解决最长公共子序列问题。输 ...


好的，下面是一个使用C++实现最长公共子序列（LCS）问题的示例代码。代码中会生成随机字符串并计算它们的LCS，同时测量不同长度字符串的执行时间。

  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <ctime>
  5. #include <cstdlib>
  6. #include <chrono>

  8. using namespace std;

  10. // 生成随机字符串
  11. string generateRandomString(int length) {
  12.     const char charset[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  13.     string result;
  14.     result.reserve(length);
  15.     for (int i = 0; i < length; ++i)
  16.         result += charset[rand() % (sizeof(charset) - 1)];
  17.     return result;
  18. }

  20. // 动态规划求解最长公共子序列
  21. int longestCommonSubsequence(const string &str1, const string &str2) {
  22.     int m = str1.size();
  23.     int n = str2.size();
  24.     vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

  26.     for (int i = 1; i <= m; ++i) {
  27.         for (int j = 1; j <= n; ++j) {
  28.             if (str1[i - 1] == str2[j - 1])
  29.                 dp[i][j] = dp[i - 1][j - 1] + 1;
  30.             else
  31.                 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
  32.         }
  33.     }
  34.     return dp[m][n];
  35. }

  37. // 用于测量和输出LCS计算的时间
  38. void measureAndDisplayLCS(int length1, int length2) {
  39.     string str1 = generateRandomString(length1);
  40.     string str2 = generateRandomString(length2);

  42.     auto start = chrono::high_resolution_clock::now();
  43.     int lcsLength = longestCommonSubsequence(str1, str2);
  44.     auto end = chrono::high_resolution_clock::now();

  46.     chrono::duration<double> elapsed = end - start;
  47.     cout << "LCS of length " << length1 << " and " << length2 << " is " << lcsLength
  48.          << ", computed in " << elapsed.count() << " seconds." << endl;
  49. }

  51. int main() {
  52.     srand(time(0)); // 初始化随机种子

  54.     // 测试不同长度的字符串
  55.     measureAndDisplayLCS(1000, 1000);
  56.     measureAndDisplayLCS(10000, 10000);
  57.     // 较大测试数据，可能会消耗较长时间
  58.     // measureAndDisplayLCS(100000, 100000);

  60.     // 显示长度为100的字符串的LCS结果
  61.     string str1 = generateRandomString(100);
  62.     string str2 = generateRandomString(100);
  63.     cout << "String1: " << str1 << endl;
  64.     cout << "String2: " << str2 << endl;
  65.     cout << "LCS Length for strings of length 100: " << longestCommonSubsequence(str1, str2) << endl;

  67.     return 0;
  68. }
复制代码


### 说明

1. **字符串生成**：`generateRandomString` 函数用于生成指定长度的随机字符串，字符集为大写字母。
2. **LCS计算**：`longestCommonSubsequence` 函数

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

卷帘红尘亦爱她
 楼主| 发表于 2024-10-15 14:55:17 | 显示全部楼层
@FishC 用c++实现解决多边形游戏问题。多边形每个顶点的数值a(|a|<=6)和边上的运算符可以随机生成，运行程序，记录分别对十条边，二十条边，三十条边，四十条边，所用的时间，列出表格显示结果。并在实验报告中单独画出一个6边形游戏的运行过程，即每一步合并的过程都画出来。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

FishC
发表于 2024-10-15 15:07:01 | 显示全部楼层
卷帘红尘亦爱她 发表于 2024-10-15 14:55
@FishC 用c++实现解决多边形游戏问题。多边形每个顶点 ...


你提到的多边形游戏问题，通常是指动态规划（Dynamic Programming）中一个用于解多边形顶点最优值的优化问题。这个问题涉及到对多边形进行适当的分隔（通常是划分为三角形），以最大化或最小化某个目标函数，例如顶点值的乘积或和。

虽然你没有提供完整的具体细节（例如问题的目标），但我可以给你一个基本思路，如何实现这样一个动态规划算法。假设我们要最小化一个多边形的顶点乘积的合值，这是一种常见的形式。不过具体解决方式会因目标不同而异。

### 基本思路
1. **定义问题状态**：设定 `dp[i][j]` 为顶点 `i` 到顶点 `j` 之间的多边形（即所有包含 `i` 和 `j` 的多边形）的最优值。
2. **状态转移方程**：
   - `dp[i][j] = min(dp[i][k] + dp[k][j] + a[i]*a[k]*a[j])`，其中 `k` 是 `i` 和 `j` 之间的一个顶点。
3. **初始化**：
   - `dp[i][i+1] = 0`（因为至少需要三个顶点才能形成一个多边形）。

### C++ 代码示例
这是一个简单的 C++ 程序框架，假设 `a` 是顶点的数值数组，`n` 是顶点数量：

  1. #include <iostream>
  2. #include <vector>
  3. #include <limits.h>

  5. using namespace std;

  7. int minPolygonTriangulation(vector<int>& a) {
  8.     int n = a.size();
  9.     vector<vector<int>> dp(n, vector<int>(n, 0));

  11.     for (int length = 2; length < n; ++length) {
  12.         for (int i = 0; i < n - length; ++i) {
  13.             int j = i + length;
  14.             dp[i][j] = INT_MAX;
  15.             for (int k = i + 1; k < j; ++k) {
  16.                 dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j]);
  17.             }
  18.         }
  19.     }

  21.     return dp[0][n - 1];
  22. }

  24. int main() {
  25.     vector<int> a = {1, 2, 3, 4}; // 示例顶点值
  26.     cout << "Minimum triangulation cost: " << minPolygonTriangulation(a) << endl;
  27.     return 0;
  28. }
复制代码


### 注意
这个方法是一个通用的解决问题的方向，具体实现和优化可能需要根据你所提的问题和约束来进行调整和测试。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

卷帘红尘亦爱她
 楼主| 发表于 2024-10-15 16:17:17 | 显示全部楼层
@FishC 用c++使用opengl完成设计一款2D的小游戏，数独小游戏，必须包含鼠标和键盘的交互。使用glad
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

下一页 »
1 ...34567891011下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-5-10 07:29

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表