7-5 sdut-最长上升子序列的和

### SDUT C语言实验中最长公共子序列 (LCS) 问题解法 #### 动态规划方法概述 动态规划（Dynamic Programming, DP）是一种常用的算法设计技术，适用于解决最优化问题。在处理字符串匹配类问题时，动态规划尤为有效。对于最长公共子序列（Longest Common Subsequence, LCS）问题，其核心在于通过构建一个二维表格 `dp` 来记录两个字符串之间的状态关系。 设给定的两个字符串分别为 \( X \) 和 \( Y \)，长度分别为 \( m \) 和 \( n \)。定义二维数组 `dp[i][j]` 表示字符串 \( X[1..i] \) 和 \( Y[1..j] \) 的最长公共子序列的长度，则可以得到如下转移方程： \[ dp[i][j] = \begin{cases} 0 & \text{if } i=0 \text{ or } j=0 \\ dp[i-1][j-1]+1 & \text{if } X[i]=Y[j] \\ \max(dp[i-1][j], dp[i][j-1]) & \text{otherwise } \end{cases} \] 最终的结果即为 \( dp[m][n] \)[^1]。 #### 实现代码 以下是基于上述理论实现的一个标准 C 语言程序： ```c #include <stdio.h> #include <string.h> void lcs(char *X, char *Y, int m, int n) { int dp[m+1][n+1]; // 初始化 dp 数组 for(int i = 0; i <= m; i++) { for(int j = 0; j <= n; j++) { if(i == 0 || j == 0) dp[i][j] = 0; else if(X[i-1] == Y[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = (dp[i-1][j] > dp[i][j-1]) ? dp[i-1][j] : dp[i][j-1]; } } printf("Length of Longest Common Subsequence is %d\n", dp[m][n]); } int main() { char X[] = "AGGTAB"; char Y[] = "GXTXAYB"; int m = strlen(X); int n = strlen(Y); lcs(X, Y, m, n); return 0; } ``` 此代码实现了计算两字符串之间最长公共子序列的功能，并打印出该子序列的长度。 #### 复杂度分析 时间复杂度主要由嵌套循环决定，由于需要遍历整个二维表，故时间为 \( O(m \times n) \)。空间上也需要开辟大小为 \( (m+1) \times (n+1) \) 的辅助矩阵用于存储中间结果，因此空间复杂度亦为 \( O(m \times n) \)。 ---

### Python实现复数运算 以下是基于Python的复数运算实现代码，利用Python内置的`complex`类型来简化复数的操作[^1]： ```python def complex_operations(): results = [] x_real, x_imaginary = map(int, input().split()) x = complex(x_real, x_imaginary) while True: line = input() if line.strip() == "0 0 0": break y_real, y_imaginary, op = line.split() y = complex(int(y_real), int(y_imaginary)) if int(op) == 1: # 加法 result = x + y elif int(op) == 2: # 减法 result = x - y elif int(op) == 3: # 乘法 result = x * y else: continue results.append(result) for res in results: print(f"{int(res.real)} {int(res.imag)}" .replace("j", "").replace("+", "")) if __name__ == "__main__": complex_operations() ``` 上述代码实现了读取输入并执行复数加减乘操作的功能。通过循环不断接收输入直到遇到终止条件 `0 0 0`。 --- ### Java实现复数运算 对于Java中的复数运算，则需要手动定义一个`Complex`类来进行封装[^2]。下面是一个完整的示例代码： ```java class Complex { private double real; private double imaginary; public Complex(double real, double imaginary) { this.real = real; this.imaginary = imaginary; } public Complex add(Complex other) { return new Complex(this.real + other.real, this.imaginary + other.imaginary); } public Complex subtract(Complex other) { return new Complex(this.real - other.real, this.imaginary - other.imaginary); } public Complex multiply(Complex other) { double r = this.real * other.real - this.imaginary * other.imaginary; double i = this.real * other.imaginary + this.imaginary * other.real; return new Complex(r, i); } @Override public String toString() { return (real != 0 ? real + " " : "") + (imaginary >= 0 && real != 0 ? "+" : "") + (imaginary != 0 ? Math.abs(imaginary) + "i" : ""); } } public class Main { public static void main(String[] args) { java.util.Scanner scanner = new Scanner(System.in); // 初始化 X System.out.println("Enter the first complex number:"); double xr = scanner.nextDouble(); double xi = scanner.nextDouble(); Complex x = new Complex(xr, xi); List<Complex> results = new ArrayList<>(); while (true) { System.out.println("Enter Y and operation code or '0 0 0' to stop:"); double yr = scanner.nextDouble(); double yi = scanner.nextDouble(); int opCode = scanner.nextInt(); if (yr == 0 && yi == 0 && opCode == 0) { break; } Complex y = new Complex(yr, yi); switch (opCode) { case 1 -> results.add(x.add(y)); case 2 -> results.add(x.subtract(y)); case 3 -> results.add(x.multiply(y)); default -> {} } } for (Complex c : results) { System.out.println(c.toString()); } } } ``` 此代码创建了一个名为`Complex`的类用于处理复数的相关计算，并提供了加法、减法以及乘法的方法。 --- ####