Introducción A La Programación Sistemática
Introducción A La Programación Sistemática
Introducción A La Programación Sistemática
SISTEMÁTICA
Una Introducción
NIKLAUS WIRTH
Eid,genossische Technische Hochschule Zürich,
Suiza
PRENTICE-SALA, Inc.
ENGLEWOOD ACANTILADOS, NEW JERSEY
Biblioteca de Catalogación de Congreso en Publica/Dato de ión
W1RTH, NIKLAUS
Programación sistemática
© 1973
Por PRENTICE-SALA, Inc.
Englewood Acantilados, New Jersey.
20 l 9 18 17 16 15 14 l 3 12 ll
Prefacio Xl
1. Introducción
2
2. Ideas fundamentales
8
3. La estructura de ordenadores. 12
4. Programando ayudas y sistemas.
5. Sorne Programas sencillos 26
6. Finiteness De programas. 29
7. Lenguajes de programación y notación 44
secuenciales. 58
8. Tipos de dato 68
9. Los programas basaron en recurrence 80
relaciones 1O. La estructura de dato del 92
archivo 103
l l. La estructura de dato de la variedad 110
12. Subrutinas, procedimientos, y funciones. 125
13. Transformaciones de representaciones de número
14. Procesamiento del texto que utiliza variedad y 155
estructuras de archivo 163
15. Stepwise Desarrollo de programa
165
Un ppendices 169
A. El PASCAL de lenguaje de programación
B. El ASCII código de carácter
Índice Subject
Índice de programas de muestra
"Atl ...Sistemas nuevos ofnotation es tal que uno puede cumplir nada por medios
ofthem cuál no también ser cumplido sin ellos; pero la ventaja es que cuándo tal
sistema de notación corresponde al innermost esencia de frecuentemente ocurriendo
necesidades, uno puede solucionar los problemas que pertenecen en aquella categoría,
de hecho puede mechanically solucionarles en casos tan complicados que sin tal una
ayuda incluso el genio deviene impotente. Por ello es con la invención ofcalculating
por letras en general; por ello sea con el cálculo diferencial *
NIKLAUS WIRTH
V:= W (2.1)
El símbolo : = se apellida el operador de asignación.
Formalmente, declaración (2.1) ahora puede ser escrito cuando
z:=x*y (2.2)
4 CHAP. 2. IDEAS FUNDAMENTALES
Valores de Variables
Paso z u
1 o 5
2 13 4
2 26 3 (2.4)
2 39 2
2 52 1
2 65 o
=
El proceso rescinde, según declaración 2, apenas u O. En este tiempo, z ha
=
adquirido el resultado final 65 5 * 13. Tal mesa es ca!Dirigido un rastro.
Nota que el listado secuencial de valores <loes no significar que estos
valores están retenidos; en cambio, cada variable ha a la vez exactamente
uno valor solo. Esto se debe a el hecho que una asignación overwrites el valor
anterior de una variable.
Valores de Variables.
Paso z u
o V
2 XIII IV
2 XXVI III (2.5)
2 XXXIX II
2 LII y
o
2 LXV o
Ejemplo: Divisió n
Estamos dar la instrucción :
Dividir el número natural x por el número natural y y denotar el cociente de entero
como q y el resto como r.
Paso l: q := O
r:= X
(2.7)
=x
Por programa (2.7), habiendo los valores 100 y y 15, está
listado en el rastro en (2.8).
=
Valores de Variables
Paso q r
o 100
2 1 85
(2.8) 2 2 70
2 3 55
2 4 40
2 5 25
2 6 10
El proceso está rescindido apenas r < y. Los resultados son q=6 y r 1O, por
ello satisfaciendo las relaciones (2.6. l):
100 = 6 * 15 + 10 y O� 10 < 15 = (2.9)
Estos dos ejemplos son descripciones de los procesos secuenciales en
qué las asignaciones individuales están actuados estrictamente en orden
secuencial en tiempo. De ahora en adelante, nuestras discusiones serán
restringidas a procesos secuenciales, donde el proceso "de palabra" siempre
será entendido para ser una abreviatura de proceso secuencial. Esta
omisión deliberada de nonsequential los procesos es hizo no sólo porque los
ordenadores convencionales operan sequentially pero principalmente
porque el diseño de nonsequential programas o sistemas de secuenciales
pero programas interdependientes para ser ejecutados al mismo tiempo-es
una tarea sutil y difícil, requiriendo como base una maestría minuciosa de
el arte de diseñar algoritmos secuenciales.
Estos dos ejemplos también muestran que cada programa describe una
secuencia
De transformaciones estatales de el conjunto de sus variables. lf El
mismo programa está obedecido dos veces con valores iniciales diferentes (x
y y), entonces sea una equivocación para decir que los dos procesos o las
computaciones eran igual. Aun así, sin duda siguen el mismo patrón
ofbehavior. La descripción de tal patrón de comportamiento sin la referencia
a un procesador particular es normalmente llamó un algoritmo. El
programa de plazo es correctamente utilizado para los algoritmos
diseñaron de modo que pueden ser obedecidos o seguidos por un tipo de
procesador concreto. La diferencia entre un general (a veces llamado
abstracto) algoritmo y un programa de ordenador líes principalmente en el
hecho que el último tiene que especificar las reglas de comportamiento en
cada poco detalle y tiene que ser compuesto según estricto notational reglas.
Las razones para este es la máquina está limitada conjunto de
instrucciones, el cual es capaz de comprensivo y ejecutando, y su
obediencia absoluta, basado en su carencia total de una actitud crítica.
Estas características de el ordenador están criticadas por más novatos en el
arte de
IDEAS FUNDAMENTALES 7
El rnost irnportant lección para ser aprendida frorn este exarnple es que
células de almacenamiento finito-aquello es, las células capaces a assurne sólo
un finitos nurnber ofdiscernible estados (ningún otros existen en realidad}-es
capaz ofstoring nurnbers único frorn afinite gama ofvalues. En un cornputer el
nurnber ofbinary almacenamiento elernents agrupó a una célula de
almacenamiento direccionable sola (palabra) es normalmente llamó el
wordlength. Las capacidades del arithrnetic la unidad está adaptada a este
rneasure. Cornrnon Valores ofwordlengths n es 8, 16, 24, 32, 48 y 64 con
conjuntos correspondientes de2 n valores distintos.
La consecuencia del básico requirernent que el cornputer rnust ser capaz
de obedecer un dado prograrn es que él rnust tener "acceso" fácil a aquel
prograrn. Dónde, entonces, es el rnost sitio apropiado para aguantar un
prograrn? Sea el brillante-y hoy en día seerningly trivial-idea de John von
Neumann para poner el prograrn a la tienda. Consiguientemente, el sarne la
tienda suele control tanto los objetos y la receta "" ofthe cornputing procesos,
aquello es, el dato y el prograrn.
Evidentemente, este concepto de el ordenador de programa almacenado
requiere que instrucciones también ser codificados. En nuestro exarnple de
una evaluación de expresión cada instrucción es representable por un
código de operación (para especificar lectura, escritura, añadiendo, rnultiplying,
etc.) y, en sorne casos, por un operando. Si los operandos están
representados por almacenamiento-direcciones de célula y si estas direcciones
están escogidas para ser la totalidad nurnbers O, 1, 2, , entonces el problern
ofencoding
prograrns Es esencialmente solucionó; cada prograrn puede ser
representado por secuencias ofnurnbers (o grupos ofnurnbers) y por tanto
puede ser depositado en un cornputer tienda.
Otra consecuencia de el almacenado-prograrn la aproximación es que
cada prograrn ocupará un seguro nurnber de células de almacenamiento,
aquello es, un seguro arnount de espacio de almacenamiento. El nurnber
ofoccupied células, los cuales son ya no disponibles de aguantar dato, es
proporcional a la longitud del prograrn texto. El prograrnrner rnust por
tanto airn para mantener su prograrns como conciso como posible.
El siguiente, irnportant capacidades ofthe rnodern digitales cornputer está
basado en el concepto ofsharing la tienda entre el prograrn y el dato.
1. Apenas ejecución ofa seguro prograrn P es terrninated, un nuevo prograrn Q
puede ser aceptado en la tienda para ejecución subsiguiente (flexibilidad,
aplicabilidad ancha).
2. Un cornputer rnay generar (según un seguro prograrn) una secuencia de
nurnbers que lo posteriormente considerará e interpretar cuando
codificó instrucciones. El dato generado en el primer paso becorne el
prograrn obedeció en el segundo paso.
3. Un cornputer X rnay ser instruido para considerar secuencias de
nurnbers de hecho representando prograrns como datos para ser
transforrned (según sorne traducción prograrn) a secuencias de
nurnbers representando prograrns codificados para un diferentes
cornputer Y.
4 PROGRAMANDO
SISTEMAS.
sida Y
Capítulo 4 mostró claramente por qué un programa tiene que constar de las
declaraciones formularon en una notación que el ordenador "entiende." A
pesar de que no sabemos aún así qué clases de declaraciones y fórmulas un
lenguaje de programación contiene, sabemos que estas declaraciones
precisamente especificarán el pretendió acciones. Este incuestionable necessity
para la precisión probablemente constituye la diferencia principal entre
comunicación entre humanos y comunicación con máquinas. El trabajo con
ordenadores requiere ambos preci- sion y claridad. Vagueness Y la ambigüedad
es estrictamente prohibida.
Un generalmente utilizado y fácilmente comprehended notación para
expresar pro- los gramos es el tan-llamados fiow-esquema o flowchart. Programa
(2.3) está descrito en (5.1) como flujo-esquema.
z:=0
u:=x
z: = z + y
u:= u - 1
14
ALGUNOS PROGRAMAS SENCILLOS 15
q:=0
r:=x
(5.2)
r:= r -
Un programa determina un ypatrón de comportamiento para un
unspecified, a menudo número infinito de procesos posibles. Los procesos
individuales son dis tinguished por los valores de las variables implicaron
en intervalos de tiempo relacionado y, en particular, por los valores iniciales
o argumentos. Pero cómo puede aseguramos que ali procesa ejecutable
según un programa dado computará el especificó resultados? Esta
cuestión de el correctness ofprograms es uno de el más central, crucial, y
asuntos inevitables de programar. El correctness de programas (2.3) y (2.7)
estuvo demostrado en mesas (2.4) y (2.8) para un par fijo de valores x y y. Este
método de establecer correctness se apellida testaje de programa; consta
de seleccionar argumentos (x y y), ejecutando el proceso con estos
seleccionó argumentos, y com paring el computó resultados con los
resultados correctos anteriormente sabidos. Este testaje experimental está
repetido con severa! Argumentos, utilizando el ordenador como el ideal
también!. No obstante, este método convencional es
16 CHAP. 5. ALGUNOS PROGRAMAS SENCILLOS
- - - P (Antecedente)
(5.3)
-- - Q
(Consiguiente)
ALGUNOS PROGRAMAS SENCILLOS 1 7
Qz-- ---
- Qn
(5.4.1)
-P
Ejemplo:
T
18 CHAP. 5. ALGUNOS PROGRAMAS SENCILLOS
(5.5.1)
Ejemplo:
----lO<< x 10
(5.5.2)
(5.6.1)
---P
(Esta regla bien puede ser considerada como la definición de el efecto de
asignar- ment.)
Ejemplos:
--x+y= 10 ---x+ 1 = 10 - - f(x) = u
x:=x+ 1
--z=IO ----x = 10 - X= U
(5.6.2)
ALGUNOS PROGRAMAS SENCILLOS 1 9
....---�--, r- y�O
(5.9)
----- r+q* y = x, r � O
20 CHAP. 5. ALGUNOS PROGRAMAS SENCILLOS
Los dos programas completos con las aserciones pertinentes están mostrados en
esquemas de flujo (5.10) y (5.11)..
- - - - -- X > O, y >
o
z:=O
u:=x
------z = O, u = X
u>O
------z + u * y = X * Y,
(5.10)
z:= z + y
u:=u-1
+ U * y =X
* y, u�O
------ Z
------z =X* y, U= 0
q:=0
r:= X
r =x
.------- (5.11)
r�O
+
1
1 -q *y+ r = X, O�r<y
--------
1
1
1
r:=r - y
1
q:=q ¡
() n (5.12)
H => p�
s (5.13.1)
----P
22 CHAP. 5. ALGUNOS PROGRAMAS SENCILLOS
_,
Yo yo
Yo yo
(5.13.2)
i (P /\ -.B )
s
L --------------------------------------------------------------------- 1
Y (5.14.1)
----Q ----------------------- Q
Podemos hacer la aserción siguiente sobre la declaración repetitiva S":
---P
S"
s
(5.14.2)
L_ __ ______________ J
Argumentos: x, y
Resultado: z
Variable auxiliar: u
z: = 0
u:=x
,----...-,--- (z + u * y = x * y) /\ (u > O)
z:=z+y (5.15)
u:= u - 1
----Z=X*Y
Argumentos: x, y
Resultados: q (cociente de entero), r (resto)
24 CHAP. 5. ALGUNOS PROGRAMAS SENCILLOS
q: = o
r: = X
'(q *y + r = x) Un (r �O)
(5.16)
EJERCICIOS
5.1 El programa siguiente computa el producto z •= x * y, donde sólo las operaciones de
adición, plegando, y halving está empleado. Los argumentos x y y es números
naturales; u y v es (auxiliar) variables de entero. El predicado extraño(u)
z:= O
u:=x
v:= Y
-------------------------------------- (z + u * v = x * y) /\ (u � 0)
(5.17)
Z =X* y
11:= udiv 2
v:=2•v
EJERCICIOS 25
5.2 El programa siguiente computa el más grande común divisor (GCD) de dos
números naturales x y y; un y b es variables de entero cuyo valor final representa el
resultado deseado.
Un:
=x
b:=y
· · GCD(Un,b) = GCD(x,
y)
(5.18)
1
1
'-Un= b =
GCD(x,y)
Cuando en Ejercicio 5.1, determinar las aserciones necesarias por utilizar estas
relaciones sabidas de la función GCD:
5.3 Siguiendo el patrón en programa (5.Yo 7), diseño un programa para computar z = x
v para los números naturales dados x y y. Incluir las aserciones necesarias para
verificar el correctness de vuestro programa.
6
FINITENESS DE
PROGRAMAS
(6.1)
Y condición B es
r�y
Dónde r, q, y y es números naturales. Escogemos N = r - y. Desde
entonces
(a) r �y Implica N �O y
(b) La ejecución de Sdecreases el valor de r y por tanto de N, finiteness es
evidentemente guaranteed. Nota, en particular, el necessity de la
condición inicial y > O.
EJERCICIOS
Un:
=x
b:=y
+ Un:= un
- b
(6.2)
+
b:= b -
Un
6.3 En qué casos <loes programa (6.2) computa el más grande común divisor de x y
y? Determinar las aserciones necesarias y suficientes.
LENGUAJES DE PROGRAMACIÓN
7 Y NOTACIÓN SECUENCIALES
7.1 ENCUESTA
29
30 CHAP. 7. LENGUAJES DE PROGRAMACIÓN Y NOTACIÓN SECUENCIALES.
Letra
(7.1) Letra
Dígito
Identificadores
x+y+z = (x +y)+ z
X* y+Z = (x *y)+ z
X+Y* z = X+ (y* z)
x - y* z - w = (x - (y* z)) - w (7.2)
X*Y-Z*W = (x *y) - (z * w)
-X+y/z = (-x)+ (y/z)
X* y/z = (x *y)/z
x/y *z = (x/y) *z
V:= E (7.3)
Declaraciones
compuestas
Empieza SI; S2;... ; Sn (7.4)
Fin
Declaraciones condicionales
(7.5)
Declaraciones repetitivas
Mientras B hacer S repetir S hasta B
Nota: Desde los dos símbolos básicos repiten y hasta que ya constituir un
par de paréntesis, la forma.
Repite SI; S2; .......... ; Sn hasta B
Es admisible sin un adicional empieza par de fin.
Declaraciones selectivas
Caso i de LI :SI; L2:S2; .......... ; Ln:Sn fin
(7.8)
en notación lineal
Reglas de verificación
1. Declaración de asignación
{Pq v:= w {P}
(Ve 5.6.1.)
2. Declaración compuesta
Preconditions: {P} SI {Q} (7.10)
{Q} S2 {R}
Consecuencia: {P} SI; S2 {R}
3. Declaraciones
condicionales
Preconditions: {P /\ B} SI {Q} (7.11)
{ P /\ -.B} S2 {Q}
Consecuencia: {P} Si B entonces Sl más S2 {Q}
Preconditions: {P /\ B} S {Q} (7.12)
(P /\ -.B) => Q
Consecuencia: {P} Si B entonces S {Q}
4. Declaraciones
(7.13)
repetitivas {P /\ B} S {P}
Precondition:
Consecuencia:
{P} Mientras B S {P /\ -.B}
{Q}
{P} S (7.14)
Preconditions: {Q /\ -,B} s {Q}
Consecuencia: {P} Repite S hasta B {Q /\ B}
5. Declaración selectiva {P /\ (i = Ld} sk {Q} Para ali
Preconditions:
Consecuencia: {P} k caso i de (7.15)
LI :SI;
L2:S2;
Empieza=
r : x; q : = O; w : y;
Mientras w� r w : = 2* w;
{w=2n *y>x}
=
Mientras w # yhacer
Empieza {q* w + =
r x, r � O} (7.22)
q : = 2* q; w : w div 2;
if w �r entonces
Empieza r : = r - w; q : =q +
=yo
Fin
Fin
{q* y+ r = x, O�r < w; q = xdiv y}
Fin.
SEC. 7.3 PROGRAMAS SENCILLOS EN NOTACIÓN SECUENCIAL 39
La sustracción repetida
Mientras un � b un : = un - (7.24.1)
b
Un: = un mod b
Empezar=
un: = x; b: y;
Repetir {un> O, b > O}
Mientras un > b un := un - b;
Mientras b > un b : = b- (7.25)
Hasta un
un;
=b
Fin. {Un= b = GCD(x,y)}
Empezar=
un : = x; b: y; u
O
b ={un> n
Repetir O, b > O}
t
= un :
Si un � b entonces un mod b;
i
{O�Un<b
} l
i
f Un > O entonces b: = b modun más
Excambio(un, b)
{Un = GCD(x,y)} (7.26)
Fin.
40 CHAP. 7. NOTACIÓN SECUENCIAL ANO PROORAMMING LENGUAS
Esta versión de computar el más grande común divisor estuvo inventado por
Euc/id y es uno de los ejemplos sabidos más tempranos de un matemáticos algo-
rithm. Es normalmente citado en el equivalente foi:m (7.27).
EJERCICIOS
expresiones Un : = b un := 2 2 :=
=
unpecado(x * y) empieza un : 1
fin
Si un= 2 entonces un := un + 1 más P(x, y)
whilea > 0doa := un - acabo
if x < y Entonces; z := cierto; else z: = falso
repeatz := z + 1.5, y:= u- yo untily = O
EJERCICIOS 41
2*3-4*5
15div4*4 80/5/3
2/3* 2
Un z - e+ ª
b*c + -c -
d + <!_
f
-b + jb2 -
4ac 2un
Yo 1
� +b
c+d
7.3 Ejecutar los programas indicaron con el especificó valores de x y y y establecer una mesa
de rastro.
7.4 Determina superior y más bajo bounds para el número de operaciones necesarias (como
funciones de x y y) en programa 7.22. Entonces determinar las aserciones necesarias y
suficientes para verificación de el programa.
42 CHAP. 7. LENGUAJES DE PROGRAMACIÓN Y NOTACIÓN SECUENCIALES.
7.5 Traduce flujo-esquema (7.29) a notación de serial. Nota que el programa com-
putes el más grande común divisor GCD(x,y) y dos multipliers e y d de modo que.
e* x + d• y= GCD(x,y)
Determinar las aserciones necesarias y suficientes para verificación de programa.
Un •= x e •= O u •=
bl •= y d •= l V •= o
q•= un div h r •= un
mod h
- -b = GCD(x,y)
+
=c*x+d*y
Un,= b b •=
r
t •= u u •= e e •= t - q * e
t •= V V •= d d •= t - q * d
(7.29)
q•= Un div b r •= un mod
b
7.6 Construir un programa, anotado con las aserciones necesarias para verificación,
aquello computa GCD(x, y) sólo en la base de las relaciones siguientes.
(Un) GCD(2 * m, 2 * n) = 2 * GCD(m, n)
(b) Extraño(n): GCD(2 * m, n) = GCD(m, n)
(c) m > n: GCD(En - n, n) = GCD(m, n)
(d) GCD(n, m) = GCD(m, n)
(e) Extrañ o(m) /\ extraño(n): ,extraño(m-n)
7.7 Entre las condiciones P, Q, y R, exactamente uno está satisfecho en ali tiempo. ( se
apellidan mutuamente condiciones exclusivas.) La probabilidad que P es satisfecho es
W p. (WQ Y W R está definido análogamente.) Determina el valor esperado de neces- sary
evaluaciones de P, Q, R como funciones de W p, WQ, WR en el siguientes estatales-
ments:
Cuál de las tres declaraciones equivalentes está seleccionado si Wp > WQ > WR?
44
El DATO ESCRIBE 45
El conjunto de valores que una variable puede suponer juegos tal una
función importante en la caracterización de el variable que se apellida su
tipo. Por tanto recomendamos que ali variables ser declarados en el
encabezando de un programa. Tal variable declaration está denotado por
var v: T (8.1)
(8.2)
Tipo t = T (8.3)
(8.4)
46 CHAP. 8. TIPOS de DATO
Tendría que ser evitado porque dejan el tipo de sorne constantes (en este
caso, el verde de color) ambiguamente definió.*
Los tipos escalares seguros están utilizados tan frequently que ambos
ellos y su.
Los operadores son presentes en cada sistema de ordenador. Estos tipos, tipos
estándares llamados, necesita no ser definido en un programa porque está
supuesto que son sabidos por cada procesador. Incluyen los valores de
verdad lógicos, la totalidad.
• Las ideas de la unión y la intersección de tipos han sido evitadas intencionadamente.
SEC'. 8. J ESCRIBE BOOLEANO 47
p q pVq p /\ ,p
q
.Falso
.Fals .Falso .Fals Cierto
(8.10) o
o
Cierto .Fals Cierto .Fals .Fals
o o o
De esta mesa, podemos derivar relaciones (8.11)-(8.14). Estas relaciones son
.Fals Cierto Cierto .Fals Cierto
útiles en muchos casos,
o particularmente cuándo
o un más sencillos pero la
forma equivalente quieta de una expresión dada está.Fals
Ciert Cierto Cierto Cierto buscada.
o o
l.pVq=qVp
Commutative Leyes (8.11)
p /\ q= q /\ p
2. (p V q) V r = p V (q V r) (8.12)
Associative Iaws
(p /\ q) /\ r = p /\ (q /\ r)
3. (p /\ q) V r = (p V r) /\ (q V r) Distributive Leyes (8.13)
(p V q) /\ r = (p /\ r) V (q
/\ r) de las leyes de
4. ,(p V q) = ,p /\ ,q (8.14)
, (p /\ q) = , p V , q Morgan
48 CHAP. 8. TIPOS de DATO
xEBy=x+y
(x EB y) EB z = x EB (y EB z)
SEC. 8.3 TIPO CHAR 49
Este tipo denota un finito, ordenó puesto ofcharacters. Tan define una
gama segura de processable números, cada sistema de ordenador también
define un conjunto de caracteres a través de qué comunica con el mundo
exterior. Estos caracteres son disponibles en su entrada (lectores) y
producción (impresoras) equipamiento. Una estandarización de conjuntos de
carácter es altamente deseable, (incluso indispensable, si varios sistemas de
ordenador son para ser conectados para comunicación mutua, transmisión de
dato, procesamiento de dato remoto, etc.). A pesar de que coordinación
completa en la estandarización de conjuntos de carácter parece para ser un
objetivo esquivo, ha sido generalmente estado de acuerdo que conjuntos de
carácter para ser utilizados por sistemas de ordenador comprenderán las
26 letras latinas, el 10 árabe decimal dígitos, y un número seguro de
caracteres especiales como marcas de puntuación. Además, un carácter pone
definido por la Organización de Estándares Internacional (ISO) y su variante
americana ASCII (Estándar americano
50 CHAP. 8. TIPOS de DATO
o 2 3 4 5 6 7
o nul Da o @ p p
1 soh do 1 U Q U q
2 stx del 2 nB R n r
3 etx dc2 # 3 e s b s
4 eot dc3 $ 4 D e t
T
enq u d u
5 dc4 % 5 E
e V
6 ack nak & 6 F V
f w
7 Bel syn 7 G w G
8 io etb 8 H X
X
bs h
9 lata 9 1 y y
10 ht em * j z j
z
11 lf sub + K [ k {
vt
12 ese < L \ 1 1
13 ff fs M ] m
14 cr qs > N n 7
15 tan rs / ? o o del
si nos
l. El conjunto de carácter tiene que contener el Ietters A-z y los dígitos 0-9.
2. Los subconjuntos de letras y dígitos tienen que ser ordenados y
coherentes. Aquello es, e es una letra sólo si 'Un' � e y e� 'Z', y e es
un dígito si y sólo si 'O' � e y e � '9'.
3. El conjunto de carácter tiene que contener un espacio (espacial), una línea
separator (denotado por eol-significando fin de Iine), y severa! Otros
caracteres, como comas y periodos, los cuales no son especificados en
detalle..
(8.20)
RcR
SEC'. 8.4 TIPO REAL 53
Implica
(-x)~ = -(.x)
Axiomas Un6-Un9 postulado un conjunto de propiedades mínimas que tiene que
ser cumplido por la aritmética de un ordenador antes de que se pueda apellidar
"utilizable" sin reserva tions. Las operaciones de aritmética básicas habladas es
adición, sustracción, multiplicación, und división, denotad by the símbolos EB,
0, ® und 0,respectivamente. Siempre supondremos x, y E R.
Un6. Commutativity De adición y multiplicación
EJERCICIOS
8.1 Cuáles de las expresiones siguientes son syntactically correctos (i.e., "tipo com patible")?
Qué es sus tipos? Supone que las variables siguientes están declaradas.
0.693097183059945296917232371458
8.4 Diseño un programa que repetidamente multiplica el complejo variable z por el com
plex constante e = 0.6 + 0.8i. Un número complejo z = x + iy (i = j"=yo) tendría que
ser representado por dos real-valoró variables, x y y.
Nota: El valor absoluto de e es l. Si el programa incluye una computación de
(x EB x)/2 # x
Pista: Primero encontrar tal un x por utilizar un dos-dígito representación decimal.
9
Los PROGRAMAS BASARON EN
RECURRENCE RELACIONES
9.1 SEOUENCES
V:= v0 ;
Mientras p( V) V : = f( V) (9.2)
J; = k;-1*Íi-1
k; = k;_ 1 + l
cuáles difieren ligeramente pero
significativamente de (9.7)..
Ejemplo: Computación de 1/x.
Dejado dos secuencias de números reales un0 , un 1, ••• y e 0,e1, ••• ser
especificado por el recurrence relaciones
Un; =ª;- i * (l +e¡_¡)
} Para > i O (9.10)
e¡ = ef-1
y los valores iniciales
ªº = 1, eo = 1 - X O<<x l
Por manipulación algebraica de fórmulas, pueda ser mostrado que
1 - en (9.11)
"
X
C¡ = e2_¡
¡
* ¡1 (3 + C¡_ ¡) O
Y los valores iniciales
Uno = X, eo = 1 - X O<<x l
Por manipulación adecuada de fórmulas, pueda ser
mostrado que (9.15)
Qn = ✓* (1 - en )
X
Y
X 1
=----- ---
(1 +}c0 )···(1 +½en -1)
Jx
El programa obtenido por sustituir recurrence relaciones (9.14) en
programa schema (9.2) es
var Un, C: real; {O<<x 1} (9.17)
beginA := x; C := 1 - x;
Mientras abs(C) > e hacer
Empezar {Un 2 = x*(l - C), C �O}
Un : = Un* (1 + 0.5* C);
C: = sqr(C) * (0.75 +0.25* C)
Fin
9.2 SERIE
T: = t0 ; S : = T;
Mientras p(S, 7) (9.23)
Empieza T: = f(7); S: = S
Fin
+T
De la definición de la declaración de asignación y la declaración
repetida que utiliza la cláusula de rato, las relaciones siguientes pueden
ser derivadas como las propiedades básicas de este programa schema.
l. l ¡ =f(t ¡ _ ¡) fori>
2. t¡ e/- tj O fo ri
3. S¡ = S¡_ ¡ + t; e/- j (9.24)
fori>
4. ,p(sm tn) O
5. p(s;, t;)
for alii < n
SEC. 9.2 SERIE 63
j>O (9.26)
Por aplicación adecuada de estas fórmulas, programa (9.32) tendrá que ser
aplicado sólo a valores de x satisfaciendo O � lxl � n/4. En este
intervalo, qué nunca, el índice de convergencia es satisfactorio para practica!
Propósitos, y el número de plazos para ser computados queda suficientemente
pequeño de mantener los efectos de redondear y errores de truncamiento
(debido a computación con un finito arith metic) dentro de límites
tolerables.
Finalmente, programa (9.32) pide la aplicación de otra regla básica de
programar: dentro de la declaración repetida, el valor x2 tiene que ser
computado. Esto cuadrando está actuado repetidamente, a pesar de que x
nunca es cambiado en ali. Esta lata de esfuerzo computacional innecesaria
y tiene que ser eliminado por computar x2 una vez-aquello es, antes de
empezar las repeticiones en la declaración de rato-y por asignar el resultado
a una variable auxiliar, el cual es entonces sustituido sistemáticamente para
cada ocurrencia de x 2 . Este procedimiento puede ser formulado como la
regla de tierra siguiente.
lf Una expresi ó n f(x) está evaluado dentro de una declaraci ó n repetitiva S y si el
argumento x no cambia durante las repeticiones, entonces un auxiliar
Variable h tiene que ser introducido al cual el valor f (x) está asignado una vez befare
la ejecución de S y cuál está sustituido para cada ocurrencia de f (x) dentro de S;
aquello es, el construir
Mientras P hacer
Empieza .. . f(x)... Fin (9.35.1)
Est á
reemplazado
h :=f(x);
por
Mientras P hacer
(9.35.2)
begin ... h ...Fin
EJERCICIOS
9.1 Reescribe programas (9.28) y (9.32)----utilizando fórmulas (9.33) y (9.34) ---------de modo
que.
Las funciones exp (x) y pecado (x) está computado efficiently (y más con exactitud).
9.2 Diseño un programa para computar una aproximación de cos (x) con una exactitud relativa
c. Programa de uso schema (9.23) y
x2
cos (x) = 1 - - +-
x4 -· · ·
2! 4!
9.3 Programa de uso schema (9.23) para desarrollar un programa para computar una
aproximación a la integral
x3 xs x1
S: exp( - u2 ) du x- + - +···
3•1! 7•3!
66 CHAP. 9. Los PROGRAMAS BASARON EN RECURRENCE RELACIONES
Pista: Observa que el índice de convergencia es abajo para x > 1. Qué es el conse
quences de el uso de un ordenador con precisión finita y una gama finita de valores? (Por
ejemplo, rastro los plazos computaron para los casos x = 1, 2, 3 ...).
9.4 Construir un programa según schema (9.2) para computar el Fibonacci num bers por
dos métodos diferentes:
fo = O,
(b) Utilizando la fórmula.
Dónde e = (1 + fi)/2.
En sitio de fi uso el valor aproximado 2.236068 y determinar el menos i para qué el dos
computó valores de/; difiere.
9.5 Verificar los resultados en programas (9.13) y (9.17) por encontrar las aserciones
necesarias y suficientes después de cada declaración derivada de el indicó invariantes.
9.6 Diseño un programa basado en schema (9.2) para computar el logarithm a la base 2 de un
número real. Uso las relaciones
ifa¡ 1 �2
lim s.
n-,
= Registro (x)
9.10 Dado un ordenador capaz de representar números reales con una exactitud relativa
6
e= yo0- (10- 10, yo0- 14), determinar cuántos plazos de la serie (9.25) y (9.29)
es necesario-en el caso peor- para obtener el maximumpossible exactitud de exp
(x) para O :e; x < 1 y pecado (x) para O :;;; x < n/4 (cf. 8.28).
LA ESTRUCTURA
10 de DATO del
ARCHIVO
Las dos propiedades más características de el dato escribe habladas tan lejos
es la indivisibilidad de sus valores y la existencia de un ordenando entre ellos.
Por ello se apellidan escalares. Por ejemplo, cada valor de entero de tipo (i.e.,
cada número entero) es una unidad o una entidad sin componentes, y el conjunto
de enteros está ordenado. Por ello no hace sentido para referir al ith dígito
(componente) de un entero, pero es sensato de hablar sobre el ith dígito de una
representación decimal de un entero que él no es un entero pero una secuencia
de caracteres. En este caso, por tanto, es evidentemente conveniente de ser
capaz de referir a la representación de el número globalmente, a pesar de que
consta de dígitos individuales. Esta capacidad de dar un nombre colectivo a un
conjunto entero de elementos es de valor grande en los datos que procesan en
general. Tales conjuntos de los valores o las variables con un nombre colectivo
solo están dichos para ser struc- tured. Allí existir severa! Métodos de estructurar,
cada señalado por la manera en qué componentes individuales es accesible y por
tanto también por su denotación.
Las variables que constan de severa! Los componentes se apellidan estructuró
variables. Para definir el tipo (gama de valores) de una variable estructurada, es
necesario de especificar
68
SEC. 1 Ü. Yo LA IDEA DE Un ARCHIVO 69
Ali componentes de las secuencias es así definido para ser del mismo
Tipo T.
Ejemplo:
Archivo de texto = del tipo de char.
Tal�gama notablemente�infinita de valores puede ser definida formalmente con la
ayuda de la operación de concatenación: la concatenación de dos archivos
rJ. = <x1, X 2···xm> und /3 = <Y1,Y2···Yn>
lts El valor es por definición siempre un F. Para razones para ser explicadas en
sección 10.2, supondremos que con cada declaration de una variable de archivo f,
un addi- tional variable de escribir Tis automáticamente introdujo. Esta variable
es para apellidarse buffer variable y denotado por f j. lt Está utilizado tampoco
para anexar componentes nuevos al archivo, o para elegir sus componentes para
inspección.
Los archivos juegan una función esencial en cada sistema de ordenador. Son
la estructura apropiada para datos para ser almacenados en dispositivos con
mechanically partes emotivas para qué el acceso secuencial de componentes es a
menudo el único posible un, porque los elementos de almacenamiento están
dirigidos pasado una lectura o escribiendo dispositivo en estrictamente orden
secuencial. Las operaciones exactas qué un sistema de ordenador puede actuar
en un dispositivo de almacenamiento seguro depende de su diseño físico. Los
dispositivos siguientes son ampliamente utilizados, y el dato almacenó encima les
es normalmente considerado para ser archivos secuenciales.
70 CHAP. 10. LA ESTRUCTURA de DATO del ARCHIVO
b;} 1
b; = b;_ 1 + 2
SEC. 10.3 INSPECCIONANDO Un ARCHIVO 71
J=l] (10.1)
Este defi nition implica que the buffer variablef i supone the value of el
primer componente de archivo-si hay uno. Para proceder a el componente
próximo, nosotros introduce the standard file operador (procedimiento) get(f).
Estos movimientos de operador
72 CHAP. 10. LA ESTRUCTURA de DATO del ARCHIVO
(10.12)
SEC. 10.3 INSPECCIONANDO Un ARCHIVO 73
Mientras ,eof(f)
empieza S; (10.13)
consigue(f)
fin
Sólo si está afirmado que fes inicialmente no vacío, entonces poder utilizamos
schema (10.14), el cual bajo esta condición es equivalente a (10.13).
Repite S;
(10.14)
consigue(J)
until eof(f)
var L: entero;
Empieza L := O;
Mientras ,eof(f)
Empieza { L = número de componentes (10.15)
leyó}
L : = L + l ; consigue(J)
Fin
Fin.
Mientras ,eof(f)
Empieza leído(f,x); (10.15)
S(x)
Fin
n;
Utilizando schema (10.14), obtenemos programa
(10.17).
var/: Archivo de real;.
m,s,x: real; n: entero;
Empieza m:= O; n:= O; reinicialización(f); (10.17)
repeatn:= n+ 1; leído(f,x); m:= m+x
Hasta que eof(f) ;
m:= m/n; s:= O; Reinicialización(f);
Repite leído(f,x); s:= s + sqr(x-m)
Hasta que eof(f);
s:= sqrt(s/n); ...
Fin.
SEC. 7.4 TEXTFILES 75
10.4 TEXTFILES
Entrada de archivo )
Ordenad Program
or a
Producción de
archivo
var Entrada,
producción: texto
Las dos variables están supuestas para denotar la dos entrada estándar y
medios de comunicación de producción de cualquier sistema de
ordenador dado. lt Es por tanto sensato de someterles a las restricciones
siguientes.
l. La entrada sólo puede ser inspeccionada pero no recolocado o regeneró.
Sólo la operación consigue es aplicable. Su generación (cf. 10.12) ocurre
con anterioridad a la iniciación del programa.
2. La producción sólo puede ser generada pero no recolocado o releído.
Sólo la operación puesta es aplicable. Su inspección (cf. 10.12) ocurre
después de la terminación del programa.
76 CHAP. 10. LA ESTRUCTURA de DATO del ARCHIVO
próxima
carrera axial a lo largo del papel de forma continua y escoger una escala
tal aquel d = X¡ - X¡ _ 1 corresponde a el dis- tance entre dos líneas en el
papel imprimido. La posición del asterisco en coordenada
= X¡ está obtenido
por computar y ¡ f(x¡), multiplicando y ¡ por un factor de escala s, y
redondeando el producto a el entero próximo. Representa el número de
espacios que tiene que preceder el asterisco en la línea. En programa (10.21),
los valores siguientes están utilizados como un ejemplo.
Mientras ,eof(f)
empieza SI;
Mientras ,eoln(f)
Empieza leído(f,ch); (10.22)
S2(ch)
Fin;
S3; readln(f)
Fin
En este schema, S2 especifica las acciones para ser tomadas para cada
carácter. SI Y S3 especifica, respectivamente, las acciones para ser ejecutadas
al principio y al final de cada línea.
Si está afirmado que el archivo consta de al menos una línea y cada
línea contiene al menos un carácter, entonces schema (l 0.23) puede ser
utilizado en vez de (10.22).
Repite SI;
Repite leído(f,ch); S2(ch)
(10.23) Hasta que eoln(f);
S3; readln(f)
Hasta que eof(f)
var ch : char;
Empieza
Mientras -,eof(entrada)
Empezar escribir(' '); {control de impresora}
Mientras ,eoln(entrada) (10.24)
Empieza leído(ch); escribe(ch)
Fin;
writeln; readln
Fin
Fin.
EJERCICIOS
Tal
aquello fi +1 � /1 und gi+1 � gi for al! i,j
Diseño un programa que fusiona los dos archivos a uno archivo ordenado h tal que
hk+yo � hk para k = yo, ... , m + n - yo
10,2 Extiende programa (10.21) de tal manera que además de la función/(x), el x-axial es
también imprimió.
10.3 Escribir un programa que copias un texto/a un fileg, por el cual las secuencias de
espacios están condensadas a un espacio solo, exceptúa si estando a principios de
una línea.
10.4 Dado un textfile entrada sobre un carácter puesto con dos distinto separators
(llamado eop y eol) cuál subdivide el archivo a párrafos (eop) y los párrafos a líneas,
diseño un programa schema para inspeccionar aquel archivo, ejecutando las
declaraciones
x[!0] x[i + j]
(11.3)
y[Rojo] y[y[Amarillo]
]
Un8
�
�
Un4 Un12
�
Un2 Un6
�
Un10
/ Un14 (11.7)
/\ /\ /\
/\
Un1 Un3 Un s Un7 Un11 Un¡3 Un¡5
(11.1O)
84 CHAP. 11. LA ESTRUCTURA de DATO de la VARIEDAD
Repite { s = j x[J] *
t
JÜ]}
i := i + l ; s := s + x[1] * y [z]
Hasta que i = n
Fin.
Cuando en ejemplo (11.6), las variedades están escaneadas estrictamente
sequentially, pero en contraste a (11.6), ali los componentes están
considerados en todo momento. La secuencia en qué están accedidos, aun
así, es irrelevante-el n las multiplicaciones incluso podrían ser actuadas al
mismo tiempo.
Este caso ocurre tan frecuentemente en el procesamiento de variedad
estructura que una notación especial es apropiada. Otra vez, expresaremos
él en la forma de una cláusulaMientras
repetitivarepite
similar a el y cláusulas.
Si Sis la declaración para ser repetida, V es una variable escalara (llamado el
controlado variable), anda y b es expresiones de el mismo tipo cuando V,
entonces la declaración.
Para V:= un a b S (11.12)
especifica que las dos declaraciones
V:= x;S (11.13)
Es para ser repetido, una vez para cada valor x en el intervalo un a b.
Siguiendo la tradición de frecuentemente utilizó lenguajes de programación,
las repeticiones están ejecutadas sequentially con valores x seleccionados en
orden ascendente de un a b. Declaración (11.12) entonces puede ser
considerado como equivalente a la secuencia de declaraciones (11.14)
Empieza V:= v 1 ; S; V:= v2 ; S; . . . ; V:= vn ; Envía (11.14)
Dónde v = 1 un, v=n b, y V¡= succ(v;_ ¡) para =i 2, ... , n. (lt Sigue que la
función de sucesor tiene que ser definida en el tipo de V, los cuales por tanto
no pueden ser reales.) Declaración (11.14) puede ser representado en una
forma cerrada por programa schema (11.15).
Si un�b
Empieza V :=
entonces
(11.15) un; while
S; V< b do
b e gin V: = succ( V); S
end
Fin
LA ESTRUCTURA de DATO de la VARIEDAD 85
El preconditions es
Un {(V= un)/\ P] S {Q(un )] (11.16. l)
(b ) {Q(pre d(x))) S {Q (x ) } for ali un< x;;;;
b
Si una declaración es para ser repetido, el uso ofa para la declaración está
recomendada cuándo el número de las repeticiones necesarias es
sabidas a priori. Si su número deviene sabido sólo mientras las
repeticiones están siendo actuadas, entonces el rato y repetir las cláusulas
son las formulaciones apropiadas .
(11.27.2)
88 CHAP. 11. LA ESTRUCTURA de DATO de la VARIEDAD
s := s+ Un[i,k]*B[k,j]
Domina completamente. De este, aprendemos el sencillos pero lección
importante que el "innermost" la declaración repetida tendría que ser
formulada con el cuidado más grande para minimizar computación y
maximize eficacia. El esfuerzo gastado en una multiplicación matricial crece
con el tercer poder de n, suponiendo que m =n =p [cf.Exercise (11.8)].
EJERCICIOS 89
EJERCICIOS
binario
i := m;j := n; (11.32)
Repite k : = (i + 1) div 2;
Si Un[k] 2 x entonces
i:= k+ l; si Un[k] � x
en ton c es j := k - l
Hasta que i > j
Yo 1.4 Un polinomio
(11.35)
Está representado por la variedad de coeficientes un. Diseño una informática de
programa Pn(x) para un dado x. Pista: factorización de Uso según Horner;
aquello es,
P.(x) = (· · · (Un0 x + un1 )* x + · · · + unn_ 1 )* x + ª• (11.36)
11.5 Diseño un programa que encuentra el más grande y el valor más pequeño en una
variedad de n números
var Un: array [! ..n]De entero.
Construir un programa que asigna los números naturales 1, 2, ..., n2 a el com ponents de
M tal que forma una plaza mágica; aquello es,
f M[i,kJ f
=k=yoM[k, 1] = e
i = 1, .. . ,n
k=Yo
Dónde C = (n/2)(n2 + 1). Supone n para ser extraño. Pista: Asignar los números 1,
..., n2 sequentially a componentes de M, empezando con 1 en M[i,j] = M[(n+ 1)/2,
n], entonces aumentando i andj por 1 (modulo n) cada vez para n - 1 pasos, y
decreasingj por 1 y dejando i sin cambios en cada nth paso.
11.7 Dado el problema para computar el primer n + 1 plazos en la serie que representa el sine
función [cf. (9.29)] para argumentos x tal que O � x � n/4, el programa siguiente
estuvo diseñado. (s Es presuntamente el resultado.)
-¿ k=Y o
Xzk* Xzk-1 - L
k=yo
Y2k* Y2k-1
'-----v----' '-----v----'
x y
Pista: El problema requiere la computación de 4n 2 productos escalares de la
forma
Y
2n
X¡k* Ykj
k=Yo
o
Utilizando (11.38), sólo 2n valores x y y está necesitado.
El método habitual de multiplicación matricial (11.30) requiere 8n3 adiciones y
multiplicaciones. Determinar el número ofoperations requirió por vuestro
programa como función de n..
SUBRUTINAS,
12 PROCEDIMIENTOS, Y
FUNCIONES.
12.2 LOCALITY
Un = ( _ �:) yB = (: - :)
3. mult(Un, B, B) cosechas B = (
7
º)·
-4 6
98 CHAP. 12. SUBRUTINAS, PROCEDIMIENTOS, ANO FUNCIONES
No t e thunt t correct results in stun te ent yo cunn be lobtuni ed in unli three Casos,
if x Unnd y unh re specifi ed uns vunlue_p unrum
nmeter s [see un so Exnercise 11.1].
Un pro cedbu
is to e re ted durinGFthise exusod
orufunción
comp ecutioun
n los fun parameter o un
Divertidoc tion G , if F G, unf n d
different procedures or functions in diff erent cun ls of G. Nosotrosll-sabidos
proc dure or
f F rep
iLos resents son algoritmos para computar un G integral de una función
ejemplos
F.
s = rf(x)dx (12.9)
Computamos
h la suma de un número finito de valores de muestra ¡;.
= Uo + 4f¡ + 2f2 + 4J3 + 2f4 + · · · + 4fn-3 + 2fn -2 + 4fn-1 + fn)
Sk
3
(12.10)
k
where ;¡ = f(Un+ i * h), h = (b - un)/n, Y = n 2 . The number of Muestra
poi nts is n + 1, unnd h is the distancia between uny two adyacente sample puntos.
The integrUn l vun lue s Es entonces aproximado por la secuencia s , s •••,,s
w hic cconverges i,1f th2e 3s function is sufficiently well behaved (Liso) y si.
Unn exh un t unrithmetic is un sumed.
(12.11)
-- ------+--+----+----+--+----+-----11---
Un b
•x
k=
Yo
k=2
k=3
SEC. 12.4 PROCEDIMIENTOS PARAMÉTRICOS Y FUNCIONA 99
Denota la asignación.
n/2 f
0
u = Pecado(x) dx
n/2
f
llamado-facilidad de parámetro.) Para caso, para computar
dx
u= 2 - - �- - -
( 12.17)
0
-
Un( c os x + b sin_2x __
_2_ _ _ _ )½
(12.19)
Sólo entonces es posible de expresar (12.17) por la declaración
u : = Simpson(O, n/2, F)
EJERCICIOS
12.1 Formula programas (7.18), (7.22), (9.17), (9.28), (10.21 ), ( 11.24), y (11.30)
Cuando procedimientos o funciones con suitably parámetros escogidos.
12.3 Ejecutar el siguiente tres programas y determinar los valores de los parámetros
reales del escribir declaraciones.
2 r 12 dx
f = 1t Jo (un2 cos 2 X+ b2 pecado2 x)½
f1(x) dx
Por la secuencia
lo.o, l1,0, 12,0, • • •
Cuál es convergente para suficientemente bien-behaved (liso) funciona f Los plazos
están definidos por el recurrence relación
1
m _ (4 * l
m
l =- -l )
m,k
4 ¡ m-1,k+yo m-1,k
_ b -Un 1
lo.k - ( do+ f1 + •·· + Í. -1 + z1 f.)
n
Dónde n = 2k y ¡; = f(un + i * (b - un)/n). Formular una función declaration con
parámetros un, b, y f y aproximar la integral (según Rom berg) a una exactitud
relativa especificada r.. Pista: El programa tiene que evaluar la función f sólo una vez
en cada punto de muestra. En cada paso, el número de punto de muestras is plegó.
Nose Unn array variable T such that unf ter el kth paso
12.6 Dejado un "cero" ofa real-función valorada f(x) ser definido como el valor x0 tal aquello
103
104 CHAP. )3. TRANSFORMACIONES DE REPRESENTACIONES de NÚMERO
(13.1)
n ¡ 2 n- n
i= 1
Este esquema es más apropiado cuándo un archivo de entrada tiene que ser
leído, donde las secuencias de dígitos son embedded dentro de un texto
general (en un programa, por ejemplo).
Fin
Hasta que i =n
Este programa puede ser fácilmente mejorado en dos respetos.
2. Por introducir una variable auxiliar v, las dos declaraciones que implican el
(normalmente caros) div y mod las operaciones están reemplazadas por
13.2 PRODUCCIÓN DE
FRACCIONES EN FORMA
POSICIONAL
O� Ó¡ < 1
J¡ = trunc(B * ó¡)
(13.10)
ó¡+ 1 = B• ó¡ - d¡
13.3 TRANSFORMACIÓN DE
REPRESENTACIONES- de PUNTO
FLOTANTE
(13.12)
Como scaled entero. Por tanto imponemos la restricción que las condiciones
(13.14)
(13.16)
Y entonces computando
m: = m* Ue¡, e2: = Vel (13.17)
Seguido posiblemente por postnormalization. Aun así, la medida de tal
mesa puede ser intolerably grande, si la gama de el exponente es grande.
Un aceptar- capaz compromise, requiriendo ligeramente más
computaciones pero basados en una mucha mesa más pequeña, consta de
tabular pares de exponente del coeficiente sólo para
1
- B< 21">
U k * B"2" - -$;u k <l (13.18)
B2 -
EJERCICIOS 1 09
EJERCICIOS
13.1 Formula dos procedimientos que
(a) Leído un número decimal representado por una señal, una parte de entero, un
punto decimal, y una fracción de el textfile entrada y assi gn su valor a la
variable paramétrica real v [cf. (13.6)], y
(b) Escribir una representación decimal de un parámetro real x a la producción de
archivo [cf. (13.8) y (13.1 !)]. Supone que lxl �max y que el entero ypartes de fracción
de x está representado por m y n dígitos, respectivamente. Principal zeroes
tendría que ser reemplazado por espacios.
13.3 Design un procedimiento a transforrn una representación de punto flotante con base 2a
una representación con basa yo O, utilizando una mesa de n pares de exponente del
coeficiente según ( yo 3.18). Supone aquello
X= m * 2et O :e; el < 2n
Para un dado n (dice,
10).
13.4 Construir un programa que genera representaciones decimales exactas de el frac-
tions 1/n para n = 2, 3, . . . , 50 cuando describió abajo y escribir las secuencias de
dígito resultantes a la producción de archivo.
(a) Cada secuencia de dígito tiene que termínate apenas el primer periodo de la
fracción decimal está completado.
(b) Un espacio tendría que ser insertado inmediatamente precediendo el primer
dígito de el periodo.
(c) Ningún real-valoró las variables tendrían que ser utilizadas en este programa.
Imprimiendo el textfile resultará en el cuadro siguiente:
.5 O
.3
.25 O
.20
.1 6
.1428 57
.020
Pista: Primero desarrollar un programa que ignora condición (b).
13.5 Diseño un procedimiento para escribir al textfile producción el valor del parámetro
de entero x como número Romano. Supone x > O. (' Yo' = 1, 'V' = 5, 'D' = 10, 'L' = 50,
'C' = 100, 'D' = 500, soy' = 1000.)
PROCESAMIENTO DEL TEXTO
que UTILIZA ARRAV
14 Y ESTRUCTURAS de ARCHIVO
Esto, aun así, puede ser decidido sólo después de la longitud de la palabra
es sabida. Por tanto sigue que copiando la palabra es posible sólo a través
de inter- mediar buffering. Como buffer, una variable de variedad con
wmax los componentes es la elección apropiada (suponiendo que wmax es
moderadamente pequeño).
Desde file f consistes of una secuencia of palabras y separator caracteres, la
estructura apropiada del programa es una declaración repetitiva. En cada
repetición, una palabra W y su teniendo éxito separator S está leído de archivo
f, y la misma palabra y su precediendo separator es entonces producción para
archivar g, cuando mostrado en figura (14.1).
(14.1)
f { w s 1 w s 1 w ,. s 1
G l w1 s1 w1 s1w1 s }
Paso i : Paso i+ 1
Un caso en qué severa! separators Sigue una palabra (i.e., espacio múltiple
o severa! Líneas de espacio) está manejado por suponer que las palabras
pueden ser vacías y que unas mentiras de palabra vacías entre cada dos
inmediatamente adyacente separators. De este modo, el carácter estrictamente
alterno de la palabra/separator la secuencia es (hipotéticamente) mantuvo.
La declaración repetida está obtenida de programa schema (10.13).
Herramientas tan auxiliares, primero introducimos dos informalmente
definió procedimientos.
l. Readword Lee una palabra al buffer variable Z. Después de que
ejecución de readword, ch representa el separator siguiendo la palabra
justo leída y almacenado en Z. La variable de entero w está asignado el
wordlength.
2. Writeword Anexa la palabra de longitud w almacenó en Z para archivar g.
Empieza readword;
Si L + w < Lmax entonces
Empezar escribir(' '); L : = L +
Fin más (14.2)
Empieza writeln; L : =
O
Fin Fin;
writeword
112 CHAP. 14. PROCESAMIENTO DEL TEXTO que UTILIZA VARIEDAD Y ESTRUCTURAS de ARCHIVO
f w 1.-s i w yo ¡ 1 s
.-
w
'
s
(14.3)
g w Yos¡ !
w í s w 1s 1
Paso O¡ ¡ Paso n
En el paso inicial, uno más el carácter está leído que está escrito, y en el paso
final, uno más está escrito que está leído. El programa final está mostrado en
(14.4). El lector se tendría que convencer que los dos procedimientos
auxiliares procesan palabras vacías correctamente. (La entrada de archivos
estándar y la producción están utilizadas en cambio fueray g).
var w: O.. wmax; {wordlength} L:
O .. Lmax; {linelength}
ch: char; {Último carácter leyó}
Z: Variedad [l .. wmax] De char; {buffer}
Procedimiento readword;
Empieza :=
w O;
Mientras hacer
Empieza w: = w + 1; Z[w] : = ch; leído(ch)
Fin
Fin;
Procedimiento writeword;
var i: l .. wmax; (14.4)
=i:
Empieza para l a w escribe (Z[i]); L : =
L+w
Fin;
Empieza L:= O; leído(ch); readword;
writeword;
Mientras ,eof(entrada)
Empieza leído(ch); readword;
Si L + w < Lmax entonces
Empezar escribir(' '); =
L : L+1
Fin más
Empieza writeln; L := O
Fin;
writeword
Fin;
writeln
Fin.
SEC. J 4.2 EDITANDO Un UNE DE TEXTO 113
¡ :=p;
Repite { Q(i)}
q :=X= (z¡ ...Z;+k- 1); (14.7)
i : = i + l ; Si i > n entonces i :
= yo hasta q V (i = p)
xd-:/- (zj···zj+k-i)
(x 1 • • •
r1o un ¡¡ J. = P, ..., i - 1 Si i � p
{
p, ... , n y 1, ..., i - 1 si ¡ < p
Ahora más allá descomponemos la comparación de dos secuencias de
caracteres a una secuencia de comparaciones de caracteres solos.
j := !;
Repite { P(j)}
q :=(x[j] =z[i+j-1]); j :=j + 1 (14.8)
Hasta que ,q V (j > k)
j := l;
Repetir si i + j > n entonces = q : falso (14.10)
más
q : = x[j] = z[i + j- 1]; j := j + 1
Hasta que ,q V (j >
k)
Sustituto de procedimiento;
vari,j: l ..n+l; q:Booleano; d:entero;
begin { step Yo: find x i n line z}
i :=p;
repeEn j : = yo ;
repeatq: =(x[j] = z[i+j-1]); j :=j + 1
Hasta que ,q V (j > k);
i:=i+ l;ifi>ntheni:= Yo hasta
q V (i = p);
116 CHAP. 14. PROCESAMIENTO DEL TEXTO que UTILIZA VARIEDAD Y ESTRUCTURAS de ARCHIVO
Si q entonces
Empieza {paso 2: sustituto y para
x} d : = m - k; p : = i;
ifd<Othen
begin j: =p + k;
whilej �n Hacer
Empieza z[j+d]=: z[j];j: =
j+ 1 (14.11)
Fin
Fin más si d
> O entonces
beginj: = n;
Mientras j � p + k Hacer
Empieza z[j + d] : = z[JJ; j : = j - 1
Fin
Fin;
n:=n+d;j:=1;
whilej � m Hacer
begin z[p] := y[j];p := p + 1 ;j:= j + l
Fin
Fin
Fin
14.3 RECONOCIMIENTO DE
PATRONES REGULARES DE
SÍMBOLOS.
l. Un
2. (ab[bc)(d[Un) (14.15)
3. ab*c 4.
Un((b[c)un)
*
1. Un
2. abd aba bcd bca (14.16)
3. ac abe abbc abbbc ...
4. Un aba aca ababa abaca acaba acaca ...
Nuestra tarea ahora puede ser reformulated: dado una expresión regular Un
definiendo un conjunto de frases sobre el vocabulario Vand dado cualquier
secuencia un ofsymbols
118 CHAP. 14. PROCESAMIENTO DEL TEXTO que UTILIZA VARIEDAD Y ESTRUCTURAS de ARCHIVO
---..•�0 �
Expresión Graph
Un
AB
--0----0- (14.17)
Un
IB
Un*
(14.18)
El algoritmo tendría que ser tal que cada decisión (representado por un
tenedor de caminos en el graph) puede ser tomado por inspeccionar el
carácter solo próximo sólo. Así describimos un esquema por qué un algoritmo
de análisis puede ser método- ically construyó de una expresión dada. Aun así,
las reglas de construcción aplican sólo si la expresión es determinista, aquello
es, si contiene no con-
stituents De las formas
AIB Y Un*B (14.19)
aAlaB = Un(AIB)
(aA)*aB = un(Aa)*B (14.20)
Y
(aA)*Unl (aB)*un =
un((Unun)*l(Ba)*)
Reglas de
construcción
Prueba(un); leído(ch)
l. 37'(un) 37'(Un); 37'(B) (14.21)
2. 37'(AB) Si ch= un entonces
3. 37'(aAIB) Empieza leído(ch); 37'(Un)
acaba más 37'(8)
= un hacer
Mientras ch
4. &((UnUn)*) Empieza leído(ch); 37'(Un)
fin
2. &'(Un(b(cld))*e) =
Prueba(un); leído(ch);
Mientras ch = b hacer
Empieza
leído(ch);
Si ch = c entonces leído(ch)
más empezar prueba(d);
leído(ch)
Fin
Fin;
Prueba(e); leído(ch)
3. P((ab*c)*d) =
Mientras ch = un
empieza
leído(ch);
Mientras ch = b lee (ch);
prueba(c); leído(ch)
Fin;
Prueba(d); leído(ch)
EJERCICIOS
más empezar w := O;
Repite w := w + 1; Zfw] := ch; leído(ch)
Hasta que ch= 1 1
122 CHAP. 14. PROCESAMIENTO DEL TEXTO que UTILIZA VARIEDAD ANO ESTRUCTURAS de
ARCHIVO
Investigar las propuestas siguientes. Qué unos son correctos? Jndicate Las
condiciones bajo qué el incorrect unos fallan.
(a) k := Yo;
fori:= Yo toLdo
begin ifi = p[k]
entonces
Empezar escribir('*'); k := k + yo
Fin
Más escribir(' ')
Fin
(b) k : = Yo ; p[n + l] : = O;
fori : = yo a L empieza
ifi = p[k] entonces
Empezar escribir('•');
Repite k : = k + yo untili#- p[k]
Fin
Más escribir(' ')
Fin
(c)i:=l;
Para k := 1 a n hacer
Empezar repetir escribir(' ');i := i
+ hasta i = p[k];
Escribe('*'); i : = i +
Fin
EJERCICIOS 1 23
(d) i: = 1; k : = 1;
Repite
Mientras i < p[kJ hacer
Empezar escribir(' '); i := i +
Fin;
Si i= p[k] entonces
Empezar escribir('•');i := i + 1
Fin;
k := k + 1
Hasta que k > n
(e) i : 1; k : = 1; =
whilek::; n Hacer
Empezar mientras i < p[k]
Empezar escribir(' '); i:= i+
Fin;
whilep[k] = idok := k + 1;
Escribe('•')
Fin
14.3 Diseño un programa que cuentas el número ofoccurrences ofeach carácter en el
archivo f Representar el resultado por un variable N, declarado cuando
Procedimiento Transmitword;
var i: O ..M ; j: O .. N ; f: Abucheo/ean;
Empieza i: = O; {Z[k + 1] = ' ', O < < k N}
Repite i: = i + 1; j : = O;
124 CHAP. 14. PROCESAMIENTO DEL TEXTO que UTILIZA VARIEDAD Y ESTRUCTURAS de ARCHIVO
14.6 Desarrollar un programa según las reglas de construcción (14.21) y (14.22) para
el análisis de expresiones de aritmética. El vocabulario es
V=()c+-*I·}
Dónde Je posiciones para cualquier letra. La estructura de la entrada está dada por
la expresión regular
).((*1/)J.)*(( + 1- )).((*!/)),)*)*.
15 STEPWISE
PROGRAMA
DESARROLLO de
(15.2)
(15.3)
De este sistema, coeficientes nuevos un\r 1 > y b \k+ 1 > está computado tal que
forman un sistema de n - k ecuaciones.
= (k + 1)
n
dk + 1) *
" b i = k+ l,... ,n (15.5)
XJ.
+
1
L,, k
j=
lj
(15.7)
Esto significa precisamente que en el sistema nuevo, ali coeficientes de el
desconocidos x k es cero, así eficazmente eliminando xk . Nota que es por
tanto unneces sary a de hecho computar los coeficientes un\Z + 1 >.
Después de que n - 1 pasos, el sistema reducido
(15.8)
Emerge de qué x n puede ser determinado inmediatamente. El remammg
unknowns está computado por sustituir el ya obtenido unknowns en el
anteriormente computó ecuaciones. Para caso, x n - 1 está obtenido por sub
stituting Xn en
(15.9)
Este proceso se apellida un atrás-paso de sustitución. El kth el paso está
expresado en la forma general
(15.10)
Para arbitrario i tal que k �i � n. (Para razones que será aparente más
tarde, i =
k es normalmente seleccionó.) Observa, aun así, que la secuencia
en qué el atrás-pasos de sustitución están ejecutados está fijado por el
hecho que para la computación de x k , los valores xk + 1, • • • , x n tiene que
ser sabido.
SEC. 15.1 SOLUCIONANDO Un SISTEMA DE ECUACIONES LINEALES 1 29
Eliminación:
l.
._J
2 5 4 *3/1 *-2/1
3 4 11 b"' ,_j
-2 5 9 -7
2.
- --
¡- --
Un<2> 1 -5 -11 -1 b<2> *9/-5
--
1 9 19
/
3.
.----
- -4/5
t -4/5
Atrás-sustitución:
l. X3 = (-4/5)/(-4/5) = 1 -�
2. x2 = ( - l + 11* l)/( -5) = - 2 ---------------------------------- �
3. X ¡ = ( +4 - 5* l - 2*(-2))/1 = 3--- �
Y formular el programa
Al llegar a este punto, tenga que ser observado que para la computación
de un\r 1 >
(Und W + 1)) según t o (15.6), the factor ai1 / ai�(bt> / ait respectively ) es
SEC. ]5.1 SOLUCIONANDO Un SISTEMA DE ECUACIONES LINEALES 131
Nota que aquí el uso está hecho de la regla que declara que el para
la declaración no causa ninguna acción si el límite especificado es menos
de el valor inicial de la variable controlada.
132 CHAP. 15. STEPWISE DESARROLLO de PROGRAMA
Está ejecutado
De dos plazas en vez de cubos. Mesa (15.2 2) contiene tales sumas en un un
ordered arreglo tal that Sii = i2 + /.
j 2 3 4 5 6 7 8 .. .
2
2 5 8
3 10 13 18
(15.2 2) 4 17 20 32
5 26 29 34 41 50
6 37 40 45 52 61 72
78 50
65 68 758
3 65
80 789
4 85
100 113 1 28
9 82
La mesa muestra
aquello 50 = 12 + 72 = 52 + 52
65 = 12 + 8 2 = 42 + 72
85 = 2 2 + 92 = 6 2 + 72
Y que 50 es por tanto el deseado menos número. La tarea principal ahora es
para encontrar un método de búsqueda que cede los candidatos en arder de
crecientes magni tude; aquello es,
2, 5, 8, 10, 13, 17, ..., 45, 50, 50
Los hechos siguientes son útiles y determinará los desarrollos futuros.
Está introducido tal que su kth el elemento representa el índice ofthe último
gener comiód candidate in el kth row ofel table;aquello es,
S[k] = k3 + j[k] 3 ( 15.25)
Ifthe Índice i ofthe último candidato considerado está utilizado en cambio
ofthe candidato x itselfand ifa función p(k) = k 3 está introducido, entonces
una segunda versión ofthe el programa puede ser formulado.
VERSIÓN 2: i: =1;
Para k =
: l a ? Hacer
beginj[k] : = 1; S[k] : = p(k) + l (15.26)
end;
Repite min : = S[i];
l : "increment j[i] Y reemplazar S[i] por el candidato
próximo en el ith fila"
2: "determinar un valor nuevo de i como el índice de la
fila con el Ieast candidato"
Hasta que S[i] = min
= lejano es "x
La declaración única que necesidades el refinamiento más
: número primo próximo." Es también el único uno refiriendo a el hecho
que somos para generar números primos en cambio ofany otro amables
ofnumbers. Introduciendo una variable Booleana prim, pueda ser
expresado cuando
Considerando el hecho que con la excepción ofthe primero, ali los números
primos son extraños, el esfuerzo computacional deprisa puede ser halved.
lfthe Número 2 está tratado como caso especial , entonces x puede ser
incremented en pasos de 2. La tarea próxima es a refine la declaración.
x x
lim = x - l. Pero es suficiente y más económico de escoger lim = yx,
desde entonces si x era divisible por un número k > yx, entonces podría
ser expresado como = k * j, el cual implica que x también sería divisible
por < j yx. Pero esto ya ha sido probado no para ser el caso.
SEC. 15.3 DETERMINA EL PRIMER n NÚMEROS PRIMOS 1 39
p[lim] >
Jx Y p[ lim - yo] ;::;
Jx (15.39)
Tan lejos, siempre supusimos que los valores p¡,... , Pi;m era sabido, aquello es,
anteriormente computó. Pero esta condición será satisfecha sólo si el candidato
x para ser probado es siempre menos de Piim , aquello es si, en cada caso,
p[i] < p[i - 1] 2 (15.40)
Afortunadamente, esta relación es una de los resultados más profundos de
teoría de número y controles para ali números primos. Notamos que el
índice lim tiene que ser redeter mined siempre que x es incremented y
también tiene que ser aumentado siempre que Piim ;::; x. Aumentando de lim
por 1 es suficiente porque x había sido incremented por único 2 desde la
última prueba y porque p¡+ 1 > p¡ + 2 para ali i. Estos con siderations Iead a
versión 5-escrito como programa completo-cuál summarizes los
desarrollos hicieron tan lejos.
Finalmente, la declaración
prim : = "x No es divisible por p[k]"
Tiene que ser sometido a refinamientos más lejanos. Con los operadores
introdujeron en Sección 8.1, el encima la declaración fácilmente puede ser
expresada tan tampoco
prim := (x mod p[k]) i= O (15.42.1)
O
prim : = (x d iv p[k]) * p[k] i= x (15.42.2 )
Esto bien puede ser considerado como el paso final en la construcción de un
programa para encontrar números primos. Dejado nos, aun así , supone que
el programa es para ser desarrollado sin la disponibilidad de un operador
de división explícito. En este caso, el stepwise proceso de refinamiento tiene
que ser llevado en más lejano. Evidentemente, la división puede ser
reemplazada por una secuencia de sustracciones y expresados por otra
declaración repetitiva.
r := x; (15.43)
Repite r: = r - p[k] hasta r � O;
prim := r < O
Aun así, desde esta declaración será ejecutada bastante frecuentemente y
el proceso de la sustracción repetida por tanto puede ser bastante costosa,
parece para ser particularmente apropiado de buscar potencialmente
más económico solu tions. Uno solución apropiada y al mismo tiempo
sencilla consta de tabular ningún t only the prime números p 1, • • • , Pum but
also their múltiplos Vk = m * Pk tal aquello
x � V[k] < x + p[k] para k = 2, ... , lim (15.44)
En este caso, el divisibility de x porP k sencillamente puede ser
determinado por com parison of x ingenio h Vk. Yof ingenioh due respeto
to the extremely frequent evalua tion de Pl m- introducimos una variable
auxiliar llamó cuadrada cuyo valor es
Cuadrado = p[lim] 2 (15.45 )
Entonces obtendremos la versión final del programa.t
t E. W. Dijkstra, "programación Estructurada", EWD249, T. H. Eindhoven (1969).
SEC. 15.3 DETERMINA EL PRIMER n NÚMEROS PRIMOS 141
VERSIÓN 6:
Índice de tipo = 1 .. n;
var x, plaza: entero;
i, k, lim: índice; prim: Booleano;
p: variedad [índice] de entero;.
V: variedad [yo ..JnJ De entero;.
beginp[Yo] : = 2; escribe(2); x: = 1; lim : = 1; cuadrado: = 4;
Para i : = 2 a n
Empieza
hacerRepite x : = x + 2;
Si cuadrado � x
entonce
s ( 15.46)
Empieza V[lim] := cuadrado;
lim : = lim + 1 ; cuadrado : = sqr(p[lim])
Fin;
k := 2;prim := cierto;
Mientras prim /\ (k < lim)
empieza si V[k] < x
entonces
V[k] : = V[k] + p[k];
prim := (x # V[k]); k := k + 1
Fin
hasta prim;
p[i] : = x; escribe(x)
Fin
Fin.
Este ejemplo claramente demuestra que por ser forzado para trabajar con
un más sencillo también! (Un ordenador sin construido-en división), el
programador está dado el incentivo para buscar una solución que
finalmente resulta para ser superior. No es uncommon para encontrar que
la disponibilidad ofvery los ordenadores potentes con tiendas grandes
desalenta programadores de refinado sus algoritmos a la mayoría de
adecuados, pertinentes, y versión económica.
La mesa siguiente muestra la frecuencia ofexecution ofthe cuatro
declaraciones diferentes en (15.46), dependiendo de el número n ofprime
numera para ser computado.
n= 10 20 50 500 1000
(15.47)
142 CHAP. 15. STEPWISE DESARROLLO de PROGRAMA
(15.53)
Cont
rol
SEC. 15.4 Un ALGORITMO HEURÍSTICO 145
U Extien
n de
Cambio
(15.55)
Contr
ol
Contr
ol
Incluso sin un elemento S[O], y el programa principal (15.54) puede ser fu rther
simplificó a
Repite extiende;
control; mientras
, bien hacer
ltegill Cambio; control etNI
U11til m = N
= _! (m 3 + 3 * m 2 + 2 * m) ( 15.58)
24
para incluso m y
N(m) = (m - !) * 1 (m - 3)
+ (m - 3) * 2 + · · · + 4 * - - + 2 * �-- (m- 1 )
2 2
= -1 (m 3+ 3 * m 2- m - 3) (15.59)
24
Para extraño m. Para grande m, N(m) aparentemente crece con thc tercer
poder de m y hace la utilidad de este programa dudoso. Aun así, su eficaz
ness puede ser drásticamente mejorado después de sorne deliberaciones
más lejanas. Cada candidato Swas generó por anexar un elemento solo a
una secuencia certificó tan bueno. Consiguientemente, basta para comparar
sólo aquellos adyacente sul>-secuencias que incluye el último carácter
anexado, aquello es, ali pares
(15.60)
SEC. 15.4 Un ALGORITMO HEURÍSTICO 147
,, 1""' �
3 2 2 3 (15.66)
�
'-._./
SEC. ) 5.4 Un ALGORITMO HEURÍSTICO 149
var S: Variedad [l .. N] De
char; m: entero; bueno:
Booleano; (15.67)
El procedimiento extiende;
Empieza m=: m + 1 ; S[m] : = '!' Fin;
cambio de procedimiento;
Empieza {cf. (15.56)} fin;
control de procedimiento;
Empieza {cf. (15.64)} fin;
impresión de procedimiento;
var i: Entero;
Empieza para i: = 1 a N escribe (S[i]);
writeln
Fin;
begin m : = 2; S[l ] : = 'l'; S[2] : = '2'; good: = cierto;
Repetir si bien entonces
Si m = N entonces empezar impresión;
fin de cambio más extiende
Más cambio;
control
Hasta que m = 2
Fin.
EJERCICIOS
15.1 El programa para solucionar un sistema de las ecuaciones lineales dadas en (15.17)
puede ser simpli- fied, si el variable Bis representó como una columna adicional de
matricial Un; aquello es,
(""
ª12
Un ª22 ª2• h2
= ��'.
Unn l ª•2 ª·· b.
Varían/ 1: yon the kth paso de eliminación, ali componentes of row un\k> are
multiplicó con el mismo scalingfactor st> (í = k, . . . , n). Nota que las solucionesj
ciertas x no es afectado por tal multiplicación. Aun así, exactitud del computado
resulta x puede ser mejorado. Escoge
j
j�k
s\k> = 1 /f un\? Para i = k•... , n
EJERCICIOS 1 51
Variante 2: En el kth paso de eliminación, todos los componentes del jth la columna
está multiplicada con el mismo scalingfactor s/> (j = k, ..... , n). El computó resultados
xj Tiene que ser reajustado consiguientemente en el atrás-fase de sustitución. Escoge
�)
sj = l
Yo i�k
n
unw ij ...................... for J
.
= k, ,n
15.4 Diseño un programa para solucionar el sistema siguiente de n ecuaciones lineales, dados
los coeficientes un;j y b;..
ª11*X1 +un12*X2 = b1
for k = 2, . . . ,n - 1
Si los coeficientes un;j está arreglado en la forma de una matriz, entonces el siguiente
tridiagonal La forma está obtenida.
Un,._ ,. -1
ª"·"
Pista: En el kth paso de eliminación, sólo el siguiente dos coeficientes tienen que ser
computados.
Todos otros coeficientes quedan igual. El tridiagonal la matriz está representada por la
variable de variedad
Dónde los coeficientes un\;1 está denotado como[i,j - 1]. De este modo, coeficientes que,
por definición, es idéntico a cero, no ocupa cualquier almacenamiento.
152 CHAP. 15. STEPWISE DESARROLLO de PROGRAMA
¿ Un, * x = b,
Para i = 1, ... ,
j= 1 j j
n
En este caso especial, el no-cero coeficientes un,j forma la matriz triangular
ª11
Un ª··
Aviso que el algoritmo Gaussiano nl de eliminación puede ser significativamente
simplificado y que único ½n(n + 1) los coeficientes tienen que ser almacenados. El
matricial un,j es por tanto representado por la variable de variedad
15.6 Extiende programa (15.34) de tal manera que él generales no sólo el menos pero el 1O
los números más pequeños representables cuando dos sumas diferentes de dos
terceros poderes de números naturales. Estos diez pares de sumas <un,, b;) es para
ser seleccionado tal que sus plazos son linearly independientes; aquello es, tiene que
haber ningún multiplier n tal aquello
Un, = n * unj y b; = n * bj i# j
15.10 Por cambiar programa (15.46) según (15.70) y por cambiar la cláusula.
Mientras n < lim hacer (15.71)
A mientras n 2 lim hacer
El programa deviene falso. Cuál es la invariante ignorada y así violada ? Reteniendo los
dos cambios, cómo puede el programa ser fácilmente corrigió? Es la versión
resultante más o menos eficaz que el algoritmo de (15.46)?.
15.11 La conclusión.
x#Un "x" no es divisible por " p
x 2 un < x + p y un = n * p
Es ambos satisfecho. Verifica por inserción de las aserciones pertinentes que estos condi-
tions es invariantes de el programa parcial siguiente [extraído de (15.46)], si p es un
número natural más grande que 2.
x:=l;Un:=0;
Repite x : = x + 2 ;
=
Si un < x entonces un :
un + p ;
{x 2 un < x + p, un = n* p}
Hasta
P (15.72)
1 54 CHAP. 15. STEPWISE DESARROLLO de PROGRAMA
15.12 Desarrollar un programa que genera en orden ascendente el menos 100 números del
conjunto M, donde M está definido como sigue..
(a) El número es en M.
(b) Ifx Es en M, entonces y = 2 * x + 1 y z = 3 * x + 1 es también en M.
(c) No other Números are in M. (M = {!, 3, 4, 7, 9, yoO ... })
15.13 Figura (15.73) muestra un anillo de 2 3 zeroes y unos en qué cada cual de el 2 3 posible
sub-las secuencias de 3 dígitos binarios ocurre exactamente una vez.
(15.73)
1
\
Diseño un algoritmo que generales tal anillo, constando de 2" dígitos que contienen cada
posibles sub-secuencia de n dígitos exactamente una vez. Seguir el principie de
stepwise refinamiento de programa.
SÍMBOLOS BÁSICOS
}
Si entonces más caso de con asignación de
Mientras repite hasta que para a
const Tipo var archivo de variedad de paréntesis de
función de procedimiento conjunto declaración cita marca
separators
récord
Símbolo de puntero
Cero
goto Etiqueta Declaración separators
Estructura de
especificadores de clase de
objeto especificadores de
clase null puntero
Operador de salto, !abe! declarator
Tipos:
IDENTIFICADORES ESTÁNDARES
(8.1)
(8.1-8.4)
155
1 56 APÉNDICE Un
V /\ , O ANO NO
=Yo= ;;;;; � < > <= >e:
{ } (• •)
APÉNDICE Un 157
SINTAXIS
IDENTIFICA Letra
DOR
Letra
UNSIGNED ENTERO
..
t·® l
UNSIGNED NÚMERO
u_nsigned
Entero
UNSIGNED CONSTANTE
-----------.....-- constant identifier ----.----------
Carácter t-----.--
CONSTANT
E Constante
identifier
unsigned Número
---------------------- Carácter
1 58 APÉNDICE Un
TIPO SENCILLO
-- Constante
TIPO
Empaq
uetado
LISTA de CAMPO
Lista de
campo
APÉNDICE Un 1 59
VARIABLE
vUnriu
n ble
id
e nt ifier expression
field
identifier
Identificador
de campo
FACTOR
unsigned Constante
function
1---------------' variable identifier
Expresión
PLAZO
ac
4�$
----<•Myo f A rf �----,r---------,----,------. ----- �--•
�f�A,1•<>
�
1 60 APÉNDICE Un
EXPRESIÓN SENCILLA
EXPRESIÓN
COLA COMPUESTA
LISTA de PARÁMETRO
Identific Tipo
Identifica
ador dor
DECLARACIÓ
N
Identific
ador de
función
Expresión
Variable
Expresión
Mientras expresión
Identific
ador Expresión
variable
Declaración
BLOQUE
Identific
ador
Lista de
parámetro
PROGRUnM
b6 o o o o 1 1 1 1
oo o1 1o
o o1 1 1
bb4s 11 o o 1
3-bo b
0000 nul Dado o @ p p
0001 soh del ! 1 Un Q Un q
" b
0010 stx dc2 2 B R r
0011 etx dc3 # 3 e s e s
0100 eot dc4 $ 4 D T d t
0101 enq nak '.i� 5 E u e u
0110 ack syn & 6 F O111 V f V
belio etb 7 G 1000 w G w
bs puede ( 8 H X h X
1001 ht em ) 9 1 y i y
1010 lf sub * J
z z
ll
jk
1011 vt ese + K t[
1100 ff fs < L
\ 1
1101 cr qs - = M ] m
1110 así que rs > N - n
1111 SI nos / ? o o del
Puso
t Undefined En el Estándar de ISO. Los símbolos varían entre versiones nacionales
diferentes; esto es el ASCII versión.
163
164 APÉNDICE B
Caracteres de
• ••••••
1 diseño: bs
ht backspace
Tabulación
-
> ••••••••
••
•• •••
,-.,
N
'-
horizontal lf
alimenta
vt
la línea
Tabulación vertical
'
•• ••••••X
tf La forma
:>
::> • • •• ••
• ••
alimenta
Ignora caracteres:
cr Retorno de
1-
• • • •• carro.
nul null Caracteres
•••
(/)
O::
w uon. • •••••••G
Puede
sub Sustituto
cancel
z
• ••• del Elimina
Q.
• ••
_J
¿ ar
.
Un: � e:(
• •• •
••• •••••••
w Separator Caracteres:
fs Archivo separator
J
�
:rQ.
e:(
gs Grupo separator
Q.
e
•• • rs Récord separator
•
• •••• •
'.L.
w
:e � f..J nos Unidad separator
o o
• •
ü
2
•
• •••• ••
C!'.l
-
::::>
•••••••<Y
Caracteres
escapada:
de
Tan cambio-fuera
o:
Q. �
C'•
2
o Yo\
••••• • • si cambio-en
••••
11
•••
••••• • •
2 V
ese
o
:¡ Escapa
.
e:(
,X)
r-
'°
••
•••• •• Caracteres
da de control del
medio: campana de
e2
1./'l
n
w anillo del belio
••••• •
w dcl-dc4 control de dispositivo
•• • em Fin de medio
••
Q.
'
w \
U j Caracteres de control de la
. •• •••
n soh Inicio de encabezar.
comunicación:
•• • stx Inicio de texto.
• •• •
:
*+
etx Fin de texto.
,.... eot Fin de transmisión.
...... • ••• enq Consulta
• •• •
• •• ••
Un,!\ ack acknowledgment
�
1Un
nak Negativo acknowledgment
Escapada de enlace
• ••• •
-11:
de dato de dado syn
síncrono idle
e
t
b Fin de bloque de transmisión
ÍNDICE SUBJECT
Un Conjunto de carácter 49
chr(x) 51
Parámetro real 95 Código 50
Dirección 10 Codificación 12
Algoritmo 6 Fase de recopilación 13
Antecedente 16 Compilador 13
Aritmética-geométrico malo 102 Esfuerzo computacional 3, 38
Variedad 81 Declaración condicional 34
Aserción 16 Consiguiente 16
Asignación 3 Constante 5
ALGOL 60, 30 Identificador constante 46
ASCII 49 continuum 51
Carácter de control 50
B
Variable controlada 84
Convergencia 64
Copia de seguridad 118 COBOL 31
Backus-Naur Formalismo (BNF) 31
símbolo básico 32
Empieza 34 D
Búsqueda binaria 83
Dato 8
Árbol binario 82
Bisección 102 Tipo de dato 45
Mordió 10 derivation Regla 21, 36, 85
Expresión determinista 119 estado
Boole, G. 47
discreto l O
Tipo de dato booleano 47, 142 div 5, 37
Inferior-arriba 126 Operador diádico 33
e E
165
166 ÍNDICE
Fin 34 Entrada 74
Entorno 94 Archivo de entrada 70
eof(f) 72 Instrucción 9, 55
Fase de ejecución 13 Entero 48
Parámetro explícito 98 Invariable 21, 23
Función exponencial 63 ISO 49
Expresión 33
L
F Lengua 29
Línea 110
Factorial 59 Local 93
Falso 41 Sección de archivo lógico 76
Fibonacci Número 66 valor lógico 47
fde 69 Bucle 15,26
Talante de archivo 70 LR-Descomposición 15.47
fin de archivo
indicador 72 longitud
de archivo 70 M
Posición de archivo 71
Estado de procesamiento del Código de máquina 13
archivo 68-69 base de punto
flotante 52 Plaza mágica 90
Coeficiente de punto flotante 52 Matricial 87
Exponente de punto flotante 52 Multiplicación matricial 88,97
Representación de punto flotante 52 mod 39
Transformación de punto flotante 107 Operador monádico 33
Flujo-esquema 14 monotonicity 53
Para 84 multi-Variedad dimensional 87
Parámetro formal 95
Función 92 N
Función designator 92
FORTRAN 30 Naur,P. 30
Neumann,John von 11
G Forma normal 52
Numérico 52
Gauss,C. F. 101, 127
Consigue(f) 71
Global 94
o
goto 120
Código de operación 11
graph 118
Más grande común divisor (GCD) 25,37, ord(x) 51
39,42 Producci ón 14
Archivo de producción 70
Desbordamiento 49, 53
H
Hardware 13
Heurístico 142 p
Horner 90
Procedimiento paramétrico 98
Variable paramétrica 97
Pivote 132,150
Sistema de número posicional 103
Si 34 pred(x) 46
Parámetro implícito 98 Tienda primaria 81
Índice 80 Número primo 138
Valor inicial 15
ÍNDICE 167