Problemas Propuestos en C

Problema 1

Sea V un vector de n coordenadas y k un natural menor o igual que n. Escribir un programa que: A- Ingrese los valores de las variables k y n, los elementos de V y el orden en que éstos aparecen en el vector. B- Ordene los elementos de V en un nuevo vector W de manera que: W(k) > W(j) si j <k W(k) < W(j) si j >k

Problema 2

Una palabra es anagrama de otra cuando se obtiene una de la otra por permutación de sus letras. Por ejemplo: pote es anagrama de tope saco es anagrama de cosa y de ocas porta es anagrama de topar, de tropa y de parto Escribir un programa que: dado un diccionario castellano pueda determinar los conjuntos de anagramas. Por ejemplo: Si en el diccionario sólo tuviésemos las palabras: cava empresa pote torta tope trota vaca los conjuntos de anagramas serían: cava - vaca empresa pote - tope torta - trota Comentario: La palabra INSTITUCIONALIZACIÓN tiene 20 letras, por lo tanto hay 19!/3 permutaciones posibles. Si suponemos que "procesar" cada permutación tarda 1 segundo, nos llevaría más de 10 años "procesarlas" todas. Entonces, hay que buscar con cuidado una solución. Es importante, además, tener en cuenta que un diccionario castellano tiene aproximadamente 75000 palabras.

Problema 3

Para un palabra dada encontrar todos sus anagramas.

Problema4

Dado un conjunto de N números cualesquiera, un número T y un entero K, cuán rápido puede Ud. determinar si existe un subconjunto de K elementos cuya suma es, a lo sumo, T?

Problema 5

Dado un vector V de N (N > 1) componentes y un entero positivo M < N V = [a(1),a(2),...,a(M),a(M+1),...,a(N)] escribir un programa que lo lleve a la forma: W = [a(M+1),a(M+2),...,a(N),a(1),...,a(M)] o sea, si consideramos: A = [a(1),a(2),...,a(M)] B = [a(M+1),a(M+2),...,a(N)] podemos pensar que se trata de llevar el vector V = AB a la forma W = BA Nota: Ningún otro vector adicional podrá usarse y deberá hacerse la menor cantidad de reordenamientos de los elementos de V. Llamamos "reordenamiento" a cada sentencia en la que se han intercambiado dos elementos de V.

Problema 6

Con la notación del problema anterior, escribir un programa que a un vector V = ABC lo lleve a la forma W = CBA

Problema7

Sea P(x) = -x4 - x3 + 1, observemos que: P(-1) = -1 + 1 + 1 = 1 > 0 P(1) = -1 - 1 + 1 = -1 < 0 los matemáticos, mediante el llamado "Teorema del Valor Intermedio" han probado que entre -1 y 1 debe existir una raíz de P, o sea, un número c tal que P(c) = 0. Escribir un programa de manera de determinar c con un error menor que 10-2. Comentario: El teorema a que hacemos referencia vale en un contexto más general, pues afirma que: si f:[a,b] --> R es una función continua y f(a) < f(b) o bien f(a) > f(b), dado cualquier valor d entre f(a) y f(b), existe c entre a y b tal que f(c) = d

Problema 8 (Los puentes de Konisberg)

Por la ciudad de Konisberg pasa un río en el que se encuentran dos islas, A y B, conectadas por un puente. En la isla A hay dos puentes que la unen con la margen izquierda y dos que la unen con la derecha. En la isla B hay un sólo puente que la une con la margen izquierda y uno sólo con la margen derecha. Quedan en total 7 puentes. El problema consiste en determinar si se puede dar un paseo caminando de manera de pasar por cada puente exactamente una vez.

Problema9

Para un número positivo a distinto de 1 y para un número b positivo cualquiera se define el "logaritmo en base a de b" (loga(b)) mediante la relación siguiente: loga(b) = x si y sólo si ax = b La importancia del logaritmo radica en las siguientes propiedades: loga(b.c) = loga(b) + loga(c) para b > 0 y c > 0 loga(bc) = c.loga(b) para b > 0 loga(b/c) = loga(b) - loga(c) para b > 0 y c > 0 Escribir un programa que permita el ingreso de un número natural n y encuentre el mayor entero menor o igual que log2(n). (Ayuda: Si 1 < b < 2 entonces 0 < log2(b) < 1 Para n > 1, log2(n) = 1 + log2(n/2))

Problema 10

Los Laboratorios Bell de E.E.U.U. encargaron a Michael Lesk desarrollar un sistema para ubicar telefónicamente a las personas que estaban vinculadas con ellos. Lo que se hizo fue lo siguiente: Como en el teléfono se tienen los números 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 y los símbolos * y #, se puede asignar a cada uno las letras del alfabeto de la siguiente manera: 2 ---------- A, B, C 3 ---------- D, E, F 4 ---------- G, H, I 5 ---------- J, K, L 6 ---------- M, N, Ñ, O 7 ---------- P, Q, R, S 8 ---------- T, U, V 9 ---------- W, X, Y, Z reservando el 0 para llamar a la operadora. Para llamar a Gómez, Juan se debe marcar el código: 4 6 6 3 9 * 5 * (El símbolo * denota que ha terminado el apellido y lo que sigue indica la inicial del nombre)

Construcciones algorítmicas

En C existen estas construcciones para implementar algoritmos:

• Sentencias simples y sentencias compuestas (con las llaves).
• Construcciones condicionales:

if ( expresión) sentencia [ else sentencia ]

switch ( expresión) { caso1 caso2 ... casoN }

• Construcciones iterativas:

while ( expresión) sentencia

do sentencia while ( expresión);

for ( expresión; expresión; expresión ) sentencia

• Instrucciones de control de flujo: break, continue y goto.

• Subprogramas: funciones.

4.1 Sentencias (statements)

Una sentencia es un fragmento de código.

Una sentencia simple es una expresión terminada en punto y coma.

Una sentencia compuesta es una serie de sentencias entre llaves.

         sentencia_simple;

// sentencia compuesta: varias sentencias entre llaves.

         {

                 sentencia

                  sentencia

                  ...

         }

Ejemplos:

/* sentencia simple */

x = y * 5 + sqrt(z);

         /* sentencia compuesta con llaves */

{

         a = b;

         b = x + 1;

         printf ( “hay %d productos”, num_prod );

}

         /* sentencias compuestas dentro de otras */

{

         { x=1; y=2; }

         { z=0; printf(“hola\n”); }

}

4.2 Sentencia if

La construcción if sirve para ejecutar código sólo si una condición es cierta:

if  ( condición )

    sentencia

La condición es una expresión de cualquier clase.

• Si el resultado de la expresión es CERO,
  se considera una condición FALSA.
• Si el resultado de la expresión NO ES CERO,
  se considera una condición CIERTA.

Ejemplo:

int x = 1;

main()

{

  if ( x == 1 ) 

         printf (“la variable x vale uno\n”);

  if ( x>=2 && x<=10 )

         printf (“x está entre 2 y 10\n”);

}

4.3 Construcción else

Con la construcción else se pueden definir acciones para cuando la condición del if sea falsa.

La sintaxis es

if ( condición )

    sentencia

else

    sentencia

Ejemplo:

if ( x==1 )

         printf (“la variable x vale uno\n”);

else

         printf (“x es distinta de uno\n”);

4.4 Bucle while

Para ejecutar el mismo código varias veces, se puede utilizar:

while ( condición )

         sentencia

La sentencia se ejecuta una y otra vez mientras la condición sea cierta.

Ejemplos:

main()

{

         int x=1;

         while ( x < 100 )

         {

                 printf(“Línea número %d\n”,x);

                 x++;

         }

}

Ejemplo usando el operador de predecremento:

main()

{

         int x=10;

         while ( --x )

         {

                 printf(“una línea\n”);

         }

}

En cada iteración se decrementa la variable x y se comprueba el valor devuelto por --x. Cuando esta expresión devuelva un cero, se abandonará el bucle. Esto ocurre después de la iteración en la que x vale uno.

4.5 Bucle for

También se pueden ejecutar bucles con for, según esta sintaxis:

         for ( expresión_inicial; condición; expresión_de_paso )

            sentencia

