El crecimiento exponencial de vaca poblaciones en Minecraft

Question

Minecraft es un juego donde puedes hacer muchas cosas, incluyendo la granja de vacas.

Cuando se alimenta de trigo, vacas en Minecraft se reproducen entre sí en pares y producir un bebé por par.

Después de unos 20 minutos, el bebé/bebés crecen y se reproducen con cada uno de los otros y de sus padres.

No hay géneros en Minecraft, ni de cualquier problema con las vacas de cría con su descendencia: todo completamente crecido las vacas son idénticos.

Entonces, ¿cuál es el número total de vacas después de n 'servicios'?

A partir de 2 vacas, el número total de vacas va como esto:

2, 3, 4, 6, 9, 13, 19, 28, 42, 63, 94, y así sucesivamente.

Deje que n sea el número de veces que las vacas han criado

Número de vacas (diferencia entre los números de arriba) = (n - n%2)/2 , donde % significa que el módulo.

Entonces, ¿cuál es el número total de vacas en cualquier n?

Sé que es una suma de algún tipo, pero ¿qué es?

Answer 1

Este es OEISA061418, curiosamente el "ejemplo" es acerca de Minecraft. La solución dada por el $n$th plazo es

$$ a(n) = \lceil K*(3/2)^n \rceil $$

donde $K=1.0815136685\dots$ $K=(2/3) K(3)$ cuando la expansión decimal de $K(3)$ está aquí.

Para que se aclare cómo se utiliza esta fórmula, suponga que desea saber cuántas vacas tiene después de la $10$th ciclo de reproducción. En primer lugar,

$$ K*(3/2)^n = (1.0815136685)*(3/2)^{10} \aprox 62.3655 $$

Ahora tenemos que tomar el techo de este número, lo que significa redondeo al entero más cercano. Por lo tanto,

$$ (10) = \lceil K*(3/2)^n \rceil = \lceil 62.3655 \rceil = 63 $$

lo cual está de acuerdo con la secuencia. Tenga en cuenta que por muy grande $n$, puede que necesite utilizar una forma más exacta el valor de $K$ (que es la razón por la que he publicado el segundo enlace.)

Answer 2

Lo que se busca es la solución a la recurrencia: $$T(1) = 2$$ $$T(n) = T(n-1) + \left\lfloor \frac{T(n-1)}{2} \right\rfloor$$ De hecho, esta función crece como una exponencial, ya que éste se comporta asintóticamente como $$T(n) \approx 2 \left( \frac{3}{2} \right)^{n - 1}$$ Desde $T(n)$ es siempre un número entero, podemos reescribir la recurrencia como $$T(n) = \left\lfloor \frac{3}{2} T(n-1) \right \rfloor$$ Esto le da una manera eficiente para calcular $T(n)$ de forma iterativa. No estoy seguro de que hay una útil forma cerrada.

Answer 3

Para repetir lo que has escrito: en cada etapa, si $N$ es el número de vacas antes de la cría, a continuación, el número de vacas es $\lfloor N/2 \rfloor$ (ver la función del suelo se define aquí).

Como una recurrencia de la relación, podemos afirmar lo siguiente:

Deje $N(k)$ el número de vacas después de $k$ etapas de la crianza. A continuación, $N$ satisface la relación de recurrencia $$ N(k+1) = N(k) + \lfloor N(k)/2 \rfloor $$ Con $N(0) = 2$. No estoy seguro de si hay una casa no recursivo expresión para $N$ como una función de la $k$, pero al menos este es un comienzo.

Answer 4

Sé que esto puede ser inútil en este punto, pero es que no ocupa mucho espacio ...

Así que esto refleja más o menos el mismo ejemplo de fibonacci (promiscuo conejitos) pero con casado vacas o algo parecido, así que después de la primera reproducción hay dos vacas (una pareja) y después de la siguiente cría que la pareja va a dar a luz otra vaca, entonces habrá 3 vacas pero sigue siendo una pareja desde que el joven (recientemente añadido) vaca no pertenecen a ninguna pareja.

La próxima cría habrá 4 vacas como se esperaba y, a continuación, obtenemos 2 parejas, así que la próxima cría de las parejas de vacas de dar a luz otros 2 vacas (un nuevo par). Y, a continuación, con 6 (4 + 2) vacas nos 3 vacas (9 vacas en total). Y así sucesivamente:

9 + 4 = 13, 13 + 6 = 19, 19 + 9 = 28, . . .

Saludos, MasterGeek.

Edit: lo sentimos, no hay dos vacas ANTES de la primera inseminación, ya que se necesita al menos un par.