Instituto de Computación
Curso de Programación 1 - Soluciones comentadas

1.  Eficiencia

Entre las buenas prácticas de programación, se menciona que los algoritmos sean "razonablemente eficientes".

Un punto importante a tener en cuenta, en este sentido, es la correcta elección de la estructura de iteración apropiada para cada problema.

La eficiencia tiene que ver con la cantidad de operaciones que se realizan en una solución. Una solución que, aún siendo correcta desde el punto de vista del resultado, realice operaciones "de más" no se considera "razonablemente eficiente"

En las secciones siguientes se ejemplifican estos conceptos.

1.1  Selección apropiada de las estructuras de iteración

Considere el siguiente ejercicio:

     CONST N = . . .;
     . . .
     TYPE
             CadenaN = ARRAY[1..N] of Char;

    FUNCTION pertenece(c : Char; cadN : CadenaN) : Boolean;

Una solución común pero INCORRECTA para este ejercicio es la siguiente:

function pertenece(c : Char; cadN : CadenaN) : Boolean;
(* SOLUCIÓN INCORRECTA*)

var i : Integer;
    encontre : Boolean;

begin

   encontre := FALSE;

   for i := 1 to N do
    if cadN[i] = c then
      encontre := TRUE;

   pertenece := encontre

end;

Esta solución, en donde se utiliza la estructura de iteración for para recorrer de forma completa el arreglo, es ineficiente. Este error es considerado grave en una evaluación.

La iteración que debe realizarse es una búsqueda, una vez que se encuentra el elemento c en cadN la iteración debe terminar. Lo correcto es utilizar una estructura de iteración CONDICIONAL, es decir, while o repeat.

Dado que asumimos evaluación por circuito corto, podemos utilizar while y diseñar una solución compacta que realice la comparación del carácter c con los elementos del arreglo en la misma condición de iteración:

function pertenece(c : Char; cadN : CadenaN) : Boolean;

var i : Integer;

begin

   i := 1;

   while (i <= N) and (cadN[i] <> c) do (* itero mientras no encuentre c *)
      i := i+1;

   pertenece := i <= N  (* si se cumple i <= N , encontré c *)

end;

1.2  Número de operaciones

Veamos los siguientes ejemplos:

Observe que el uso de la función sqrt en la definición de EsPrimo tiene el efecto de disminuir el número de operaciones ejecutadas:

function EsPrimo(numero: integer): boolean;
var
  i,tope: integer;

  function divide(n,m: integer): boolean;
  begin
    divide := m mod n = 0;
  end;

begin
  i := 2;
  tope := trunc(sqrt(numero));
  while (i<=tope) and not divide(i,numero) do
      i := i+1;

  EsPrimo := i > tope;
end;

Sea el ejercicio 1 del segundo parcial de 2005:

Escribir un programa que lea de la entrada un número n entero mayor o igual que 0 y un número x real distinto de 0, y despliegue el valor de la siguiente suma:

El programa sólo puede hacer sumas, multiplicaciones y divisiones. La cantidad de multiplicaciones no puede ser mayor que el doble de N y la cantidad de divisiones no puede ser mayor que N. No se pueden utilizar subprogramas auxiliares ni invocar subprogramas predefinidos salvo los de entrada y salida.

se pide calcular una sumatoria, exigiendo:

• "La cantidad de multiplicaciones no puede ser mayor que el doble de N y la cantidad de divisiones no puede ser mayor que N".

A continuación se muestran dos soluciones que no respetan esa exigencia pedida en la letra, lo cual es un error grave (se señalan otros errors también):

  program Suma(input,output);
 (* SOLUCIÓN INCORRECTA*)
  var
     n,j,z,i:Integer;          (* los nombres de las variables no son adecuados *)
     x,k: Real;     

 begin 
     readln (n,x);
     for j := 2 to n do
        begin
           z := j;
           repeat
              z := z * (z-1)
           until ((z-1) = 1)            (* hace más de 2*n multiplicaciones *)
           k := x;
           i := j;
           repeat 
              k := k * x;
              i := i-1
           until (i = 0)                 (* hace más de 2*n multiplicaciones *)
           x := x + (k DIV z)            (* usa DIV *)
     end;
     writeln (x);
end.

Otra forma de hacer más de 2 * n multiplicaciones:

(* SOLUCIÓN INCORRECTA*)
var x, termino,suma:Real;
    j,i,n,z: Integer;
begin
    read (n,x);
    suma := 1;
    termino := 1;
    z := 1;
    for  i := 1 to n do
      begin
         for j := 1 to i do
           z := z*i;                  (* hace más de 2 * n multiplicaciones *)                                
         termino := (termino * x) / z    
         z := 1;
         suma := suma + termino;
      end;
      writeln (suma);
end.  

Solución correcta:

program Suma(input,output);
var x, potencia, suma: real;
     i, n, factorial: integer;
begin
    readLn(n); readLn(x);
    factorial:= 1;  
    potencia:= 1;
    suma:= 1;
    for i:= 1 to n do
       begin
           potencia:= potencia * x;
           factorial:= factorial * i;
           suma:= suma + potencia / factorial;
       end;
    writeLn(suma);
end.

Sea el ejercicio 1 del examen de julio 2006:

 function amigables(m,n: integer): boolean;

1.3  Búsquedas en arreglos teniendo en cuenta propiedades de los elementos

A veces, la búsqueda de un elemento en un arreglo puede hacerse más eficientemente considerando propiedades del elemento que se busca. En general, realizar la búsqueda ignorando dicha propiedad se considera error leve o medio (salvo que se pida expresamente en la letra, en cuyo caso, sería error grave).

Sea el ejercicio 1 del examen de julio 2007:

Estuds_por_digito = ARRAY [0 .. 9] OF Integer;

Observar que lo que está en negrita indica propiedades del elemento que pueden usarse para hacer una búsqueda más eficiente, tal como está planteado en la solución propuesta:

FUNCTION May_dig_par(estudiantes:Estuds_por_digito; valor:Integer) : Integer;

VAR indice : Integer;

BEGIN

    (* inicializo el indice con el mayor digito par posible *)

    indice := 8;


    (* busco una celda del arreglo que cumpla la condicion, 
      empezando por el mayor indice, decrementando de a dos 
      para mirar solo los pares 
     *)

    WHILE (indice >= 0) AND (estudiantes[indice] >= valor) DO
        indice := indice - 2;


    (* retorno resultado *)

    IF indice >= 0 THEN
        May_dig_par := indice	
    ELSE
        May_dig_par := -1

END;

¿Cómo sería una búsqueda ineficiente?

1.4  Arreglos: Recorridas múltiples, copias innecesarias, etc.

Es importante NO ABUSAR del uso de arreglos. Por ejemplo, usar un arreglo auxiliar para guardar datos de la entrada y después operar con ellos, cuando se pueden realizar las operaciones a medida que se van ingresando, es un error grave. En general, el uso de MAXINT como tamaño de un arreglo se considera error grave.

Sea el ejercicio 2 del examen de julio 2006:

 type
    ArregloChar = array [1..Max] of char;

 function circular(A,B: ArregloChar): integer;

Una solución común es copiar el arreglo A a uno auxiliar, que se va transformando en todas las posibles permutaciones y comparando con B. Sin embargo, si se utiliza la información que se da en la letra sobre el índice, se ve que se puede resolver el problema sin ese arreglo auxiliar, como se plantea en la solución dada:

const Max=...;

type ArregloChar = array [1..Max] of char;


function circularIndice(indice: integer; A,B: ArregloChar) : boolean;
{ retorna true si es A es una permutación circular de B
  de índice i }
   function siguiente(i: integer): integer;
   { auxiliar que permite la recorrida circular del arreglo }
   begin
      if i < Max then
        i:= i+1
      else
        i:= 1;
      siguiente := i;
   end;
var
   k,j: integer;
begin
    k:= indice;
    j:= 1;
    while (j<=Max) and (A[j] = B[k]) do
    begin
        j:= j+1;
        k:= siguiente(k);
    end;
    circularIndice:= j > Max;
end;



function circular(A,B:ArregloChar): integer;
var
  i:integer;
begin
    i:=1;
    while (i <= Max) and not circularIndice(i,A,B) do
       i:=i+1;

    if i <= Max then 
       circular:= i
    else 
       circular:= 0;
end;

2.  Errores de rango

2.1  Salirse del rango de un arreglo

