Exercise number of occurrences always returns 0

Question

Exercise number of occurrences always returns 0

Navigation

#1 by (1 votes)

-2

I do not know how to do this exercise.

It gives me that the number of occurrences is zero and as much as I look at the code I do not know why. This is my tried code:

#include <iostream>
using namespace std;
const unsigned TAM1=11;
const unsigned TAM2=4;
typedef unsigned TNumeros[TAM1];
typedef unsigned TPermutacion[TAM2];
typedef bool TTachados[TAM2];

void inicializa(TTachados& tachados){
for(unsigned cont=0;cont<TAM2;cont++){
    tachados[cont]=false;
}
}

bool esta(int num, const TPermutacion& permutacion, const TTachados& tachados){
bool encontrado=false;
int cont=0;
while(cont<TAM2&&!encontrado){
    if(permutacion[cont]==num&&tachados[cont]==false){
        encontrado=true;
    }
    ++cont;
}
return encontrado;
}

bool todosTachados(const TTachados& tachados){
bool loestan=true;
int cont=0;
while(loestan&&cont<TAM2){
    if(tachados[cont]!=true){
        loestan=false;
    }
    ++cont;
}
return loestan;
}

bool esOcurrencia(int pos, const TNumeros& numeros,const TPermutacion& permutacion, TTachados& tachados){
for(int cont=pos;cont<TAM2+pos;cont++){
    if(esta(numeros[cont], permutacion, tachados)){
        tachados[cont-pos]=true;
    }
}
return todosTachados(tachados);
}

unsigned numOcurrencias(const TNumeros& numeros, const TPermutacion& permutacion){
TTachados arrtachados;
int suma=0, cont=0;
inicializa(arrtachados);
while(cont+TAM2<=TAM1){
    if(esOcurrencia(cont, numeros, permutacion, arrtachados)){
        ++suma;
    }
    inicializa(arrtachados);
    ++cont;
}
return suma;
}

void leeNumeros(TNumeros& arrnum){
for(unsigned cont=0;cont<TAM1;cont++){
    cin>>arrnum[cont];
}
}

void leePermutacion(TPermutacion& arrper){
for(unsigned cont=0;cont<TAM2;cont++){
    cin>>arrper[cont];
}
}

int main(){
TNumeros arrnum;
TPermutacion arrper;
cout<<"Introduzca los numeros"<<endl;
leeNumeros(arrnum);
cout<<"Introduzca la permutacion"<<endl;
leePermutacion(arrper);
cout<<"El numero de ocurrencias es de "<<numOcurrencias(arrnum, arrper);
}

c++

asked by anonimo115 28.08.2017 в 10:53

source

1 answer

How to use the conditions with the contents of a txt file in python [closed] Error autopy python module [closed]

score 1 · Accepted Answer

If we analyze this function:

bool esta(int num, const TPermutacion& permutacion, const TTachados& tachados){
  bool encontrado=false;
  int cont=0;
  while(cont<TAM2&&!encontrado){
    if(permutacion[cont]==num&&tachados[cont]==false){
      encontrado=true;
    }
    ++cont;
  }
  return encontrado;
}

What it does is, basically, check if a certain number is in the permutacion array and also verify that it has not already been used.

In principle everything is correct, but ... What happens when you have to cross out the number? To find the answer we have to go to the function that calls this first:

bool esOcurrencia(int pos, const TNumeros& numeros,const TPermutacion& permutacion, TTachados& tachados){
  for(int cont=pos;cont<TAM2+pos;cont++){
    if(esta(numeros[cont], permutacion, tachados)){
      tachados[cont-pos]=true;
    }
  }
  return todosTachados(tachados);
}

And this is when the problems begin to appear. To mark the number as used we do not use the index within the permutation but the index of the array numeros Is this detail important? I think so, let's see it with the example of the exercise (with a sad debugger you can also see it):

permutacion: 1 4 1 12
numeros: 12 1 1 4

esOcurrencia(0)
  esta(12)
    permutacion[0] != 12
    permutacion[1] != 12
    permutacion[2] != 12
    perumtacion[3] == 12
  tachados[0] = true
  esta(1)
    permutacion[0] == 1
  tachados[1] = true
  esta(1)
    permutacion[0] == 1, pero tachados[0] == true
    permutacion[1] != 1
    perumtacion[2] == 1
  tachados[2] = true
  esta(4)
    permutacion[0] != 4
    permutacion[1] == 4, pero tachados[1] == true
    permutacion[2] != 4
    permutacion[3] != 4

  conclusion: no hay coincidencia

The element to cross out should be given by the function esta and it is not the case ... that causes the algorithm to fail in the vast majority of situations.

You have a real cacao of functions ... the variables are not declared where they should be or updated by the function that really knows what needs to be updated.

The esta function should look, given your code, rather like this:

bool esta(int num, const TPermutacion& permutacion, TTachados& tachados){
  bool encontrado=false;
  int cont=0;
  while(cont<TAM2&&!encontrado){
    if(permutacion[cont]==num&&tachados[cont]==false){
      tachados[cont] = true;
      encontrado=true;
    }
    ++cont;
  }
  return encontrado;
}

And a possibility for the esOcurrencia function could be

bool esOcurrencia(int pos, const TNumeros& numeros,const TPermutacion& permutacion, TTachados& tachados){
  for(int i=0;i<TAM2; i++){
    if (!esta(numeros[i+pos], permutacion, tachados)){
      return false; // si falla un numero no tiene sentido seguir
    }
  }

  //Si todos los numeros estan no hay que comprobar nada,
  //la ocurrencia es real
  return true; 
}

Personally I think replacing while with for for loops with known range improves the readability of the code.

On the other hand, it does not make sense that the function esOcurrencia receives as parameter the array tachados . You could (and should) manage the function internally, but that change is in your account.