Algoritmo que calcula el máximo y mínimo de un vector técnica divide y vencerás

Question

INICIO
Si Cini<Cfin-1, hacer:
 mitad = Parte entera de (Cini+Cfin)/2
 [Max1, Min1]= MaximoMinimoDV (A, Cini, mitad)
[Max2, Min2]= MaximoMinimoDV (A, mitad+1, Cfin)
Max= Máximo(Max1, Max2);
Min= Mínimo(Min1, Min2);

En otro caso, hacer:
 si A[Cmin]>A[Cmax]
 Max = A[Cmin] ; Min = A[Cmax]
 en otro caso
Max = A[Cmax] ; Min = A[Cmin]
Fin-En otro caso
Fin-En otro caso
FIN-Algoritmo

este es el pseudocodigo que me han dado. Y yo he implementado esto, pero creo que no esta bien , alguien podria echarme una mano ?

int* MaxMin(int *A, const int Cini, const int Cfin) {
    int *v1,*v2;
    v1=new int [2]; // v1[max1,min1]
    v2=new int[2]; // v2[max2,min2]

    if (Cini<Cfin-1)
    {
        int mitad= (Cini-Cfin)/2;
        v1=MaxMin(A,0,mitad);
        v2=MaxMin(A,mitad+1,4);

        int max=maximo(v1[0],v2[0]); //devuelve max de 2 num
        int min=minimo(v1[1],v2[1]); //devuelve min de 2 num
    }
    if (Cini=Cfin-1)
    {
        if (A[Cini]>A[Cfin]{
            max=A[Cini];
            min=A[Cfin];
        }else
        {
            max=A[Cfin];
            min=A[Cini];
        }
    }else

        max=A[Cini];
        min=max;
}

Answer 1

Vigila las comparaciones

En C++ las comparaciones se realizan siempre con dos signos de igualdad seguidos, no con uno.

if (Cini=Cfin-1)

La línea anterior se descompone en las siguientes operaciones individuales:

Cini = Cfin-1;
if (Cini)

Y el resultado de esta operación es un comportamiento no especificado ya que, técnicamente, if solo debe evaluar un resultado de verdadero (true o 1) o falso (false o 0)... mientras que una variable de tipo entero cubre un rango mucho más amplio de valores. Lo que suceda cuando Cini==25 es totalmente dependiente del compilador y del procesador, aunque lo más común es que el resultado sea true.

En cualquier caso este error no es ningún misterio ya que el propio compilador te está avisando de que estás intentando modificar una variable de solo lectura:

error: assignment of read-only parameter 'Cini'
     if (Cini=Cfin-1)
             ^

Para terminar este punto, la solución pasa por poner una comparación en vez de una asignación:

if (Cini==Cfin-1)

Si abres un paréntesis, acuérdate de cerrarlo

if (A[Cini]>A[Cfin]{

Esta es otra línea que te arroja un error en tiempo de compilación y lo que dice el mensaje de error:

error: expected ')' before '{' token
     if (A[Cini]>A[Cfin]{
                        ^

El mensaje es claro como el agua. El compilador esperaba un cierre de paréntesis y, sin embargo, se está encontrando una llave de apertura. La solución en este caso también es trivial. Basta con añadir el cierre del paréntesis:

if (a[Cini]>A[Cfin]){

Cuidado con el ámbito de las variables

Otro error que sale en tiempo de compilación:

error: 'max' was not declared in this scope
     max=A[Cini];
     ^

El origen de este error es un poco más complicado de ver pero ahí está.

Fíjate que las variables max y min las estás declarando dentro de un if y, sin embargo, posteriormente usas esas mismas variables en el else correspondiente. El problema es que las llaves del if ya están delimitando el ámbito de estas variables:

if (Cini<Cfin-1)
{ // <<--- Inicio del ambito
    int mitad= (Cini-Cfin)/2;
    v1=MaxMin(A,0,mitad);
    v2=MaxMin(A,mitad+1,4);

    int max=maximo(v1[0],v2[0]); //devuelve max de 2 num
    int min=minimo(v1[1],v2[1]); //devuelve min de 2 num
} // <<--- Fin del ambito (max y min dejan de existir)

Los usos de las variables en el else no son válidos porque para el compilador esas variables no existen... luego no se pueden usar.

Tienes que mover la declaración de las variables a una zona común, es decir, tienes que declararlas antes del if:

int max, min;
if (Cini<Cfin-1)
// ...

Cuidado con el ámbito (parte 2)

Pregunta: ¿Ves algo raro en esta parte del código?

    }else

        max=A[Cini];
        min=max;
}

Si la respuesta es no, vuelve a mirar. El else no tiene llave de apertura, luego únicamente la instrucción max=A[Cini] entra en el ámbito del else, la otra se ejecutará de forma incondicional... lo dicho, cuidado con eso.

Cuando una instrucción de control de flujo tiene que ejecutar más de una instrucción es imprescindible agruparlas todas con llaves:

int* MaxMin(/*...*/) {
    // ...
    }else{
        max=A[Cini];
        min=max;
    }
}

PD.: La llave que se ve al final de tu código es la que finaliza la función.

Presta atención a las operaciones matemáticas

El número que se encuentra a mitad de camino entre un mínimo y un máximo, ¿Cómo se calcula? Desde luego así no:

int mitad = (Cini-Cfin)/2;

¿Cual es el problema? Que si Cfin es mayor que Cini, el resultado va a ser negativo y dificilmente va a encontrarse en el punto medio entre los dos números... Tienes que intercambiar los dos valores:

int mitad = (Cfin-Cini)/2;

Y aun así seguirá sin estar bien. ¿Por qué? Veamos:

Cini = 0, Cfin = 10 => (10-0)/2 = 5 -> OK
Cini = 5, Cfin = 10 => (10-5)/2 = 2 -> ¿en serio?

Con lo que llevas hecho hasta ahora estás calculando el punto medio asumiendo que Cini es 0, pero cuando no es así el resultado de la operación no va a ser correcto.

Para que el resultado sea correcto tienes que volver a sumar Cini:

int mitad = Cini + (Cfin-Cini)/2;

La función no retorna nada

Este error es sencillo de ver. La función está declarada así:

int* MaxMin(int *A, const int Cini, const int Cfin) {

Es decir, de ella se espera que devuelva un puntero de tipo int... pero carece de return, luego es imposible que devuelva algo.

Bien, ¿y qué devolvemos aquí?

Viendo el pseudocódigo no existe ninguna razón para que la función devuelva un puntero. Únicamente tiene que devolver dos valores: máximo y mínimo y para esto hay una clase que cumple a la perfección y es std::pair. Peeeero no es mi intención resolver todo tu ejercicio por varias razones:

1. No te has molestado en compilar el ejercicio 1.1. Si lo has compilado no te has molestado en leer los mensajes de error 1.2. Si los has leido, no te has molestado en entenderlos (y mira que son sencillos)
2. En tu pregunta no das detalles acerca de qué es lo que le ocurre a tu programa (y no, "creo que no está bien" no es algo significativo)
3. Son deberes de clase y la única forma de aprender es pegarse con el código

Y no voy a hablar acerca de tu comentario "gracias por tu amabilidad (ironia)... vaya forma de hablar" porque de eso también podría sacar sustancia como para rellenar el equivalente a esta respuesta. Si llegas nuevo a un sitio lo primero que tienes que hacer es entender cómo funciona y qué normas tiene. [es.so] es un sitio que te puede ayudar muchísimo pero requiere el esfuerzo por parte de todos... no olvides que no te estamos cobrando un duro por ayudarte, así que antes de criticar a los demás mira a ver si es que estás haciendo algo mal.

Answer 2

Dado que estás programando en C++, usa el lenguaje para simplificar tu código.

---

El algoritmo de divide y vencerás funciona sobre rangos de valores, así que alimenta tu función con iteradores; a priori no te importa qué tipo de iteradores sean¹ mientras puedas iterar con ellos, así que usemos una plantilla para expresarlo:

template<typename ITERATOR>
auto MinMax(ITERATOR begin, ITERATOR end);

La función MinMax devolverá el valor mínimo y máximo entre los iteradores proveídos, su tipo retorno es deducido según el contenido de la misma, siguiendo (no del todo) tu pseudocódigo la función es sencillamente esto:

template<typename ITERATOR>
auto MinMax(ITERATOR begin, ITERATOR end)
{
    if (auto distance = std::distance(begin, end); distance <= 1)
    {
        return std::tuple{std::min(*begin, *end), std::max(*begin, *end)};
    }
    else
    {
        auto half = distance / 2;
        auto [min_l, max_l] = MinMax(begin, begin + half);
        auto [min_r, max_r] = MinMax(begin + half + 1, end);
        return std::tuple{std::min(min_l, min_r), std::max(max_l, max_r)};
    }
}

La instrucción Si Cini<Cfin-1 puede interpretarse como "si la distancia entre el iterador de inicio y el iterador de final es menor o igual a 1" ya que para que el índice de inicio sea menor al anterior al índice de final, el índice final debe estar a una distancia de 1 del índice de inicio o ser el índice de inicio y eso es lo que hace la condición de la función:

/*                                                                La separación entre begin
                                                                  y end es de 1 o 0
                                               vvvvvvvvvvvvv <--- elementos */
if (auto distance = std::distance(begin, end); distance <= 1)
//                  ~~~~~~~~~~~~~~~~~~~~~~~~~ <--- Distancia entre begin y end

Si se cumple que no podemos dividir más, entonces nos quedamos con el mínimo y el máximo de los iteradores en esta instrucción:

return std::tuple{std::min(*begin, *end), std::max(*begin, *end)};

La instrucción anterior construye una tupla² deduciendo los tipos de sus elementos⁴ la cuál es usada para que la función deduzca su tipo de retorno³.

Si podemos dividir más, hacemos la llamada recursiva dividiendo el alcance de nuestros iteradores:

auto half = distance / 2;
auto [min_l, max_l] = MinMax(begin, begin + half);
auto [min_r, max_r] = MinMax(begin + half + 1, end);
return std::tuple{std::min(min_l, min_r), std::max(max_l, max_r)};

Usamos el enlazado estructurado⁴ para capturar el mínimo y máximo de la parte izquierda de la división del espacio de los iteradores y la parte derecha del mismo, usando el mismo tipo de retorno que en la otra rama de la condición, para permitir la deducción del tipo de retorno.

De esta manera, la función MinMax acepta contenedores arbitrarios y somete su contenido al algoritmo divide y vencerás para hallar el mínimo y máximo de valores arbitrarios:

unsigned u[]{0,1,2,3,4,5,6,7,8, ... ,36,37,38,39,40};
MinMax(std::begin(u), std::end(u) - 1);

std::vector<double> d{387461298.3,76.340, ... ,6.90,3.6,3.4,63.4,98.7};
MinMax(std::begin(d), std::end(d) - 1);

std::string panagrama{"Benjamin pidio una bebida de kiwi y fresa. Noe, sin verguenza, la mas exquisita champanya del menu."};
MinMax(std::begin(panagrama), std::end(panagrama) - 1);

Puedes ver el código funcionando en Wandbox 三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ.

---

1. Debería ser un iterador de acceso aleatorio, pero sin la librería de conceptos, complicaríamos el código.
2. C++11.
3. C++14.
4. C++17.