Cuando se manejan índices de un arreglo, es muy importante tener en cuenta si alguno de ellos puede referenciar una celda inválida del arreglo (fuera del rango). Por ejemplo en el ejercicio 3 del segundo parcial de 2006 se dice:

type
       ArregloNum = array [1..N] of integer;

function EntreNegativos(a: ArregloNum): integer 

Observar que, para un índice, se maneja el anterior y el posterior al mismo.

En este ejercicio el error más común es "salirse del arreglo", es decir, referenciar una celda inválida del arreglo (fuera del rango) (error grave), como se ilustra en la siguiente solución de la function EntreNegativos.

(* SOLUCIÓN INCORRECTA*)
var i, soluc:Integer;
    existe:boolean;
begin
    i := 2;
    existe := false
    while i <= N and not existe do        (* puede causar salida del rango del arreglo                      
                                             si i=N, pues en i+1 se accede a a[N+1] *)
        if (a[i] >= 0) and (a[i-1] < 0) and (a[i+1] < 0) then
            soluc := i
        else i := i+1;
    if soluc < N then entreNegativos := soluc
    else entreNegativos := N + 1;
end;

Esta solución tiene además otro error, ¿cuál?

2.1.1 Uso inadecuado de la evaluación de booleanos por circuito corto

La evaluación de booleanos por circuito corto está relacionada con el punto anterior, ya que en un and si la primera condición es falsa, no se evalúa la segunda y eso puede evitar que se referencie una celda del arreglo fuera del rango, como se ilustra en la siguiente solución del examen de febrero de 2006, en el ejercicio 1 parte a).

const 
   MaxArray = . . .; {algún valor apropiado, mayor que 1 }

type 
   RangoArray = 1..MaxArray;
   Arreglo = array [RangoArray] of Integer;

function ordenado(inf,sup: RangoArray; arr: Arreglo): boolean; 

function ordenado(inf,sup: RangoArray;  arr: Arreglo): boolean;
var
   i : integer;

begin

   i:= inf;

   while (i<sup) and (arr[i]<=arr[i+1]) do (* evaluación por circuito corto:
                                              cuando i = sup no chequeo la condición a la derecha del and *)
      i:= i+1;

   ordenado:= i = sup;

end; { ordenado }

¿Qué pasaría si la condición se pone al revés: (arr[i]<=arr[i+1]) and (i<sup) ?

2.1.2 Volver a acceder al arreglo luego de la iteración

En soluciones similares a la anterior, es frecuente exceder el rango del arreglo luego de que finaliza la iteración, por chequear la condición arr[i]<=arr[i+1] en vez de chequear i = sup al momento de asignar el resultado de la función. Se ilustra este error en el código siguiente:

function ordenado(inf,sup: RangoArray;  arr: Arreglo): boolean;
(* SOLUCIÓN INCORRECTA*)
var
   i : integer;

begin

   i:= inf;

   while (i<sup) and (arr[i]<=arr[i+1]) do
      i:= i+1;

   ordenado:= arr[i]<=arr[i+1];    (* si el arreglo está ordenado se cumple i=sup, 
                                      por lo que i+1 no es una celda válida *)

end; { ordenado }

2.2  Variables de tipo subrango

También podemos causar un error por salir de rango si le asignamos un valor no válido a una variable declarada de tipo subrango. Esto sucede a menudo si, al declarar un índice para recorrer un arreglo, le asignamos el tipo subrango correspondiente al tamaño del arreglo. Como, en general, las iteraciones sobre arreglos terminan cuando el índice sobrepasa el valor máximo del arreglo, el último incremento del índice provoca un error de rangos. Este error se ilustra en el ejemplo siguiente, donde  si i : RangoArray, cuando i = M y a[i] <> valor, se incrementa i y se produce el error de salida de rango (RangoArray = 1.. M;).  Si i : Integer, no se produce ese error.

i:= 1;

while (i <= M) and (a[i] <> valor) do
       i:= i+1;

encontrado:= i<=M

Es conveniente declarar estos índices de tipo Integer.

3.  Otros errores frecuentes

3.1  Elección incorrecta de estructuras de iteración, aunque no se afecte la eficiencia

En el siguiente ejemplo, la utilización de while en vez de for, se considera error medio.

CONST
        M = . . .;
TYPE
        RangoM = 1..M;
        MatrizMxM = ARRAY[RangoM,RangoM] OF Integer;

