Subconjuntos densos en orden lexicográfico
Este problema es en realidad encontrar un conjunto específico de episodios.
Este problema es muy simple si en lugar de generar una colección específica, se genera una colección específica.
Tome N=5, K=3 como ejemplo. c (5, 3), elija 3 de 5 sin repetición, el resultado del cálculo es (5 * 4 * 3) / (1 * 2 * 3) = 10, de los cuales 10.
Luego enuméralo en detalle:
(1,2,3), (1,2,4), (1,2,5), (1,3, 4 ), (1,3,5), (1,4,5)
(2,3,4), (2,3,5), (2,4,5)
p>(3,4,5)
Sí, es 10.
Ten en cuenta que cada fila está separada por el primer número, por lo que puedes ver:
Si el primero es 1, hay seis conjuntos.
Si el primero es 2 (pero el primer número es 2 y no contiene 2), entonces hay 3 grupos.
El primero son 3, con 1 juego.
¿Existe alguna regla para 6, 3 y 1? Veamos específicamente los seis conjuntos de 6
El primer conjunto es 1, lo que significa que el primer conjunto de números se ha fijado en 1 y 1 ya no está seleccionado. En otras palabras, el 1 ya no está seleccionado, por lo que nos quedan dos de los cuatro números 2, 3, 4 y 5.
Elige dos de cuatro. Esto es muy familiar. ¿No es como elegir tres de cinco?
Luego calcula C (4, 2), (4 * 3) / (1 * 2) = 6, que de hecho es 6, esto es lo mismo que elegir 3 de 5;
Mira los otros dos números 6, 3 y 1, es lo mismo. Elija dos de tres para obtener tres conjuntos, elija dos de dos para obtener un conjunto.
A estas alturas, quizás ya sepas que C(5,3) = C(4,2)+C(3,2)+C(2,2).
¿No parece recursiva esta fórmula?
Aquí podemos intentar cambiar el valor inicial, como n = 7, k = 4, el resultado es c (7, 4) = c (6, 3) + c (5, 3) +c(4,3)+c(3,3).
Viendo este resultado, podemos asumir que c(n,k) = c(n-1,k-1)+c(n-2,k-1)...+c(k -1,k-65438=1
¿Qué pasa cuando K==1? Si lo piensas bien, sabrás que si eliges 1 de N números, el resultado será N conjuntos
De esta manera podemos obtener la fórmula del número establecido
C(N,K)=C(N-1,K-1)+C(N-2,K) . -1)...+C(K-1,K-1)(K>=2)
c(N,K)=N(K=1)
Ahora que tenemos la fórmula, la recursividad está bien implementada
INT C(N,K){
if (K == 1) devuelve N
<; p>Otrosrenturn c（n-1，k-1）+c（n-2，k-1）+...+c（k-1，k-1）/ / Solo usar for o while.
}
Esa es la idea, pero el problema es solicitar un conjunto específico
Establecer una matriz global S[K+. 1] aquí (establezca K+1 para evitar el uso de S[0] para facilitar la lectura de ideas de código) para almacenar la colección específica que se generará
Ahora que conocemos C(. n,k)=C(n-1,k-1)+C(n-2,k-1)+...+C(k-1,k-1 =2), entonces ¿Cuáles son las características de el conjunto específico C(N-1, K-1)? La respuesta es el primer número, que es 1.
Dado que el primer número es 1, es S[1] = 1;
p>
Echemos un vistazo.
La recursividad primero hará C(N,K) = C(N-1,K-1)+C(N-2,K-1)...e ingresará C(N-1,k- y luego C(N -2, K-2), el cual se caracteriza porque el segundo número es 2, es decir, S[2] = 2
Esto continúa hasta que sale el primer grupo, s[k] =; k; en este momento Estando en C (N-K+1,1), es decir, al final del día se debe seleccionar el número K, y se ha seleccionado el número anterior K-1, es decir, 1. , 2, 3, 4...k -1
Cuáles son las opciones para -1, N es x. Muy simple, solo usa un for y selecciona todos estos n-k números.
c(N-K+1,1) ¿cuál es el siguiente de la recursividad?
Por otro lado, ¿cómo se produce C(N-K+1,1)? p>
C(N-K+2,2) = C(N-K +1,1)+C(N-K,1)...+C(1,1)
Se convierte Descubra que C(N-K+1,1) proviene de esto, así que la siguiente entrada es C(N-K,1).
¿Cuál es la diferencia entre C(N-K+1,1)?
c(N-K+1), 1) es establecer el número K-1 en K-1 y luego seleccionar el número K,
Entonces C (). N-K, 1), es decir, el número K-1 no es K-1, pero su siguiente número es K, y el número K-1 se establece en K,
Luego continúe con y seleccione todos los números restantes desde K+1 hasta N-K-1 y genere el conjunto, completando así C(N-K, 1).
En este punto, el 90% de las ideas específicas han surgido, quedando el final. toque final
c (N-K-1, 1), K-1 El número es K+1, y luego elige 1 de K+2 a N.
Y cómo. ¿Se calculan aquí los K-1, K+1, K, K+2 y 1 específicos?
Si ha entendido la idea, de hecho, cuando obtiene C (N-K-1, 1) , ya sabes "C (N-K-1, 1), y el número de K-1 es k+65438+.
No importa si no lo entiendes.
Cambie la función recursiva inicial C(N,K) a C( N, K, A, B, C, D, E
Tome n = 5 y k = 3 como an. Por ejemplo, dejemos que C(5, 3) establezca el número cero en 0. Elija tres números del 1 al 5.
Entonces, el C(5,3) inicial se reescribe como C(5,3,0). ,0,1,5,3)
C(5,3) = C(4,2)+C(3,2)+C(2,2)
Luego C(4,2) establece que el número 1 es 1, luego elige dos números del 2 al 5, por lo que C(4, 2, 1, 1, 2, 5, 2) se reescribe como C(4, 2, 2). ).
C(3,2) es establecer el número 1 a 2 y luego seleccionar 2 números del 3 al 5, por lo que C(3,2) se reescribe como C(4,2,1, 2 , 3, 5, 2).
C(2,2) es establecer el número 1 a 3 y luego seleccionar 2 números del 4 al 5, por lo que C(2,2) se reescribe como C(4,2,1, 3 , 4, 5, 2).
Observando estos tres ejemplos, podemos encontrar que A=K global-K recursivo, B=N global-N recursivo, C=B+1, D=N global, E=K recursivo.
Vale, el 10% restante ya está solucionado. Este número está completo.