Una de las dificultades más comunes son los vectores, sobretodo comprender la diferencia entre el indice de un vector (posición) y el valor contenido en el índice del vector (datos).
Para complicarlo aún más viene el tema de las matrices, que no son más que vectores pero en dos dimensiones, esto es que ahora el índice está formado por dos posiciones.
Sobre teoría de matrices se ha escrito mucho, lo que pretendo en este post es simplemente mostrar como acceder a una matriz y determinar si es una matriz identidad o no (¿Qués es una matriz identidad?). Para este fin utilizaremos el recorrido secuencial de una matriz fila a fila y para cada elemento de la fila veremos si tiene el valor correcto que le corresponde a la matriz identidad (1 en la diagonal y 0 en el resto de campos):
int esIdentidad = 1; //variable que indica si la matriz es identidad o no
int x, y = 0; //indice de filas y columnas
int N=10;//dimensión de la matriz
//se asumen que la matriz es de Identidad hasta que se muestre que tenga un valor incorrecto
while(esidentidad)
{
//recorre todos los elementos de la fila hasta que encuentre algún error o termine la fila
for(int y=0; y<N && esIdentidad; y++)
{
//la diagonal debe tener el valor 1, en caso contrario no puede ser una matriz Identidad
if(x==y && Matriz[x][y] !=1) esidentidad = 0;
//los que no están en la diagonal deben ser 0, en caso contrario no puede ser una matriz identidad
if(x!=y && Matriz[x][y] !=0) esidentidad = 0;
}
x++;//cada iteración del while se corresponde con cada fila de la matriz
}
//resultado de la evaluación
if(esIdentidad) print("La matriz es identidad");
else print("La matriz no es identidad");
Vemos que el el indice de la matriz está compuesto por dos posiciones: x e y.
Vemos que el valor en una posición determinada de la matriz se accede a través de las posiciones: Matriz[x][y].
Vemos que cuando encuentra un valor que no se corresponde con la matriz identidad cambia la variable esIdentidad para salir inmediatamente de los bucles for y while, puesto que al primer valor incorrecto no hace falta seguir recorriendo la matriz, ya sabemos que no es de Identidad.
Vemos que para recorrer una matriz hace falta 2 bucles anidados, en este caso el while recorre las filas de la matriz y el for recorre las columnas para cada fila.
domingo, 20 de julio de 2014
domingo, 23 de marzo de 2014
Recursividad
Se dice que una función es recursiva cuando su ecuación de solución se utiliza a si misma para resolverse.
Un ejemplo típico de recursividad es la función Factorial, sabemos que el Factorial de un numero es igual al producto de dicho número multiplicado por el factorial del número anterior:
Factorial(4) = 4 * Factorial(3)
Vemos que está definiendo la solución del factorial empleando la misma fórmula del factorial, puesto que:
Factorial(3) = 3 * Factorial(2)
Factorial(2) = 2 * Factorial(1)
....
Pero, ¿Cuándo termina la recursividad? Es absolutamente necesario definir lo que se llama un TOPE, que es cuando la recursividad termina, sino seguiríamos hasta el infinito.
Para el caso del ejemplo típico del factorial, se sabe que esta función se aplica a un conjunto de números enteros mayores o iguales a 0, del cual Factorial(0) = 1, siendo esta fórmula la única que no utiliza la recursividad para su definición, por tanto:
Toda función recursiva necesita un TOPE, dicho tope es una de la soluciones de la función que no se define por si misma.
Si generalizamos podemos decir que, Para toda N tal que N>=0, Factorial(N) se resuelve con las siguientes ecuaciones:
Si N=0, Factorial(N) = 1
Si N>0, Factorial(N) = N * Factorial(N-1)
Para cualquier otro valor de N, No existe conjunto solución para Factorial(N)
Otra característica importante de una función recursiva es que al llamarse a si misma los parámetros deben variar, sino entrará en bucle infinito, por ejemplo esto sería un error:
Factorial(N) = N * Factorial(N) ---> En este caso caerá en bucle infinito porque NUNCA llegará al TOPE
Por tanto:
En toda función recursiva es necesario que la llamada si misma garantice que en algún punto llegará al TOPE.
//ejemplo de función recursiva
//asumimos que el valor N que ingresa es >=0
int factorial (int N)
{
//lo primero que definimos en una función recursiva el el TOPE
if(N == 0) return 1;
//La llamada recursiva con N-1 asegura que en algún momento llegará a ejecutar factorial(0)
return N * Factorial(N-1);
}
¿Por qué es importante definir el tope al principio?
¿Podríamos utilizar la operación unaria -- para llamar de forma recursiva: Factorial(N--)?
Un ejemplo típico de recursividad es la función Factorial, sabemos que el Factorial de un numero es igual al producto de dicho número multiplicado por el factorial del número anterior:
Factorial(4) = 4 * Factorial(3)
Vemos que está definiendo la solución del factorial empleando la misma fórmula del factorial, puesto que:
Factorial(3) = 3 * Factorial(2)
Factorial(2) = 2 * Factorial(1)
....
Pero, ¿Cuándo termina la recursividad? Es absolutamente necesario definir lo que se llama un TOPE, que es cuando la recursividad termina, sino seguiríamos hasta el infinito.
Para el caso del ejemplo típico del factorial, se sabe que esta función se aplica a un conjunto de números enteros mayores o iguales a 0, del cual Factorial(0) = 1, siendo esta fórmula la única que no utiliza la recursividad para su definición, por tanto:
Toda función recursiva necesita un TOPE, dicho tope es una de la soluciones de la función que no se define por si misma.
Si generalizamos podemos decir que, Para toda N tal que N>=0, Factorial(N) se resuelve con las siguientes ecuaciones:
Si N=0, Factorial(N) = 1
Si N>0, Factorial(N) = N * Factorial(N-1)
Para cualquier otro valor de N, No existe conjunto solución para Factorial(N)
Otra característica importante de una función recursiva es que al llamarse a si misma los parámetros deben variar, sino entrará en bucle infinito, por ejemplo esto sería un error:
Factorial(N) = N * Factorial(N) ---> En este caso caerá en bucle infinito porque NUNCA llegará al TOPE
Por tanto:
En toda función recursiva es necesario que la llamada si misma garantice que en algún punto llegará al TOPE.
//ejemplo de función recursiva
//asumimos que el valor N que ingresa es >=0
int factorial (int N)
{
//lo primero que definimos en una función recursiva el el TOPE
if(N == 0) return 1;
//La llamada recursiva con N-1 asegura que en algún momento llegará a ejecutar factorial(0)
return N * Factorial(N-1);
}
¿Por qué es importante definir el tope al principio?
¿Podríamos utilizar la operación unaria -- para llamar de forma recursiva: Factorial(N--)?
domingo, 9 de febrero de 2014
Inserción de valores en un vector ordenado
En esta ocasión trabajaremos una estructura fija (vector) como si fuese una estructura variable, esta solución se puede aplicar en escenarios en los cuales sabemos que:
- Como máximo utilizaremos un número determinado de elementos.
- La inicialización (inserción) se realiza una vez o con muy poca frecuencia,
- Y se necesita acceder continuamente a elementos en concreto.
Por ejemplo, sabemos que en un aula no se puede exceder de los 100 alumnos, la matrícula se realiza al principio de curso y durante el curso se puede acceder en cualquier momento al expediente de cualquiera de los alumnos matriculados.
En un aula podrían inscribirse 25 alumnos y en otra 82 alumnos, si se quisiera imprimir un listado de los alumnos matriculados en cada aula no es necesario recorrer el vector de 100 elementos, sino que en el primero se recorrerá 25 veces y en el segundo 82.
Para hacer uso de los vectores de esta forma utilizaremos una variable auxiliar que representará el número de elementos utilizados, así cada vez que necesitemos hacer una operación sobre todos los elementos no recorreremos todos los elementos del vector sino todos los utilizados.
int listaOrdenada[N];
int numelem = 0; //cantidad de elementos ocupados de la lista
Ahora complicaremos un poco el problema y suponemos que los alumnos cuando se matricula no vienen de forma ordenada, pero se requiere almacenarlos de forma ordenada por apellido, esto implica que cada vez que se agrega un alumno a la lista de matriculados se debe buscar la posición del vector en la cual se debe insertar, no siempre será el último.
Este tipo de problema utiliza varios de los conceptos vistos en entradas anteriores, tales como:
- El uso de vectores para almacenar información del mismo tipo.
- El uso de vectores como estructura que ocupa un espacio de memoria fija de la cuál sólo utilizaremos una parte de forma dinámica.
- El uso de los iteradores for y while para realizar una acción sobre cada elemento de un vector.
- Recorridos de vectores en forma ascendente y en forma descendente
- El uso de comprador if para determinar la posición en la cual se debe insertar el nuevo elemento.
Para simplificar el problema supondremos que los alumnos son números enteros y sus apellidos son números mayores que cero y os invito a que modifiquéis el código para adaptarlo a un vector de una estructura de alumnos que incluya los nombres y los apellidos.
Os dejo el código a continuación en C:
#include <stdio.h>
#include <stdlib.h>
#define N 100
int main(int argc, char *argv[])
{
//definición de variables
int listaOrdenada[N];
int numelem = 0; //cantidad de elementos ocupados de la lista
int numero;
int i, j;
//inicializa vector
for(i=0; i<N; i++) listaOrdenada[i] = 0;
//proceso
//mensajes iniciales
printf("Ingrese los numeros de la lista \n\nLos numeros deben ser mayores que 0 \nPara introducir pulse <ENTER> \n");
printf("como maximo puede ingresar %d numeros \n", N);
printf("Para finalizar pulse 0 y <ENTER>\n");
//Lee valor a ingresar en el vector
printf("Numero: ");
scanf("%d", &numero);
printf("Numero ingresado %d \n", numero);
while(numero != 0 && numelem < N)
{
i = 0;
//ubica la posición para insertar el número
while(i<numelem && listaOrdenada[i] < numero) i++;
//en el caso que se inserte en la última posición: i == numelem
if(i==numelem) {
listaOrdenada[i]=numero;
numelem++;
}
else{
//tiene que desplazar a todos los elementos posteriores
j = numelem;
numelem++;
//recorre la lista de forma inversa para desplazar los valores
while(j>i){
listaOrdenada[j] = listaOrdenada[j-1];
j--;
}
listaOrdenada[i] = numero;
}
//imprime la lista de elementos
for(i=0; i<numelem; i++) printf("%d \t",listaOrdenada[i]);
printf("\n\nNumero: ");
scanf("%d", &numero);
printf("Numero ingresado %d \n", numero);
}
printf("Elementos utilizados: %d \n", numelem);
system("PAUSE");
return 0;
}
- Como máximo utilizaremos un número determinado de elementos.
- La inicialización (inserción) se realiza una vez o con muy poca frecuencia,
- Y se necesita acceder continuamente a elementos en concreto.
Por ejemplo, sabemos que en un aula no se puede exceder de los 100 alumnos, la matrícula se realiza al principio de curso y durante el curso se puede acceder en cualquier momento al expediente de cualquiera de los alumnos matriculados.
En un aula podrían inscribirse 25 alumnos y en otra 82 alumnos, si se quisiera imprimir un listado de los alumnos matriculados en cada aula no es necesario recorrer el vector de 100 elementos, sino que en el primero se recorrerá 25 veces y en el segundo 82.
Para hacer uso de los vectores de esta forma utilizaremos una variable auxiliar que representará el número de elementos utilizados, así cada vez que necesitemos hacer una operación sobre todos los elementos no recorreremos todos los elementos del vector sino todos los utilizados.
int listaOrdenada[N];
int numelem = 0; //cantidad de elementos ocupados de la lista
Este tipo de problema utiliza varios de los conceptos vistos en entradas anteriores, tales como:
- El uso de vectores para almacenar información del mismo tipo.
- El uso de vectores como estructura que ocupa un espacio de memoria fija de la cuál sólo utilizaremos una parte de forma dinámica.
- El uso de los iteradores for y while para realizar una acción sobre cada elemento de un vector.
- Recorridos de vectores en forma ascendente y en forma descendente
- El uso de comprador if para determinar la posición en la cual se debe insertar el nuevo elemento.
Para simplificar el problema supondremos que los alumnos son números enteros y sus apellidos son números mayores que cero y os invito a que modifiquéis el código para adaptarlo a un vector de una estructura de alumnos que incluya los nombres y los apellidos.
Os dejo el código a continuación en C:
#include <stdio.h>
#include <stdlib.h>
#define N 100
int main(int argc, char *argv[])
{
//definición de variables
int listaOrdenada[N];
int numelem = 0; //cantidad de elementos ocupados de la lista
int numero;
int i, j;
//inicializa vector
for(i=0; i<N; i++) listaOrdenada[i] = 0;
//proceso
//mensajes iniciales
printf("Ingrese los numeros de la lista \n\nLos numeros deben ser mayores que 0 \nPara introducir pulse <ENTER> \n");
printf("como maximo puede ingresar %d numeros \n", N);
printf("Para finalizar pulse 0 y <ENTER>\n");
//Lee valor a ingresar en el vector
printf("Numero: ");
scanf("%d", &numero);
printf("Numero ingresado %d \n", numero);
while(numero != 0 && numelem < N)
{
i = 0;
//ubica la posición para insertar el número
while(i<numelem && listaOrdenada[i] < numero) i++;
//en el caso que se inserte en la última posición: i == numelem
if(i==numelem) {
listaOrdenada[i]=numero;
numelem++;
}
else{
//tiene que desplazar a todos los elementos posteriores
j = numelem;
numelem++;
//recorre la lista de forma inversa para desplazar los valores
while(j>i){
listaOrdenada[j] = listaOrdenada[j-1];
j--;
}
listaOrdenada[i] = numero;
}
//imprime la lista de elementos
for(i=0; i<numelem; i++) printf("%d \t",listaOrdenada[i]);
printf("\n\nNumero: ");
scanf("%d", &numero);
printf("Numero ingresado %d \n", numero);
}
printf("Elementos utilizados: %d \n", numelem);
system("PAUSE");
return 0;
}
martes, 21 de enero de 2014
Listas dinámicas
La
manera más práctica de trabajar con una lista de objetos del mismo
tipo es un Vector (o Array), cuando se instancia un vector se está
reservando en memoria una cantidad fija de bytes para almacenar la
información, así si tenemos:
int
myList[5]; //reserva espacio para 5 variables de tipo int
myList[0]
= 1; //almacena el valor 1 en la primera posición del vector
Ahora
utilizaré un ejemplo de un problema tipo de examen, habla sobre el
registro de reclamaciones de un comercio, cada reclamación debe
contener:
- El nombre de la persona que realiza la reclamación
- La fecha de la reclamación
- La descripción de la reclamación
- El estado de la reclamación: 0 si está abierta, 1 si está resuelta.
Para
representar una reclamación podemos utilizar una estructura de este
tipo:
typedef
struct reclamacion
{
String
nombrePersona;
Date
fechaReclamacion;
String
descripcion;
int
estado;
}Reclamacion;
Ahora
creamos un Vector para almacenar la lista de reclamaciones:
Reclamacion
Lista[100]; //vector de capacidad para 100 reclamaciones
Pero,
y ¿Qué pasa si hay más de 100 reclamaciones?
Cuando
no sabemos la dimensión que puede tomar una lista lo mejor es
reservar memoria de forma dinámica, para eso podemos utilizar los
punteros.
Así,
sólo creamos una variable de tipo puntero que apunte a la
estructura, y modificamos la estructura para que apunte al siguiente
elemento de la lista, así;
typedef
struct reclamacion
{
String
nombrePersona;
Date
fechaReclamacion;
String
descripcion;
int
estado;
struct
reclamacion * siguiente; //este puntero apunta a la siguiente
reclamación
}Reclamacion;
Reclamacion
* listaReclamaciones;
listaReclamaciones
= NULL; //inicializamos el puntero a NULL hasta que empiecen a llegar
las reclamaciones
//creamos
la primera reclamación
Reclamacion
* rec1 = new Reclamacion;
rec1.nombrePersona
= “Juan”;
rec1.fechaReclamacion
= new Date(); //representa que toma la fecha actual (esto varía
según el lenguaje de programación)
rec1.descripcion
= “ejemplo de reclamacion1”;
rec1.estado
= 0; //lo inicializa a 0 porque cuando se crea está abierta
rec1->siguiente
= NULL; //inicializa a NULL porque es un puntero
Ahora
para agregar la primera reclamación a la lista hacemos que la
variable listaReclamaciones ya no apunte a NULL sino que apunte al
elemento rec1:
listaReclamaciones
= rec1;
Para
el caso de una segunda reclamación es distinto y dependerá
si se quiere agregar al principio de la lista o al final de la lista,
vamos a agregarlo al final, así listaReclamaciones apuntará a rec1
y rec1->siguiente apuntará a rec2:
//creamos
la segunda reclamación
Reclamacion
* rec2 = new Reclamacion;
rec2.nombrePersona
= “Pedro”;
rec2.fechaReclamacion
= new Date();
rec2.descripcion
= “ejemplo de reclamacion2”;
rec2.estado
= 0;
rec2->siguiente
= NULL;
Si
hacemos:
listaReclamaciones->siguiente
= rec2; //es lo mismo que rec1->siguiente = rec2
Tenemos
el problema resuelto, rec1->siguiente ya no apunta a NULL sino que
apunta a rec2 y rec2 es la última de la lista.
¿Y
que pasa si no sabemos la cantidad de elementos que tiene la lista y
queremos agregar un elemento al final?
La
solución es tomar un puntero auxiliar y desplazamos hasta el último
elemento de la lista y hacer que este último elemento apunte al
elemento nuevo que queremos agregar a la lista:
//puntero
auxiliar que se desplaza hasta el último elemento
Reclamacion
* pAuxiliar = listaReclamaciones; //se inicializa apuntando al
primero de la lista
//mientras
el siguiente del auxiliar es distinto a nulo, avanza el puntero al
siguiente elemento, hasta llegar al último
while(pAuxiliar->siguiente
!= NULL) pAuxiliar = pAuxiliar->siguiente;
//ahora
agregamos el nuevo elemento al final de la lista
pAuxiliar->
siguiente = nuevaRec; //nuevaRec es el nuevo elemento de tipo
reclamacion*
Existen
muchas variantes:
- agregar el elemento al inicio de la lista
- agregar el elemento en medio de la lista (por ejemplo para una lista ordenada)
sábado, 30 de noviembre de 2013
Representación de un puntero en memoria
La representación de la memoria para una variable de tipo int se puede entender de forma muy simple, en tiempo de ejecución cuando las variable se crean se les asigna un espacio físico en memoria, así cuando vemos:
//se define la variable a de tipo int
int a;
La variable a tiene reservado un espacio para almacenar su contenido (el valor de la variable) y se sabe que ese contenido tiene que ser de tipo int porque así ha sido definida.
Sin embargo, cuando utilizamos variables de tipo punteros la comprensión de la asignación de la memoria es un poco más complicada, una variable de tipo puntero tiene en su definición "al menos un *", aquí unos ejemplos:
int * b;
int **c;
Cuando se reserva memoria para un puntero, se separa un espacio de memoria pero el contenido debe tener el formato de una dirección de memoria. si tomamos como ejemplo:
int * b;
El primer paso es identificar el nombre de la variable y el tipo de la variable:
nombre de variable: b
tipo de la variable: int *
como el tipo de la variable contiene "al menos un *" entonces el contenido (el valor) tiene el formato de una dirección, esa dirección debe apuntar al tipo de variable al cual apunta.
Para saber el tipo de variable al cual apunta, seguimos el segundo paso, que consiste en leer la misma definición de la variable pero ahora el * pasa a ser parte del nombre de la variable:
nombre de variable: *b
tipo de la variable: int
En una tabla:
Podemos ver que para la variable b el contenido es la dirección 0003, y en la dirección 3 se encuentra la variable *b de tipo int en la que se guarda el contenido 3.
Podríamos aprovechar el espacio de memoria de a para guardar el contenido de b:
int a = 5;
int* b;
*b = a; //*b y a son del mismo tipo por eso se puede realizar la instrucción de asignación.
La representación en la tabla de memoria sería:
Podemos ver que en este caso: a y *b están en la misma dirección de memoria.
//se define la variable a de tipo int
int a;
La variable a tiene reservado un espacio para almacenar su contenido (el valor de la variable) y se sabe que ese contenido tiene que ser de tipo int porque así ha sido definida.
Sin embargo, cuando utilizamos variables de tipo punteros la comprensión de la asignación de la memoria es un poco más complicada, una variable de tipo puntero tiene en su definición "al menos un *", aquí unos ejemplos:
int * b;
int **c;
Cuando se reserva memoria para un puntero, se separa un espacio de memoria pero el contenido debe tener el formato de una dirección de memoria. si tomamos como ejemplo:
int * b;
El primer paso es identificar el nombre de la variable y el tipo de la variable:
nombre de variable: b
tipo de la variable: int *
como el tipo de la variable contiene "al menos un *" entonces el contenido (el valor) tiene el formato de una dirección, esa dirección debe apuntar al tipo de variable al cual apunta.
Para saber el tipo de variable al cual apunta, seguimos el segundo paso, que consiste en leer la misma definición de la variable pero ahora el * pasa a ser parte del nombre de la variable:
nombre de variable: *b
tipo de la variable: int
Ahora vemos que la dirección a la que apunta el contenido de b (el valor de b) apunta a una dirección de memoria cuyo nombre se puede interpretar como *b y cuyo tipo es int.
Para verlo de una forma más práctica representaremos las siguientes líneas de código:
int a = 5:
//reserva memoria para el puntero, esta asignación varía según el lenguaje de programación
int* b = new int();
*b = 3;
En una tabla:
Podemos ver que para la variable b el contenido es la dirección 0003, y en la dirección 3 se encuentra la variable *b de tipo int en la que se guarda el contenido 3.
Podríamos aprovechar el espacio de memoria de a para guardar el contenido de b:
int a = 5;
int* b;
*b = a; //*b y a son del mismo tipo por eso se puede realizar la instrucción de asignación.
La representación en la tabla de memoria sería:
Podemos ver que en este caso: a y *b están en la misma dirección de memoria.
sábado, 19 de octubre de 2013
Estructuras (Struct)
Cuando programamos hacemos uso de tipos básicos de datos, como enteros, decimales, caracteres, cadenas de caracteres, fechas. Pongo un ejemplo simple:
//definición de nombre y edad de la persona
char *nombre;
int edad;
//instanciación del nombre y la edad de la persona
nombre = "Juan";
edad = 21;
digamos que ahora queremos trabajar con la información de 2 personas:
//definición de nombre y edad de las personas
char *nombre1;
int edad1;
char *nombre2;
int edad2;
//instanciación del nombre y la edad de las personas
nombre1 = "Juan";
edad1 = 21;
nombre2 = "Pedro";
edad2 = 25;
¿Qué pasaría si queremos trabajar con 100 personas? ¿Crearíamos 100 variables para el nombre y 100 variables para la edad?
Lo primero que se nos ocurre es que si son muchos elementos iguales podemos utilizar un Array, pero los elementos de un Array deben ser todos del mismo tipo por ejemplo char * para guardar un array de nombres o int para guardar un Array de edades. Así podríamos modificar nuestro programa para poder manejar la información de las 100 personas:
//instanciación de los Arrays de nombres y de edades
char * nombres[100];
int edades[100];
Con esto tendríamos resuelto el manejo de la información de 100 personas con nombre y edad, pero qué pasaría si ahora además del nombre y la edad queremos saber: el apellido, la fecha de nacimiento, el número de identificación, el email, etc. ¿Tendríamos que crear un Array para cada dato?
La solución para esto son las estructuras (se llaman también registros o tuplas), son agrupaciones de tipos de datos para crear un nuevo tipo de dato definido por el programador, así con un único tipo de dato crearíamos un solo Array.
Para el ejemplo nuestro nuevo tipo de dato sería Persona y lo definiríamos así:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//nombre y edad quedan dentro de la estructura Persona
typedef struct Persona {
char * nombre;
int edad;
//si quisiéramos agregar más información a la persona la agregaríamos aquí y no modificaríamos la definición del Array
} Persona;
int main(int argc, char *argv[])
{
//Definimos un Array de 100 elementos de tipo Persona
//Persona es el tipo de variable
//listaPersonas es el nombre de la variable
Persona listaPersonas[100];
}
Las estructuras se utilizan normalmente en la programación estructurada y su concepto es similar al de las clases (programación orientada a objetos).
viernes, 13 de septiembre de 2013
Números primos
Empiezo un nuevo curso y revisando el material que debo tratar con una de mis alumnas de este semestre me encuentro con un problema clásico, un enunciado que se repite mucho ya que mezcla conceptos de estructuras de control (condicionales e iterativas) y aplica conceptos matemáticos, este post va de los números primos.
El problema busca determinar si un número es primo o no, por lo tanto, preparamos la información del problema:
¿Qué tengo?
Tengo un número entero positivo mayor que 1
¿Que quiero?
Determinar si dicho número es primo o no
¿Cómo lo hago?
Primero debemos tener claro lo que es un número primo, dejamos el enlace a wikipedia, en el que dice: un número primo es un número natural mayor que 1 que tiene únicamente dos divisores distintos: él mismo y el 1.
Para que quede más claro:
5 es primo, porque sólo es divisible entre 1 y 5, no es divisible entre 2, ni 3 ni 4 y no consideramos evaluar si es divisible entre 6, 7 o más porque el divisor de un número debe ser siempre menor o igual a él.
6 no es primo, porque es divisible entre 2 y 3.
Generalizando, basta con encontrar un número entre 1 y N que sea divisor de N, para decir que N no es primo.
Analizamos, todo lo que hemos dicho hasta ahora:
1. Basta con encontrar un número: esto se traduce en una iteración con condicionante booleana que se detendrá cuando encuentre un divisor.
2. Entre 1 y N: esto se traduce como que la iteración tendrá el condicionante que el divisor buscado debe iterar entre 1 y N.
Planteamos el pseudocódigo:
//asumimos que tenemos una función con parámetro N que es un entero mayor a 1
//definimos la condicionante booleana
bool esPrimo = true; //asumimos que es primo a menos que encontremos un divisor
//definimos variable que itera entre 1 y N buscando un divisor
int iDivisor = 2;
//iteración
mientras(esPrimo AND iDivisor < N)
{
//condicionante que puede hacer que esPrimo cambie: cuando encuentra un divisor
SI (N % iDivisor == 0) //la operación % indica que calcula el residuo de la división de N entre iDivisor
{
esPrimo = false;
}fin_SI
iDivisor++; //incrementa el iDivisor para continuar la búsqueda
}fin_mientras
//puede salir de la iteración porque encontró un divisor, en ese caso esPrimo será falso
//puede salir de la iteración porque no encontró divisor, en ese caso iDivisor es igual a N
//condicionante
SI(esPrimo)
{
imprime("Es Primo")
}
Caso contrario
{
imprime("No es primo")
}
Este problema, como todos, se puede resolver de distintas formas, si revisáis el enlace de wikipedia por ejemplo, podréis ver que los números primos cumplen muchas propiedades que pueden aplicarse al programa para mejorar el rendimiento (por ejemplo reducir el número de iteraciones), sobretodo si se quieren evaluar números muy grandes.
El problema busca determinar si un número es primo o no, por lo tanto, preparamos la información del problema:
¿Qué tengo?
Tengo un número entero positivo mayor que 1
¿Que quiero?
Determinar si dicho número es primo o no
¿Cómo lo hago?
Primero debemos tener claro lo que es un número primo, dejamos el enlace a wikipedia, en el que dice: un número primo es un número natural mayor que 1 que tiene únicamente dos divisores distintos: él mismo y el 1.
Para que quede más claro:
5 es primo, porque sólo es divisible entre 1 y 5, no es divisible entre 2, ni 3 ni 4 y no consideramos evaluar si es divisible entre 6, 7 o más porque el divisor de un número debe ser siempre menor o igual a él.
6 no es primo, porque es divisible entre 2 y 3.
Generalizando, basta con encontrar un número entre 1 y N que sea divisor de N, para decir que N no es primo.
Analizamos, todo lo que hemos dicho hasta ahora:
1. Basta con encontrar un número: esto se traduce en una iteración con condicionante booleana que se detendrá cuando encuentre un divisor.
2. Entre 1 y N: esto se traduce como que la iteración tendrá el condicionante que el divisor buscado debe iterar entre 1 y N.
Planteamos el pseudocódigo:
//asumimos que tenemos una función con parámetro N que es un entero mayor a 1
//definimos la condicionante booleana
bool esPrimo = true; //asumimos que es primo a menos que encontremos un divisor
//definimos variable que itera entre 1 y N buscando un divisor
int iDivisor = 2;
//iteración
mientras(esPrimo AND iDivisor < N)
{
//condicionante que puede hacer que esPrimo cambie: cuando encuentra un divisor
SI (N % iDivisor == 0) //la operación % indica que calcula el residuo de la división de N entre iDivisor
{
esPrimo = false;
}fin_SI
iDivisor++; //incrementa el iDivisor para continuar la búsqueda
}fin_mientras
//puede salir de la iteración porque encontró un divisor, en ese caso esPrimo será falso
//puede salir de la iteración porque no encontró divisor, en ese caso iDivisor es igual a N
//condicionante
SI(esPrimo)
{
imprime("Es Primo")
}
Caso contrario
{
imprime("No es primo")
}
Este problema, como todos, se puede resolver de distintas formas, si revisáis el enlace de wikipedia por ejemplo, podréis ver que los números primos cumplen muchas propiedades que pueden aplicarse al programa para mejorar el rendimiento (por ejemplo reducir el número de iteraciones), sobretodo si se quieren evaluar números muy grandes.
Suscribirse a:
Entradas (Atom)