BF算法的实现：病毒感染检测
一、问题引入
BF（Brute-Force）算法介绍了BF算法的具体实现，但并未结合具体案例。
本随笔就是结合案例（病毒感染检测）对BF算法进行结合分析。
案例4.1: 病毒感染检测
医学研究者最近发现了某些新病毒， 通过对这些病毒的分析， 得知它们的 DNA 序列都是环状的。现在研究者巳收集了大量的病毒DNA 和人的DNA 数据，想快速检测出这些人是否感染了相应的病毒。为了方便研究，研究者将人的DNA 和病毒DNA 均表示成由一些字母组成的字符串序列，然后检测某种病毒DNA 序列是否在患者的DNA 序列中出现过，如果出现过，则此人感染了该病毒， 否则没有感染。例如， 假设病毒的DNA 序列为baa, 患者1 的DNA 序列为aaabbba,则感染， 患者2 的DNA 序列为babbba, 则未感染。（注意， 人的DNA 序列是线性的， 而病毒的DNA 序列是环状的）
二、解决过程
- 函数：virus_dna_extend()
int virus_dna_extend(char virus_src[], char virus_dst[][DNA_SIZE_MAX], int *num_of_virus)
{
int virus_len = strlen(virus_src);
int i = virus_len;
int idx = 0;
char *temp = (char *)malloc(2* DNA_SIZE_MAX *sizeof(char));
if (temp == NULL)
return OVERFLOW;
memset(temp, 0, (2 * virus_len + 1) * sizeof(char));
memcpy(temp, virus_src, virus_len);
for (int j = 0; j < virus_len; j++)
{
temp[i++] = temp[j];
}
temp[2 * virus_len + 1] = '\0';
//printf("%s\n", temp);
for (int i = 0; i < virus_len; i++)
{
for (int j = 0; j < virus_len; j++)
{
virus_dst[idx][j] = temp[i + j];
}
virus_dst[idx][virus_len + 1] = '\0';
//printf("%s\n", virus_dst[idx]);
idx++;
}
*num_of_virus = idx;
free(temp);
return 0;
}
- 函数：virus_detect()
int virus_detect(const char *person_dna, const char virus_dna[][DNA_SIZE_MAX], int num_of_virus)
{
int result = FALSE;
for (int i = 0; i < num_of_virus; i++)
{
if (-1 != index_bf(person_dna, virus_dna[i], 0))
{
result = TRUE;
break;
}
}
return result;
}
- 函数：main()
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define FALSE 0
#define TRUE 1
#define OVERFLOW 2
int main(void)
{
char person_dna[10][DNA_SIZE_MAX] = {
"bbaabbba",
"aaabbbba",
"abceaabb",
"abaabcea",
"cdabbbab",
"cabbbbab",
"bcdedbda",
"bdedbcda",
"cdcdcdec",
"cdccdcce"
};
char virus_dna[10][2 * DNA_SIZE_MAX + 1] = {
"baa",
"baa",
"aabb",
"aabb",
"abcd",
"abcd",
"abcde",
"acc",
"cde",
"cced"
};
printf("病毒DNA "
"患者DNA "
"检测结果 \n");
for (int i = 0; i < 10; i++)
{
char vir_dst[100][DNA_SIZE_MAX] = { 0 };
const char *negative = "NO";
const char *positive = "YES";
int num_of_vir = 0;
virus_dna_extend(virus_dna[i], vir_dst, &num_of_vir);
int result = virus_detect(person_dna[i], vir_dst, num_of_vir);
if (result == TRUE)
printf("%-20s %-20s %-20s\n", virus_dna[i], person_dna[i], positive);
else
printf("%-20s %-20s %-20s\n", virus_dna[i], person_dna[i], negative);
}
return 0;
}
💡 运行结果
三、反思总结
重点理解病毒DNA的扩展函数，至于BF算法函数请参考BF（Brute-Force）算法
四、参考引用
数据结构第二版：C语言版