1 [0] 1 Count Pattern

1 [0] 1 Patrón Conde: Aquí, vamos a resolver un problema algoritmo de búsqueda basado en el patrón encontramos en la ronda de codificación de Samsung.

Descripción:

Este artículo proporciona una solución a un problema algoritmo de búsqueda basado en el patrón llegó en la ronda de codificación de Samsung.

Planteamiento del problema:

Dada una cadena binaria, escribir un algoritmo para encontrar el número de patrones de la forma 1 [0] 1 que [0] representa cualquier número de ceros (requisito mínimo es de un 0), debe haber no puede ser cualquier otro carácter excepto 0 en la secuencia [0].

Solución

Algoritmo:

  1. Conjunto l = longitud de la cadena de inicialización y recuento a 0.
  2. encuentra el número de 1 de la cadena. If todo entrada es 1, entonces existe tal patrón para la entrada de cadena.
  3. Encuentra primera ‘1’ para un patrón 1 [0] 1
    While ( String [elemento]! = ‘1’ )
    Ir al siguiente elemento.
  4. Comprobar if el siguiente elemento de la cadena es ‘0’ o no.
  5. If el siguiente elemento es ‘0’
    Continue comprobación siguiente elemento hasta la subcadena de 0 acabados. ([0] parte en el patrón)
  6. Una vez terminado cheque el siguiente elemento. If es ‘1’ aumento recuento .
    En la siguiente iteración de este ‘1’ elemento va a ser el elemento de patrón siguiente 1 [0] 1 de partida.
  7. Continue pasos 3 a 6 hasta acabados de longitud de cadena para su procesamiento.
  8. Return recuento .

C ++ aplicación para 1 [0] 1 Patrón Count

#include <bits/stdc++.h>
using namespace std;
int my(string s){
//set variables
int l=s.length(),count=0;
for(int i=0;i<l;i++){
//count no of 1's
if(s[i]!='0')
count++;
}
//if no of 1=total length then no 1[0]1 pattern
if(count==l)
return 0;
int i=0,flag=0,start=0,end=1;
count=0;
while(i<l){
//go to first '1' of a pattern
while(s[i]!='1'){
i++;
}
//first 1 is found,check the next
i=i+1;
//if next is a 0
if(s[i]=='0'){
//procedd till elements are 0
while(s[i]=='0')
i++;
//if the element after end of 0 substring is 1
if(s[i]=='1'){
//pattern is found & increase count
count++;
}
}
}
return count; //return no of pattern
}
int main()
{
cout<<"program to find no of 1[0]1 patterns in string"<<endl;
string s;
cout<<"enter string"<<endl;
cin>>s;
int k=my(s);
cout<<k<<endl;
return 0;
}

salida

First run:
program to find no of 1[0]1 patterns in string
enter string
001010100001101
4
Second run:
program to find no of 1[0]1 patterns in string
enter string
111111111111111111111110
0


Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *