TRABAJO COMPUTACIONAL Nº 2 LENGUAJES DE PROGRAMACIÓN

...

[pic 1]

Este número es 1×8 + 1×4 + 0×2 + 1 + 1×(1/2) + 0×(1/4) + 1×(1/8)(=13,625 en decimal)

De la forma en que en el sistema de números binarios sólo se pueden utilizar ceros y unos, a continuación con el concepto de una tabla, se ejemplifica la utilización de los mismo.

[pic 2]Bits: Un dígito binario por sí solo (como "0" o "1") se llama un "bit". Por ejemplo 11010 tiene cinco bits de longitud.

La palabra bit viene de las palabras inglesas "binary digit”.

Hablando sobre Shift.

Syntaxis[pic 3]

Shift hacia la izquierda.

De por si el shift se utiliza como un desplazador, en este caso, el desplazamiento es hacia la izquierda. En el caso específico al ser utilizado como un operador en el lenguaje “C++” el operador hace que los bits de la expresión se desplacen hacia la izquierda por el número de posiciones especificadas por la expresión aditiva (additive-expression).

Los espacios que han sido vaciados se han de llenar con ceros, el cambio a la izquierda es de por sí un cambio lógico, es decir que que los bits que se desplazan fuera del final se descartan, incluyendo el bit del signo. El siguiente ejemplo muestra operaciones de desplazamiento hacia la izquierda utilizando números sin signos. El mismo explica lo que sucede con los bits desplazados.

Programa hecho en C++[pic 4]

Shift hacia la derecha.

El operador Shift a la derecha hace que el patrón de bits en la expresión de cambio se desplace por el número de posiciones especificadas por la expresión aditiva. Para los números sin signo, las posiciones de bits que han sido desocupadas por el operador Shift estén cerradas. Para los números con signo, el bit de signo se utiliza para rellenar las posiciones de bits vacantes. En otras palabras, si el número es positivo, se utiliza 0, y si el número es negativo, se utiliza 1.

El resultado de un cambio a la derecha de un número negativo con signo depende de la implementación. Aunque Visual C ++ utiliza el bit de signo para rellenar posiciones de bits vacías, no hay garantía de que otras implementaciones también lo hagan.

En el siguiente ejemplo se presentarán números utilizando >> como operador, demostrando el comportamiento de los bits.

[pic 5]

En un plano matemático.

Coeficiente Binomial.

Los coeficientes binomiales, números combinatorios o combinaciones son números estudiados en combinatoria que corresponden al número de formas en que se pueden extraer subconjuntos a partir de un conjunto dado.

El número de formas de escoger k elementos a partir de un conjunto de n, puede denotarse de varias formas, como por ejemplo:

[pic 6]

La definición no permite calcular el valor de los coeficientes binomiales, salvo listando los subconjuntos y contándoles. Sin embargo, existe una fórmula explícita que nos proporciona el valor de C(n,k).

En el trabajo se nos ha dado la forma de la función a utilizar, siendo la siguiente:

[pic 7]

Definición recursiva:

[pic 8]

Utilizando como condición de término y valores iniciales:

[pic 9]

Demostración:

[pic 10]Sucesión de Fibonacci.

La sucesión de Fibonacci es la sucesión de números:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Cada número se calcula sumando los dos anteriores a él.

- El 2 se calcula sumando (1+1)

- Análogamente, el 3 es sólo (1+2),

- Y el 5 es (2+3),

Siendo la regla para la sucesión:

La sucesión de Fibonacci se puede escribir como una "regla".

la regla es xn = xn-1 + xn-2

donde:

- xn es el término en posición "n"

- xn-1 es el término anterior (n-1)

- xn-2 es el anterior a ese (n-2)

Siendo dada así para el trabajo la siguiente plantilla para la función recursiva:

[pic 11]

Funcion de Ackermann

En teoría de la computación, la función de Ackermann es una función matemática recursiva encontrada en 1926 por Wilhelm Ackermann, la cual posee un crecimiento extremadamente rápido. Hoy en día, hay una serie de funciones que son llamadas funciones Ackermann. Todas ellas tienen una forma similar a la ley original la función de Ackermann y también tienen un comportamiento de crecimiento similar. Esta función toma dos números naturales como argumentos y devuelve un único número natural. Como norma general se define como sigue:

[pic 12]

Esta función crece extremadamente rápido: el valor A(4,2) ya tiene 19.729 dígitos. Este crecimiento desmesurado se puede utilizar para demostrar que la función computable f(n) = A(n, n) crece más rápido que cualquier función recursiva primitiva, y por ello no es recursiva primitiva.

Análisis de los Resultados de Ejecución

a) Determinar la cantidad de ceros (0’s) que tiene la representación binaria de un entero positivo n. Por ejemplo, si n=16, la función deberá retornar 4; esto, debido a que (16)10 = (10000)2. Usar sólo operaciones numéricas (no tratar los dígitos como caracteres). Comprobar con n=3333.

Código de la Función.

[pic 13]

Resultados de la Ejecución: