informatica

1

2013 1M.A. Zapata, A. Francés, J.C.Ciria

Componentes del ordenador

Bus del sistema

Unidad Central de Proceso (CPU)

8

Memoria Principal

Periférico

1Periférico

n

Memoria Secundaria

El bus es un sistema digital que transfiere datos entre los componentes de un ordenador entre ordenadores


Bus del sistema

Memoria Principal

???? ???????? ???????? ???????? ???????? ???????? ???????? ???????? ???????? ???????? ???????? ???????? ????

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

Memoria Secundaria

Periférico

1Periférico

n

CP (Contador de Programa) Dirección de memoria de la siguiente instrucción que debe ser ejecutada.

Ac (Acumulador): registro que se encuentra en la ALU, donde se almacena el primer dato para el caso de operaciones binarias, y el resultado de la operación de la ALU.

DM: Dirección de memoria de la que se quiere leer, o donde se quiere escribir.

RI (Registro de Instrucción): guarda la instrucción que está siendo ejecutada


Unidadde

Control

Señalesde

controlinternas

8

8

8

4

4

4

4

...

CP

DM

RI

Ac

ALU

2


1. Cargar el programa

Bus del sistema

Memoria Principal Memoria Secundaria

Periférico

1Periférico

n

???? ???????? ???????? ???????? ???????? ???????? ???????? ???????? ???????? ???????? ???????? ???????? ????

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

0001 01110001 10000100 01111000 10000101 10011100 10011111 0000

???? ???????? ???????? ???????? ???????? ????


Unidadde

Control

Señalesde

controlinternas

8

8

8

4

4

4

4

...

CP

DM

RI

Ac

ALU


¿Qué significa el programa? (i)

Diccionario código máquina-castellano

0001: leer1100: escribir (en pantalla)

1000: sumar1001: restar1010: multiplicar1011: dividir

0100: cargar (en el acumulador)0101: almacenar (en memoria principal)

1111: fin de programa

0001 01110001 10000100 01111000 10000101 10011100 10011111 0000

???? ???????? ???????? ???????? ????

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

almacenar

leerleercargarsumar

escribirfin

3


¿Qué significa el programa? (y ii)

0001 01110001 10000100 01111000 10000101 10011100 10011111 0000

???? ???????? ???????? ???????? ????

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

almacenar

leerleercargarsumar

escribirfin

El programa utiliza variables, que también se almacenan en la memoria principal

C

ABAB

C

C

AB


2. Inicializar el Contador de Programa (CP)

Bus del sistema


Ac

DM

RI

ALU

Unidadde

Control

Señalesde

controlinternas

8

8

8

4

4

4

4

Memoria Principal

...

leer Aleer Bcargar Asumar Balmacenar Cescribir Cfin 0000

???? ???????? ???????? ???????? ???????? ????

0000

0001

0010

0011

0100

0101

0110

ABC

1010

1011

Memoria Secundaria

Periférico

1Periférico

n

CP 0000

4


3. Leer de memoria la dirección indicada por CP

Bus del sistema


Ac

DM

RI

ALU

Unidadde

Control

Señalesde

controlinternas

8

8

8

4

4

4

4

Memoria Principal

...


???? ???????? ???????? ???????? ???????? ????

0000

0001

0010

0011

0100

0101

0110

ABC

1010

1011

Memoria Secundaria

Periférico

1Periférico

n

CP 0000


4. Almacenar en RI y DM la instrucción leída

Bus del sistema


Ac

ALU

Unidadde

Control

Señalesde

controlinternas

8

8

8

4

4

4

4

Memoria Principal

...

Memoria Secundaria

Periférico

1Periférico

n

CP 0000

DM

RI


???? ???????? ???????? ???????? ???????? ????

0000

0001

0010

0011

0100

0101

0110

ABC

1010

1011

leer

A

5


5. Incrementar en 1 el CP

Bus del sistema


Ac

ALU

Unidadde

Control

Señalesde

controlinternas

8

8

8

4

4

4

4

Memoria Principal

...

Memoria Secundaria

Periférico

1Periférico

n

CP 0000

DM

RI


???? ???????? ???????? ???????? ???????? ????

0000

0001

0010

0011

0100

0101

0110

ABC

1010

1011

leer

A

0001


6. Ejecución de la instrucción leída

Bus del sistema


Ac

ALU

Unidadde

Control

Señalesde

controlinternas

8

8

8

4

4

4

4

...

Memoria Secundaria

Periférico

1

CP 0000

DM

RIleer

A

0001

Memoria Principal


???? ???????? ???????? ???????? ???????? ????

0000

0001

0010

0011

0100

0101

0110

ABC

1010

1011

Periférico

n10

6


¿ y ahora?

Bus del sistema


Ac

ALU

Unidadde

Control

Señalesde

controlinternas

8

8

8

4

4

4

4

...

Memoria Secundaria

Periférico

1

CP 0000

DM

RIleer

A

0001

Memoria Principal


???? ???????? ???????? ???????? ???????? ????

0000

0001

0010

0011

0100

0101

0110

ABC

1010

1011

Periférico

n10

Ha terminado de ejecutarse la primera instrucción.Como no es instrucción de fin, se vuelve otra vez al paso 3 (leer de memoria la celda que indica CP)


Ejecución de la segunda instrucción

Bus del sistema


Ac

ALU

Unidadde

Control

Señalesde

controlinternas

8

8

8

4

4

4

4

...

Memoria Secundaria

Periférico

1

CP 0000

DM

RI

0001 0010

10

Memoria Principal


???? ???????? ???????? ???????? ???????? ????

0000

0001

0010

0011

0100

0101

0110

ABC

1010

1011

1015

Periférico

n

leer

A

leer

B

7


Ejecución de la tercera instrucción

Bus del sistema


Unidadde

Control

Señalesde

controlinternas

ALU

8

8

8

4

4

4

4

...

Memoria Secundaria

Periférico

1

CP 0000

DM

RI

0010 0011

10

Memoria Principal


???? ???????? ???????? ???????? ???????? ????

0000

0001

0010

0011

0100

0101

0110

ABC

1010

1011

1015

Periférico

n

leer

B

cargar

A

Ac10


Ejecución de la cuarta instrucción

Bus del sistema


Unidadde

Control

Señalesde

controlinternas

8

8

8

4

4

4

4

...

Memoria Secundaria

Periférico

1

CP 0000

DM

RI

0011 0100

10

Memoria Principal


???? ???????? ???????? ???????? ???????? ????

0000

0001

0010

0011

0100

0101

0110

ABC

1010

1011

1015

Periférico

n

cargar

A

sumar

B

Ac1025

ALU

8


Ejecución de la quinta instrucción

Bus del sistema


Unidadde

Control

Señalesde

controlinternas

8

8

8

4

4

4

4

...

Memoria Secundaria

Periférico

1

CP 0000

DM

RI

0100 0101

10

Memoria Principal


???? ???????? ???????? ???????? ???????? ????

0000

0001

0010

0011

0100

0101

0110

ABC

1010

1011

1015

Periférico

n

sumar

B

almacenar

C

Ac10

ALU

25

25


Ejecución de la sexta instrucción

Bus del sistema


Unidadde

Control

Señalesde

controlinternas

8

8

8

4

4

4

4

...

Memoria Secundaria

CP 0000

DM

RI

0101 0110

10

Memoria Principal


???? ???????? ???????? ???????? ???????? ????

0000

0001

0010

0011

0100

0101

0110

ABC

1010

1011

1015

Periférico

n

almacenar

C

escribir

C

Ac10

ALU

25

25

Periférico

1

25

9


Final del programa

Bus del sistema


Unidadde

Control

Señalesde

controlinternas

8

8

8

4

4

4

4

...

Memoria Secundaria

CP 0000

DM

RI

0110 0111

10

Memoria Principal


???? ???????? ???????? ???????? ???????? ????

0000

0001

0010

0011

0100

0101

0110

ABC

1010

1011

1015

Periférico

n

escribir

C

fin

0000

Ac10

ALU

25

25

Periférico

1

25


Fin del programa

1


Codificación del software


Codificación de datos en binario

Los ordenadores utilizan el sistema binario para codificar cualquier tipo de información (números, caracteres, imagen, sonido…)

La unidad mínima de información es el BIT (BInary digiT)

Un bit tiene dos valores posibles, que representamos mediante los caracteres 0 y 1.

2


Sistemas posicionales de numeración

Cada número se representa mediante una colección ordenada de cifras, cada una de las cuales contribuye con un valor que depende:

– del propio valor de la cifra– de un valor llamado base (el número de cifras disponibles)

– de la posición de la cifra en la colección

Base decimal:– Base: 10– Cifras: 0, 1, 2, 3, …, 9

Ejemplos:

1 9 0 5

-1 7 . 2 5 =

Nota: Los sistemas posicionales requieren de una cifra especial para representar el valor CERO, que fue introducido en Europa por los árabes Más información en: http://thales.cica.es/rd/Recursos/rd97/Otros/SISTNUM.html

0123

= 1·103 + 9·102 + 0·101 + 5·100

01 -1 -2

−(1·101 + 7·100 + 2·10-1 + 5·10-2 )


Sistema binario

Base dos (binario):– Base: 2 Cifras: 0, 1

Ejemplo: 1101.01 (2

1 1 0 1 . 0 1

0123 -1 -2

= 1·23 + 1·22 + 0·21 + 1·20 + 0·2-1 + 1·2-2 = 13.25(10

¿Cuál es la representación en base 10 del número 1001.11 (2 ?

3


Paso decimal � binario

18 29 2

41 220 2

10 201

0

1 0 0 1 0

Parte entera: sucesivas divisiones por la base (2) hasta que el cociente valga 0; los restos son las cifras del resultado, en orden inverso al de obtención

¿Cuál es la representación binaria del número 18(10 ?

(2


Parte decimal: sucesivos productos por la base (2) hasta que la parte decimal es cero; tras cada multiplicación:• Se toma la parte entera como una cifra del resultado, que

ocupan las posiciones -1, -2,…• Antes de pasar al siguiente producto, la parte entera se hace

cero


¿Cuál es la representación binaria de 0.6875(10?

0.6875 * 2 = 1.375

0.375 * 2 = 0.75

0.75 * 2 = 1.5

0.5 * 2 = 1.0

0.6875 (10 = 0.1011 (2

4


Convención: si no se indica explícitamente lo contrario, suponemos que un número está representado en base decimal.

Ejercicio: expresar en base 2 los siguientes números:

13.25 = ¿? (20.1 = ¿? (2



Suma en base 2

Operaciones aritméticas

0 + 0 = 0(2

0 + 1 = 1(2

1 + 0 = ¿?1 + 1 = ¿?

1 + 1 + 1 = ¿?

1(2

11(2

Números de más de un dígito: de modo análogo:

1 1 1 1 0 1 0(2

0 1 1 0 0 0 1(2

10(2

11

10 110101

Para realizar las operaciones aritméticas (suma, diferencia, producto,…) de números expresados en cualquier base podemos utilizar los algoritmos que normalmente usamos en base decimal.

(2

5


Sistema octal

Base ocho (octal):– Cifras: 0, 1,… , 7 − Base: 8

Ejemplos:

743(8 = 7·82 + 4·81 + 3·80 = 483(10

Paso de decimal a octal: similar al usado en binario483.25(10 = ??(8

Paso de octal a binario: representar cada cifra octal por su equivalente binario usando siempre tres cifras:

743(8

Paso de binario a octal: agrupar los dígitos binarios en grupos de tres, comenzando por la derecha, y transformar cada uno en una cifra octal conservando la posición:

11010(2

= 171 140 031111 100 011 (2

= 3 2(8= 11 010 (2 = 26(10


Sistema hexadecimal

Base hexadecimal:– Cifras: 0, 1,… , 9, A, B, C, D, E, F − Base: 16

Las letras A, B,…,F representan los valores 10, 11,…,15Ejemplos:

1 0

7B(16 = 7·161 + 11·160 = 123(10

Paso de decimal a hexadecimal: similar al usado en binario483.25(10 = ??(16

Paso de hexadecimal a binario: representar cada cifra hexadecimal por su equivalente binario usando siempre cuatro cifras:

7C3(16 = 0111 1100 0011(2

Paso de binario a hexadecimal: agrupar los dígitos binarios en grupos de cuatro, comenzando por la derecha, y transformar cada uno en una cifra hexadecimal conservando la posición:

11010(2 = 1A(16 = 26(10

6


Codificación de enteros

El número de bits disponibles para representar un número es finito(¡¡ la memoria de un ordenador es finita !!)

¿Cuántos números enteros distintos es posible representar…… con 3 bits?

… con n bits?

de 000 a 111 : 8 números distintos

2n números distintosde 0 … 0 a 1 …1 :n n



El número de bits disponibles para representar un número es finito

Eso afecta al resultado de las operaciones:

¿Cuál es el resultado de sumar 3 + 5 ... si sólo disponemos de 3 bits?

10 111 0

00 0

1

1

1

101 es el número que sumado a 011 me da 0:Podemos utilizarlo para representar números negativos (complemento a 2):Podemos tomar 101 como la representación de -3

7



El número de bits disponibles para representar un número es finitoPodemos representar negativos mediante su complemento a 2

¿Cómo se calcula?(Ejemplo: representación de -5, si disponemos de 8 bits para representar un número)

1.Se toma el valor absoluto (5)

2.Intercambiamos 0 <-> 1

3.Sumamos 1

Comprobación:

0000 0101

1111 1010

1111 1011

0000 0101

1111 1011

Existen otras convenciones posibles para representar números negativos, pero con el complemento a 2 la suma de enteros, independientemente de su signo, se realiza con el mismo algoritmo que la suma de positivos.



El número de bits disponibles para representar un número es finitoPodemos representar negativos mediante su complemento a 2Al tratar con un entero, hay que especificar cómo interpretarlo:

Consideramos sólo positivos Consideramos positivos y negativosSi el primer bit es 0: positivoSi el primer bit es 1: negativo

01234567

0123

-4-3-2-1

000001010011100101110111

8



El número de bits disponibles para representar un número es finitoPodemos representar negativos mediante su complemento a 2Al tratar con un entero, hay que especificar cómo interpretarlo:

número de bits

Sólo positivos Positivos y negativosSi el primer bit es 0: positivoSi el primer bit es 1: negativo

3 mayor

menor

n mayor

menor

011(2

011…1(2

n

= 3

= 2n-1 -1

100(2 = -4

100…0(2

n

= - 2n-1

000(2

111…1(2

n

= 0

= 2n -1

111(2 = 7

000…0(2

n

= 0

¿Cuál es el rango de enteros que podemos representar usando n bits?


Codificación de números reales

Coma flotante: la idea es representar el número real en “notación científica” (pero usando base 2).

mantisa

exponente

Un número real: +/- 1.m 2e

SignoMantisa

Exponente

10.25 = 1010.01(2 = + 1.01001 x 2 3

9



Coma flotante: la idea es representar el número real en “notación científica” (pero usando base 2).

mantisa

exponente10.5 = 1010.1(2 = + 1.0101 x 2 3

nm bits para la mantisa

1 bit para el signo: 0 (positivo), 1(negativo)

ne bits para el exponente

0 0 1 1 0 1 0 1

A mayor ne: podemos representar reales más grandes y más pequeños (en valor absoluto)A mayor nm: podemos representar reales con más decimales (mayor precisión)



En esta idea se basa el estándar IEEE754Para representar reales “cortos”) utiliza 32 bits: 1 para el signo, 23 mantisa (precisión), 8 para el exponente (magnitud).

nm bits para la mantisa

1 bit para el signo: 0 (positivo), 1(negativo)

ne bits para el exponente

Nota: en el estándar, el exponente se codifica con sesgo 2ne-1-1

10



Sólo representamos una cantidad finita de reales, usando una cantidad fijada de bytes.

La precisión es finita: eso puede dar lugar a errores de redondeo: operaciones cuyo resultado no es representable en particular al operar con números de magnitud muy diferente

Ejemplo: 10-20 + 1 se redondea a 1 (no hay precisión suficiente)


Codificación de caracteres

La idea para codificar caracteres en binario es sencilla: basta adoptar una serie de acuerdos!!

– Cuántos y qué caracteres representamos:alfabéticos (mayúsculas/minúsculas)dígitos (0, 1, 2, …)símbolos (+, −, :, !, ?, %, $…)otros ??

– Del número de caracteres determinamos cuántos bits necesitaremos para representar cada uno.

n caracteres bitsej. Si n=95 (26 < 95 ≤ 27 = 128) necesitamos 7 bits

– Asociamos a cada carácter un entero codificado en binario:ej.:

n2log

Carácter Codificación (binaria) Codificación (base 10)

'A' 0100 0001(2 65

'B' 0100 0010(2 66

'a' 0110 0001(2 97

11


Código ASCII


Codificación de caracteres (estándares)

• Uno de los primeros estándares fue ASCII (American Standard Code for Information Interchange). Usa 7 bits para codificar 128 caracteres (no contiene caracteres como ‘Ñ’, ‘ñ’, ‘á’, ‘ç’,…)

• Diversas ampliaciones que usan 1 byte (256 caracteres). Por ejemplo, ISO-8859-1 (ISO-Latin-1). En todas los 128 primeros caracteres coinciden con ASCII.

• ANSI (American National Standard Institute) es el usado por Windows. Es una revisión de ASCII ampliado a 1 byte.

• EBCDIC (de IBM para grandes ordenadores): 1 byte

• UNICODE (Java): 2 bytes = 65536 caracteres¿ … ?

12


Ejercicio

Suponemos:• Las celdas de memoria tienen 7 bits• Codificamos los reales siguiendo una versión simplificada del estándar IEEE754:

• Codificamos los enteros por el método de complemento a 2• Codificamos los caracteres siguiendo el código ASCII

2.25 = 10.01(2 = + 1.001 x 2 1 0 0 0 1 0 0 1

Usando un lenguaje de programación, reservamos celdas para almacenar:

Un número natural, mUn entero, nUn real, xUn carácter, c

1 0 1 0 1 0 1

1 0 1 0 1 0 1

1 0 1 0 1 0 1

1 0 1 0 1 0 1

m:

n:

x:

c:

Si el contenido de las respectivas celdas es el siguiente, ¿cómo se interpretan (qué valor se asigna a cada uno)?


Ejercicio

Con el estándar IEEE754,si se dispone de nm bits para la mantisa, ¿cuál es la mayor precisión posible?

¿Cuál es el menor número 1 + x que sea distinguible de 1?

… si nm = 23… si nm = 52

1


Informática

Tipos de datosy

sentencias elementales


Los algoritmos manipulan datos, que pueden ser de distintos tipos.

Un tipo de datos es un conjunto bien definido de valores (dominio)

y de operaciones definidas sobre ellos

Tipos de datos elementales:• Booleano• Entero• Real• Carácter• Cadena de caracteres

Tipos de datos

2


Dominio: valores lógicos VERDADERO y FALSONotación: V, FOperadores:

Tipos de datos: booleano (i)

Y V F

V

F

O V F

V

F

De igualdad (== , !=)

== V F

V

F

!= V F

V

F

NO V F

VF FV

FF

VV

FV

FV

VF

VF

FV

NO:operador unario (un solo operando) Y, O, ==, !=: binarios (dos operandos)

Lógicos ( NO , Y , O)


Comprueba las igualdades: NO (PA Y PB) = (NO PA) O (NO PB)

Tipos de datos: booleano (y ii)

PA PB PA Y PB NO (PA Y PB ) NO PA NO PB (NO PA) O (NO PB)

V V

V F

F V

V V

NO (PA O PB) = (NO PA) Y (NO PB)

PA PB PA O PB NO (PA O PB ) NO PA NO PB (NO PA) Y (NO PB)

V V

V F

F V

V V

3


Dominio: conjunto de todos los enterosNotación: notación decimal (10, -4, +33)Operadores:

Tipos de datos: entero

Relacionales: >, <, ≥, ≤, ==, != (el resultado: booleano)

6 > 3 � Verdadero

Aritméticos (el resultado es entero)cambio de signo (-) - 3 � -3 - -4 � 4suma (+)resta (-)producto (*)cociente (/) 3/2 � 1, 2/3 � 0resto (%) 3%2 � 1, 2%3 � 2


Dominio: conjunto de todos los realesLiterales: notación decimal (1., 1.4, -3.5) o científica (2.2E2 = 2.2 102)Operadores:

Tipos de datos: real

Relacionales: >, <, ≥, ≤, ==, != (el resultado: booleano)

-6 > 3 � Falso

Aritméticos (el resultado es real)cambio de signo (-)suma (+)resta (-)producto (*)cociente (/) 3.0/2.0 � 1.5, 2.0/3.0 � 0.66

4


Dominio: conjunto de símbolos para representar letras, dígitos,...• Símbolos de la tabla ASCII (ISO-8859-1)

Literales: 'a', 'b', 'A', '0', '1', '+', '%'• especiales: ‘\’’, ‘\\’ (similares a C/C++)

Operadores:

Tipos de datos: carácter

Relacionales: >,<, ≤, ≥, ==, != (el resultado es booleano)orden de su código según la tabla ASCII (casi alfabético)

'0' 48

'1' 49

'2' 50

... ...

'9' 57

'ñ' 164

'Ñ' 165

'A' 65

'B' 66

'C' 67

... ...

'Z' 90

'a' < 'b':'a' < 'B':'1' < '2':'a' < '1':

'a' 97

'b' 98

'c' 99

... ...

'z' 122

97 < 98 � Verdadero97 < 66 � Falso49 < 50 � Verdadero97 < 49 � Falso


Dominio: cadenas de caracteres (~ palabras, frases)secuencias finitas de caracteres de la tabla ASCII

Literales: “entre comillas dobles”1 literal entero'1' literal carácter"1" literal cadena

Operadores:

Tipos de datos: cadena

Relacionales: >,<, ≤, ≥, ==, !=• resultado booleano (verdad, falso)• orden lexicográfico inducido por el orden de los caracteres:(~ alfabético)Una cadena es menor que otra si coinciden sus primeros n-1 caracteres y el n-ésimo de la primera cadena es menor queel n-ésimo de la segunda:

"abc" < "b": "ana" < "aro":"02" < "1":

� Verdadero� Verdadero� Verdadero

5


Los algoritmos manipulan datos.

Los objetos de datos básicos que se manipulan en un programa son variables y constantes.

Una variable...• tiene un tipo de dato (booleano, entero, real, carácter) bien

definido.• tiene un nombre (identificador)• tiene un valor• tiene asignado un espacio en la memoria principal, y una

dirección de memoria.

Variables, constantes y expresiones


Una constante puede ser:• Un literal: 7, -14.77, 'a'• Una constante con nombre: podemos definir una constante llamada PI a la que asignamos un valor 3.141592

Una expresión es una combinación bien formada de operadores y operandos (que pueden ser constantes o variables).

Evaluar una expresión es realizar las operaciones que contiene, obteniendo un valor como resultado. El tipo de expresión es el tipo de dato al que corresponde el valor devuelto.

Variables, constantes y expresiones

6


1) Operadores unarios (!, -)

2) * / %

3) + -

4) Operadores de relación (>, <, ≥, ≤)

5) Operadores de igualdad ( ==, !=)

6) Y

7) O

Asociatividad: de izquierda a derechaAnte la duda: usar paréntesis

Precedencia de operadores


Expresiones

Evaluación de expresiones compuestas: se evalúan, de izquierda a derecha (asociatividad), las subexpresiones en orden de precedencia de sus operadores. Las subexpresiones entre paréntesis se evalúan primero.

Ej.: 17 + 3 < 1.0 * 8.0

17 + 3 < 8.0

20 < 8.0

falso

¡ mezcla tipos entero y real ! ¿es correcto?

Promoción automática de entero a real dentro de una expresión

7


Metodología

Ante un problema: (no hay un método universal para resolver todos los problemas)

Análisis/Especificación: ¿Hemos comprendido correcta y completamente el problema, con todas sus implicaciones? ¿Hemos previsto sus posibles puntos críticos? Determinar qué debe hacer el algoritmo y cuáles son sus entradas y resultados

Diseño: Encontrar una solución para el problema, haciendo abstracción de aspectos técnicos (de la plataforma, del lenguaje de programación…) (Pseudocódigo). Empezar por una descripción a grandes rasgos, que se irá refinando hasta obtener una solución detallada..Decidir qué estructuras de datos vamos a necesitar.

Implementación: codificación en un lenguaje de programación (C/C++), teniendo en cuenta sus peculiaridades específicas.


Ejemplo

Problema: dado un entero n≥0, que representa una cantidad de tiempo en segundos, calcular su equivalente en horas, minutos y segundos.

>>

<<

Salida

Entrada

Memoria

horas

n

minutos

segundos

Procesamiento(aritmética y control)

8


Ejemplo

Problema: dado un entero n≥0, que representa una cantidad de tiempo en segundos, calcular su equivalente en horas, minutos y segundos.

Análisis: Entradas: un entero ≥0Salidas: tres enteros ≥0 (dos de ellos <60)


Ejemplo

¿Qué variables necesitamos? n horas minutos segundos

Estado inicial: ¿? ¿? ¿? ¿?

Paso 2) Calcular el número de horas, tomando el cociente de dividir n / 3600

3783 1 ¿? ¿?

Paso 3) Calcular el resto de dividir n / 3600, y guardarlo en n

183 1 ¿? ¿?

Paso 4) Calcular el número de minutos, tomando el cociente de dividir n/60

183 1 3 ¿?

Paso 5) Calcular el número de segundos, tomando el resto de dividir n/60

183 1 3 3

Paso 1) Leer el valor de n

3783 ¿? ¿? ¿?

Paso 6) Mostrar el resultado por pantalla

Estado final:

9


Ejemplo

¿Qué variables necesitamos? n horas minutos segundos

Estado inicial: ¿? ¿? ¿? ¿?

Paso 2) Calcular el número de horas, tomando el cociente de dividir n / 3600

3783 1 ¿? ¿?

Paso 3) Calcular el resto de dividir n / 3600, y guardarlo en n

183 1 ¿? ¿?

Paso 4) Calcular el número de minutos, tomando el cociente de dividir n/60

183 1 3 ¿?

Paso 5) Calcular el número de segundos, tomando el resto de dividir n/60

183 1 3 3

Paso 1) Leer el valor de n

3783 ¿? ¿? ¿?

Paso 6) Mostrar el resultado por pantalla

Estado final:

Algoritmo: Secuencia (ordenada) finita de pasos que permiten obtener la solución de un problema.

Traza de un algoritmo: la secuencia de estados por los que va pasando


Tipos de sentencias

¿Qué tipos de sentencias necesitamos?

� Declaración de variables: cuántas vamos a usar y de qué tipos

� Asignación: almacenar en una variable el resultado de evaluar una expresión

� Comunicación con el exterior:– Lectura de teclado (asignación externa): asignar a una

variable un valor que tecleamos– Escritura en pantalla: mostrar en pantalla el valor de

una variable

10


Declaración de variables

• Sintaxis: <id_variable> ES <tipo><id_var1>, <id_var2> ES <tipo>

• Semántica:No expresa una acción. Sólo indica cuántas variables usaremos, sus nombres y el tipo de cada una de ellas.

n, horas, minutos, segundos ES entero

x ES real

b ES booleano


Asignación

• Sintaxis: cómo se escribe la instrucciónid_variable expresión

– La expresión puede ser una constante o una variable– id_variable y expresión deben ser del mismo tipo– Si id_variable es real, la expresión puede ser entera

• Semántica: qué hace la sentencia1) Se evalúa la expresión2) El valor obtenido se almacena en la variable (su valor

anterior se pierde)

11


Asignación: ejemplos

horas n / 3600n n % 3600minutos n / 60segundos n % 60

Suponer que x es una variable entera y

b una variable booleana

x 1324

b falsox 7+5*2

x 17

b falsob x > 3

x 17

b verdad

x 1.0

b ‘a’ERROR !!


Lectura de teclado

• Sintaxis: leer(id_var) leer(id_var1, id_var2,...)– Las variables pueden ser de cualquier tipo básico (entero,

real, carácter, cadena)

• Semántica: en el teclado se escriben caracteres que representan un valor adecuado para el tipo de la variable. Entonces, el valor se asigna a la variable. Si el valor no es adecuado el resultado de la operación está indefinido (ERROR)

Ej.: variables x real, n entero, c carácter, s cadena

Leer(x) 7.5 -48.3 -4.1E2 Hola X

Leer(n) -1234 34 abc 7.5

Leer(c) a 1 ,

Leer(s) hola

Cadenas y caracteres se introducen sin comillas

MAL

12


Escritura en pantalla

• Sintaxis: escribir(expresión) escribir(exp1, exp2, ...)– Las expresiones pueden ser de cualquier tipo básico (entero,

real, carácter, cadena y booleano)– Las expresiones pueden ser simplemente una variable o una

constante• Semántica:

1) Se evalúa la expresión2) En pantalla se escribe una secuencia de caracteres que

representa el valor (cadenas y caracteres sin comillas)

Escribir(7+4) 11

Escribir(2*x) 2.2 (suponiendo que el valor de x es 1.1)

Escribir(“hola”) hola

Escribir(7<4) falso

escribir(exp1, exp2) equivale a escribir(exp1), escribir(exp2)


Estructura de un algoritmo

Algoritmo nombre_algConstantes cte1 = valor1

cte2 = valor2...

Variables var1 es tipo1...

Principiosecuencia de sentencias(se ejecutan en el ordenen que se escriben)

Fin

Pasos:

Declarar las variables (y, en su caso, constantes) necesariasPedir al usuario que teclee el valor de nLeer el valor de nCalcular el número de horas, tomando el cociente de dividir n / 3600Calcular el resto de dividir n / 3600, y guardarlo en nCalcular el número de minutos, tomando el cociente de dividir n/60Calcular el número de segundos, tomando el resto de dividir n/60Mostrar el resultado por pantalla

Recordatorio de sentencias:

Declaración id_variable {, id_variable} es <tipo_dato>

Ej: n es entero

x, y es real

x,y,z es real

Lectura (de teclado) leer (id_variable)

Ej: leer (x)

Asignación id_variable expresión

Ej: m n/4

Escritura (en pantalla) escribir (expresión {,expresión})

Ej: escribir ( "El resultado es ", m)

{ }: el contenido del paréntesis se puede repetir 0 o muchas veces

13


Estructura de un algoritmo

Algoritmo nombre_algConstantes cte1 = valor1

cte2 = valor2...

Variables var1 es tipo1...

Principiosecuencia de sentencias(se ejecutan en el ordenen que se escriben)

Fin

Algoritmo Conversion_HorasConstantes

SEGUNDOS_POR_HORA = 3600SEGUNDOS_POR_MINUTO = 60

Variablesn, h, min, seg es entero

Principioescribir(“Cantidad segundos: “)leer(n)horas n / SEGUNDOS_POR_HORA

n n % SEGUNDOS_POR_HORA

min n / SEGUNDOS_POR_MINUTO

seg n % SEGUNDOS_POR_MINUTO

escribir(horas, min, seg)Fin

Ejemplo

1

2013 M.A. Zapata, A. Francés, J.C.Ciria 0

Informática

Tipos de datosSentencias elementales

en C


Niveles de abstracción

Nivel lógico: diseño de soluciones implementables en cualquier lenguaje de programación con el paradigma imperativo (C, FORTRAN, PASCAL…)• Nos centramos en el algoritmo en sí, haciendo abstracción de

detalles "técnicos"• Permite demostrar formalmente la validez del algoritmo,

independientemente de qué herramienta se usará para implementarlo

Nivel físico: implementación del diseño, teniendo en cuenta las características específicas del lenguaje concreto utilizado.

2


Booleanos: no existen en C. En C++: bool

Carácter: char

Enteros: char short int longcalificador: unsigned

Reales: float double long double

Tipos de datos predefinidos de C/C++


Tipo bool de C++

Dominio: valores lógicos verdadero/falsoLiterales: true, falseOperadores:• lógicos: ! (negación), && (y lógico), || (o lógico)• de igualdad: ==, !=

En C existen los operadores lógicos, pero no existe el tipo bool.

• el valor 0 (cero) de cualquier tipo representa falso• cualquier valor distinto de 0 representa verdad

3


Dominio: caracteres de la tabla ASCIILiterales: 'a', '0', '1', '+',...Operadores: >,<, <=, >=, ==, !=

(orden del código ASCII)devuelven 0 (falso) ó 1 (verdad)

Literales para representar caracteres especiales:

'\0' código ascii 0 (carácter nulo)

'\n' código ascii 10 (nueva línea)

'\t' código ascii 9 (tabulador)

'\’' '\”' '\\'

Tipo char


Tipos enteros en C

Un entero ocupa un número determinado de bits en memoria. A la hora de interpretarlo, hay que especificar si se trata de un número con o sin signo:

Tipos:

charshortintlong

[unsigned][unsigned][unsigned][unsigned]

Nota: en notación BNF [] significa opcional

Literales: 10, -798 (notación decimal)Operadores:• Aritméticos: +, -, *, /, %• Relacionales: >,<, <=, >=, ==, !=

4


Tipos de enteros en C/C++

short ≥ 2 bytes

short -215 215 - 1

unsigned short 0 216-1

long ≥ 4 bytes

long -231 231 - 1

unsigned long 0 232-1

Tamaño long ≥ tamaño int ≥ tamaño short

Los tipos int y unsigned int coinciden con la correspondiente versión short o long: la elección puede ser diferente para distintos compiladores de C

char 1 byte

char -27 27 - 1

unsigned char 0 28-1

int


float double long doubleTamaño ≤ 4 bytes ≤ 8 bytes ≤ 8 bytes

Precisión ≤ 8 decimales ≤ 16 decimales

Dominio 3.4e-38 a 3.4e+38(4 bytes)

1.7e-308 a 1.7e+308(8 bytes)

3.4e-4932 a 3.4e+4932(12 bytes)

Literales: 10.23, -798.32 (notación decimal)4.476E1 (científica)

Operadores:• Aritméticos: +, -, *, /• Relacionales: >,<, <=, >=, ==, !=

Tipos reales en C

5


Sentencias elementales en C/C++

NOTA: toda sentencia elemental termina en ;

Declaración de variables:<tipo> var1, var2, var3,..., varN;

Asignación:var = expresión;

Lectura de teclado (C++):cin >> var1 >> var2 >> ... >> varN;

Escritura en pantalla (C++):cout << exp1 << exp2 << ... << expN;


Identificadores

• Palabras no reservadas por el lenguaje (if, while,...)• Formadas por letras (excepto 'ñ', 'Ñ', 'á',...),

dígitos y carácter '_'• NO empiezan por dígito (10x no es válido)• Las letras mayúsculas y minúsculas son caracteres

distintos (case sensitive)• Pueden tener longitud arbitraria, pero sólo se

distinguen los 31 primeros caracteres

Ejemplos:Var, var, VAR, v10, _v10, precioArticulo, precio_articulo

6


Declaración de variables

Sintaxis:<tipo> var; <tipo> var1, var2,..., varN;

Ejemplos:char car, c1;int n, edad;double precioArticulo;

Semántica: Se reserva el identificador como nombre de la variable. El valor de la variable queda indefinido.


Variables para representar cadenas

• En C no existe un tipo predefinido para representar cadenas de caracteres.

char var[MAX];

• MAX es una constante entera positiva. Podemos almacenar en var cadenas con longitud MAX-1 caracteres.

Inicialización:char ej[30] = "hola mundo";

7


Asignación

Sintaxis:<var> = <expresión>;

– C no obliga a que la expresión y la variable sean del mismo tipo; pero si no se puede hacer una conversión adecuada lo advierte con un mensaje de warning (corriendo el riesgo de pérdida de datos).

Ejemplos:int m, n; float x;n = 10; x = 5;n = n*16;x = x*4 – n/2;

Semántica:1. Se evalúa la expresión2. El valor obtenido se almacena en la variable (destruyendo el

valor anterior)


Inicialización de variables

Es posible unir declaración y asignación en una misma sentencia:

<tipo> var = expresión;

char salto = '\n';

int n = -7;

double r = 9.6, t;

8


Escritura en pantalla (C++)

La sentencia en C es printf

Sintaxis:cout << expresión;cout << exp1 <<...<< expN;

– Las expresiones pueden ser de cualquier tipo, pero las booleanas deben ir entre paréntesis

– Se deben añadir explícitamente blancos y saltos de línea para separar el valor de las expresiones

Ejemplos: cout << "hola mundo";cout << "El resultado es " << 7*5 << '\n';cout << (1<7);

Semántica:Se evalúan las expresiones y se sacan por pantalla en el mismo orden en que aparecen en la sentencia.


Lectura de teclado (C++)

La sentencia en C es scanf

Sintaxis:cin >> var;cin >> var1 >>... >> varN;

– Las variables pueden ser de cualquier tipo elemental y también cadenas (char[]), pero sólo lee una palabra.

Ejemplos:cin >> n; cin >> x >> y >> z;

Semántica:– En general, se suspende la ejecución del programa hasta que se

teclean algunos caracteres y se pulsa retorno de carro.– cin intenta interpretar los caracteres introducidos como un dato del

tipo de la variable.– Los caracteres sobrantes se utilizarán en lecturas siguientes (sin

suspender la ejecución del programa).

9


Ejemplo

Algoritmo Conversion_HorasConstantes

SEGUNDOS_POR_HORA = 3600SEGUNDOS_POR_MINUTO = 60

Variablesn, h, min, seg es entero

Principioescribir(“Cantidad segundos: “)leer(n)horas � n / SEGUNDOS_POR_HORA

n � n % SEGUNDOS_POR_HORA

min � n / SEGUNDOS_POR_MINUTO

seg � n % SEGUNDOS_POR_MINUTO

escribir(horas, min, seg)Fin

Implementa el algoritmo que, dado un tiempo expresado en segundos (por un número entero), lo desglose en horas, minutos y segundos

Declaración de variables:<tipo> variable1,..., variableN;Ej: int n; double x;

Asignación:variable = expresión;Ej: n = 2*m/3;

Lectura de teclado (C++):cin >> variable1 >> ... >> varN;Ej: cin >> n;

Escritura en pantalla (C++):cout << expr1 << ... << exprN;Ej: cout<< m << ", " << n;

Recuerda:


Compilación, precompilación y ejecución

Compilación: traducción del código fuente al código máquina del procesador (ejecutable).

En C/C++, previamente se realiza una precompilación– Las directivas del precompilador no son sentencias– Se ejecutan antes de la compilación– Las más frecuentes son:

#include <fichero> //inserta código de otro fichero fuente#define PI 3.141592 //define constantes simbólicas

La compilación crea un fichero llamado MiFichero.exe que contiene el código ejecutable.

La ejecución del programa comienza por la primera sentencia de la "función" main.

10


Programa: ejemplo

#include <iostream>

# define SEGUNDOS_HORA 3600# define SEGUNDOS_MINUTO 60

using namespace std;

int main() {

int n, h, min, seg;

cout << "Dame la cantidad en segundos: ";

cin >> n;

h = n / SEGUNDOS_HORA ;n = n % SEGUNDOS_HORA ;min = n / SEGUNDOS_MINUTO ;seg = n % SEGUNDOS_MINUTO ;

cout << "El tiempo introducido equivale a " << h << " horas, " <<min << " minutos y " << seg << " segundos" << '\n' ;

return 0;}

Directivas del precompilador#include <iostream>

# define SEGUNDOS_HORA 3600# define SEGUNDOS_MINUTO 60

using namespace std;

int main() {

int n, h, min, seg;

cout << "Dame la cantidad en segundos: ";

cin >> n;

h = n / SEGUNDOS_HORA ;n = n % SEGUNDOS_HORA ;min = n / SEGUNDOS_MINUTO ;seg = n % SEGUNDOS_MINUTO ;

cout << "El tiempo introducido equivale a " << h << " horas, " <<min << " minutos y " << seg << " segundos" << '\n' ;

return 0;}


Ciclo de vida de un programa

1. Edición (usando bloc de notas, codeblocks…)

2. El programador da la orden de compilar el programa:a) El compilador invoca automáticamente al preprocesador, que ejecuta

las directivas de preprocesador (incluir otros ficheros, hacer sustituciones…)

b) El compilador traduce el programa a código máquina, ejecutable por el ordenador.mingw32-g++.exe -c prueba.cpp -o prueba.o

3. El linkador incluye en el programa funciones procedentes de bibliotecas externas (matemáticas, de entrada/salida…)

mingw32-g++.exe prueba.o -o ejecutable.exe

4. El programa ejecutable se carga en la memoria principal

5. Ejecución del programa

11


Compilación y ejecución (detalle)

0. Incluimos en el path (ruta de búsqueda) la carpeta donde está el compilador2. Compilamos el fichero .cpp, generando el código objeto (prueba.o)3. Linkamos el código objeto, generando un fichero ejecutable (ejecutable.exe)4. Damos orden de cargar el ejecutable en memoria y de ejecutarlo.5. El programa se ejecuta

2

34

5

0

/* Para conocer los rangos de valores de los distintos tipos de datos de tu compilador puedes usar las cabeceras <limits.h> y <float.h>, que definen constantes para el tamaño de los tipos enteros y reales, respectivamente. El siguiente programa te facilitará esa información:*/ #include <iostream> #include <limits.h> #include <float.h> #include <math.h> using namespace std; int main() { cout << "Rango de valores:" <<'\n'; cout << "\t char:\t" << CHAR_MIN << " a " << CHAR_MAX << '\n'; cout << "\t unsigned char:\t" << 0 << " a " << UCHAR_MAX << '\n'<<'\n'; cout << "\t short:\t" << SHRT_MIN << " a " << SHRT_MAX << '\n'; cout << "\t unsigned short:\t" << 0 << " a " << USHRT_MAX << '\n'<<'\n'; cout << "\t int:\t" << INT_MIN << " a " << INT_MAX << '\n'; cout << "\t unsigned int:\t" << 0 << " a " << UINT_MAX << '\n'<<'\n'; cout << "\t long:\t" << LONG_MIN << " a " << LONG_MAX << '\n'; cout << "\t unsigned long:\t" << 0 << " a " << ULONG_MAX << '\n'<<'\n'; cout << "Tipos reales:" << '\n'; cout << "\tfloat:\n"; cout << "\t\t digitos decimales de precision: "<<FLT_DIG << '\n'; cout << "\t\t numero x menor tal que 1+x != x: "<<FLT_EPSILON << " = 2^" << log(FLT_EPSILON) / log (2) << '\n'; cout << "\t\t valor minimo: "<<FLT_MIN << " = 2^" << log(FLT_MIN) / log (2) << '\n'; cout << "\t\t valor maximo: "<<FLT_MAX << " = 2^" << log(FLT_MAX) / log (2) << '\n'; cout << "\n\tdouble:\n"; cout << "\t\t digitos decimales de precision: "<<DBL_DIG << '\n'; cout << "\t\t numero x menor tal que 1+x != x: "<< DBL_EPSILON << " = 2^" << log(DBL_EPSILON) / log (2) << '\n'; cout << "\t\t valor minimo: "<<DBL_MIN << " = 2^" << log(DBL_MIN) / log (2) << '\n'; cout << "\t\t valor maximo: "<<DBL_MAX << " = 2^" << log(DBL_MAX) / log (2) << '\n';

cout << endl << endl; double x , y, total; x = DBL_MAX; y = DBL_MAX / pow (10, DBL_DIG); total = x + y; cout << x << " + " << y << " = " << total << endl; short n, m = SHRT_MAX; n = m + 1; cout << m << " + 1 = " << n << endl; return 0; }

1


Informática

Sentencias estructuradas (i)


Estructuras de control

Objetivos

• Adquirir conciencia de la necesidad de mecanismos de control de flujo de un programa

• Adquirir la noción de sentencia estructurada

• Familiarizarse con los principios de la programación estructurada

2


Estructuras de control

Contenido:

• Sentencias compuestas. Concatenación de sentencias.

• Composiciones condicionales.

• Composiciones iterativas. Procesamiento de secuencias.


Algoritmo:

Conjunto ordenado y finito de operaciones que permite hallar la solución de un problema. Además: finitud, definibilidad, entrada, salida, efectividad

¿En qué orden se ejecutan las sentencias?

ordenado

3



Orden secuencial: en el mismo orden en que están escritas

ESCRIBIR ( “Dame un tiempo en segundos”);LEER(n);h n/3600; m (n % 3600) / 60;s (n % 60);ESCRIBIR (n, “segundos son ”); ESCRIBIR (h , “horas, ”); ESCRIBIR (m , “minutos y ”);ESCRIBIR (s , “segundos ”);

1)2)3)4) 5)6)7)8) 9)

Pero hay problemas que no podemos solucionar si sólo consideramos este orden, por ejemplo:

•Leer dos números por teclado, y mostrarlos por pantalla ordenados•Calcular el factorial de un entero



Leer dos números por teclado y escribirlos en orden creciente

ESCRIBIR ( “Dame dos números”);

LEER(m, n);

ESCRIBIR (m, n);

ESCRIBIR (n, m);

1)

2)

¿Cuál se ejecuta a continuación de 2)?

Sólo se ejecuta una de las dos sentencias ESCRIBIRDepende de si m ≤ n o no

4



Leer un entero por teclado y calcular su factorial

1)2)3)

4)5)

6)7)

8)9)

ESCRIBIR ( “Dame un número entero”);LEER( n );i n ;

factorial i; i i-1;

factorial factorial * i;i i -1;


¿?¿?¿?i factorialn

¿?¿?5¿?55

555545

20452035

60356025



Leer un entero por teclado y calcular su factorial

¿Cuántas veces deben ejecutarse las sentencias


?

5



Existe un orden natural (secuencial) de ejecución de las sentencias de un programa. Pero a veces será necesario alterarlo...

... para elegir, de entre varias opciones, cuál es la siguiente sentencia que debe ejecutarse

... para repetir la ejecución de una o varias sentencias mientras se dé una condición


Sentencia estructurada

sentencias elementales

mecanismo de control de flujo

Una serie de

junto con un

que determina en qué orden deben ejecutarse

6


Sentencias estructuradas: secuencial (bloque)

Sintaxis:sentencia_1sentencia_2

. . .sentencia_n

Las sentencias pueden ser elementales o estructuradas

Semántica:Las sentencias se ejecutan empezando por la primera, en el orden en que están escritas. Tras ejecutarse la última sentencia, se sale del bloque.

Ejemplo: los algoritmos realizados hasta ahora tienen una única sentencia "bloque" que agrupa a todas las sentencias elementales

sentencia_1

sentencia_2

sentencia_n


Sentencias estructuradas: condicional

Sintaxis:SI condición

sentencia_1;[ SI NO

sentencia_2;]FIN SI

• La cláusula SI NO es opcional• sentencia_1, sentencia_2 pueden ser sentencias

estructuradas

Semántica:1) Se evalúa la condición

2) Si el valor es VERDAD, se ejecuta la sentencia_1. Si no, se ejecuta la sentencia_2.

3) Termina la ejecución de la sentencia condicional

