首页 > 试题广场 >

DNA序列

[编程题]DNA序列

热度指数：125232 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

一个 DNA 序列由 A/C/G/T 四个字母的排列组合组成。 G 和 C 的比例（定义为 GC-Ratio ）是序列中 G 和 C 两个字母的总的出现次数除以总的字母数目（也就是序列长度）。在基因工程中，这个比例非常重要。因为高的 GC-Ratio 可能是基因的起始点。

给定一个很长的 DNA 序列，以及限定的子串长度 N ，请帮助研究人员在给出的 DNA 序列中从左往右找出 GC-Ratio 最高且长度为 N 的第一个子串。

DNA序列为 ACGT 的子串有: ACG , CG , CGT 等等，但是没有 AGT ， CT 等等

数据范围：字符串长度满足 $1 \le n \le 1000 \$ ，输入的字符串只包含 A/C/G/T 字母

输入描述:

输入一个string型基因序列，和int型子串的长度

输出描述:

找出GC比例最高的子串,如果有多个则输出第一个的子串

示例1

输入

ACGT
2

输出

CG

说明

ACGT长度为2的子串有AC,CG,GT3个，其中AC和GT2个的GC-Ratio都为0.5，CG为1，故输出CG

示例2

输入

AACTGTGCACGACCTGA
5

输出

GCACG

说明

虽然CGACC的GC-Ratio也是最高，但它是从左往右找到的GC-Ratio最高的第2个子串，所以只能输出GCACG。

算法知识视频讲解

彭洋a

#include <stdio.h>

#include <string.h>

float rate(char str[],int n)

{

int num = 0;

for(int i = 0;i<n;i++)

{

if(str[i] == 'C'||str[i]== 'G')

{

num++;

}

return (float)num/n;

}

int main() {

char str[1001] = {'\0'};

int n = 0;

while (scanf("%s %d", str, &n) != EOF) {

int len = strlen(str);

float ret = 0;

char* ptr = str;

for(int i = 0;i<len-n;i++)

{

float tmp = rate(&str[i],n);

if(ret<tmp)

{

ret = tmp;

ptr = &str[i];

}

for(int i = 0;i<n;i++)

{

printf("%c",*ptr);

ptr++;

}

return 0;

}

发表于 2023-10-18 14:43:13 回复(0)

牛客364244344号

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

#define N 1001



int main()
{
    char s[N] = {0};
    int k;
    scanf("%s", s);
    scanf("%d", &k);
    int len = strlen(s);
    char str[len][k+1];
    int max = 0;
    int cnt = 0;
    for(int i = 0; i <= len-k; i++){
        cnt = 0;
        for(int j = i; j <i+k; j++){
            str[i][j-i] = s[j];
            if(s[j] == 'C' || s[j] == 'G'){
                cnt++;
            }
        }
        max = max > cnt ? max : cnt;
        str[i][k] = '\0';
    }
    for(int i = 0; i <= len-k; i++){
        cnt = 0;
        for(int j = 0; j < k; j++){
            if(str[i][j] == 'C' || str[i][j] == 'G'){
                cnt++;
            } 
        }
        if(max == cnt){
            printf("%s\n", str[i]);
            break;
        }
    }
    
    return 0;
}

发表于 2023-10-10 22:29:57 回复(0)

初牛小客

#include <stdio.h>
#include <string.h>

int main() {
    char str[1001] = {};
    int N;
    int sub[1000] = {0};
    int max_ratio = 0;
    scanf("%s", str);
    scanf("%d", &N);

    int len = strlen(str);
    for (int i = 0; i < len - N + 1; i++) {
        int count = 0;
        for (int j = i; j - i < N; j++) {
            if (str[j] == 'G' || str[j] == 'C')
                count++;
        }
        sub[i] = count;                                     //记录以str[i]开头的子串GC-Ratio
        max_ratio = max_ratio > count ? max_ratio : count;  //记录最大GC-Ratio
    }

    for (int i = 0; i < len - N + 1; i++) {
        if (sub[i] == max_ratio) {       //找到第一个最大GC-Ratio的子串
            for (int j = i; j - i < N; j++) {
                printf("%c", str[j]);
            }
            break;
        }
    }
    return 0;
}

发表于 2023-03-03 19:10:40 回复(0)

好奇的王老五最喜欢秋天

#include <stdio.h>
#include <string.h>

int main()
{
    char str[1000];
    fgets(str,sizeof(str),stdin);
    int len = strlen(str)-1;
    int num = 0;
    scanf("%d",&num);
    int left = 0;
    int right = 0;
    char rev[num];
    int numcg = 0;
    int flag[1000] = {0};
    int max = 0;
    
    while(right<=len-1)
    {
        if(((right-left+1)==num) && (left<right))
        {
            for(int i=0;i<num;i++)
            {
                if((str[left+i]=='C')||(str[left+i]=='G'))
                {
                    numcg++;
                }
            }
            flag[left] = numcg;
            numcg = 0;
            right++;
        }
        else
        {
            if((right-left+1)>num)
            {
                left++;
            }
            else
                right++;
        }
    }
    for(int i=0;i<len-1;i++)
    {
        if(flag[i]>max)
            max = flag[i];
    }
    for(int j=0;j<len-1;j++)
    {
        if(flag[j]==max)
        {
            for(int k=0;k<num;k++)
            {
                printf("%c",str[j+k]);
            }
            return 0;
        }
    }  
    return 0;
}

C语言，个人理解的滑动窗口法

发表于 2022-09-11 10:34:04 回复(0)

更健康

#include <stdio.h>
#include <string.h>

float gc_ratio(char *p, int n)
{
    int sum = 0;
    for(int i=0; p[i] != '\0'; i++) {
        if (p[i] == 'G' || p[i] == 'C')
            sum++;
    }
    
    return ((float)sum/(float)n);
}

int main(void)
{
    char str[1000] = {0};
    scanf("%[^\n]", str);
    int n;
    scanf("%d", &n);
    
    char sub[1000][1000] = {0};
    int k =0, i =0, j= 0;
    for (i=0; str[i] != '\0'; i++) {
        if (j == n) {
            sub[k][j] = '\0';
            k++;
        }
        for (j=0; j<n; j++) {
            sub[k][j] = str[i+j];
        }
    }
    float record = 0;
    int index = 0;
    for (i = 0; i< k; i++) {
        if (gc_ratio(sub[i],n) > record) {
            record = gc_ratio(sub[i],n);
            index = i;
        }
    }
    printf("%s\n", sub[index]);
}

发表于 2022-08-21 21:18:37 回复(0)

子沐728592488

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int main() {
char inPutStr[1001];
int n = 0;
char* p = NULL;
int max = 0;
int count = 0;
char* restStr = NULL;

memset(inPutStr, 0x00, sizeof(inPutStr));
scanf("%s %d", inPutStr, &n);
restStr = (char*)malloc(sizeof(char) * (n + 1));
memset(restStr, 0x00, sizeof(char) * (n + 1));
for (int i = 0; i < strlen(inPutStr); i++) {
count = 0;
if ((i + n) < strlen(inPutStr)) {
for (int j = i; j < i + n; j++) {
if ((inPutStr[j] == 'C') || (inPutStr[j] == 'G')) {
count++;
}
}
if (count > max) {
max = count;
p = &inPutStr[i];
}
} else {
break;
}
}
if (p != NULL) {
strncpy(restStr, p, n);
restStr[n] = '\0';
printf("%s\n", restStr);
} else {
printf("%s\n", inPutStr);
}

free(restStr);
return 0;
}

发表于 2022-06-07 22:59:39 回复(0)

练习时长的代码练习生

#include <stdio.h>
#include <string.h>

int main(){
    char gene[1000];int n;int sum=0;
    scanf("%s",gene);scanf("%d",&n);
    for(int i=0;i<n;i++){
        if(gene[i]=='C' || gene[i]=='G'){
            sum++;
        }
    }
    int max=sum;int len=strlen(gene);int max_i=0;
    for(int i=0;i<=len-n;i++){
        if((gene[i]=='C' || gene[i]=='G') && (gene[i+n]=='A' || gene[i+n]=='T')){
            sum--;
        }
        if((gene[i]=='A' || gene[i]=='T') && (gene[i+n]=='C' || gene[i+n]=='G')){
            sum++;
        }
        if(sum>max){
            max=sum;max_i=i+1;
        }
    }
    for(int i=0;i<n;i++){
        printf("%c",gene[max_i+i]);
    }
}

发表于 2022-06-07 12:49:06 回复(0)

已注销

#include <stdio.h>
#include <string.h>
#define    N    1000
int main()
{
    char str[N];
    int m,i,j,len,ra[N]={0};
    scanf("%s%d",str,&m);
    len=strlen(str);
    for(i=0;i<len-m;i++)
    {
        for(j=i;j<i+m;j++)
        {
            if(str[j]=='C'||str[j]=='G')
                ra[i]++;
        }
    }
    j=0;
    for(i=0;i<len-m;i++)
    {
        if(ra[i]>ra[j])
            j=i;
    }
    for(i=j;i<j+m;i++)
        printf("%c",str[i]);
    return 0;
}

发表于 2022-05-02 09:28:51 回复(0)

baixu

// 一个 DNA 序列由
// A/C/G/T 四个字母的排列组合组成。
// G 和 C 的比例（定义为 GC-Ratio ）是序列中 G 和 C 两个字母的总的出现次数除以总的字母长度）。
// 给定一个很长的 DNA 序列，以及限定的子串长度 N ，
// 请帮助研究人员在给出的 DNA 序列中从左往右找出 GC-Ratio 最高且长度为 N 的第一个子串。
// DNA序列为 ACGT 的子串有: ACG , CG , CGT 等等，但是没有 AGT ， CT 等等

#include<stdio.h>
#include<string.h>

struct {
float Ratio;//子串对应的GC-Ratio
int gc_cnt;//GC个数
int sn;//出现的序号
char str_child[1000];//子串
} data[1000], temp;

int main() {
char str[1000];
int num;
scanf("%s", str);
scanf("%d", &num);
int len = strlen(str);
int h = 0;
int k = 0;
for (int i = 0; i < len - num + 1; i++) {
k = 0;
//子串是，从第1个向后数1个，从第2个向后数1个，从第3个向后数1个

for (int j = i; j < i + num; j++) {
data[h].str_child[k++] = str[j]; //存子串
}
data[h].sn = h;
h++;//子串个数
}
//统计每个子串的GC个数
for (int i = 0; i < h; i++) {
//遍历子串，计算GC-Ratio
for (int j = 0; j < num; j++) {
if ((data[i].str_child[j] == 'G') || data[i].str_child[j] == 'C') {
data[i].gc_cnt += 1;
}
}
}
//计算GC-Ratio
for (int i = 0; i < h; i++) {
data[i].Ratio = (float)data[i].gc_cnt / num;
}
for (int i = 0; i < h; i++) {
for (int j = i + 1; j < h; j++) {

if (data[i].Ratio > data[j].Ratio) {
temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
}
//比较最大值和所有的值是否最大，如果有和最大值一样的值，输出最先出现的那个
int outNum = h - 1;
for (int i = 0; i < h; i++) {
if (data[outNum].Ratio == data[i].Ratio) {
//输出序号最小的那个
if (data[i].sn < data[outNum].sn) {
outNum = i;
}
}
}
printf("%s",data[outNum].str_child);

return 0 ;
}

发表于 2022-04-13 22:10:42 回复(0)

牛客445266458号

#include<stdio.h>
#include<string.h>
int main()
{
    char str[1000]={0};
    int n;
    scanf("%s",str);
    scanf("%d",&n);
    int i,j,count=0,sum=0,q;
    int len=strlen(str);
    for(i=0;i<=len-n;i++)
    {
        for(j=i;j<i+n;j++)
        {
            if(str[j]=='C'||str[j]=='G')
            {
                count++;
            }
        }
        if(count>sum)
        {
            sum=count;
            q=i;
        }
        count=0;
    }
    for(i=q;i<q+n;i++)
    {
        printf("%c",str[i]);
    }
    return 0;
}

发表于 2022-03-19 13:44:53 回复(0)

Hey2333777

#include
int main()
{
    char str[1000];
    scanf("%s",str);
    int len=strlen(str);
    int num;//sub-string length
    scanf("%d",&num);

    int min=0;
    int max=0;

    for(int i=0; i<len-(num-1); i++)
    {
        int j=i;
        int count=0;//Each sub-string
        int times=0;
        while(times<num)
        {
            if(str[j]=='C'||str[j]=='G')//Detect number of c,g in each sub-string
            {
                count++;
            }
            j++;
            times++;
        }

        if(count>max)//Times
        {
            max=count;
            min=i;//Store value of i at this times
        }
    }

    for(int i=0; i<num; i++)
    {
        printf("%c",str[min]);
        min++;
    }
}

发表于 2021-12-14 00:38:41 回复(0)

牛客489027493号

滑动窗口

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define STR_LEN 1001

bool IsGC(char c)
{
    if (c == 'G' || c == 'C') {
        return true;
    }
    
    return false;
}

// 窗口两边都闭合
int main(void)
{
    char str[STR_LEN];
    int fast = 0; // 窗口右边界
    int slow = 0; // 窗口左边界
    int leftIdx = 0; // 存储GC比例最好左边界
    int rightIdx = 0; // 存储GC比例最好右边界
    
    while (scanf("%s", str) != EOF) {
        int n;
        scanf("%d", &n);
        
        // 设置初始窗口
        int GCcnt = 0;
        for (int i = 0; i < n ; i++) {
            if (IsGC(str[i])) {
                GCcnt++;
            }
        }
        leftIdx = 0;
        slow = 0; // 指向上一个窗口左边界,窗口滑动时需要判断上一窗口左边界是否为GC
        rightIdx = n - 1;
        fast = n; // 指向下一个窗口右边界
        
        int tmp = GCcnt;
        while (fast < strlen(str)) {
            if (IsGC(str[fast])) {
                tmp++;
            }
            if (IsGC(str[slow])) {
                tmp--;
            }
            slow++;
            // 遇到更高GC比率则更新
            if (tmp > GCcnt) {
                GCcnt = tmp;
                leftIdx = slow;
                rightIdx = fast;
            }
            // 窗口向后滑动
            fast++;
            
        }
        
        for (int i = leftIdx; i <= rightIdx; i++) {
            printf("%c", str[i]);
        }
        printf("\n");
    }
    return 0;
}

发表于 2021-11-27 09:34:22 回复(0)

校长_

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

int main()
{
    char str1[1000] = {0};
    int sub_str_len = 0;
    int len = 0;
    int MaxP = 0;
    int CG_Num_Max = 0;
    while(scanf("%s", str1) != EOF)
    {
        int front, rear;
        int CG_Num = 0;
        scanf("%d", &sub_str_len);
        len = strlen(str1);    //DNA序列的长度
        front = 0; //子串的头指针

        /*先算出第一个子串的CG ratio*/
        for(int i=0; i<sub_str_len; i++)
        {
            if(str1[i] == 'C' || str1[i] == 'G')
            {
                CG_Num++;
            }
        }
        MaxP = 0;
        CG_Num_Max = CG_Num;
        /*双端队列原理，遍历DNA序列*/
        for(front = 1; (front+sub_str_len) <= len; front++)
        {
            if(str1[front-1] == 'C' || str1[front-1] == 'G')
            {
                CG_Num--;
            }
            if(str1[front+sub_str_len-1] == 'C' || str1[front+sub_str_len-1] == 'G')
            {
                CG_Num++;
            }
            if(CG_Num > CG_Num_Max)
            {
                MaxP = front;
                CG_Num_Max = CG_Num;
            }
        }
        for(int i=0; i<sub_str_len; i++)
        {
            printf("%c", str1[MaxP+i]);
        }
        printf("\n");   
    }
    return 0;
}

发表于 2021-09-03 15:05:13 回复(0)

80后大叔

垃圾题目描述，直接一句话把人误导了：DNA序列为ACGT的子串有:ACG,CG,CGT等等，但是没有AGT，CT等等。
还以为ACGT 不能间隔出现，结果只需要统计CG的数量就行了

#include<stdio.h>
int getSUB(char DNA[500], int m, int len) {
//     printf("now: %d:", m);
    int lenOfRatio = 0;
    int isSUB = 0;
//     for(int i = 0; i < len - 1; i++) {
//         printf("[%d]%c-", i, DNA[m+i]);
//         if(DNA[m+i] == 'A' && (DNA[m+i+1] == 'C' || DNA[m+i+1] == 'A')) {
//             printf("1");
//         } else if (DNA[m+i] == 'C' && (DNA[m+i+1] == 'A' || DNA[m+i+1] == 'G' || DNA[m+i+1] == 'C')) {
//             printf("2");
//             lenOfRatio++;
//         } else if (DNA[m+i] == 'G' && (DNA[m+i+1] == 'C' || DNA[m+i+1] == 'T' || DNA[m+i+1] == 'G')) {
//             printf("3");
//             lenOfRatio++;
//         } else if (DNA[m+i] == 'T' && (DNA[m+i+1] == 'G' || DNA[m+i+1] == 'T')) {
//             printf("4");
//         } else {
//             printf("not GC\n");
//             isSUB = -1;
//             break;
//         }
//     }
//     if(isSUB == 0 && (DNA[m+len-1] == 'C' || DNA[m+len-1] == 'G')) {
//         lenOfRatio++;
//     } else {
//         return -1;
//     }
    for(int i = 0; i < len; i++) {
        if(DNA[m+i] == 'C' || DNA[m+i] == 'G') {
            lenOfRatio++;
        }
    }
    return lenOfRatio;
}
int main() {
    char DNA[500];
    int len;
    while(gets(DNA) && scanf("%d\n", &len) != EOF) {
        int maxRatio = 0;
        int dest = 0;
        for(int i = 0; i <= strlen(DNA) - len; i++) {
            int getRatio = getSUB(DNA, i, len);
            if(getRatio > 0 && getRatio > maxRatio) {
                dest = i;
                maxRatio = getRatio;
            }
        }
        for(int i = 0; i < len; i++) {
            printf("%c", DNA[dest++]);
        }
    }
}

发表于 2021-08-21 13:10:24 回复(0)

牛客735570582号

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main()
{
    char DNA_str[1000];
    int N;
    int i,j;
    while(gets(DNA_str))
    {
        scanf("%d",&N);
        int len=strlen(DNA_str);
        int CG_len=0;
        for(i=0;i<N;i++)
        {
            if(DNA_str[i]=='C'&&DNA_str[i]=='G')
            {
                CG_len++;
            }
        }
        int max_CGlen;
        max_CGlen=CG_len;
        int firstpos=0;
        i=1;j=N;
        for(;j<len;i++,j++)
        {
            if(DNA_str[i-1]=='C'||DNA_str[i-1]=='G')
            {
                CG_len--;
            }
            if(DNA_str[j]=='C'||DNA_str[j]=='G')
            {
                CG_len++;
            }
            if(max_CGlen<CG_len)
            {
                max_CGlen=CG_len;
                firstpos=i;
            }
        }
        for(i=firstpos;i<firstpos+N;i++)
        {
            printf("%c",DNA_str[i]);
        }
        printf("\n");
    }
    return 0;
}

发表于 2021-07-16 13:42:31 回复(0)

提交观点

问题信息

字符串

难度：

15条回答 736收藏 30618浏览

通过挑战的用户

查看代码

94的菜鸟

2022-10-19 19:44:29
sallywait

2022-09-25 22:58:54
漫默123

2022-09-20 10:47:54
white_DOG

2022-09-19 16:23:08
Scotty2...

2022-09-18 17:41:01

DNA序列

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题