【GESP】C++三级练习 luogu-B2111 基因相关性

GESP三级练习，字符串练习（C++三级大纲中6号知识点，字符串），难度★✮☆☆☆。

luogu-B2111 基因相关性

题目要求

题目描述

为了获知基因序列在功能和结构上的相似性，经常需要将几条不同序列的 DNA 进行比对，以判断该比对的 DNA 是否具有相关性。

现比对两条长度相同的 DNA 序列。首先定义两条 DNA 序列相同位置的碱基为一个碱基对，如果一个碱基对中的两个碱基相同的话，则称为相同碱基对。接着计算相同碱基对占总碱基对数量的比例，如果该比例大于等于给定阈值时则判定该两条 DNA 序列是相关的，否则不相关。

输入格式

有三行，第一行是用来判定出两条 DNA 序列是否相关的阈值，随后 $2$ 行是两条 DNA 序列（长度不大于 $500$）。

输出格式

若两条 DNA 序列相关，则输出 yes，否则输出no。

输入输出样例 #1

输入 #1

0.85
ATCGCCGTAAGTAACGGTTTTAAATAGGCC
ATCGCCGGAAGTAACGGTCTTAAATAGGCC

输出 #1

yes

---

题目分析

解题思路

1. 题目要求比较两条DNA序列的相关性，通过计算相同碱基对的比例与给定阈值比较来判断。

2. 解题关键点：
   • 需要统计两条DNA序列中相同位置相同碱基的数量
   • 计算相同碱基对占总碱基对的比例
   • 将比例与给定阈值进行比较
3. 具体思路：
   • 输入阈值和两条DNA序列
   • 遍历两条序列，统计相同位置相同碱基的数量
   • 计算相同碱基对的比例（相同碱基对数量/总碱基对数量）
   • 将计算出的比例与阈值比较，大于等于阈值输出”yes”，否则输出”no”
4. 时间复杂度分析：
   • 只需要遍历一次DNA序列，时间复杂度为O(n)，其中n为序列长度
   • 空间复杂度为O(1)，只需要存储几个变量

---

示例代码

#include <iostream>
#include <string>

int main() {
    // 定义阈值变量
    double level;
    // 定义两个DNA序列字符串
    std::string str_1, str_2;
    // 输入阈值和两个DNA序列
    std::cin >> level >> str_1 >> str_2;
    // 记录相同碱基对的数量
    int same_count = 0;
    // 遍历DNA序列，统计相同碱基对
    for (int i = 0; i < str_1.size(); i++) {
        if (str_1[i] == str_2[i]) {
            same_count++;
        }
    }
    // 计算相同碱基对的比例，与阈值比较并输出结果
    if ((double)same_count / str_1.size() >= level) {
        std::cout << "yes";
    } else {
        std::cout << "no";
    }
    return 0;
}

---

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP各级别考纲要点、知识拓展和练习题目清单详见C++学习项目主页

“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限，欢迎加入。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。