La expresión_inicial se ejecuta antes de entrar en el bucle.

Si la condición es cierta, se ejecuta sentencia y después expresión_de_paso.

Luego se vuelve a evaluar la condición, y así se ejecuta la sentencia una y otra vez hasta que la condición sea falsa.

El bucle for es (casi) equivalente a

         expresión_inicial;

         while ( condición )

         {

             sentencia

             expresión_de_paso;

         }

Ejemplo típico de uso:

int i;

...

for ( i=0; i<10; i++ )

    printf (“%d “, i );

4.6 Bucle for: omisión de expresiones

Las tres expresiones del bucle for se pueden omitir, con el siguiente resultado.

Se omite	Resultado
expresión_inicial	no se hace nada antes del bucle
condición	la condición es siempre cierta (1)
expresión_de_paso	no se hace nada tras cada iteración

Ejemplos:

for ( ; resultado!=-1 ; ) { ... }

for ( ; ; ) { /* Bucle infinito */ }

4.7 Bucle do...while

Parecido al bucle while, pero iterando al menos una vez.

Sintaxis:

do {

    sentencia

} while ( condición );

La sentencia se ejecuta al menos la primera vez; luego, mientras la condición sea cierta, se itera la sentencia.

Se recomienda no utilizar esta construcción, porque las construcciones while y for bastan para diseñar cualquier clase de bucles. Muy pocos programas hoy día usan esta construccíón.

4.8 Control de bucles: break y continue

break y continue permiten controlar la ejecución de bucles while, for y do...while

Se puede salir de un bucle directamente con break.

continue va directamente al final del bucle y emprende una nueva iteración.

while (...)

{

  ...

  ...

   break;

  ...

}

while (...)

{

  ...

  ...

  continue;

  ...

}

4.9 Instrucción goto

Sirve para saltar incondicionalmente a un punto cualquiera del programa. La sintaxis es

goto etiqueta;

etiqueta es un identificador que indica el punto al que queremos saltar. La etiqueta se define colocándola en el punto adecuado seguida de dos puntos.

Sólo se puede saltar a una etiqueta que se encuentre en la misma función donde se invoca a goto.

Ejemplo:

parriba:         // declaración de etiqueta

         ...

         // salto directo a una etiqueta

         if (error) goto pabajo;

         ...

         if (repetir) goto parriba;

pabajo:          // declaración de etiqueta

4.10 Construcción switch

Se utiliza para ejecutar acciones diferentes según el valor de una expresión.

Ejemplo de sintaxis:

switch ( expresión )

{

         case valor1:

           ... sentenciasA...

         break;

         case valor2:

           ... sentenciasB ...

         break;

         case valor3:

         case valor4:

           ... sentenciasC ...

         break;

         default:

           ... sentenciasD ...

}

Las sentenciasA se ejecutarán si expresión adquiere el valor1.

Las sentenciasB se ejecutarán si adquiere el valor2.

Las sentenciasC se ejecutarán si adquiere el valor3 o el valor4, indistintamente.

Cualquier otro valor de expresión conduce a la ejecución de las sentenciasD; eso viene indicado por la palabra reservada default.

Ejemplo de switch:

int opcion;

printf ( "Escriba 1 si desea continuar; 2 si desea terminar: " );

scanf ( "%d", &opcion );

   switch ( opcion )

   {

            case 1:

                 printf ("Vale, continúo\n");

              break;

            case 2:

                 salir = 1;

              break;

            default:

                    printf ("opción no reconocida\n");

   }

4.11 Precauciones con if y bucles

Asignaciones en los if y los bucles

Hemos visto que una asignación es una expresión. Por ello se puede colocar dentro de cualquier construcción if, while o similar:

         if ( variable = valor ) { ... }

Este uso muchas veces es erróneo, porque casi siempre pretendemos escribir:

         if ( variable == valor ) { ... }

Pero como es correcto, el compilador no abortará si se encuentra estas construcciones (de todas formas, muchos compiladores emiten una advertencia si encuentran asignaciones dentro de ifs).

Bucles for

Aunque el C lo permite, es conveniente no modificar la variable contadora dentro del bucle.