¿Hay una forma eficiente (es decir: sin construir el triángulo real) para averiguar un número de la fila que primero se produce en triángulo de Pascal?
Esto es equivalente a responder: dado cuál es el número más pequeño que existe tal que . Esto es debido a que un número en la fila y columna en el triángulo de Pascal es igual a `` .
El enlace proporcionado por JavaMan, de hecho, responde a esta pregunta: Cómo revertir la $n$ elija $k$ fórmula?
Un resumen del algoritmo -- me llevó tiempo para averiguar de que contestar, así que estoy escribiendo como un algoritmo, en lugar de una explicación de uno. Si quieres saber cómo funciona esto, le recomiendo visitar la respuesta y upvoting, es muy informativo -- es como sigue. En primer lugar, el problema es minimizar n da X de modo que:
$${n \choose k} = X$$
Primero determinamos max(k) dado que sabemos que:
$$X > \frac{4^k}{2k+1}$$
From there we iterate over 1 to max(k). At each step of the iteration, n, if it exists is contained in the interval:
$$\sqrt[k]{k! X} + k \ge n \ge \sqrt[k]{k! X}$$
We iterate over that interval and check if ${n \elegir k}=X$. A continuación, podemos fácilmente encontrar el mínimo ejemplo n.
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.
