C语言随机生成一个一万个字符的字符串s1的数据文件Character.txt。发出k(k=100)个随机数整数[0,9999]下标,给这k个字符随机赋值,形成第二个一万个字符的字符串s2。求这两个字符串的LCS,并计算重复率=Length(LCS)/Length(s1)。
时间: 2024-05-10 12:16:15 浏览: 91
以下是一个简单的C语言程序,可以生成一个一万个字符的字符串s1的数据文件Character.txt,并根据给定的下标随机赋值,形成第二个一万个字符的字符串s2,并计算它们的LCS和重复率。
```c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define LENGTH 10000
#define K 100
void generate_s1(char *filename);
void generate_s2(char *filename, int *index);
int main()
{
char s1[LENGTH];
int index[K];
srand((unsigned)time(NULL));
// 生成s1并写入文件
generate_s1("Character.txt");
// 随机生成k个下标
for (int i = 0; i < K; i++)
index[i] = rand() % LENGTH;
// 生成s2并写入文件
generate_s2("Character2.txt", index);
// 读取文件中的s1和s2
FILE *fp1 = fopen("Character.txt", "r");
FILE *fp2 = fopen("Character2.txt", "r");
if (fp1 == NULL || fp2 == NULL)
{
printf("Failed to open file.\n");
return 0;
}
fgets(s1, LENGTH+1, fp1);
char s2[LENGTH+1];
fgets(s2, LENGTH+1, fp2);
fclose(fp1);
fclose(fp2);
// 计算LCS和重复率
int dp[LENGTH+1][LENGTH+1];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= LENGTH; i++)
{
for (int j = 1; j <= LENGTH; j++)
{
if (s1[i-1] == s2[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];
}
}
int lcs_len = dp[LENGTH][LENGTH];
double repeat_rate = (double)lcs_len / LENGTH;
printf("LCS length: %d\n", lcs_len);
printf("Repeat rate: %.2f%%\n", repeat_rate * 100);
return 0;
}
void generate_s1(char *filename)
{
FILE *fp = fopen(filename, "w");
if (fp == NULL)
{
printf("Failed to open file.\n");
return;
}
for (int i = 0; i < LENGTH; i++)
fprintf(fp, "%c", rand() % 26 + 'a');
fclose(fp);
}
void generate_s2(char *filename, int *index)
{
FILE *fp = fopen(filename, "w");
if (fp == NULL)
{
printf("Failed to open file.\n");
return;
}
char s2[LENGTH];
for (int i = 0; i < LENGTH; i++)
s2[i] = rand() % 26 + 'a';
for (int i = 0; i < K; i++)
s2[index[i]] = rand() % 26 + 'a';
for (int i = 0; i < LENGTH; i++)
fprintf(fp, "%c", s2[i]);
fclose(fp);
}
```
程序的主要思路如下:
1. 首先使用 `generate_s1` 函数生成一个一万个字符的随机字符串,并写入文件 "Character.txt"。
2. 随机生成100个下标,用于后面生成 s2。
3. 使用 `generate_s2` 函数生成第二个一万个字符的字符串 s2,并将随机下标处的字符随机赋值。
4. 读取文件中的 s1 和 s2。
5. 使用动态规划算法计算 s1 和 s2 的 LCS,同时统计 LCS 的长度。
6. 计算重复率,并输出结果。
注意,重复率的计算公式为 Length(LCS)/Length(s1)。
阅读全文