Tengo varias dudas sobre un programa que necesito realizar:
El problema consiste en que a partir de una cadena de caracteres, consiga calcular la longitud de la cadena de caractéres descendente más larga, dando su tamaño y origen. Por ejemplo la cadena: abc es de longitud 3 y su origen está en 0, sin embargo la cadena : zab, su cadena más larga descendente es de longitud 2, y el origen es la posición 1.
El problema debe resolverse basado en el algoritmo de DIvide y Vencerás.
Esto es lo que llevo hasta ahora
#include "DYV.hpp"
#include <sys/time.h>
#include "memcount.hpp"
#include <stdlib.h>
using namespace std;
char array[50];
namespace espacioDYV {
char GeneradorLetras(){
char c = rand () % (122-97+1) + 97;
return c;
}
int GeneradorIndices(int linf, int lsup){
int x = rand()%(lsup-linf+1)+linf;
return x;
}
bool Pequeno(int p, int q){
if (((q-p)==1)or((q-p)==0)){
return true;
}
else {
return false;
}
}
int Dividir(int p, int q){
int r;
if ((((q-p)+1)%2) == 0){
return r=(((q-p+1)/2)+p);
}
else{
return r=(((q-p)/2)+p);
}
}
Solucion SolucionDirecta(int p, int q){
Solucion solu;
if ((q-p)==0){
solu.Longitud=1;
solu.Origen=p;
return solu;
}
else{
int letraascii1= array[p];
int letraascii2= array[q];
if (letraascii1 <= letraascii2){
solu.Longitud=2;
solu.Origen=p;
//cout << "La solucion es: (" << solu.Longitud << ", " << solu.Origen << ")" << endl;
return solu;
}
else {
solu.Longitud=1;
solu.Origen=p+1;
//cout << "La solucion es: (" << solu.Longitud << ", " << solu.Origen << ")" << endl;
return solu;
}
}
}
Solucion Combinar(Solucion solu1, Solucion solu2){
Solucion solu1posible=solu1;
Solucion solu2posible=solu2;
Solucion solu3posible;
solu3posible.Longitud=0;
solu3posible.Origen=-1;
int contador=solu1.Origen+solu1.Longitud-1;
int letraascii1=array[contador];
int letraascii2=array[contador+1];
//cout << "Contador: " << contador << endl;
//cout << solu1posible.Longitud << endl;
while ((letraascii1 <= letraascii2) and ((contador+1) != solu2.Origen)){
//cout << "Entro aquí" << endl;
solu1posible.Longitud++;
contador++;
letraascii1=array[contador];
letraascii2=array[contador+1];
}
//cout << solu1posible.Longitud << endl;
if (((contador+1) == solu2.Origen) and (letraascii1 <= letraascii2)){
//cout << solu1posible.Longitud << "+" << solu2.Longitud << endl;
solu1posible.Longitud=solu1posible.Longitud+solu2.Longitud;
return solu1posible;
}
while ((contador+1) != solu2.Origen){
int Longitud = 1;
contador++;
solu3posible.Origen=contador;
letraascii1=array[contador];
letraascii2=array[contador+1];
while (letraascii1 <= letraascii2){
Longitud++;
contador++;
letraascii1=array[contador];
letraascii2=array[contador+1];
}
if (Longitud > solu3posible.Longitud){
solu3posible.Longitud=Longitud;
solu3posible.Origen=contador;
}
}
if (letraascii1 <= letraascii2){
solu3posible.Longitud=solu3posible.Longitud+solu2posible.Longitud;
}
if ((solu1posible.Longitud >= solu2posible.Longitud) and (solu1posible.Longitud >= solu3posible.Longitud)) return solu1posible;
else if (solu2posible.Longitud >= solu3posible.Longitud) return solu2posible;
else return solu3posible;
}
Solucion DYV (int p, int q){
int m;
if (Pequeno(p, q)){
return SolucionDirecta(p, q);
}
else {
m=Dividir(p,q);
return Combinar(DYV(p, m-1), DYV(m, q));
}
}
}
using namespace espacioDYV;
int main(){
srand(time(NULL));
for(int i=0;i<50;i++){
//cin >> array[i];
array[i]=GeneradorLetras();
}
cout << array;
Solucion m;
srand(time(NULL));
int p=GeneradorIndices(0,49);
cout << endl << "Indice p: " << p << endl;
int q= GeneradorIndices(p,49);
cout << "Indice q: " << q << endl;
m=DYV(p, q);
cout << "La solucion es: (" << m.Longitud << "," << m.Origen << ")" << endl;
}
Las dudas que me surgen son las siguientes, al pasarle a la función DYV dos índices muy alejados me salta una violación de segmento y no sé dónde está el error. Con índices relativamente cercanos, me resuelve bien el problema.
Otra cosa que me gustaría arreglar y no sé cómo es, pasarle por el intérprete yo mismo el tamaño del array y poder trabajar de la misma manera en la que he trabajado con él en este código, o sea, definiéndolo de manera global.