PROGRAMACIÓN ESTRUCTURADA

T-1

INTRODUCCIÓN.-

El programador debe planificar un problema, depurarlo y refinarlo antes de probarlo en el ordenador. A este proceso se le llama Algoritmo (conjunto de acción que permiten al programador resolver el programa.). Una vez resuelto el problema mediante algoritmos hay que transcribirlos a un lenguaje de programación.

Software de traducción:

-Compilador. Coge toda la secuencia de acciones y comprueba que no hay errores en las

instrucciones, traduce a código máquina creando un programa ejecutable.

-Traductor. Comprueba que no hay errores léxicos en cada una de las acciones y las ejecuta

diréctamente.

ESTRUCTURA DE UN PROGRAMA.-

Estructuras Básicas:

-Secuencial.

-Composición condicional. Nos va a permitir establecer que acciones se van a ejecutar

dependiendo de una condición previa y ejecutará las instrucciones que quiera.

-Composición alternativa. Es igual pero con anidamientos.

-Composición selectiva. Permite elegir una de entre varias acciones dependiendo de una

serie de condiciones que se excluyen mutuamente.

EJEMPLO:

Según indicador:

Valor 1: Bloque de instrucciones 1

Valor 2: Bloque de instrucciones 2

.........

Valor n: Bloque de instrucciones n

Fin según.

COMPOSICIÓN ITERATIVA.-

Su función es repetir la ejecución de un bloque de acciónes un número de veces; el nº de veces que se ejecuta el bloque de acciones, puede estar determinado por una condición o bien ser un nº determinado de forma especifica.

Bucle. Es una estructura que se repite un nº de veces.

Formas de salida del bucle:

-Por condición. Existen dos composiciones iterativas por condición dependiendo que la

condición se compruebe antes o despues.

A

Repetir

Bl. Acciones

Hasta que condición

Fin repetir

B

Mientras condición hacer

Bl. Acciones

Fin mientras

-Por contador. Se le dice que repita las acciones un nº de veces.

Para variable = valor ini. Hasta valor fin.

Bl. Acciones

Fin para.

TIPOS DE DATOS.-

Especifican el dominio para donde las constantes y variables van a tomar sus valores.

El puntero es un dato que nos permite manipular la memoria del ordenador de forma dinámica.

Los operadores asociados a los tipos de datos son los siguientes:

-Numeros. +,-,*,/,^

-Cadenas. Concatenación (+).

-Lógicos. NOT, AND, OR.

Existen un conjunto de operadores llamados relacionales que se utilizan para comparar variables del mismo tipo, ya sean numéricas, carateres o cadenas, el resultado de aplicar estos operadores será siempre V/F (Verdadero o Falso): <, >, <=, =>, =, <>.

EJERCICIOS:

1)¿Que sucede en los siguientes algoritmos y con que valor terminan las variables utilizadas?

a)

Contador = 0

T = 0

Mientras contador => 0 hacer

T = T + 2

F. Mientras

Visualizar “El resultado para T es “, T,” y para contador”, Contador)

El programa nunca acabará puesto que el contador siempre será 0 y entramos en un bucle que nunca acabará.

b)

Contador = 0

T = 0

Mientras contador <= 10 hacer

T = T + 2

Contador = Contador + 1

F. Mientras

Visualizar (“El resultado para t es “, T,”y para contador”, Contador)

Visualizaríamos en la pantalla: “El resultado para t es 22 y para contador 11.

2)Efectuar un programa que nos diga el equivalente en pesetas de un nº de euros.

a)Utiliza la sentencia mientras.

Visualiza (“Introduce el valor de pesetas con respecto de los euros”)

Leer (Cambio)

Visualiza (“Introduce la cantidad de euros a cambiar”)

Leer (Cantidad)

Mientras Cantidad <> 0 hacer

Total = Cantidad * Cambio

Visualiza (Cantidad,”de euros equivalen a”, Total,”Pts.”)

Visualiza (“Introduce la cantidad de euros a cambiar”)

Leer (Cantidad)

F. Mientras

b)Utiliza la sentencia repetir.

Visualiza (“Introduce el valor de pesetas con respecto de los euros”)

Leer (Cambio)

Repetir

Visualiza (“Introduce la cantidad de euros a cambiar”)

Leer (Cantidad)

Total = Cantidad * Cambio

Visualiza (Cantidad,”de euros equivalen a”, Total,”Pts”)