sentencia_1

condición V

sentencia_1sentencia_2

condición VF

7


condicional :ejemplo

Leer dos números por teclado y escribirlos en orden creciente

Algoritmo Ordenar númerosVariables

m,n es enteroPrincipio

leer(m, n)SI (m<n)

escribir (m,n)SI NO

escribir (n,m)FIN SI

Fin

escribir (m,n)escribir (n,m)

m<n VF


Sentencias estructuradas en C/C++: secuencial (bloque)

Sintaxis:{

sentencia_1 ;sentencia_2 ;

. . .sentencia_n ;

}Las sentencias pueden ser elementales o estructuradas

Semántica:Las sentencias se ejecutan empezando por la primera, en el orden en que están escritas. Tras ejecutarse la última sentencia, se sale del bloque.

sentencia_1

sentencia_2

sentencia_n

8


Bloque

Ejemplo:int main() {

int x = 2;{

int y = 3;cout << "x= " << x << " y= " << y << endl;

}x = x*2;cout << "x= " << x << endl;

}

NOTAS:

• En C se pueden declarar nuevas variables al comienzo de cada bloque (uso exclusivo dentro del bloque)

• En C++ se pueden declarar variables en cualquier parte (se pueden usar desde el punto donde se declaran hasta el final del bloque en que se declaran)

