PDF de programación - 3E. Ejemplos de secuencias

Fundamentos de la programación

3E

Grado en Ingeniería Informática
Grado en Ingeniería del Software
Grado en Ingeniería de Computadores
Facultad de Informática
Luis Hernández Yáñez
Universidad Complutense

Recorridos

Un aparcamiento
¿Paréntesis bien emparejados?
¿Dos secuencias iguales?
Números primos menores que N

Búsquedas

Búsqueda de un número en un archivo
Búsquedas en secuencias ordenadas

404
405
409
412
413
417
419
420

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

Fundamentos de la programación: Tipos e instrucciones II (Anexo II)

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

Fundamentos de la programación: Tipos e instrucciones II (Anexo II)

Página 404

Secuencia de caracteres E y S en archivo
E = Entra un coche; S = Sale un coche
¿Cuántos coches quedan al final de la jornada?
Varios casos, cada uno en una línea y terminado en punto
Final: línea sólo con punto

Fundamentos de la programación: Tipos e instrucciones II (Anexo II)

Página 405

#include <iostream>
using namespace std;
#include <fstream>

int main() {

int coches;
char c;
bool terminar = false;
ifstream archivo;
archivo.open("parking.txt");
if (!archivo.is_open()) {

}
else {

}
return 0;

// Recorrido...
archivo.close();

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

}

cout << "¡No se ha podido abrir el archivo!" << endl;

Fundamentos de la programación: Tipos e instrucciones II (Anexo II)

Página 406

while (!terminar) {

archivo >> c;
if (c == '.') { // . como primer carácter? (centinela)

terminar = true;

}
else {

coches = 0;
while (c != '.') { // Recorrido de la secuencia

cout << c;
if (c == 'E') {

coches++;

}
else if (c == 'S') {

coches‐‐;

}
archivo >> c;

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

}
...

Fundamentos de la programación: Tipos e instrucciones II (Anexo II)

Página 407

parking.cpp
parking.cpp

if (coches >= 0) {

cout << endl << "Quedan " << coches << " coches.";

cout << endl << "Error: Más salidas que entradas!";

}
else {

}
cout << endl;

}

}

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

Fundamentos de la programación: Tipos e instrucciones II (Anexo II)

Página 408

Cada paréntesis, con su pareja

a b ( c ( d e ) f g h ( ( i ( j k ) ) l m n ) o p ) ( r s ) #

Secuencia de caracteres terminada en # y con parejas de paréntesis:
Contador del nivel de anidamiento:
Al encontrar '('incrementamos –Al encontrar ')'decrementamos
Al terminar, el contador deberá tener el valor 0
Errores:
— Contador ‐1: paréntesis de cierre sin uno de apertura pendiente
— Contador termina con un valor positivo
Más paréntesis de apertura que de cierre
Algún paréntesis sin cerrar: (a(b(cd(e)f)gh(i))jk#

abc)de(fgh(ij))#

Fundamentos de la programación: Tipos e instrucciones II (Anexo II)

Página 409

Un error puede interrumpir el recorrido:

char c;
int anidamiento = 0, pos = 0;
bool error = false;
cin >> c;
while ((c != '#') && !error) {

pos++;
if (c == '(') {

anidamiento++;

}
else if (c == ')') {

anidamiento‐‐;

}
if (anidamiento < 0) {

error = true;

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

}

}
if (!error) {
cin >> c;

}

Fundamentos de la programación: Tipos e instrucciones II (Anexo II)

Página 410

parentesis.cpp
parentesis.cpp

if (error) {

cout << "Error: cierre sin apertura (pos. " << pos 

<< ")";

}
else if (anidamiento > 0) {

cout << "Error: Apertura sin cierre";

}
else {

cout << "Correcto";

}
cout << endl;

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

Fundamentos de la programación: Tipos e instrucciones II (Anexo II)

Página 411

iguales.cpp
iguales.cpp

bool iguales() {

bool sonIguales = true;
double d1, d2;
ifstream sec1, sec2;
bool final = false;
sec1.open("secuencia1.txt");
sec2.open("secuencia2.txt");
sec1 >> d1;
sec2 >> d2; // Al menos estarán los centinelas (0)
while (sonIguales && !final) {

sonIguales = (d1 == d2);
final = ((d1 == 0) || (d2 == 0));
if (!final) {
sec1 >> d1;
sec2 >> d2;

Cambia secuencia2.txtpor secuencia3.txt
Cambia secuencia2.txtpor secuencia3.txt
y por secuencia4.txtpara comprobar otros casos
y por secuencia4.txtpara comprobar otros casos

}

}
sec1.close();
sec2.close();
return sonIguales;

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

}

Fundamentos de la programación: Tipos e instrucciones II (Anexo II)

Página 412

Secuencia calculada: números divisibles sólo por 1 y ellos mismos (< N)

primos.cpp
primos.cpp

#include <iostream>
using namespace std;
bool primo(int n);
int main() {

int num, candidato;
cout << "Entero en el que parar (>1): ";
cin >> num;
if (num > 1) {

candidato = 2; // El 1 no se considera un número primo
while (candidato < num) {

cout << candidato << " "; // Mostrar número primo
candidato++;
while (!primo(candidato)) { // Siguiente primo

candidato++;

}

}

}
return 0;

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

}

Fundamentos de la programación: Tipos e instrucciones II (Anexo II)

Página 413

bool primo(int n) {

bool esPrimo = true;

for (int i = 2; i <= n ‐ 1; i++) {

if (n % i == 0) {

esPrimo = false; // Es divisible por i

}

}

return esPrimo;

}

Fundamentos de la programación: Tipos e instrucciones II (Anexo II)

Página 414

Mejoras:probar sólo impares; sólo pueden ser divisibles por impares;
no pueden ser divisibles por ninguno mayor que su mitad

primos2.cpp
primos2.cpp

candidato = 2;
cout << candidato << " "; // Mostrar el número primo 2
candidato++; // Seguimos con el 3, que es primo
while (candidato < num) {

cout << candidato << " ";   // Mostrar número primo
candidato = candidato + 2;  // Sólo probamos impares
while (!primo(candidato)) { // Siguiente número primo

candidato = candidato + 2;

}
} ...

bool primo(int n) {

bool esPrimo = true;
for (int i = 3; i <= n / 2; i = i + 2) {

if (n % i == 0) {

esPrimo = false; // Es divisible por i

}
}...

Fundamentos de la programación: Tipos e instrucciones II (Anexo II)

Página 415

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

Otra mejora más: Paramos al encontrar el primer divisor

primos3.cpp
primos3.cpp

bool primo(int n) {

bool esPrimo = true;

int i = 3;
while ((i <= n / 2) && esPrimo) {

if (n % i == 0) {

esPrimo = false;

}
i = i + 2;

}

return esPrimo;

}

Fundamentos de la programación: Tipos e instrucciones II (Anexo II)

Página 416

Fundamentos de la programación: Tipos e instrucciones II (Anexo II)

Página 417

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

#include <iostream>
using namespace std;
#include <fstream>

buscaarch.cpp
buscaarch.cpp

int busca(int n);
// Devuelve la línea en la que se encuentra o ‐1 si no está

int main() {

int num, linea;

cout << "Valor a localizar: ";
cin >> num;
linea = busca(num);
if (linea != ‐1) {

cout << "Encontrado (línea " << linea << ")" << endl;

}
else {

}
return 0;

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

}

cout << "No encontrado" << endl;

Fundamentos de la programación: Tipos e instrucciones II (Anexo II)

Página 418

int busca(int n) {

int i, linea = 0;
bool encontrado = false;
ifstream archivo;
archivo.open("enteros.txt");
if (!archivo.is_open()) {

linea = ‐1;

}
else {

archivo >> i;
while ((i != 0) && !encontrado) {

linea++;
if (i == n) {

encontrado = true;

}
archivo >> i;

}
if (!encontrado) {

linea = ‐1;

}
archivo.close();

}
return linea;

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

}

Centinela
Centinela

Fundamentos de la programación: Tipos e instrucciones II (Anexo II)

Página 419

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

Fundamentos de la programación: Tipos e instrucciones II (Anexo II)

Página 420

Secuencia ordenada de menor a mayor:
paramos al encontrar uno mayor o igual al buscado
Los que resten serán seguro mayores: ¡no puede estar el buscado!

buscaord.cpp
buscaord.cpp

cout << "Valor a localizar: ";
cin >> num;
archivo >> i;
while ((i != 0) && (i < num)) {

cout << "Encontrado (pos.: " << cont << ")";

cont++;
archivo >> i;

}
if (i == num) {

}
else {

cout << "No encontrado";

}
cout << endl;
archivo.close();

Fundamentos de la programación: Tipos e instrucciones II (Anexo II)

Página 421

Si el elemento está: procesamiento similar a secuencias desordenadas

2

5

9

15

16

24

41

73

78

82

123

153

159

...

num

i

9
?

?2
59

archivo >> i;

(i != 0) 
&& (i < num)
truetrue

cont++;

archivo >> i;

false
false

Fundamentos de la programación: Tipos e instrucciones II (Anexo II)

Página 422

Si el elemento no está: evitamos buscar en el resto de la secuencia

2

5

9

15

16

24

41

73

78

82

123

153

159

...

num

10
?

i

5915
?2

archivo >> i;

(i != 0) 
&& (i < num)
truetrue

cont++;

archivo >> i;

No se procesa
No se procesa
el resto
el resto
de la secuencia
de la secuencia

false
false

Fundamentos de la programación: Tipos e instrucciones II (Anexo II)

Página 423

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L

Licencia CC (Creative Commons)

Este tipo de licencias ofrecen algunos derechos a terceras personas
bajo ciertas condiciones.
Este documento tiene establecidas las siguientes:
Reconocimiento (Attribution):
En cualquier explotación de la obra autorizada por la licencia
hará falta reconocer la autoría.
No comercial (Non commercial):
La explotación de la obra queda limitada a usos no comerciales.
Compartir igual (Share alike):
La explotación autorizada incluye la creación de obras derivadas
siempre que mantengan la misma licencia al ser divulgadas.
Pulsa en la imagen de arriba a la derecha para saber más.

Fundamentos de la programación: Tipos e instrucciones II (Anexo II)

Página 424

z
e
ñ
á
Y
 
z
e
d
n
á
n
r
e
H
 
s
i
u
L