algorithm - enésimo número feo
math primes (11)
Estoy trabajando para encontrar el n. ° feo número. Tenga en cuenta que estos números están distribuidos de forma extremadamente dispersa a medida que n aumenta.
Escribí un programa trivial que calcula si un número dado es feo o no.
Este parece el enfoque equivocado para el problema que estás tratando de resolver: es un algoritmo de Shlemiel.
¿Está familiarizado con el algoritmo Seive of Eratosthenes para encontrar primos? Algo similar (explotar el conocimiento de que cada número feo es 2, 3 o 5 veces otro número feo) probablemente funcionaría mejor para resolver esto.
Los números cuyos únicos factores primos son 2, 3 o 5 se llaman números feos.
Ejemplo:
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...
1 puede considerarse como 2 ^ 0.
Estoy trabajando para encontrar el n. ° feo número. Tenga en cuenta que estos números están distribuidos de forma extremadamente dispersa a medida que n aumenta.
Escribí un programa trivial que calcula si un número dado es feo o no. Para n> 500 - se volvió super lento. Intenté usar la memorización - observación: ugly_number * 2, ugly_number * 3, ugly_number * 5 son todos feos. Incluso con eso es lento. Intenté usar algunas propiedades del registro, ya que eso reducirá este problema de la multiplicación a la suma, pero aún no tengo mucha suerte. Pensé en compartir esto con todos ustedes. Alguna idea interesante?
Usando un concepto similar a "Tamiz de Eratóstenes" (gracias Anon)
for (int i(2), uglyCount(0); ; i++) {
if (i % 2 == 0)
continue;
if (i % 3 == 0)
continue;
if (i % 5 == 0)
continue;
uglyCount++;
if (uglyCount == n - 1)
break;
}
Yo es el enésimo número feo.
Incluso esto es bastante lento. Estoy tratando de encontrar el número feo número 1500.
Aquí hay otro enfoque O (n) (solución Python) basado en la idea de fusionar tres listas ordenadas. el verdadero desafío es encontrar el siguiente número feo más grande? por ejemplo, sabemos que los primeros cinco números feos son [1,2,3,4,5]. los números feos son en realidad de las siguientes tres listas:
- lista 1: 1 * 2, 2 * 2, 3 * 2, 4 * 2, 5 * 2 ...;
- lista 2: 1 * 3, 2 * 3, 3 * 3, 4 * 3, 5 * 3 ...;
- lista 3: 1 * 5, 2 * 5, 3 * 5, 4 * 5, 5 * 5 ....
Entonces el enésimo número feo es el enésimo número de la lista fusionada de las tres listas anteriores:
1, 1 * 2, 1 * 3, 2 * 2, 1 * 5, 2 * 3 ...
def nthuglynumber(n):
p2, p3, p5=0,0,0
uglynumber=[1]
while len(uglynumber)<n:
ugly2, ugly3, ugly5= uglynumber[p2]*2, uglynumber[p3]*3, uglynumber[p5]*5
next=min(ugly2, ugly3, ugly5)
if next==ugly2: p2+=1
if next==ugly3: p3+=1
if next==ugly5: p5+=1
uglynumber+=[next]
return uglynumber[-1]
- PASO I: calcular los números feos actuales de las tres listas
- ugly2, ugly3, ugly5 = uglynumber [p2] * 2, uglynumber [p3] * 3, uglynumber [p5] * 5
- PASO II, encuentre el próximo número feo más grande:
- siguiente = min (feo2, feo3, feo5)
- PASO III: moviendo el puntero hacia adelante si su número feo es el próximo-mayor número
- si sigue == feo2: p2 + = 1
- si siguiente == feo3: p3 + = 1
- si siguiente == feo5: p5 + = 1
- nota aquí: no usar if, elif y else
- PASO IV: agregando el siguiente número feo más grande en la lista fusionada unglynumber
- uglynumber + = [next]
Aquí hay una solución correcta en ML. La función fea () devolverá una secuencia (lista diferida) de números hamming. La función nth se puede usar en esta secuencia.
Esto utiliza el método Sieve, los siguientes elementos solo se calculan cuando es necesario.
datatype stream = Item of int * (unit->stream);
fun cons (x,xs) = Item(x, xs);
fun head (Item(i,xf)) = i;
fun tail (Item(i,xf)) = xf();
fun maps f xs = cons(f (head xs), fn()=> maps f (tail xs));
fun nth(s,1)=head(s)
| nth(s,n)=nth(tail(s),n-1);
fun merge(xs,ys)=if (head xs=head ys) then
cons(head xs,fn()=>merge(tail xs,tail ys))
else if (head xs<head ys) then
cons(head xs,fn()=>merge(tail xs,ys))
else
cons(head ys,fn()=>merge(xs,tail ys));
fun double n=n*2;
fun triple n=n*3;
fun ij()=
cons(1,fn()=>
merge(maps double (ij()),maps triple (ij())));
fun quint n=n*5;
fun ugly()=
cons(1,fn()=>
merge((tail (ij())),maps quint (ugly())));
Este fue el primer año de trabajo CS :-)
Básicamente, la búsqueda podría hacerse O (n):
Considere que mantiene un historial parcial de números desagradables. Ahora, en cada paso, debes encontrar el siguiente. Debería ser igual a un número del historial multiplicado por 2, 3 o 5. Elija el más pequeño de ellos, agréguelo al historial y suelte algunos números para que el más pequeño de la lista multiplicado por 5 sea más grande que el más grande.
Será rápido, porque la búsqueda del siguiente número será simple:
min (más grande * 2, más pequeño * 5, uno desde el medio * 3),
eso es más grande que el número más grande en la lista. Si son escasos, la lista siempre contendrá pocos números, por lo que la búsqueda del número que se multiplicará por 3 será rápida.
Creo que puedes resolver este problema en tiempo sub-lineal, probablemente O (n ^ {2/3}).
Para darle la idea, si simplifica el problema para permitir factores de solo 2 y 3, puede lograr O (n ^ {1/2}) tiempo comenzando por buscar la potencia más pequeña de dos que sea al menos tan grande como el enésimo número feo, y luego generar una lista de O (n ^ {1/2}) candidatos. Este código debería darte una idea de cómo hacerlo. Se basa en el hecho de que el enésimo número que contiene solo potencias de 2 y 3 tiene una factorización prima cuya suma de exponentes es O (n ^ {1/2}).
foo(n):
p2 = 1 # current power of 2
p3 = 1 # current power of 3
e3 = 0 # exponent of current power of 3
t = 1 # number less than or equal to the current power of 2
while t < n:
p2 *= 2
if p3 * 3 < p2:
p3 *= 3
e3 += 1
t += 1 + e3
candidates = [p2]
c = p2
for i in range(e3):
c /= 2
c *= 3
if c > p2: c /= 2
candidates.append(c)
return select(candidates, n - (t - candidates.length())) # linear time select
La misma idea debería funcionar para tres factores permitidos, pero el código se vuelve más complejo. La suma de los poderes de la factorización cae a O (n ^ {1/3}), pero necesita considerar más candidatos, O (n ^ {2/3}) para ser más precisos.
Este problema se puede hacer en O (1).
Si eliminamos 1 y miramos los números entre 2 y 30, notaremos que hay 22 números.
Ahora, para cualquier número x en los 22 números anteriores, habrá un número x + 30 entre 31 y 60 que también es feo. Por lo tanto, podemos encontrar al menos 22 números entre 31 y 60. Ahora, para cada número feo entre 31 y 60, podemos escribirlo como s + 30. Entonces, también será feo, ya que s + 30 es divisible por 2, 3 , o 5. Por lo tanto, habrá exactamente 22 números entre 31 y 60. Esta lógica se puede repetir para cada bloque de 30 números después de eso.
Por lo tanto, habrá 23 números en los primeros 30 números, y 22 por cada 30 después de eso. Es decir, los primeros 23 feos se producirán entre 1 y 30, 45 feos se producirán entre 1 y 60, 67 feos se producirán entre 1 y 30, etc.
Ahora, si me dan n, digamos 137, puedo ver que 137/22 = 6.22. La respuesta estará entre 6 * 30 y 7 * 30 o entre 180 y 210. Por 180, tendré 6 * 22 + 1 = 133 ° número feo en 180. Tendré 154 ° número feo en 210. Por lo tanto, estoy buscando 4º número feo (desde 137 = 133 + 4) en el intervalo [2, 30], que es 5. El número feo número 137 es entonces 180 + 5 = 185.
Otro ejemplo: si quiero el número feo número 1500, cuento 1500/22 = 68 bloques. Por lo tanto, tendré 22 * 68 + 1 = 1497a feo a 30 * 68 = 2040. Los siguientes tres feos en el bloque [2, 30] son 2, 3 y 4. Así que nuestro feo requerido está en 2040 + 4 = 2044.
El punto es que puedo simplemente construir una lista de números desagradables entre [2, 30] y simplemente encontrar la respuesta haciendo búsquedas en O (1).
Mi respuesta se refiere a la respuesta correcta dada por Nikita Rybak . Para que uno pueda ver una transición de la idea del primer acercamiento a la del segundo.
from collections import deque
def hamming():
h=1;next2,next3,next5=deque([]),deque([]),deque([])
while True:
yield h
next2.append(2*h)
next3.append(3*h)
next5.append(5*h)
h=min(next2[0],next3[0],next5[0])
if h == next2[0]: next2.popleft()
if h == next3[0]: next3.popleft()
if h == next5[0]: next5.popleft()
Lo que ha cambiado desde el primer enfoque de Nikita Rybak es que, en lugar de agregar los siguientes candidatos en una sola estructura de datos, es decir, Conjunto de árbol, uno puede agregar cada uno de ellos por separado en 3 listas FIFO. De esta forma, cada lista se mantendrá ordenada todo el tiempo, y la siguiente menos candidata siempre debe estar a la cabeza de una o más de estas listas.
Si eliminamos el uso de las tres listas anteriores, llegamos a la segunda implementación en la respuesta de Nikita Rybak . Esto se hace mediante la evaluación de los candidatos (que se incluirán en tres listas) solo cuando sea necesario, para que no haya necesidad de almacenarlos.
En pocas palabras :
En el primer enfoque, colocamos a cada nuevo candidato en una sola estructura de datos, y eso es malo porque demasiadas cosas se mezclan de manera imprudente. Esta estrategia deficiente inevitablemente implica O (log (tamaño del árbol)) la complejidad del tiempo cada vez que hacemos una consulta a la estructura. Al ponerlos en colas separadas, sin embargo, verá que cada consulta toma solo O (1) y es por eso que el rendimiento general se reduce a O (n). Esto se debe a que cada una de las tres listas ya está ordenada, por sí misma.
Para encontrar el n-ésimo número feo en O (n ^ (2/3)), el algoritmo de jonderry funcionará muy bien. Tenga en cuenta que los números involucrados son enormes, por lo que cualquier algoritmo que intente comprobar si un número es feo o no tiene ninguna posibilidad.
Encontrar todos los n feos números más pequeños en orden ascendente se hace fácilmente mediante el uso de una cola de prioridad en el tiempo O (n log n) y el espacio O (n): Primero crea una cola prioritaria de números con los números más pequeños, incluyendo número 1. Luego repita n veces: elimine el número más pequeño x de la cola de prioridad. Si x no se ha eliminado antes, entonces x es el siguiente número feo más grande, y agregamos 2x, 3x y 5x a la cola de prioridad. (Si alguien no conoce el término cola de prioridad, es como el montón en el algoritmo de heapsort). Aquí está el comienzo del algoritmo:
1 -> 2 3 5
1 2 -> 3 4 5 6 10
1 2 3 -> 4 5 6 6 9 10 15
1 2 3 4 -> 5 6 6 8 9 10 12 15 20
1 2 3 4 5 -> 6 6 8 9 10 10 12 15 15 20 25
1 2 3 4 5 6 -> 6 8 9 10 10 12 12 15 15 18 20 25 30
1 2 3 4 5 6 -> 8 9 10 10 12 12 15 15 18 20 25 30
1 2 3 4 5 6 8 -> 9 10 10 12 12 15 15 16 18 20 24 25 30 40
Prueba del tiempo de ejecución: extraemos un número feo de la cola n veces. Inicialmente tenemos un elemento en la cola, y después de extraer un número feo, agregamos tres elementos, aumentando el número en 2. Entonces, después de encontrar números feos, tenemos como máximo 2n + 1 elementos en la cola. La extracción de un elemento se puede hacer en tiempo logarítmico. Extraemos más números que solo los números feos, pero a lo sumo n números feos más 2n - 1 otros números (los que podrían haber estado en el tamiz después de n-1 pasos). Por lo tanto, el tiempo total es menos de 3n extracciones de elementos en tiempo logarítmico = O (n log n), y el espacio total es como máximo 2n + 1 elementos = O (n).
Supongo que podemos usar la programación dinámica (DP) y calcular el n . ° número feo . La explicación completa se puede encontrar en http://www.geeksforgeeks.org/ugly-numbers/
#include <iostream>
#define MAX 1000
using namespace std;
// Find Minimum among three numbers
long int min(long int x, long int y, long int z) {
if(x<=y) {
if(x<=z) {
return x;
} else {
return z;
}
} else {
if(y<=z) {
return y;
} else {
return z;
}
}
}
// Actual Method that computes all Ugly Numbers till the required range
long int uglyNumber(int count) {
long int arr[MAX], val;
// index of last multiple of 2 --> i2
// index of last multiple of 3 --> i3
// index of last multiple of 5 --> i5
int i2, i3, i5, lastIndex;
arr[0] = 1;
i2 = i3 = i5 = 0;
lastIndex = 1;
while(lastIndex<=count-1) {
val = min(2*arr[i2], 3*arr[i3], 5*arr[i5]);
arr[lastIndex] = val;
lastIndex++;
if(val == 2*arr[i2]) {
i2++;
}
if(val == 3*arr[i3]) {
i3++;
}
if(val == 5*arr[i5]) {
i5++;
}
}
return arr[lastIndex-1];
}
// Starting point of program
int main() {
long int num;
int count;
cout<<"Which Ugly Number : ";
cin>>count;
num = uglyNumber(count);
cout<<endl<<num;
return 0;
}
Podemos ver que es bastante rápido, solo cambia el valor de MAX para calcular un número más feo
Una solución simple y rápida en Java. Utiliza el enfoque descrito por Anon. .
Aquí TreeSet es solo un contenedor capaz de devolver el elemento más pequeño en él. (No duplicados almacenados)
int n = 20;
SortedSet<Long> next = new TreeSet<Long>();
next.add((long) 1);
long cur = 0;
for (int i = 0; i < n; ++i) {
cur = next.first();
System.out.println("number " + (i + 1) + ": " + cur);
next.add(cur * 2);
next.add(cur * 3);
next.add(cur * 5);
next.remove(cur);
}
Dado que el número feo número 1000 es 51200000, almacenarlos en bool[] no es realmente una opción.
editar
Como una recreación del trabajo (depuración del estúpido Hibernate), aquí hay una solución completamente lineal. ¡Gracias a Marcog por la idea!
int n = 1000;
int last2 = 0;
int last3 = 0;
int last5 = 0;
long[] result = new long[n];
result[0] = 1;
for (int i = 1; i < n; ++i) {
long prev = result[i - 1];
while (result[last2] * 2 <= prev) {
++last2;
}
while (result[last3] * 3 <= prev) {
++last3;
}
while (result[last5] * 5 <= prev) {
++last5;
}
long candidate1 = result[last2] * 2;
long candidate2 = result[last3] * 3;
long candidate3 = result[last5] * 5;
result[i] = Math.min(candidate1, Math.min(candidate2, candidate3));
}
System.out.println(result[n - 1]);
La idea es que para calcular a[i] , podemos usar a[j]*2 para algunos j < i . Pero también debemos asegurarnos de que 1) a[j]*2 > a[i - 1] y 2) j sea lo más pequeño posible.
Entonces, a[i] = min(a[j]*2, a[k]*3, a[t]*5) .
aquí está mi código, la idea es dividir el número por 2 (hasta que dé el resto 0) luego 3 y 5. Si al final el número se convierte en uno, es un número feo. puedes contar e incluso imprimir todos los números feos hasta n.
int count = 0;
for (int i = 2; i <= n; i++) {
int temp = i;
while (temp % 2 == 0) temp=temp / 2;
while (temp % 3 == 0) temp=temp / 3;
while (temp % 5 == 0) temp=temp / 5;
if (temp == 1) {
cout << i << endl;
count++;
}
}