Hasta que Cantidad = 0

c)Modificar el algoritmo para que a parte calcule el total de euros que se cambian.

F = 0

Visualiza (“Introduce el valor de pesetas con respecto de los euros”)

Leer (Cambio)

Visualiza (“Introduce la cantidad de euros a cambiar”)

Leer (Cantidad)

Mientras Cantidad <> 0 hacer

Total = Cantidad * Cambio

Visualiza (Cantidad,”de euros equivalen a”, Total,”Pts.”)

F = F + Cantidad

Visualiza (“Introduce la cantidad de euros a cambiar”)

Leer (Cantidad)

F. Mientras

Visualizar (“Has cambiado”, F,”euros”)

3)Realizar un algoritmo que calcule el factorial de un nº que se lee por teclado.

a)Utiliza la sentencia Mientras.

Var

N: Entero

Resultado: Entero

Inicio

Visualiza (“Escribe un número”)

Leer (N)

Resultado = 1

Mientras N > 0 Hacer

Resultado = Resultado * N

N = N - 1

F. Mientras

Visualiza (“El factorial es”, Resultado)

Fin

b)Utiliza la sentencia Repetir.

Var

N: Entero

Resultado: Entero

Inicio

Visualiza (“Escribe un número”)

Leer (N)

Resultado = 1

Repetir

Resultado = Resultado * N

N = N - 1

Hasta que N = 0

Visualiza (“El factorial es”, Resultado)

Fin

4)Realizar un algoritmo que sume los 1.000 primeros números enteros.

a)Utiliza la sentencia Para.

Var

N: Entero

Resultado: Entero

Inicio

Resultado=0

Para N=0 Hasta N=1.000 Hacer

Resultado=Resultado+N

F.Para

Visualiza (La suma de los 1.000 primeros números es”, Resultado)

Fin

b)Utiliza la sentencia Mientras:

Var

N: Entero

Resultado: Entero

Inicio

N=1

Resultado=0

Mientras N<=1.000 Hacer

Resultado=Resultado+N

N=N+1

F.Mientras

Visualiza (“La suma de los 1.000 primeros números es”, Resultado)

Fin

4)Realiza un algoritmo que lea 100 números y los sume.

a)Utiliza la sentencia Repetir

Var

N: Entero

Resultado: Entero

Contador: Entero

Inicio

Contador = 0

Resultado = 0

Repetir

Visualiza (“Escribe un nº”)

Leer (N)

Resultado = Resultado +N

Contador = Contador + 1

Hasta que Contador = 100

Visualiza (“La suma de los 100 números introducidos es”, Resultado)

Fin

b)Utiliza la sentencia Para.

Var

N: Entero

Resultado: Entero

Contador: Entero

Inicio

Resultado = 0

Para Contador=1 hasta Contador=100

Visualiza (“Escribe un nº”)

Leer (N)

Resultado = Resultado + N

F.Para

Visualiza (“La suma de los 100 números introducidos es”, Resultado)

Fin

5)Realizar un algoritmo que sume los números pares del 1-50.

a)Utiliza la sentencia Mientras.

Var

Contador: Real

Resultado: Real

Inicio

Contador = 0

Resultado = 0

Mientras Contador < = 50 Hacer

Resultado = Resultado + Contador

Contador = Contador + 2

F.Mientras

Visualiza (“La suma de los números pares que se encuentran entre 1-50 es”, Resultado)

Fin

b)Utiliza la sentencia Para.

Var

Contador: Real

Resultado: Real

X: Real

Inicio

Resultado = 0

Para Contador=1 Hasta Contador=25

X = 2 * Contador

Resultado = Resultado + X

F.Para

Visualizar (“La suma de los números pares que se encuentran entre 1-50 es”, Resultado)

Fin

c)Repite el algoritmo pero utilizando el operador MOD.

Var

N:Entero

Suma: Entero

Inicio

Suma = 0

Para N=1 hasta N=50 hacer

Si N MOD 2 <> 0 Hacer

Suma = Suma + N

F.Si

F.Para

Visualiza (“El resultado es”, Suma)

Fin

El operador x MOD y, realiza la división de x/y, y muestra el resto.

El operador SQRT ( Variable/s) realiza la raíz cuadrada.

6)Realiza un algoritmo que devuelve el cambio mínimo de monedas de una cantidad introducida por teclado hasta que la cantidad sea =0, teniendo en cuenta que las monedas posibles son: 1Pts, 5Pts, 25Pts y 100Pts.

VAR

Dinero: Entero

Cien: Entero

Veinticinco: Entero

Duros: Entero

Pesetas: Entero

Resto: Entero

INICIO

Repetir

Visualiza (“Introduce importe”)

Leer (Dinero)

Cien = Dinero/100

Resto = Dinero MOD 100

Veinticinco = Resto/25

Resto = Resto MOD 25

Duros = Resto/5

Resto = Resto MOD 5

Pesetas = Resto

Visualiza (“Su cambio es: ”,Cien,” de 100, “,Veinticinco,” de 25, “,Duros,” de 5 y “,Pesetas,” Pts.

Hasta que Dinero = 0

FIN

7)Realizar un algoritmo que de una serie de números hasta que se introduce el valor 0, visualice el valor máximo, el mínimo y el total de números introducidos. Teniendo en cuenta que el valor más grande es 1.000 y el más pequeño es cero.

VAR

Número: Entero

Máximo: Entero

Mínimo: Entero

Contador: Entero

INICIO

Mínimo = 1000

Máximo = 0

Contador = 0

Repetir

Visualiza (“Introduce un número”)

Leer (Número)

Mientras Número <= 1000 entonces hacer

Si Número > Máximo entonces hacer

Máximo = Número

Contador = Contador + 1

Sino entonces

Si Número < Mínimo entonces hacer

Mínimo = Número

Contador = Contador + 1

Sino entonces hacer

Contador = Contador + 1

F.Mientras

Hasta que Número = 0

Visualiza (Máximo,” es máximo, “,Mínimo,” es mínimo y has introducido “,Contador,” números.”)

FIN

INTRODUCCIÓN A LA PROGRAMACIÓN EN PASCAL

(T-2)

INTRODUCCIÓN.-

El alfabeto base de Pascal está formado por:

-Las Mayúsculas: A...Z.

-Las minúsculas: a...z.

-Dígitos: 0...9.

-Caracteres especiales: +, -, *,...

Existen tres conceptos básicos, como son:

-Identificador. Es el nombre que recibe un objeto y permite referenciar dicho objeto, a lo largo del programa. Existen dos tipos:

-Palabras reservadas. Son palabras que tienen un significado propio para el conpilador por lo que solo pueden utilizarse con ese significado preestablecido, durante el programa (BEGIN, PROGRAM,...).

-Identificaciones definidas por el usuario. Son nombres de objetos que van a ser utilizados por el programador, están formados por letras y dígitos, pero siempre han de comenzar por letra y tambien es posible utilizar el caracter de subrallado.

TIPOS DE DATOS BÁSICOS.-

Integer. (-32.767 a 32.767).

Real.

Char (Caracteres).

Boolean.

Existen distintos tipos de operadores que trabajan con distintos tipos de datos:

-“+”. Suma cualquier tipo de dato.

-“-“. Resta cualquier tipo de dato.

-“*”. Multiplica cualquier tipo de dato.

-“DIV”. Sirve para dividir, pero solo nos devuelve como resultado el cociente entero.

-“MOD”. Nos da únicamente el resto de una división.

-“/”. Divide cualquier tipo de dato, pero si la división no es exacta, nos devuelve un número real.

ESTRUCTURA DE UN PROGRAMA.-

Pascal es un lenguaje de programción estructurada, lo que implica, que utiliza como sentencias básicas, la secuenciación, selección e interacción, además tiene una característica que es modularidad.

Ej:

PROGRAM Nombre del programa (input, output).

CONST

(Nombre de la constante) {Nombre identificado = Valor;}

TYPE

[Tipos definidos por el usuario]

VAR

{Nombre del la variable}: Nombre tipo.

BEGIN

(Sentencias del programa principal).

END.

TIPOS DE DATOS ENUMERADOS Y SU RANGO.-

Pascal permite definir tipos de datos nuevos, según las necesidades del programador, esto se hace en la sección “TYPE” de la forma:

{Nombre del tipo = Dominio del tipo;}

Lo que permite definer variables de un tipo específico, más adecuado al programador.

Existen 2 tipos elementales que pueden definir el programador:

-Tipo enumerado.Se define especificando de forma numerada el domínio del tipo. Es

decir dando todos los valores posibles que puede contener.

Ej:

TYPE

Color = (Rojo, Azul, Verde, Amarillo);

VAR

Color1: Color;

Esta variable solo aceptará como valores, los definidos en el tipo “Color”.

-Tipo subrango. El dominio se define especificando un determinado rango de cualquier

tipo de datos excepto el real.

Ej:

TYPE

Edad = 16..70;

VAR

Edad1 : Edad;

La variable “Edad1” solo aceptará valores comprendidos entre 16 y 70.

TIPOS DE DATOS ARRAY.-

Un array es un conjunto de variables del mismo tipo que se referencian con el mismo nombre, seguido de un mismo indice que indica la posición del elemento en el vector:

Ej:)Definición de un vector vidimensional o matriz de enteros, cuyos indices son del tipo subrango 1..10,-7..100.

a)

TYPE

Matriz=ARRAY[1..10,-7..100] of Integer;

b)

TYPE

Sub1=1..10;

Sub2=-7..100;

Matriz=ARRAY[sub1,sub2] of Integer;

Pascal tambien permite definer directamente variables de tipo array.

VAR

Matriz:ARRAY[1..10,-7..100] of integer;

-7 100

1

.

Tambien tenemos la posibilidad de no restringirnos exlusívamente a índices de tipo numérico o subrango, sino que nos permite también tipos enumerados.

Ej:

a)

TYPE

Animal=(león, zorro, tigre, gacela);

Animales=ARRAY[animal] of Integer;

VAR

Total:Animales;

b)

CONST

Maxi=100;

TYPE

Rango=1..Maxi;

Mi_vector=ARRAY[Rango] of real;

VAR

V1:Mi_vector;

c)

CONST

Maxi=100;

TYPE

Rango=1..Maxi;

Mi_matriz=ARRAY[rango,rango] of Real;

Esto es lo mismo que decir:

Mi_Matriz=ARRAY[rango] of ARRAY[rango] of Real;

1)Programa que lee una secuencia de 50 números y los imprime en orden inverso al de entrada.

Program numeros;

CONST

Maxi=50;

TYPE

Numeros=ARRAY[1..maxi] of Integer;

VAR

Numero:Numeros;

Contador:Integer;

BEGIN

For Contador:=1 to maxi do

Begin

Writeln (`Introduce el nº de la posición `,contador);

Readln (Numero[Contador]);

End;

For Contador:=Maxi downto 1 do

Begin

