Clase 11

Temas: Sesión de práctica

Ejercicio de clase

Descripción

La descripción completa del problema se encuentra aquí. El problema consiste en que dado un número N de listas de números enteros positivos de tamaño 10 decir si, la lista se encuentra ordenada o no.

Entrada

La primer linea contien un número entero positivo N, donde 0 < N < 20, que indica el número de casos a procesar. Luego siguen N lineas, una por cada caso.

Cada linea contiene 10 enteros positivos menores a 100.

Salida

La salida inicia con la frase Lumberjacks: seguida de una linea por caso con la respuesta. La palabra Ordered si la lista está ordenada o la palabra Unordered si la lista está desordenada.

Ejemplo de entrada:

4
13 25 39 40 55 62 68 77 88 95
88 62 77 20 40 10 99 56 45 36
91 78 61 59 54 49 43 33 26 18
10 10 10 10 10 10 10 10 10 10

Ejemplo de salida

Lumberjacks:
Ordered
Unordered
Ordered
Ordered

Solución

La solución implementada se basa en una premisa, la lista está ordenada hasta que se demuestre lo contrario.

Así, recorremos la lista en búsqueda de un par de número consecutivos que nos digan si está ordenada o no. Veamos el código.

#include <iostream>
using namespace std;

int main() {
    int N;
    int beards[10];

    cin >> N;
    cout << "Lumberjacks:\n";
    
    while(N--) {

        for (int i = 0; i < 10; i++) {
            cin >> beards[i];
        }
        
        // La lista esta ordenada ascendentemente 
        // hasta que se demuestre lo contrario
        bool sorted_asc = true;
        // La lista esta ordenada descendentemente
        // hasta que se demuestre lo contrario
        bool sorted_desc = true;
        
        // Recorremos la lista iniciando desde 1 
        // y comparamos la posición actual con la anterior
        for (int i = 1; i < 10; i++) {
            if (beards[i-1] > beards[i]){
                // Si la posición anterior es mayor a la actual
                // entonces no están ordenados ascendentemente
                sorted_asc = false;
            } else if (beards[i-1] < beards[i]){
                // Si la posición anterior es menor que la actual
                // entonces no estan ordenados descendentemente
                sorted_desc = false;
            }
        }
        
        // Si al terminar de comparar cada par de elementos consecutivos
        // alguna variable quedó en True indica que toda la lista estaba
        // ordenada ya sea ascendentemente o descendentemente
        // o que todos los elementos son iguales (por tanto también está ordenada)
        if (sorted_desc || sorted_asc) {
            cout << "Ordered\n";
        } else {
            cout << "Unordered\n";
        }
    }

    return 0;
}

Tarea

Resolver el problema sin usar un array de 10 elementos para almacenar la lista de números.

Tip: Solo necesitas dos variables enteras.