int x= 2

x = x*2

cout << "x= " << x << endl;

int y = 3

cout << x…


Bloque

Ejemplo:int main() {

int x = 2;{

int y = 3;cout << "x= " << x << " y= " << y << endl;

}x = x*2;cout << "x= " << x << "y= " << y << endl;

}ERROR !!!

de compilación

NOTAS:



int x= 2

x = x*2

cout << "x= " << x << endl;

int y = 3

cout << x…

NOTAS:



9


Composición condicional en C/C++

Hay dos sentencias de selección en C/C++

• if / else selección simple• switch selección múltiple


C/C++: sentencia if

Sintaxis:if (condición) sentencia_1

[else sentencia_2]

• La cláusula else es opcional• sentencia_1, sentencia_2 pueden ser sentencias estructuradas• Los paréntesis de la condición son obligatorios• La condición es una expresión de cualquier tipo. Recordar que en C no hay booleanos

(el valor 0 representa falso y cualquier valor 0 representa verdad)• La sentencia if NO termina en ‘;’. Si hay un ‘;’ tras sentencia_1 o sentencia_2

depende de ellas mismas.

Semántica:1. Se evalúa la condición

2. Si el valor representa VERDAD ( 0), se ejecuta la sentencia_1. Si representa FALSO (=0), se ejecuta la sentencia_2.