Write (Numero[Contador],', `);

END.

PROGRAMACIÓN MODULAR.-

Funciones. Son unos pequeños programas que se sitúan fuera del programa principal y sirven para realizar unas operaciones concretadas por el programador y devolver el resultado a una variable.

Procedimientos. Son al igual que las funciones unos pequeños programas que se sitúan fuera del programa principal, pero a diferencia de las funciones, los procedimientos pueden trabajar con las variables indicadas y devolver los resultados a más de una variable.

Tanto las funciones como los procedimientos se definen entre el “BEGIN” del programa principal y después de las definiciones de variables.

PROCEDIMIENTO

Program Ejemplo1; (*Programa que suma dos numeros introducidos por teclado*)

VAR

Num1:Integer;

Num2:Integer;

Resultado:Integer;

PROCEDURE suma_dos(a,b:Integer;Var res:Integer);

Begin

res:=a+b;

End;

BEGIN

Writeln (`Introduce el primer sumando');

Read (Num1);

Writeln(`Introduce el segundo sumando');

Read (Num2);

Suma_dos(Num1,Num2,resultado);

Write(`El resultado de `,Num1,'+',Num2,'=',Resultado);

END.

Como se puede deducir “Num1” le asigna su valor a “a”, “Num2” a “b” y “Resultado” a “res”. En este caso al acabar el procedimiento, tan solo “res” devolverá su valor final a “Resultado”, ya que es la única variable que acompaña a (Var), a diferencia de “a” y “b” que, suponiendo que hubieran sido modificadas, no variarían los valores de “Num1” y “Num2”.

FUNCION

Program ejemplo; (*Suma dos numeros introducidos por teclado*)

VAR

Num1:Integer;

Num2:Integer;

Resultado:Integer;

FUNCTION Suma_dos (a,b:Integer):Integer;

Begin

Suma_dos:=a+b;

End;

BEGIN

Writeln (`Introduce el valor del primer sumando');

Read (Num1);

Writeln(`Introduce el valor del segundo sumando');

Read (Num2);

Resultado:=Suma_dos(Num1,num2);

Writeln(`El resultado de `,Num1,'+',Num2,'=',Resultado);

END.

RECURSIVIDAD.-

Es cuando dentro de una función o procedimiento, se llama a esta misma. De este modo es posible simplificar un trabajo repetitivo, consiguiendo así un bucle que acabaría cuando se cumpliesen unas condiciones que pondríamos como “fin de recursividad”. Por ejemplo, si quisiésemos encontrar el factorial de un número de forma recursiva se haría de la siguiente manera:

PROGRAM Factorial;

VAR

Fact, Num: Integer;

PROCEDURE facto (num: integer; Var res: integer);

Begin

If num>1 then

Begin

Res:=Res*num;

Num:=num-1;

Facto (num, res);

End;

End;

BEGIN

Fact:=1;

Write (`Introduce un numero: `);

Readln (num);

Facto (num, fact);

Writeln (`El factorial de `,num,' es `,fact,'.');

Readln;

END.

METODOS DE BUSQUEDA Y ORDENACIÓN

(T-3)

METODOS DE BUSQUEDA.-

· Búsqueda secuencial.

Este método sirve para cualquier tipo de array. Consiste en ir recorriendo el contenido del array hasta que se encuentre el dato buscado o se llegue al final. Este método no es muy efectivo, puesto que al enfrentarse a un alto numero de información, si el dato buscado no se encuentra al principio, resulta muy lento.

Ej:

PROGRAM Secuencial;

CONST

Max= 20;

TYPE

Rango= 1..max;

Vector= ARRAY [Rango] of integer;

VAR

V: vector;

Num: Integer;

Pos, cont: Rango;

BEGIN

Pos:=0;

Cont:=pos;

Repeat

Cont:=Cont+1;

If v[cont]=num then

Pos:=cont;

Until (cont=max) OR (pos<>0);

END.

· Búsqueda binária.

Este método de búsqueda solo puede utilizarse con un array ordenado. Es más eficaz que la búsqueda secuencial. Consiste en un procedimiento recursivo que compara el elemento buscado con el elemento que ocupe la posición media de un rango comprendido entre el principio y el final de la estructura. Si el elemento buscado es mayor que el comparado se redefinirá el rango entre el elemento que ocupa la posición media y el elemento que ocupa el final del rango, sí no, hace lo mismo pero entre la mitad del rango y el principio. Y así hasta dar con el dato buscado o no encontrarlo.

Ej:

PROCEDURE Binaria (Ini, fin, num: Integer; V:Vector; Var pos:Integer);

Var

Med, Rango: Integer;

Begin

Rango:= (Fin-Ini)+1;

Med:=Rango DIV 2;

Med:=Ini+Med;

IF Rango > 1 Then

If V[Med]= num then

Pos:= med

Else

If num> V[Med] then

Binaria (med+1, fin, num, v, pos)

Else

Binaria (Ini, med-1, num, v, pos)

Else

IF num=V[med] then

Pos:=med

Else

Pos:=0;

End;

METODOS DE ORDENACIÓN.-

· Método de la burbuja.

Consiste en recorrer el array buscando el nº mayor y colocándolo en la última posición. Después la variable que indica la última posición del array decrementaría una posición y es en esta donde colocaríamos el siguiente nº que se considere mayor.

7

8

2

5

Mayor = 8

7

2

5

8

Mayor = 7

2

5

7

8

Ej:

PROCEDURE Burbuja (n:Integer; Var a: Datos);

Var

Aux, i, k:Integer;

Begin

For k:=1 to n-1 do

Begin

i:=1;

Repeat

If a[i] > a[i+1] then

Begin

Aux:= a[i];

A[i]:=a[i+1];

A[i+1]:=aux;

End;

I:= i+1;

Until i > n-k;

End;

End;

Una mejora sobre el algoritmo es hacer que salga del bule si no se ha hecho ninguna modificación al recorrer el array.

· Ordenación por selección.

Consiste en repetir el siguiente proceso desde el primer elemento hasta el último. Se selecciona la componente de menor valor de todas las situadas a la derecha de la tratada y se intercambia por esta.

V= 32, 51, 27, 85, 66, 13

Se busca la componente más pequeña.

V= 32, 51, 27, 85, 66, 13

Se intercambia.

V= 13, 51, 27, 85, 66, 32

Se sigue con la siguiente componente.

V= 13, 51, 27, 85, 66, 32

V= 13, 27, 51, 85, 66, 32

V= 13, 27, 32, 85, 66, 51

V= 13, 27, 32, 51, 66, 82

Ej:

PROCEDURE Selección (n: Integer; Var a: Datos);

Var

I, j, k, aux: Integer;

Begin

For i:=1 to n-1 do

Begin

K:=i;

Aux:=a[i];

For j:=i+1 to n do

Begin

If a[j] < aux then

Begin

K:=j;

Aux:=a[j];

End;

A[k]:=a[i];

A[i]:=aux;

End;

End;

End;

· Ordenación por inserción.

Consiste en repetir el siguiente proceso desde la segunda componente hasta la última. Se toma dicha componente y se inserta en el lugar que le corresponda a la izquierda de o de entre las situadas a la izquierda si procede.

A: 32, 51, 27, 85, 66, 13

A= 32, 51, 27, 85, 66, 13

A= 27, 32, 51, 85, 66, 13

A= 27, 32, 51, 85, 66, 13

A= 27, 32, 51, 66, 85, 13

A= 13, 27, 32, 51, 66, 85

Ej

PROCEDURE Inserción (n:integer; Var a:datos);

Var

Aux, i, j:Integer;

Begin

For i:=2 to n do

Begin

Aux:=a[i];

J:=i-1;

While (j >=1) AND (a[j] > aux) do

Begin

A[j+1]:=a[j];

A[j]:=aux;

J:=j-1;

End;

End;

End;

· Ordenación por fusión.

Se subdivide el vector original hasta que tengamos subvectores de cómo máximo 2 elementos. Posteriormente se ordenan los subvectores y se van mezclando ordenadamente hasta conseguir el vector original, pero ordenado.

6

7

5

8

4

9

3

0

2

6

7

5

8

4

6

7

5

8

4

6

7

5

4

8

5

6

7

4

5

6

7

8

9

3

0

2

9

3

0

2

3

9

0

2

0

2

3

9

0

2

3

4

5

6

7

8

9

Ej

PROCEDURE Fusion (Vector_e:datos; a, b:Integer; Var Vector_s:datos);

Var

M:Integer;

Vector_s1, Vector_s2:datos;

Begin

If a=b then (*El vector de salida tiene una sola componente*)

Vector_s[1]:=Vector_e[a]

Else

If b-a=1 then

If Vector_e[a]>Vector_e[b] then

Begin

Vector_s[1]:=Vector_e[b];

Vector_s[2]:=Vector_e[a];

End

Else

Begin

Vector_s[1]:=Vector_e[a];

Vector_s[2]:=Vector_e[b];

End

Else (*Hay más de 2 componentes, hay que subdividir el vector*)

Begin

M:=(a+b) DIV 2;

Fusion (vector_e, a, m, vector_s1);

Fusion (vector_e, m+1, b, vector_s2);

Mezclavec (Vector_s1, Vector_s2, m-a+1, b-m, vector_s);

End;

End;

PROCEDURE Mezclavec (v1, v2:datos; n1, n2:Integer; Var sal:Datos);

Var

I,j,k:Integer;

Begin

I:=1;

J:=1;

K:=1;

While (i<=n1) AND (j<=n2) do

Begin

If v1[i]<= v2[j] then

Begin

Sal[k]:=v1[i];

I:=i+1;

End

Else

Begin

Sal[k]:=V2[j];

J:=j+1;

End;

K:=K+1;

End;

If i<>n1+1 then

Begin

Repeat

Sal[k]:=v1[i];

I:=i+1;

K:=k+1;

Until i=n1+1;

End;

End;

Lógicamente el procedimiento de mezclar los vectores habría que definirlo en el programa principal antes que el de fusion, para que el compilador lo reconozca.

· Metodo de ordenación rápida (quick sort)

El método de ordenación rápida es el último que se presenta en este tema. Se considera el método más eficiente cuando se usa de forma óptima.

La idea básica de este algoritmo es usar un elemento como pivote, de forma que el vector quede dividido en dos partes: una contendrá los elementos menores o iguales que el pivote; la otra los mayores. Como vemos en el primer paso se selecciona como pivote el primer elemento del vector.

Sea V= 3, 2, 5, 4, 1, 7, 6, 0

V= 2, 1, 0, 3, 5, 4, 7, 6

En el segundo paso, se seleccionan pivotes para los dos vectores generados, y se procede a subdividir los vectores según otros pivotes.

V= 1, 0, 2, 3, 4, 5, 7, 6

Este proceso se aplica a los vectores que se van generando hasta que solo contengan como máximo dos elementos. Si el vector tiene un solo elemento, el proceso sobre dicho vector, ha terminado. Si contiene dos elementos, como sucede con (1, 0) y (7, 6), sólo es necesario realizar una comparación para ordenarlos. Al finalizar este proceso, todos los números están en su posición correcta, siendo sólo necesario combinarlos de nuevo en un único vector. A diferencia del método de ordenación por fusión, no se necesita ninguna comparación para construir el vector, puesto que los elementos ya están totalmente ordenados.

PROCEDURE Ordenación_rapida (vector_e: Datos; a,b:Integer; Var vector_s: Datos);

Var

Piv, i, j, k, z:Integer;

Vector_e1, Vector_e2, Vector_s1, Vector_s2: Datos;

Begin

I:=1;

J:=1;

K:=2;

Z:=1;

If b<>0 then

If a=b then (*Solo hay un elemento*)

Vector_s[1]:=Vector_e[a]

Else

If b-a=1 then (*Solo hay 2 elementos*)

If vector_e[a]<=vector_e[b] then (*No intercambia*)

Begin

Vector_s[1]:=Vector_e[a];

Vector_s[2]:=Vector_e[b];

End

Else (*Hay que intercambiar*)

Begin

Vector_s[1]:=Vector_e[b];

Vector_s[2]:=Vector_e[a];

End

Else Begin (*Hay tres elementos o más*)

Piv:=Vector_e[1];

While k<=b do Begin

(*Escribir en el vector izquierda*)

If piv> vector_e[k] then Begin

Vector_e1[i]:=Vector_e[k];

I:=i+1;

End

Else Begin (*Escribir en el vector derecha*)

Vector_e2[j]:=Vector_e[k];

J:=j+1;

End;

K:=k+1;

End;

(*Ordenar el vector de la izquierda*)

Ordenacion_rapida (Vector_e1,1,i-1,vector_s1);

(*Ordenar el vector de la derecha*)

Ordenación_rapida (vector_e2,1,j-1,vector_s2);

(*El vector más pequeño se escribe en el vector*)

For k:=1 to i do

Begin

Vector_s[z]:=Vector_s1[k];

Z:=z+1;

End;

Vector_s[z]:=piv; (*Escribir el pivote en el vector*)

Z:=z+1;

For k:=1 to j do

Begin

Vector_s[z]:=Vector_s2[k];

Z:=z+1;

End;

End;

End;

PROGRAMACIÓN DINÁMICA

(T-4)

INTRODUCCIÓN.-

Podemos definir una estructura como la relación existente entre los diferentes elementos de un grupo. Dato como la representación de un valer o un conjunto de valores referidos a un determinado contexto. De esta forma podemos definir estructura como la relación existente entre los datos de un determinado contexto.

Los leguajes de programación nos ofrecen unos tipos básicos o elementos, ya sean normalizados (enteros, reales, caracteres, buleanos, y punteros), o no normalizados (enumerados y subrrangos). Además ofrecen tipos estructurados como los registros, vectores, matrices y el conjunto de estos.

Todos estos tipos sirven como base al programa para poder implementar los tipos estructurados no normalizados, que vamos a ver en este tema. Estos tipos se pueden implementar con estructuras estáticas (Ejemplo de pila y cola basada en un array) o memoria dinámica. En concreto implementaremos los tipos: lista, pila y cola, utilizando punteros.

NOTA: DECIMOS QUE UNA VARIABLE “P” ES UN PUNTERO (^) SI ESA VARIABLE APUNTA HACIA UNA VARIABLE DE UN DETERMINADO TIPO O SI ALMACENA LA DIRECCIÓN DE MEMORIA DONDE SE ENCUENTRA UN ELEMENTO DE UN DETERMINADO TIPO.

Ej:

TYPE

Nodo=Record

Dato:Integer;

Sig:^Nodo;

End;

Lista=^Nodo;

VAR

L:lista;

Descargar

L

dato

sig

dato

Sig

Enviado por:	Pedro
Idioma:	castellano
País:	España