La siguiente solución:

procedure trasponer(var a : MatrizMxM);
(* SOLUCIÓN INCORRECTA*)
var i, j : Integer;
begin
   i := 1;
   while (i <= M) do begin
      j := 1;
      while (j <= M) do begin
         if (i <> j) then
            intercambiar(a[i, j], a[j, i]);
         j := j + 1;
      end;
      i := i + 1;
   end;
end;

tiene un error y una observación de mal estilo de programación.

El mal estilo de programación refiere a que se usa while donde debería usarse for: dado que sabemos a priori que tenemos que recorrer toda la matriz, la solución más adecuada es usar for.

El error consiste en que la condición del segundo while es incorrecta, si dejamos (j <= M) el procedimiento trasponer deja la matriz tal como está. Por ejemplo, los valores a[2,3] y a[3,2] se intercambian cuando (i = 2, j = 3), pero vuelven a intercambiarse cuando (i = 3, j = 2). ¿Qué hay que cambiar en la condición para que el algoritmo se comporte de forma correcta?

Reescriba el procedimiento usando únicamente for.

El procedimiento intercambiar es el siguiente:

procedure intercambiar(var a, b : Integer);
var aux : Integer;
begin
   aux := b;
   b := a;
   a := aux;
end;

3.2  Asignar un registro campo a campo (en vez de hacerlo con una sola asignación).

Ejemplo:

TipoElemento = RECORD
		  codigo : Integer;
		  valor	 : Integer 
	       END;	 

Conjunto = RECORD
		 elemento : ARRAY [1 .. MAXCONJ] OF TipoElemento;
		 tope	  : 0..MAXCONJ
	      END;	  

procedure AgregarElemento(elem: TipoElemento; VAR conj: Conjunto);
(* agrega un elemento a un conjunto *)
(* SOLUCIÓN INCORRECTA*)

BEGIN
   conj.tope := conj.tope+1;
   conj.elemento[conj.tope].codigo := elem.codigo; 
   conj.elemento[conj.tope].valor := elem.valor;   (*lo correcto es: conj.elemento[conj.tope] := elem*)  
END

3.3  if 's innecesarios

En muchos casos, se chequean condiciones innecesarias, lo cual, según el caso, puede ser considerado un error medio o leve.

Se ilustra en la siguiente solución del ejercicio 1 del examen de julio 2009:

const
   Max = . . . ;
type
   RangoIndice = 1..Max;
   ArregloEntero = record
         info: array [RangoIndice] of integer;
         tope: 0..Max;
   end;

function SubSecuencia(A1,A2: ArregloEntero) : boolean

function subsecuencia (A1,A2:ArregloEntero) :boolean
(* SOLUCIÓN INCORRECTA*)

var i, j:integer;
seguir:boolean;
begin
    if (A1.tope=0) or (A2.tope=0) then              (* esto es chequeado por la condición del while, 
                                                          este if innecesario se considera error *)
            subsecuencia := true

    else begin
           i:=1; j:= 1;
           while (j <= A1.tope) and (j <= A2.tope)  (* con esta condición no se chequea que las celdas 
                                                                   que quedan alcancen para que sea subsecuencia *)

               ... 

4.  Interpretación incorrecta de la letra

Leer mal la letra de los ejercicios lleva indefectiblemente a errores ya sean graves, medios o leves.

Tomemos como ejemplo el ejercicio 3 del segundo parcial de 2008:

CONST
 MAX = 20;
TYPE
 TNumero = array[1..MAX] of char;

function validarLuhn(numero : TNumero) : boolean;

1  7  3  4  2  6  7  8  9  0  4  2  3  9  5  6  7  8  9  0
  x2    x2    x2    x2    x2    x2    x2    x2    x2    x2
-----------------------------------------------------------
  14     8    12    16     0     4    18    12    16     0

Obviar la exigencia de la letra "... o alguno de los caracteres de la secuencia no corresponde a un dígito ..." induciría a un error grave: recorrer el arreglo completo con un for para ir procesando todos los elementos.

Dado que alguno de los caracteres puede no corresponder a un dígito, la solución correcta sería ir recorriendo el arreglo mientras no haya valores inválidos (no dígitos), lo cual se implementa mediante una iteración condicional. Ver solución.