3. Termina la ejecución de la sentencia condicionalsentencia_1sentencia_2

condición VF

10


C/C++: sentencia if (ejemplos)

Ordenar dos enteros leídos de teclado (el primero debe acabar teniendo el valor más pequeño).

int main() {int n, m;cout << "Introduce dos enteros: ";cin >> m >> n;

if (m > n) {

m = n; n = m;

}

cout << m << " " << n;}

¿? ¿?

m n

¿? ¿?

4 5

4 4

5 4

4 4

4 4



Ordenar dos enteros leídos de teclado (el primero debe acabar teniendo el valor más pequeño).

int main() {int n, m, auxcout << "Introduce dos enteros: ";cin >> m >> n;

if (m > n) {

aux = m; m = n; n = aux;

}

cout << m << " " << n;}

¿? ¿? ¿?

m n

¿? ¿?

4 55 4

¿?

¿?

aux

5 4 5

4 4 5

4 5 5

4 5 5

11



int main() {int n, m, aux;cout << "Introduce dos enteros: ";cin >> m >> n;

if (m > n) {


}

cout << m << " " << n;}

Sí: Agrupan varias sentencias en una única de tipo bloque

Las llaves, ¿ son obligatorias ?



int main() {int n, m, aux;cout << "Introduce dos enteros: ";cin >> m >> n;

if (m > n) {


}

cout << m << " " << n;}

