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语言版

热门相关:地球第一剑   霸皇纪   致灿烂的你   天启预报   薄先生,情不由己