Archivo de la Categoría 'Programación en Lenguajes Estructurados'

Búsqueda Binaria

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
Proceso busqueda_binaria
 
Escribir ""	
Escribir "Introduzca n:"
Leer n
Dimension v(n)
 
Escribir ""
Para i <- 1 Hasta n Hacer
	Escribir i, ":"
	Leer v(i)
FinPara
 
Escribir ""
Escribir "Introduzca valor a buscar:"
Leer valor
 
inicio <- 1
fin <- n
valor_encontrado <- Falso
Mientras ( inicio <= fin ) y ( no valor_encontrado ) Hacer
	centro <- (inicio + fin) / 2
	Si v(centro) = valor 
	Entonces valor_encontrado <- Verdadero
	Sino Si v(centro) < valor 
	       Entonces inicio <- centro + 1
	       Sino fin <- centro -1
	       FinSi
	FinSi
FinMientras
 
Si valor_encontrado = Falso
Entonces Escribir "El valor ", valor, " no se ha localizado en el vector."
Sino Escribir "El valor ", valor, " ocupa la posicion ", centro, " en el vector."
FinSi
 
FinProceso

Búsqueda Secuencial en un vector ordenado

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Proceso busqueda_secuencial_vector_ordenado
 
Escribir ""
Escribir "Introduzca valor a buscar:"
Leer valor
 
i <- 1
valor_encontrado <- 0
Mientras (i <= n) y (valor_encontrado = 0) y ( v(i) <= valor ) Hacer
	Si v(i) = valor Entonces
		valor_encontrado <- 1
	Sino
		i <- i + 1
	FinSi
FinMientras
 
Escribir ""
Segun valor_encontrado Hacer
	0: Escribir "El valor ", valor, " no se ha localizado en el vector."
	1: Escribir "El valor ", valor, " ocupa la posicion ", i, " en el vector."
FinSegun
Escribir ""	
 
FinProceso

Búsqueda Secuencial en un vector desordenado

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Proceso busqueda_secuencial
 
Escribir ""	
Escribir "Introduzca n:"
Leer n
Dimension v(n)
 
Escribir ""
Para i <- 1 Hasta n Hacer
	v(i) <- azar(10) + 1
	Escribir i, ": ", v(i)
FinPara
 
Escribir ""
Escribir "Introduzca valor a buscar:"
Leer valor
 
i <- 1
valor_encontrado <- 0
Mientras (i <= n) y (valor_encontrado = 0) Hacer
	Si v(i) = valor Entonces
		valor_encontrado <- 1
	Sino
		i <- i + 1
	FinSi
FinMientras
 
Escribir ""
Segun valor_encontrado Hacer
	0: Escribir "El valor ", valor, " no se ha localizado en el vector."
	1: Escribir "El valor ", valor, " ocupa la posicion ", i, " en el vector."
FinSegun
Escribir ""
 
FinProceso

Elementos duplicados en un vector

Supongamos un vector desordenado, v, de n números naturales potencialmente repetidos. Vamos a desarrollar un algoritmo que reemplace cada número repetido por -1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
Proceso marcar_repetidos_vector
// Hipótesis: n es mayor o igual a 2
 
Escribir ""
Escribir "Introduzca n:"
Leer n
Dimension v(n)
 
Escribir ""
Escribir "Vector inicial:"
Para i <- 1 Hasta n Hacer
     v(i) <- azar(10) + 1
     Escribir "     ", v(i)
FinPara
 
modificaciones <- 0
Para i <- 1 Hasta n-1 Hacer		
    Si v(i) <> -1 Entonces 
          Para j <- i+1 Hasta n Hacer
                Si v(i)=v(j) Entonces 
                         v(j) <- -1
                         modificaciones <- modificaciones + 1
	FinSi
          FinPara
     FinSi
FinPara
 
Escribir ""
Escribir "Vector final:"
Para i <- 1 Hasta n Hacer
     Escribir "     ", v(i)
FinPara
Escribir ""
Escribir "Modificaciones: ", modificaciones
Escribir ""
 
FinProceso

Criba de Eratóstenes

La Criba de Eratóstenes es una técnica para generar todos los números primos menores que un número natural, N, dado:

  • Se comienza escribiendo el 2 (el número 1 no es primo) y los números impares entre 3 y N.
  • Se toma el número 3 y se borran sus múltiplos.
  • Se toma el número 5 y se borran sus múltiplos.
  • Y así sucesivamente, hasta que nos topemos con un número impar mayor o igual a sqrt{N}, momento en que detendremos el proceso de borrado.

Sea, por ejemplo, N=100. Vamos a seguir los pasos citados:

  • Escribimos el número 2 y los números impares entre 3 y 100:

      2 3   5   7   9  
    11   13   15   17   19  
    21   23   25   27   29  
    31   33   35   37   39  
    41   43   45   47   49  
    51   53   55   57   59  
    61   63   65   67   69  
    71   73   75   77   79  
    81   83   85   87   89  
    91   93   95   97   99  

  • Borramos los múltiplos de 3:

      2 3   5   7      
    11   13       17   19  
        23   25       29  
    31       35   37      
    41   43       47   49  
        53   55       59  
    61       65   67      
    71   73       77   79  
        83   85       89  
    91       95   97      

  • Borramos los múltiplos de 5:

      2 3   5   7      
    11   13       17   19  
        23           29  
    31           37      
    41   43       47   49  
        53           59  
    61           67      
    71   73       77   79  
        83           89  
    91           97      

  • Borramos los múltiplos de 7:

      2 3   5   7      
    11   13       17   19  
        23           29  
    31           37      
    41   43       47      
        53           59  
    61           67      
    71   73           79  
        83           89  
                97      

  • Borramos los múltiplos de 9:

      2 3   5   7      
    11   13       17   19  
        23           29  
    31           37      
    41   43       47      
        53           59  
    61           67      
    71   73           79  
        83           89  
                97      

  • Como 11>sqrt{100}=10 detenemos el proceso de borrado.

La implementación del ejemplo en pseudocódigo sería:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
Proceso criba_eratostenes_100
 
	Dimension primo(100)
 
	primo(1) <- Falso
            primo(2) <- Verdadero		
	Para i <- 3 Hasta 100 Hacer
		primo(i) <- ( i mod 2 <> 0 )
	FinPara
 
	// Borrado de los múltiplos de 3
	// Primer número a borrar: 9
	// Paso: 3
	Para i <- 9 Hasta 100 Con Paso 3 Hacer		
		primo(i) <- Falso
	FinPara
 
	// Borrado de los múltiplos de 5
	// Primer número a borrar: 15
	// Paso: 5
	Para i <- 15 Hasta 100 Con Paso 5 Hacer
		primo(i) <- Falso
	FinPara
 
	// Borrado de los múltiplos de 7
	// Primer número a borrar: 21
	// Paso: 7
	Para i <- 21 Hasta 100 Con Paso 7 Hacer		
		primo(i) <- Falso
	FinPara
 
	// Borrado de los múltiplos de 9
	// Primer número a borrar: 27
	// Paso: 9
	Para i <- 27 Hasta 100 Con Paso 9 Hacer		
		primo(i) <- Falso
	FinPara
 
	// Lista de primos entre 1 y 100
             Escribir ""
	Escribir "Primos entre 1 y 100:"
	Para i <- 1 Hasta 100 Hacer		
		Si primo(i) = Verdadero Entonces
			Escribir "   ", i
		FinSi
	FinPara
             Escribir ""
 
FinProceso

Generalizando a N el pseudocódigo anterior tendríamos:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Proceso criba_eratostenes_N
 
             Escribir ""
	Escribir "Por favor, introduzca N:"
	Leer N	 
	Dimension primo(N)
 
	primo(1) <- Falso
	primo(2) <- Verdadero		
	Para i <- 3 Hasta N Hacer
		primo(i) <- ( i mod 2 <> 0 )
	FinPara
 
	Para i <- 3 Hasta RC(N) Hacer
		Para j <- (i*2) Hasta N Con Paso i Hacer
			primo(j) <- Falso; // Borrado del número j
		FinPara
	FinPara
 
	// Listamos los primos entre 1 y N
	Escribir ""
	Escribir "Primos entre 1 y ", N, ":"
	Para i <- 1 Hasta N Hacer		
		Si primo(i) = Verdadero Entonces
			Escribir "   ", i
		FinSi
	FinPara
	Escribir ""
 
FinProceso

Ordenación por Intercambio Directo (burbuja)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Proceso ordenacion_intercambio
 
	// Solución válida para vectores de dos o más elementos
 
	Escribir ""
	Escribir "Longitud del vector: "
	Leer n
	Dimension v(n)
 
	Para i <- 1 Hasta n Hacer
		v(i) <- azar(100) + 1
	FinPara
 
	Para i <- n Hasta 2 Con Paso -1 Hacer
		Para j <- 1 Hasta i-1 Hacer
			Si v(j) > v(j+1) Entonces
				aux <- v(j)
				v(j) <- v(j+1)
				v(j+1) <- aux
			FinSi
		FinPara
	FinPara
 
	Escribir ""
	Escribir "Resultado:"
	Para i <- 1 Hasta n Hacer
		Escribir v(i)
	FinPara
 
FinProceso

Ordenación por Selección Directa

Proceso ordenacion_seleccion
 
     // (c) ciclos-informatica.com
     // Entrada: Vector de enteros
     // Salida: Vector en orden creciente
     // Método de ordenación: Selección Directa
 
     // Línea en blanco
     Escribir ""
 
     // Declaración automática del vector
     n <- azar(9)+2; // Longitud entre 2 y 10
     Dimension v(n)
 
     // Carga automática del vector
     Para i<-1 Hasta n Hacer
             v(i) <- azar(1000)+1; // Valor entre 1 y 1000
     FinPara
 
     // Visualización del vector desordenado
     Escribir "Vector inicial (desordenado):"
     Para i<-1 Hasta n Hacer
	Escribir "     ",v(i)
     FinPara
     Escribir ""
 
     // Ordenación del vector por el método de selección
     Para i<-1 Hasta n-1 Hacer
	posMenor <- i
	Para j<-i+1 Hasta n Hacer
              	     Si v(j)<v(posMenor) Entonces
	             posMenor <-j
	     FinSi
	FinPara
                // Intercambio de v(i) y v(posMenor)
	aux <- v(i)
	v(i) <- v(posMenor)
	v(posMenor) <- aux
     FinPara
 
     // Visualización del vector ordenado
     Escribir "Vector final (ordenado):"
     Para i<-1 Hasta n Hacer
               Escribir "     ",v(i)
     FinPara
     Escribir ""
 
FinProceso

Soluciones a varios problemas de pseudocódigo

Aquí tenéis las soluciones a varios problemas pendientes: