Digamos que tenemos números naturales$n,k$. ¿Existe una forma efectiva de representar$k$ como$a_1\cdot\ldots\cdot a_n$ tal que cada$a_i$ es natural y la suma$a_1+\cdots +a_n$ es mínima?
No parece tan difícil, pero no puedo entenderlo. En caso de que$n=2$ sólo necesitamos tomar la raíz cuadrada de$k$ y tomar$k=ab$, donde$a$ es el mayor divisor de$k$y$a\leq\sqrt{k}$ es el divisor más pequeño de$b$ con$k$.
Pero no puedo entender el caso cuando$b\geq\sqrt{k}$.
Tenemos la condición $k={a_1a_2...a_n}$
Dado $a_1, a_2, ... a_{n-1}$ tenemos $a_n=\frac k {a_1a_2...a_{n-1}}$
Queremos minimizar $A=a_1+ a_2+ ... +a_{n-1}+\frac k {a_1a_2...a_{n-1}}$
$\frac {\partial A}{\partial a_1}=1-\frac k {{a_1}^2a_2...a_{n-1}}$
Para un mínimo de $A$ tenemos $1-\frac k {{a_1}^2a_2...a_{n-1}}=0$
${{a_1}^2a_2...a_{n-1}}=k$
Se puede demostrar que ${{a_i}^n}=k$ o $a_i=k^{\frac 1 n}$.
Esto le da la solución a la no-entero problema. El entero problema es más difícil.
Para $n=2$ es suficiente para encontrar el mayor divisor menos de $\sqrt k$ porque esto es equivalente a encontrar el menor divisor mayor que $\sqrt k$. Pensar acerca de la lista de factores que aumentan de 1 a $k$: todos ellos están en pares (a menos $\sqrt k$ es un número entero).
Para $n>2$ el problema se vuelve más difícil. Mis primeros pensamientos fueron:
1) Encontrar el menor divisor $b$ que satisface $b=>\frac {k} {{k}^{\frac 1 n}}$.
2) Dividir el $k$$b$.
3) Reducir el $n$ por 1 y repita.
Otros usuarios los comentarios acerca de que no es único solutins, así que me sugirió la alternativa:
1) Encontrar el mayor divisor $b$ que satisface $b<={{k}^{\frac 1 n}}$.
2) Dividir el $k$$b$.
3) Reducir el $n$ por 1 y repita.
Un enfoque combinado fue a probar ambos y a identificar el mejor conjunto.
PERO los comentarios mostró que de esta forma no dar la solución correcta en ciertos casos (por ejemplo,$k=6300$).
Así que he vuelto a pensar más en ello.
Deje $b_i=k^{\frac i n}$
En la no-entero situación en la que nos han $b_1=a_1$ y $b_2=a_1a_2$ y que, en general, $b_i=a_1a_2...a_i$
En el entero problema que queremos $a_1a_2...a_i$ a que se acerque a $b_i$ como sea posible.
Así, para cada $b_i$ encontrar el menor divisor de $k$ que es mayor que $b_i$ y el mayor divisor de $k$ que es menor que $b_i$. Esto nos da un total de $2(n-1)$ posibles divisores de $k$. Tendremos que investigar cada uno de estos divisores a su vez:
Supongamos que hemos elegido para investigar el divisor $d_i$ que está cerca de a $b_i$ (ya sea por encima o por debajo). Debemos considerar las posibles separaciones de $d_i$ a $a_1a_2...a_i$ y las posibles separaciones de $\frac k {d_i}$ a $a_{i+1}a_{i+2}...a_n$. Utilice el mismo método para k.
¿Cuánto tiempo va a tomar?
Hay $2(n-1)$ posibles divisores a considerar en el primer paso.
Cada uno de estos produce un mayor $2(n-2)$ posibles divisores en el segundo paso. Habrá cierta superposición con los divisores identificado en el primer paso, pero no podemos asumir que esto va a suceder. Podría ser posible construir un algoritmo de la capacidad para comprobar ya se intentó divisores.
En el tercer paso será la $2(n-3)$ posibles divisores. Así que el total de posibles conjuntos de investigar, $2(n-1) \times 2(n-2) \times 2(n-3) \times ... \times 2=2^{n-1} {(n-1)}!$
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
