2.5: Ejercicios de programación

Última actualización
Guardar como PDF

Page ID: 111190

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

1. El Tamiz de Eratóstenes

Un método para computar todos los números primos menos de un cierto entero positivo fijo\(N\) es listar todos los números de\(n\) tal manera que\(1 \lt n \lt N\text{.}\) Comenzar eliminando todos los múltiplos de\(2\text{.}\) Siguiente eliminar todos los múltiplos de Ahora eliminar todos los múltiplos de\(3\text{.}\) Ahora eliminar todos los múltiplos de \(5\text{.}\)Observe que ya\(4\) ha sido tachado. Continuar de esta manera, notando que no tenemos que ir hasta el final\(N\text{;}\) es suficiente parar en\(\sqrt{N}\text{.}\) Usando este método, computar todos los números primos menores que También\(N = 250\text{.}\) podemos usar este método para encontrar todos los enteros que son relativamente primos a un entero\(N\text{.}\) Simplemente eliminar los factores primos de\(N\) y todos sus múltiplos. Usando este método, encuentra todos los números que son relativamente primos a\(N= 120\text{.}\) Usando el tamiz de Eratóstenes, escribe un programa que calculará todos los números primos menores que un número entero\(N\text{.}\)

2

Deje que la función de\({\mathbb N}^0 = {\mathbb N} \cup \{ 0 \}\text{.}\) Ackermann sea la función\(A :{\mathbb N}^0 \times {\mathbb N}^0 \rightarrow {\mathbb N}^0\) definida por las ecuaciones

\ begin {alinear*} A (0, y) & = y + 1,\\ A (x + 1, 0) & = A (x, 1),\\ A (x + 1, y + 1) & = A (x, A (x + 1, y))\ texto {.} \ end {alinear*}

Usa esta definición para computar\(A(3, 1)\text{.}\) Escribe un programa para evaluar la función de Ackermann. Modificar el programa para contar el número de sentencias ejecutadas en el programa cuando se evalúa la función de Ackermann. Cuántas declaraciones se ejecutan en la evaluación de\(A(4, 1)\text{?}\) What about\(A(5, 1)\text{?}\)

3

Escribir un programa de computadora que implementará el algoritmo euclidiano. El programa debe aceptar dos enteros positivos\(a\) y\(b\) como entrada y debe generar así\(\gcd( a,b)\) como enteros\(r\) y\(s\) tal que

\[ \gcd( a,b) = ra + sb\text{.} \nonumber \]