Sí: Agrupan varias sentencias en una única de tipo bloque

Las llaves, ¿ son obligatorias ?

Equivale a:

SI m>n

aux m

FIN SI

m n

n aux

12



int main() {int n1, n2, n3;cout << “Introduce tres enteros: “;cin >> n1 >> n2 >> n3;

if ((n1 <= n2) && (n2 <= n3))cout << "creciente";

elseif ((n1 >= n2) && (n2 >= n3))

cout << "decreciente";else

cout << "desordenada";

}

No son necesarias las llaves:

• Sólo hay una sentencia

El ‘;’ final se escribe porque lo necesita cout, NO la sentencia if

Dados tres enteros, introducidos por teclado, decidir si están dados en orden creciente, decreciente o si están desordenados


Problema de los else’s colgantes

Problema: leer tres enteros de teclado. La salida será un mensaje en pantalla indicando si el primer entero es estrictamente menor o mayor que los otros dos. En otro caso no se escribirá nada en pantalla.

Algoritmo ejemploVariables a, b, c son enterosPrincipio

leer(a, b, c)SI (a < b)

SI (a < c)escribir(a, " es el menor")

FIN SISI NO

SI (a > b Y a > c)escribir(a, " es el mayor")

FIN SIFIN SI

Fin

Las palabras “FIN SI” indican dónde

terminan las sentencias “SI”....

... y queda claro a qué “SI”

pertenece el “SI NO”

13


Problema de los else’s colgantes

int main() {int a, b, c;cin >> a >> b >> c;if ( a < b )

{if ( a < c ){

cout << a << “ es el menor”;}

}else

{if ( a > b && a > c ){

cout << a << “ es el mayor”;}

}}

¿A qué if corresponde el else?

Al inmediatamente anterior del

mismo bloque al que no se le haya

asignado todavía un else

SOLUCIÓN: poner llaves para separar bloques

RECOMENDACIÓN: poner todas las llaves


C/C++: switch (selección múltiple)

SINTAXIS:switch (expresión) {

case cte1: sentencia11....sentencia1kbreak;


........[ default: sentencia_d1

....sentencia_dkbreak; ]

}

expresión: de un tipo entero o char(los paréntesis son obligatorios)

Constantes del mismo tipo que la expresión (puede haber tantas como se quiera, pero sólo una en cada case)

La cláusula default es opcional:

• No es necesario que sea la última

El break de la última cláusula (case o default) no es necesario

Las sentencias pueden ser simples o estructuradas

14


C/C++: switch (selección múltiple)

SINTAXIS:switch (expresión) {



........[ default: sentencia_d1

....sentencia_dkbreak; ]

}

Los case’s y default actúan como etiquetas dentro del switch

SEMÁNTICA:

1. Se evalúa la expresión

2. Si el valor coincide con una de las constantes, se ejecutan las sentencias que hay tras el correspondiente case hasta

• Llegar a un break

• Llegar al final del switch (})

3. Si no coincide con ninguna constante, se procede del mismo modo comenzando con las sentencias de la parte default (si no hay default no se hace nada)


C/C++: switch (ejemplo)

int main() {char letra;cin >> letra;switch (letra) {

case 'a':case 'e':case 'i':case 'o':case 'u':

cout << letra << " es una vocal";break;

default:cout << letra << " NO es una vocal";break;

}}

15


El operador =

¿Es correcto el siguiente programa?

cout << "Introduce un número";cin >> n;if ( c = 2)

cout << "Has introducido el número 2";

Se ha utilizado el operador de asignación (=) en lugar del de comparación (==).

Variabl = expr es una expresión, cuyo valor es el resultado de evaluar expr.

En el caso anterior, (c=2) es una expresión con valor 2: siempre es cierta.

Para evitar el problema: escribir la condición al revés: (2==c)

cout << "Introduce un número";cin >> n;if ( c = 2)

cout << "Has introducido el número 2";


Fin

1


Informática

Sentencias estructuradas (ii): Bucles


Bucle (ejemplo): Factorial (análisis)

Problema: calcular el factorial de un entero n>0.

entradas) un entero n 0 (por teclado)salidas) un entero: n! (por pantalla)

Solución:El factorial de un número es n! = 1 * 2 * … * (n-1) * (n-2) * n

Además de n, necesitamos otras dos variables enteras:

• una (fact) para ir almacenando los productos parciales:

1 1*2 = 2 2 * 3 = 6 6 * 4 = 24 … 1*2*3* … * n = n!

• otra (k) que lleve cuenta del último factor considerado:

1 2 3… n-1 n

Bastará con comenzar con k=1 y repetir el proceso n veces (~ inducción).

Al finalizar la variable fact tendrá el valor n!.

2


Bucle (ejemplo): Factorial (diseño)

Algoritmo factorialVariables

n, fact, k SON enterosPrincipio

leer(n)

fact 1

k 1MIENTRAS (k <= n)fact fact * k

k k + 1FIN MIENTRASescribir(fact)

Fin

5 ¿? ¿?

5 1 ¿?

5 1 1

5 1 1

5 1 2

n fact k





leer(n)

fact 1



Fin

5 ¿? ¿?

5 1 ¿?

5 1 1

5 1 2

n fact k

5 2 2

5 2 3

3





leer(n)

fact 1



Fin

5 ¿? ¿?

5 1 ¿?

5 1 1

5 2 3

n fact k

5 6 3

5 6 4





leer(n)

fact 1



Fin

5 ¿? ¿?

5 1 ¿?

5 1 1

5 6 4

n fact k

5 24 4

5 24 5

4





leer(n)

fact 1



Fin

5 ¿? ¿?

5 1 ¿?

5 1 1

5 24 5

n fact k

5 120 5

5 120 6





leer(n)

fact 1



Fin

5 ¿? ¿?

5 1 ¿?

5 1 1

5 24 5

n fact k

5 120 5

5 120 6

5





leer(n)

fact 1



Fin

5 ¿? ¿?

5 1 ¿?

5 1 1

5 24 5

n fact k

5 120 5

5 120 6

Estructura del bucle:

Cuerpo: una sentencia que se repiteEn nuestro caso:el bloquefact fact * kk k + 1

Condición:mientras se cumpla, seguimos dentro del buclesi no se cumple, salimos del bucle

En nuestro caso:k <=n


Sentencias estructuradas: bucle

Sintaxis:

MIENTRAS condiciónsentencia_1;

FIN MIENTRAS

• sentencia_1 puede ser elemental o estructurada

Semántica:1) Se evalúa la condición

2) Si es VERDAD, se ejecuta el cuerpo del bucle(sentencia_1) y se vuelve a 1).Si no, se sale del bucle.

El bucle siempre termina evaluando la condición. Si la primera vez que la condición se evalúa es falsa, el cuerpo no se ejecuta.

¡Cuidado con los bucles infinitos!

condición V

F

sentencia

6





leer(n)fact 1k 1MIENTRAS (k <= n)

fact fact * kk k + 1

FIN MIENTRASescribir(fact)

Fin

leer (n)

fact 1

k 1

escribir (fact)

calcular factorialk <= n V

Fsentenciak k + 1

fact fact * k


Dados dos números naturales, m y n, calcular su máximo común divisor

Bucle (ejemplo): m.c.d (análisis)

Problema: calcular el mcd de dos naturales, m y n

Análisis:

entradas) dos enteros m, n 0 (por teclado)salidas) un entero: mcd (por pantalla)

Solución: Vamos probando sucesivamente con m, m-1, m-2…

hasta encontrar un número que sea divisor de m y de n.

7


Bucle (ejemplo): m.c.d (diseño)

Algoritmo mcdVariables

m,n, mcd SON enterosPrincipio

leer(m,n)mcd m

MIENTRAS ( m%mcd != 0 O n%mcd != 0 )mcd mcd -1

FIN MIENTRASescribir("El mcd de ", m , " y ", n, " es ", mcd)

Fin


Corrección de un bucle

¿Cómo asegurar que un bucle es correcto?

• Informal: traza

• Formal:– Hace lo que queremos: invariante del bucle– Problema de la parada: función de cota

8


Técnicas de demostración: inducción matemática

Sean una propiedad P: N {true, false} definida sobre los números naturales

Si se cumplen las dos siguientes condiciones:

1) P(1) es válido.2) Si P(n) es cierta para un natural n, entonces lo es

también para n+1 [ P (n+1) es cierta]

entonces P es cierta para todos los números naturales

Nota: el enunciado puede generalizarse a los números enteros, y generalizando la hipótesis 1) suponiendo que la propiedad P se verifica dentro de un intervalo [a,b]



Ejemplo: el problema del embaldosado.Sea un tablero dividido en mxm cuadrados iguales (m filas, m columnas), donde m es una potencia de 2. En él elegimos un cuadrado cualquiera.¿Es posible cubrir todo el tablero con teselas con la forma de L de modo que quede cubierto TODO el tablero, EXCEPTO el cuadrado seleccionado?

Si m= 2n con n=1, sí

9



Hipótesis: es posible cubrir un tablero de lado 2n-1. ¿Es posible cubrirlo si el lado mide 2n?

Descomponemos el tablero en cuatro, de lado 2n-1.

En uno cualquiera de los cuadrantes, seleccionamos un cuadrado

En cada uno de los otros tres cuadrantes, seleccionamos un cuadrado de modo que hagan esquina

Por hipótesis, es posible rellenar cada uno de los cuatro cuadrantes con la L. Por tanto, es posible rellenar todo el tablero.

Ejercicio: por inducción, probar n3 < 2n, para números naturales n lo suficientemente grandes( Es suficiente con que la condición se cumpla para todo n ≥ n0 ≥ 1 )


Invariante de un bucle (1)

Invariante de un bucle: es una propiedad sobre las variables del bucle que se satisface antes y después de cada iteración (prueba por inducción)

Invariantes:fact = (k-1) !

y k n+1

Hay que probar:1. Son ciertas al inicio del bucle2. Si son ciertas antes de una

iteración, entonces lo son después de la misma.

Corolario: son ciertas siempre

fact = (k-1) !y k n+1

1. Son ciertas al inicio del bucle2. Si son ciertas antes de una

iteración, entonces lo son después de la misma.

Corolario: son ciertas siempre

leer (n)

fact 1

k 1

escribir (fact)

calcular factorialk <= n V

Fsentenciak k + 1

fact fact * k

10



Invariantes: fact = (k-1) ! y k n+1¿Son ciertos al inicio del bucle?

Al inicio:k = 1 ( n>= 0) fact = 1 = 0!

¡¡ Son ciertas !!



leer(n)fact 1k 1MIENTRAS (k <= n)

fact fact * kk k + 1

FIN MIENTRASescribir(fact)

Fin



Invariantes: fact = (k-1) ! y k n+1Si son ciertas al inicio de una iteración, ¿lo son ciertos al final?

MIENTRAS (k <= n)fact fact * kk k + 1

FIN MIENTRAS

Si se ejecuta el cuerpo del bucle (es decir, k0 n):fact = (k0 – 1)! k0 y k = k0 + 1

luego el invariante es cierto al terminar la iteración:fact = k0! = (k – 1)! y k = k0 + 1 n+1

Y al salir del bucle: n < k n+1 k = n+1 y así fact = n!

Hipótesis: al inicio son ciertask = k0 n+1fact = (k0 – 1)!

11



Algoritmo primo

Variables n, k son enteros

Principio

leer(n); k 2

mientras (n%k 0)

k k + 1

fin mientras

si (k < n) escribir(“no es primo”)

si_no escribir(“es primo”)

Fin

El invariante puede ser usado como técnica de diseño de bucles correctos

Problema: determinar si un entero n > 1 es primo

Análisis: entradas) un entero n > 1 (por teclado)salidas) un mensaje (por pantalla)

Idea: encontrar el menor entero k que divide a n

Invariante:k n y j, 2 j < k, n “no es divisible por” j


Función de cota

La función de cota o función limitadora es una función f, de las variables del bucle en Z, tal que1. si la condición es verdad, el valor de la función para el valor de las variables

antes de realizar la iteración i-ésima es fi 02. tras la ejecución del bucle, el valor de la función para los nuevos valores de las

variables es fi+1 < fiEl bucle terminará tras un número finito de iteraciones ya que:

f1 > f2 > f3 > .... > fi > fi+1 > .... 0

Algoritmo factorial

Variables n, fact, k son enteros

Principio

1) leer(n); fact 1; k 1

2) mientras (k <= n)

3) fact fact * k

4) k k + 1

fin mientras

escribir(fact)

Fin

• Función limitadora: f(n,k) = n – k

• Suponer que el valor de la variable k antes de una iteración es

k = k0

1. Dado que k0 n entonces f(n,k0) 0

2. Y tras la ejecución de la iteración

f(n,k) =

f(n,k0+1)= n – k0 –1 < n –k0 = f(n,k0)

12


Composición de sentencias estructuradas

¿Cómo se combinan las sentencias estructuradas?

Secuencialmente:

VFV

F

VF

VF


Composición de sentencias estructuradas

¿Cómo se combinan las sentencias estructuradas?

Anidadas unas dentro de otras:

VF

VF

VF

13


Sentencias estructuradas

Los bloques básicos de un programa son sentencias estructuradas

3 tipos de sentencias estructuradas: bloque, condicional, bucle

Cada una: un único punto de entrada y un único punto de salida

Pueden componerse secuencialmente o anidadas

Hay una única sentencia inicial, en la que empieza a ejecutarseel programa.

Al acabar la ejecución de una sentencia, se pasa a la siguiente. Si no hay siguiente, se termina el programa.


Bucles en C/C++

C/C++ proporciona tres modos de implementar los bucles:

• La sentencia while• La sentencia do ... while• La sentencia for

14


Bucles en C/C++: while (sintaxis)

MIENTRAS condiciónsentencia

FIN MIENTRASwhile (condición)

sentencia;

sentenciacondiciónV

F


Bucles en C/C++: while (semántica)

La semántica de la sentencia while es la misma que hemos definido para el pseudocódigo:

while (condición)sentencia;

1) Se evalúa la condición

2) Si es VERDAD, se ejecuta el cuerpo del bucle(sentencia_1) y se vuelve a 1).Si no, se sale del bucle.

El bucle siempre termina evaluando la condición. Si la primera vez que la condición se evalúa es falsa, el cuerpo no se ejecuta.

15


Bucles en C/C++: do ... while (sintaxis)


FIN MIENTRAS dosentencia;

while(condición);

sentenciacondiciónV

F

En algunos problemas es natural verificar la condición después de haber ejecutado la sentencia:

sentencia


FIN MIENTRAS

sentencia

condiciónV

F

do .. while es la únicasentencia estructurada que

termina en ;


Bucles en C/C++: do ... while (semántica)

dosentencia;

while (condición);

1) Se ejecuta el cuerpo del bucle


3) Si es VERDAD, se vuelve a 1.Si no, se sale del bucle.

El cuerpo del bucle siempre se ejecuta al menos una vez.

16


Factorial (variación 1)

Completa el probrama para calcular el factorial, de modo que nos aseguremos de que el usuario ha tecleado un número válido (entero positivo):

Introduce un número entero positivo-2Introduce un número entero positivo-4Introduce un número entero positivo-1Introduce un número entero positivo-8Introduce un número entero positivo-9Introduce un número entero positivo-100Introduce un número entero positivo-3 Introduce un número entero positivo3El factorial de 3 es 6


Diseño del algoritmo



escribir ("Introduce un número entero positivo")leer (n)

MIENTRASescribir ("Introduce un número entero positivo")leer (n)

FIN MIENTRAS

Calcular el factorial de n como ya sabemosFin

(n <= 0)

17


Implementación del algoritmo




MIENTRAS n<= 0escribir ("Introduce un número entero positivo")leer (n)

FIN MIENTRAS

Calcular el factorial de n como ya sabemosFin

do{

cout << "Introduce un entero positivo: ";cin >> n;

}while (n<= 0);


Factorial (variación 2)




MIENTRAS (n<=0)escribir ("Introduce un número entero positivo")leer (n)

FIN MIENTRAS

Calcular el factorial de n

Fin

El usuario sólo dispone de tres oportunidades

n, fact, k, contador SON enteros

( ¿…? )

contador contador + 1FIN MIENTRAS

contador 0

SI ( ¿?) Calcular el factorial de nSI NO escribir ("Agotaste tus posibilidades, cansino")FIN SI

18


Bucles en C/C++: for (;;) (sintaxis)

for (inicialización ; condición ; incremento )sentencia;

Frecuentemente un bucle está controlado por un contador, que se inicializa antes del bucle y se incrementa en cada iteración

contador valor_inicial;

MIENTRAS (condición)sentencia;contador contador + incremento;

FIN MIENTRAScondición V

F

inicialización

incremento

otras sentencias


Bucles en C/C++: for (;;) (semántica)

1) Se ejecuta la inicialización


3) Si es VERDAD, se ejecuta la sentencia y, a continuación, se realiza el incremento.Si no, se sale del bucle.

for (inicialización ; condición ; incremento )sentencia;

19


Bucles en C/C++: for (;;) (ejemplo)

i1;

MIENTRAS (i≤n)

ESCRIBIR (i);i i+1;

FIN MIENTRAS

for (i=1; i<= n; i=i+1)cout << i;

i≤n V

F

i 1

i i+1;

ESCRIBIR (i);


El operador ++

for (i=1; i<= n; i ++)cout << i;

• Es un operador unario.• Incrementa en una unidad el valor de la variable a que se

aplica.• Puede escribirse antes o después de la variable:

++i : primero se incrementa el valor de i y, a continuación, se evalúa la expresión en la que se encuentra.

i++ : primero se evalúa la expresión en la que se encuentra y, a continuación, se incrementa el valor de i.

20


El operador ++ (ejemplos)

int i;

i = 4;

cout << i << endl;

cout << i++ << endl;

cout << i << endl;

cout << ++i << endl;

cout << i<< << endl;

4

4

5

6

6


Bibliografía recomendada

Programación MetódicaJ.L. Balcázar, McGraw-Hill 1993

Curso de ProgramaciónJ. Castro, F. Cucker, X. Messeguer, A. Rubio, L.Solano Prentice-Hall Hispanoamericana 1995

Diseño de Programas. Formalismo y AbstracciónM. Peña Prentice-Hall 1993

Fundamentos de Programación. Algoritmos y Estructuras de DatosL. Joyanes Aguilar, McGraw-Hill, 1996

Documents

informatica