Dado un conjunto de enteros finitos S y un entero P, ¿cómo puede encontrar eficientemente cómo crear P a partir de elementos en S utilizando las cuatro operaciones básicas?

Answer 1

Hay una respuesta diferente dependiendo de si desea el algoritmo más eficiente o la expresión más eficiente. También depende de si se permite el uso repetido del mismo número entero; supongo que sí.

Considere que si un conjunto contiene dos números que son relativamente primos, entonces alguna secuencia de sumar y restar esos dos números dará como resultado ‘1’. Luego, la suma repetida de ‘1’ puede dar como resultado cualquier número P. Si no hay dos números que sean relativamente primos, entonces podemos elegir un par, crear su MCD (nuevamente, usando solo sumas y restas, esto es posible) y dividirlo por El MCD. Por lo tanto, todo lo que necesitamos para encontrar * alguna * expresión para P es una cantidad de trabajo proporcional a:

• Identificar los dos elementos mínimos de S (opcional), [math] \ mathcal {O} (| S |) [/ math]
• Calcule el MCD de esos dos elementos, [math] \ mathcal {O} (\ log B) [/ math] donde [math] B [/ math] es el número más pequeño, utilizando el algoritmo Euclidiano Extendido
• Si no es 1, divida por el MCD y recalcule para obtener una expresión igual a 1.
• Genere una expresión que sea P repeticiones del valor derivado del paso anterior: [math] \ mathcal {O} (P) [/ math]

Afortunadamente, esto nos da una prueba de que cualquier conjunto de dos o más enteros distintos de cero tendrá alguna expresión igual a [math] P [/ math]. (Incluso si los dos enteros son inversos entre sí, esto no causa dificultad, solo comience uno de ellos al cuadrado).

Podemos mejorar el tiempo de ejecución de psuedo-polinomio a polinomio enviando el número en una representación “base [matemática] N [/ matemática]” donde [matemática] N [/ matemática] es cualquier entero conveniente del conjunto (o base 2 si todo con lo que tenemos que trabajar son los 1).

Ahora, para encontrar la representación más pequeña de [matemáticas] P [/ matemáticas], vamos a tener que hacer mucho más trabajo. Hay muchos posibles árboles de expresión de los que preocuparse, y muchos de ellos tendrán los mismos valores, ya que la multiplicación y la suma son conmutativas (¡y distributivas!) Si el árbol mínimo para [matemáticas] P [/ matemáticas] es en absoluto considerable es poco probable que lo encontremos antes de que se quede sin memoria, si intentamos BFS o programación dinámica.

Así que aquí está lo que sugeriría. Iterar sobre el número L de hojas en el árbol. Para generar todos los árboles [math] L [/ math] -leaf:

• Elija uno de los cuatro operadores para la raíz
• Si el operador es – o /, pruebe recursivamente todas las combinaciones de subárboles de hoja J y hoja K de manera que [matemática] J + K = L [/ matemática] para las dos ramas
• Si el operador es [matemática] * [/ matemática] o [matemática] + [/ matemática], intente recursivamente todas las combinaciones de subárboles de hoja J y hoja K con ambas [matemática] J + K = L [/ matemática] y [matemáticas] J \ leq K [/ matemáticas]

Hasta la cantidad de memoria disponible, guarde en caché todos los subárboles indexados por número de hojas, eliminando aquellos con valores duplicados o aquellos cuyo valor aparece en un árbol más pequeño.

El número de árboles binarios con hojas L viene dado por el número catalán [matemática] C_ {L-1} = \ frac {1} {L} {2 (L-1) \ elige L-1} [/ matemática], y es exponencialmente más grande que esto debido a la elección de operadores en cada nodo interno del árbol.