编程论坛 → C语言论坛

关于连续N个1的字符串问题

小星在北方发布于 2020-12-23 09:10， 2020 次点击

连续的n个1（我测试了很多数据感觉都是对的，但是提交上去答案就是错的，希望大家能指出我的错误，谢谢！）
时间限制: 1 Sec  内存限制: 128 MB
提交: 3117  解决: 2064
[状态] [讨论版] [提交] [命题人:admin]
题目描述
计算机数据都是由0和1组成的，看着长长的0101001110101111011，要找出连续n个1的子串有多少个，确实麻烦，请你编程实现吧。
输入
输入第一行为一个字符串，由0和1组成，长度小于1000；输入第二行为一个正整数n。
输出
输出一个整数，表示连续n个的1的子串的个数。
样例输入 Copy
0101001110101111011
2
样例输出    Copy
6

程序代码：

#include "stdio.h"
#include "string.h"
int main (){
    int i,m,deno=0,time=0;
    char str[1005];
    scanf("%s", str);
    scanf("%d", &m);
    for(i=0; str[i]!='\0'; i++){
        if(str[i] == '1'){
            deno++;
        }

        if(deno == m  &&  str[i+1]!='0'){
            time = i+1;
            break;
        }

    }
    if(m==0) printf("0");
    else  printf("%d", time);
    return 0;
}

7 回复

#2

xianfajushi2020-12-23 09:59

能把样例解释清楚？从输入字符串看连续2个1至多只有3个怎么会是6个？

#3

zbjzbj2020-12-23 10:40

样例不对，楼主的答案也不对。
试试这个：
0101001110101111011
3

#4

rjsp2020-12-23 10:51

你这算法……，我没法形容了

我想出的算法是：
a. 先将连续的1的数目计算出来。例如 0101001110101111011，那么就是 1个，1个，3个，4个，2个。
b. m个1中有几个连续n个的1？当然就是 m+1-n 个啦（结果为负数的话，就舍弃）！最终结果是 (1+1-2) + (1+1-2) + (3+1-2) + (4+1-2) + (2+1-2) = 6

#5

rjsp2020-12-23 11:07

程序代码：

#include <stdio.h>

int main( void )
{
    char s[1000];
    size_t n;
    scanf( "%s", s );
    scanf( "%zu", &n );

    size_t result = 0;
    size_t onelen = 0;
    for( size_t i=0; s[i]!='\0'; ++i )
    {
        if( s[i] == '1' )
            result += (++onelen>=n);
        else
            onelen = 0;
    }
    printf( "%zu\n", result );
}

#6

小星在北方2020-12-23 17:14

回复 2楼 xianfajushi

说的是，连续N个1的子串，假如三个连续的1就有两种子串，四个连续的1就有三种可能，就是相邻的组合问题，这里是把所有出现的可能都加起来。

#7

小星在北方2020-12-23 17:15

回复 2楼 xianfajushi

样例是题目给出的，绝对是对的，我的是错的。

#8

小星在北方2020-12-23 17:17

回复 3楼 zbjzbj

真心感谢！！听你这么一讲我清楚啦，我起初没有理解好题目意思，目前刚刚接触C，所以对算法什么的还是不太清楚，感谢指出，感谢！

1