algorithm - Impresión de números de la forma 2 ^ i*5 ^ j en orden creciente
smooth-numbers (10)
Como matemático, lo primero en lo que siempre pienso cuando veo algo como esto es "¿ayudarán los logaritmos?".
En este caso podría.
Si nuestra serie A está aumentando, el registro de la serie (A) también está aumentando. Como todos los términos de A tienen el formato 2 ^ i.5 ^ j, entonces todos los miembros del registro de la serie (A) tienen el formato i.log (2) + j.log (5)
Luego podemos ver la serie log (A) / log (2) que también está aumentando y sus elementos tienen el formato i + j. (Log (5) / log (2))
Si resolvemos la i y j que genera la lista ordenada completa para esta última serie (llámela B), entonces i y j también generarán la serie A correctamente.
Esto solo está cambiando la naturaleza del problema, pero es de esperar que resulte más fácil de resolver. En cada paso puede aumentar i y disminuir j o viceversa.
Si observamos algunos de los primeros cambios que puede hacer (a los que probablemente me referiré como transformaciones de i, j o simplemente de las transformas), nos dará algunas pistas de hacia dónde nos dirigimos.
Claramente, aumentar i en 1 aumentará B en 1. Sin embargo, dado que log (5) / log (2) es aproximadamente 2.3, aumentar j en 1 mientras que disminuir i en 2 dará un aumento de solo 0.3. El problema entonces es, en cada etapa, encontrar el aumento mínimo posible en B para los cambios de i y j.
Para hacer esto, simplemente mantuve un registro a medida que aumentaba las transformaciones más eficientes de i y j (es decir, qué sumar y restar de cada una) para obtener el menor aumento posible en la serie. Luego aplique el que sea válido (es decir, asegurándose de que i y j no sean negativos).
Ya que en cada etapa puede disminuir i o disminuir j hay efectivamente dos clases de transformaciones que pueden verificarse individualmente. Una nueva transformación no tiene que tener el mejor puntaje general para ser incluido en nuestros controles futuros, simplemente mejor que cualquier otro en su clase.
Para probar mis pensamientos, escribí una especie de programa en LinqPad. Las cosas clave que se deben tener en cuenta son que el método Dump () simplemente envía el objeto a la pantalla y que la sintaxis / estructura no es válida para un archivo c # real. Convertirlo si quieres ejecutarlo debería ser fácil.
Esperemos que cualquier cosa no explicada explícitamente sea comprensible a partir del código.
void Main()
{
double C = Math.Log(5)/Math.Log(2);
int i = 0;
int j = 0;
int maxi = i;
int maxj = j;
List<int> outputList = new List<int>();
List<Transform> transforms = new List<Transform>();
outputList.Add(1);
while (outputList.Count<500)
{
Transform tr;
if (i==maxi)
{
//We haven''t considered i this big before. Lets see if we can find an efficient transform by getting this many i and taking away some j.
maxi++;
tr = new Transform(maxi, (int)(-(maxi-maxi%C)/C), maxi%C);
AddIfWorthwhile(transforms, tr);
}
if (j==maxj)
{
//We haven''t considered j this big before. Lets see if we can find an efficient transform by getting this many j and taking away some i.
maxj++;
tr = new Transform((int)(-(maxj*C)), maxj, (maxj*C)%1);
AddIfWorthwhile(transforms, tr);
}
//We have a set of transforms. We first find ones that are valid then order them by score and take the first (smallest) one.
Transform bestTransform = transforms.Where(x=>x.I>=-i && x.J >=-j).OrderBy(x=>x.Score).First();
//Apply transform
i+=bestTransform.I;
j+=bestTransform.J;
//output the next number in out list.
int value = GetValue(i,j);
//This line just gets it to stop when it overflows. I would have expected an exception but maybe LinqPad does magic with them?
if (value<0) break;
outputList.Add(value);
}
outputList.Dump();
}
public int GetValue(int i, int j)
{
return (int)(Math.Pow(2,i)*Math.Pow(5,j));
}
public void AddIfWorthwhile(List<Transform> list, Transform tr)
{
if (list.Where(x=>(x.Score<tr.Score && x.IncreaseI == tr.IncreaseI)).Count()==0)
{
list.Add(tr);
}
}
// Define other methods and classes here
public class Transform
{
public int I;
public int J;
public double Score;
public bool IncreaseI
{
get {return I>0;}
}
public Transform(int i, int j, double score)
{
I=i;
J=j;
Score=score;
}
}
No me he molestado en ver la eficiencia de esto, pero sospecho que es mejor que algunas otras soluciones porque en cada etapa lo único que tengo que hacer es verificar mi conjunto de transformaciones: averiguar cuántas de ellas hay en comparación con "n" No es trivial. Está claramente relacionado, ya que cuanto más avanzas, más transformaciones hay, pero la cantidad de nuevas transformaciones se hace cada vez más pequeña en números más altos, por lo que quizás sea solo O (1). Sin embargo, estas cosas de O siempre me confundieron. ;-)
Una ventaja sobre otras soluciones es que le permite calcular i, j sin necesidad de calcular el producto, lo que me permite calcular cuál sería la secuencia sin necesidad de calcular el número real.
Por lo que valía después de los primeros 230 nunmbers (cuando int se queda sin espacio) tuve 9 transformaciones para verificar cada vez. Y dado que es solo mi total que se desbordó, corrí en el primer millón de resultados y llegué a i = 5191 y j = 354. El número de transformaciones fue de 23. El tamaño de este número en la lista es de aproximadamente 10 ^ 1810. El tiempo de ejecución para llegar a este nivel fue de aproximadamente 5 segundos.
PD: Si te gusta esta respuesta, no dudes en decírselo a tus amigos, ya que pasé mucho tiempo en esto y unos cuantos +1 serían una buena compensación. O, de hecho, solo comenta para decirme lo que piensas. :)
¿Cómo se imprimen los números del formulario 2^i * 5^j en orden creciente?
For eg:
1, 2, 4, 5, 8, 10, 16, 20
En primer lugar, (como ya han mencionado otros) esta pregunta es muy vaga !!!
Sin embargo, voy a dar un tiro basado en su vaga ecuación y el patrón como su resultado esperado. Así que no estoy seguro de que lo siguiente sea cierto para lo que está tratando de hacer, sin embargo, ¡puede darle una idea sobre las colecciones de Java!
import java.util.List;
import java.util.ArrayList;
import java.util.SortedSet;
import java.util.TreeSet;
public class IncreasingNumbers {
private static List<Integer> findIncreasingNumbers(int maxIteration) {
SortedSet<Integer> numbers = new TreeSet<Integer>();
SortedSet<Integer> numbers2 = new TreeSet<Integer>();
for (int i=0;i < maxIteration;i++) {
int n1 = (int)Math.pow(2, i);
numbers.add(n1);
for (int j=0;j < maxIteration;j++) {
int n2 = (int)Math.pow(5, i);
numbers.add(n2);
for (Integer n: numbers) {
int n3 = n*n1;
numbers2.add(n3);
}
}
}
numbers.addAll(numbers2);
return new ArrayList<Integer>(numbers);
}
/**
* Based on the following fuzzy question @
* http://.com/questions/7571934/printing-numbers-of-the-form-2i-5j-in-increasing-order
*
*
* Result:
* 1 2 4 5 8 10 16 20 25 32 40 64 80 100 125 128 200 256 400 625 1000 2000 10000
*/
public static void main(String[] args) {
List<Integer> numbers = findIncreasingNumbers(5);
for (Integer i: numbers) {
System.out.print(i + " ");
}
}
}
En realidad, esta es una pregunta muy interesante, especialmente si no desea que sea una complejidad N ^ 2 o NlogN.
Lo que yo haría es lo siguiente:
- Defina una estructura de datos que contenga 2 valores (i y j) y el resultado de la fórmula.
- Defina una colección (por ejemplo, std :: vector) que contenga estas estructuras de datos
- Inicialice la colección con el valor (0,0) (el resultado es 1 en este caso)
- Ahora en un bucle haz lo siguiente:
- Busque en la colección y tome la instancia con el valor más pequeño.
- Quitarlo de la colección.
- Imprime esto
- Crea 2 nuevas instancias basadas en la instancia que acabas de procesar
- En la primera instancia el incremento i
- En la segunda instancia el incremento j
- Agregue ambas instancias a la colección (si aún no están en la colección)
- Bucle hasta que tengas suficiente
El rendimiento se puede modificar fácilmente seleccionando la estructura de datos y la recopilación adecuadas. Por ejemplo, en C ++, podría usar un std :: map, donde la clave es el resultado de la fórmula, y el valor es el par (i, j). Tomar el valor más pequeño es tomar la primera instancia en el mapa (* map.begin ()).
Escribí rápidamente la siguiente aplicación para ilustrarla (¡funciona! Pero no contiene más comentarios, lo siento):
#include <math.h>
#include <map>
#include <iostream>
typedef __int64 Integer;
typedef std::pair<Integer,Integer> MyPair;
typedef std::map<Integer,MyPair> MyMap;
Integer result(const MyPair &myPair)
{
return pow((double)2,(double)myPair.first) * pow((double)5,(double)myPair.second);
}
int main()
{
MyMap myMap;
MyPair firstValue(0,0);
myMap[result(firstValue)] = firstValue;
while (true)
{
auto it=myMap.begin();
if (it->first < 0) break; // overflow
MyPair myPair = it->second;
std::cout << it->first << "= 2^" << myPair.first << "*5^" << myPair.second << std::endl;
myMap.erase(it);
MyPair pair1 = myPair;
++pair1.first;
myMap[result(pair1)] = pair1;
MyPair pair2 = myPair;
++pair2.second;
myMap[result(pair2)] = pair2;
}
}
Entonces tenemos dos bucles, uno incrementando i y segundo incrementando j comenzando ambos desde cero, ¿verdad? (El símbolo de multiplicar es confuso en el título de la pregunta)
Puedes hacer algo muy sencillo:
- Añadir todos los elementos en una matriz
- Ordenar la matriz
¿O necesitas otra solución con más análisis de matemáticas?
EDITAR: Solución más inteligente al aprovechar la similitud con el problema de clasificación de mezcla
Si imaginamos un conjunto infinito de números de 2^i y 5^j como dos flujos / listas independientes, este problema tiene el mismo aspecto que el conocido problema de clasificación de mezcla.
Así que los pasos de solución son:
- Obtenga dos números uno de cada uno de los flujos (de 2 y de 5)
- Comparar
- Vuelve mas pequeño
- obtener el siguiente número de la secuencia de los más pequeños devueltos anteriormente
¡y eso es! ;)
PD: la complejidad de la clasificación de fusión always es O(n*log(n))
Esto se adapta bien a un estilo de programación funcional. En F #:
let min (a,b)= if(a<b)then a else b;;
type stream (current, next)=
member this.current = current
member this.next():stream = next();;
let rec merge(a:stream,b:stream)=
if(a.current<b.current) then new stream(a.current, fun()->merge(a.next(),b))
else new stream(b.current, fun()->merge(a,b.next()));;
let rec Squares(start) = new stream(start,fun()->Squares(start*2));;
let rec AllPowers(start) = new stream(start,fun()->merge(Squares(start*2),AllPowers(start*5)));;
let Results = AllPowers(1);;
Funciona bien con Resultados, siendo un tipo de flujo con valor actual y un método siguiente.
Caminando a través de él:
- Defino min para completenes.
- Defino un tipo de flujo para tener un valor actual y un método para devolver una nueva cadena, esencialmente la cabeza y la cola de un flujo de números.
- Defino la función de fusión, que toma el menor de los valores actuales de dos flujos y luego incrementa ese flujo. Luego recurre para proporcionar el resto de la secuencia. Esencialmente, dados dos flujos que están en orden, producirá un nuevo flujo que está en orden.
- Defino que los cuadrados son una corriente que aumenta en potencias de 2.
- AllPowers toma el valor de inicio y fusiona la secuencia resultante de todos los cuadrados en este número de potencias de 5. con la secuencia resultante de multiplicarla por 5, ya que estas son sus dos únicas opciones. De hecho, te quedas con un árbol de resultados.
El resultado es la fusión de más y más secuencias, por lo que se combinan las siguientes secuencias
1, 2, 4, 8, 16, 32 ...
5, 10, 20, 40, 80, 160 ...
25, 50, 100, 200, 400 ...
.
.
. La fusión de todos estos resulta ser bastante eficiente con la optimización del compilador y la compilación, etc.
Estos podrían ser impresos en la consola de esta manera:
let rec PrintAll(s:stream)=
if (s.current > 0) then
do System.Console.WriteLine(s.current)
PrintAll(s.next());;
PrintAll(Results);
let v = System.Console.ReadLine();
Se pueden hacer cosas similares en cualquier lenguaje que permita la recursión y pasar las funciones como valores (es un poco más complejo si no se pueden pasar las funciones como variables).
Estoy seguro de que todos pueden tener la respuesta a estas alturas, pero solo quería orientar esta solución ...
Es un Ctrl C + Ctrl V de http://www.careercup.com/question?id=16378662
void print(int N)
{
int arr[N];
arr[0] = 1;
int i = 0, j = 0, k = 1;
int numJ, numI;
int num;
for(int count = 1; count < N; )
{
numI = arr[i] * 2;
numJ = arr[j] * 5;
if(numI < numJ)
{
num = numI;
i++;
}
else
{
num = numJ;
j++;
}
if(num > arr[k-1])
{
arr[k] = num;
k++;
count++;
}
}
for(int counter = 0; counter < N; counter++)
{
printf("%d ", arr[counter]);
}
}
La pregunta que se me hizo fue devolver un conjunto infinito de soluciones. Reflexioné sobre el uso de árboles, pero sentí que había un problema con averiguar cuándo cosechar y podar el árbol, dado un número infinito de valores para i & j. Me di cuenta de que podía usarse un algoritmo de tamiz. A partir de cero, determine si cada entero positivo tuvo valores para i y j. Esto se facilitó dando vuelta a la respuesta = (2 ^ i) * (2 ^ j) y resolviendo para i en su lugar. Eso me dio i = log2 (respuesta / (5 ^ j)). Aquí está el código:
class Program
{
static void Main(string[] args)
{
var startTime = DateTime.Now;
int potential = 0;
do
{
if (ExistsIandJ(potential))
Console.WriteLine("{0}", potential);
potential++;
} while (potential < 100000);
Console.WriteLine("Took {0} seconds", DateTime.Now.Subtract(startTime).TotalSeconds);
}
private static bool ExistsIandJ(int potential)
{
// potential = (2^i)*(5^j)
// 1 = (2^i)*(5^j)/potential
// 1/(2^1) = (5^j)/potential or (2^i) = potential / (5^j)
// i = log2 (potential / (5^j))
for (var j = 0; Math.Pow(5,j) <= potential; j++)
{
var i = Math.Log(potential / Math.Pow(5, j), 2);
if (i == Math.Truncate(i))
return true;
}
return false;
}
}
Para una solución O (N), puede utilizar una lista de números encontrados hasta el momento y dos índices: uno que representa el número siguiente que se multiplicará por 2 y el otro que se multiplicará por 5. Luego, en cada iteración, Disponemos de dos valores candidatos para elegir el más pequeño.
En Python:
numbers = [1]
next_2 = 0
next_5 = 0
for i in xrange(100):
mult_2 = numbers[next_2]*2
mult_5 = numbers[next_5]*5
if mult_2 < mult_5:
next = mult_2
next_2 += 1
else:
next = mult_5
next_5 += 1
# The comparison here is to avoid appending duplicates
if next > numbers[-1]:
numbers.append(next)
print numbers
Si puedes hacerlo en O (nlogn), aquí hay una solución simple:
Get an empty min-heap
Put 1 in the heap
while (you want to continue)
Get num from heap
print num
put num*2 and num*5 in the heap
Ahí tienes. Por min-heap, me refiero a min-heap
Visualizo este problema como una matriz M donde M(i,j) = 2^i * 5^j . Esto significa que tanto las filas como las columnas están aumentando.
Piense en dibujar una línea a través de las entradas en orden creciente, comenzando claramente en la entrada (1,1) . A medida que visita las entradas, las condiciones de aumento de fila y columna aseguran que la forma formada por esas celdas siempre será una partición entera (en notación en inglés). Lleve un registro de esta partición ( mu = (m1, m2, m3, ...) donde mi es el número de entradas más pequeñas en la fila i , por lo tanto m1 >= m2 >= ... ). Entonces, las únicas entradas que necesita comparar son aquellas entradas que se pueden agregar a la partición.
Aquí hay un ejemplo crudo. Supongamos que ha visitado todas las x s ( mu = (5,3,3,1) ), entonces solo necesita verificar las @ s:
x x x x x @
x x x @
x x x
x @
@
Por lo tanto, el número de controles es el número de celdas que se pueden agregar (de manera equivalente al número de formas de subir en orden de Bruhat si tiene la mente de pensar en términos de posets).
Dada una partición mu , es fácil determinar cuáles son los estados que se pueden agregar. Imagen una cadena infinita de 0 s después de la última entrada positiva. Entonces puede aumentar mi en 1 si y solo si m(i-1) > mi .
De vuelta al ejemplo, para mu = (5,3,3,1) podemos aumentar m1 (6,3,3,1) o m2 (5,4,3,1) o m4 (5,3,3,2) o m5 (5,3,3,1,1) .
La solución al problema luego encuentra la secuencia correcta de particiones (cadena saturada). En pseudocódigo:
mu = [1,0,0,...,0];
while (/* some terminate condition or go on forever */) {
minNext = 0;
nextCell = [];
// look through all addable cells
for (int i=0; i<mu.length; ++i) {
if (i==0 or mu[i-1]>mu[i]) {
// check for new minimum value
if (minNext == 0 or 2^i * 5^(mu[i]+1) < minNext) {
nextCell = i;
minNext = 2^i * 5^(mu[i]+1)
}
}
}
// print next largest entry and update mu
print(minNext);
mu[i]++;
}
Escribí esto en Maple parando después de 12 iteraciones:
1, 2, 4, 5, 8, 10, 16, 20, 25, 32, 40, 50
y la secuencia de celdas de salida agregada y obtuvo esto:
1 2 3 5 7 10
4 6 8 11
9 12
correspondiente a esta representación matricial:
1, 2, 4, 8, 16, 32...
5, 10, 20, 40, 80, 160...
25, 50, 100, 200, 400...