El blog de Wewewew

La función scanf

10 3161565164181
aab baa aba

int a;
long long int b;
char cadena[15];
scanf("%d %lld", &a, &b); 
scanf("%s", cadena); // 'cadena' es ya una referencia a memoria

La función fgets

// ...
LLLLLLLLL
3 2
// ...

int i, j;
char entrada[10];
fgets(entrada,10,stdin);
// Procesamos 'entrada', que contiene la siguiente secuencia de caracteres: 
// 'L','W','W','W', 'L', 'L', 'L', 'L', 'W' y '\n' <= ¡Sí! el salto de línea
// Recuperamos los enteros:
fgets(entrada,10,stdin);
sscanf(entrada,"%d %d",&i,&j);

Integración de Monte Carlo

Apelando al hecho de que una integral es la sumatoria de la infinidad de resultados de evaluar una función en un intervalo dado, se toman puntos de evaluación aleatorios dentro de ese intervalo dado, se evalúan y se van acumulando para luego realizarles un ajuste matemático, les diría que lo buscaran en Wikipedia, pero este documento me resultó especialmente revelador.

Para el caso de la implementación de POO lo que se consideró fue la creación de dos clases Random y Funcion, la primera para generar números aleatorios y la segunda para evaluar la función.

Aproximación a π

Para este caso se toma un cuarto de círculo de radio = 1, y se lanzan n dardos hacia él de esos n dardos supongamos que m aciertan en él entonces mediante matemágia, podemos encontrar que  π ≈ 4 * m / n

Para (mal) aplicar la POO, existe una clase que hace uso de Random, la clase definida en el ejericio anterior y de otra, llamada Aproximación en la cual se realiza la simulación de los dardos

Comprobación de primalidad (Algoritmo Monte Carlo)

Existe un test de primalidad, inventado por Fermat que nos dice que si tomamos la siguiente frómula a^(n-1) % n para cualquier número a ∈ [1,n-1] y si el resultado de eso es distinto de 1 entonces sabemos que n no es primo. Tomando una gran cantidad de números con valores aleatorios para a ∈ [1,n-1] podríamos asegurar con cierta probabilidad si un número n es primo. Si el test falla, es decir el resultado para cualquiera a es distinto de 1 podemos asegurar que n no es primo.

Resolución del problema de las N reinas (Algoritmo Las Vegas)

El ya conocidísimo problema delas N reinas también se puede resolver mediante probabilidad, es decir, tomamos la columna 1 y colocamos la primera reina, después para la segunda columna tratamos de colocar la siguiente reina en una posición elegida aleatoriamente, si se logró, continuamos con la siguiente columna, y así hasta colocar las N reinas o no poder colocar una, en ese caso falla.

Bastante simple.

• Se usa una lista para para ir almacenando las frecuencias de cada caracter
• Se usa un arreglo de árboles para generar el árbol único de códificación
• Se usa una cola para obtener el código asignado a cada símbolo

FUNC Fibonacci (↓n: NATURAL): NATURAL
   VARIABLES
       tabla: ARRAY [0..n] DE NATURALES
       i: NATURAL
   INICIO
       SI n = 0 ENTONCES
           DEVOLVER 0
       SINOSI n = 1 ENTONCES
           DEVOLVER 1
       SINO
           tabla[0] := 0
           tabla[1] := 1
           PARA i = 2 HASTA n HACER
               tabla[i] := tabla[i-1] + tabla[i-2]
           FINPARA
           DEVOLVER tabla[n]
       FINSI
   FIN

long long fibonacciArreglo(int n) {
    long long * lista;
    if(n == 0) return 0;
    if(n == 1) return 1;
    lista = (long long *) malloc(sizeof(long long) * n);
    lista[0] = 0;
    lista[1] = 1;
    int i;
    for (i = 2; i <= n; i++) {
        lista[i] = lista[i-1] + lista[i-2];
    }
    return lista[n];
}

long long fibonacciCola(int n) {
    Cola cola;
    if (n == 0) return 0;
    if (n == 1) return 1;
    creaLista(&cola);
    formar(&cola, 0);
    formar(&cola, 1);
    int i;
    for (i = 2; i <= n; i++) {
        // Quitamos el elemento menos reciente
        long long fi1 = atender(&cola);
        // Obtenemos el valor del siguiente más reciente
        long long fi2 = valorPrincipio(&cola);
        // Almacenamos el resultado en la cola
        formar(&cola, fi1 + fi2);
    }
    return valorFinal(&cola);
}

Práctica 1: "Pruebas a posteriori (Algoritmos de ordenamiento)"

• Burbuja (Bubble Sort)
• Burbuja Simple
• Burbuja Mejorada
• Inserción (Insertion Sort)
• Selección (Selection Sort )
• Shell (Shell Sort)
• Ordenamiento con árbol binario de busqueda (Binary Search Tree)

Práctica 2: "Análisis temporal y notación de orden (Algoritmos de busqúeda)"

• Búsqueda lineal o secuencial (No recursiva)
• Búsqueda binaria o dicotómica (No recursiva)
• Búsqueda en un árbol binario de búsqueda (No recursiva)
• Modificar los tres algoritmos para trabajar con procesos ligeros (Hilos).

Práctica 3: "Divide y vencerás (Rotación de una imagen)"

1.- Sección de declaraciones

Lugar para incluir cabeceras, macros, variables globales... también es posible definir patrones a usar en la sección de reglas

%%

2.- Sección de reglas

Aquí es donde se asocian los patrones(expresiones regulares) a buscar con sentencias(código) de C. Cada vez que el analizador encuentra un a cadena que coincide con el patrón, se ejecuta el código en C

%%

3.- Sección de código en C

Contiene sentencias en C y funciones que serán copiadas íntegramente en el archivo que Felx genere, comúnmente se colocan aquí las funciones que se llamarán en la sección de reglas.