La pregunta podría formularse como un número n de 6 bits, ¿cuál es la probabilidad de que sea un factor de un número X de 15 bits elegido al azar?
Comience con el rango 0 a 2 ^ 15–1 = 0 a 32767 sin signo, -16384 a 16384 con signo.
segundo rango 0 2 ^ 6–1 = 0 a 63 sin signo, -31 a 31 con signo.
- Cómo aprender estructuras de datos de manera efectiva
- ¿Aprender la construcción del compilador mejora la habilidad / visión de resolución de problemas de programación? ¿Si es así, cómo? ¿O por qué no?
- ¿Existe un algoritmo de tiempo O (N) para esta pregunta?
- Cómo ordenar matrices en C
- ¿Qué son los árboles de búsqueda binarios?
Asuma primero sin firmar, ya que eso es más difícil.
El factor más grande sería 63.
X es aleatorio, entonces
X {X: impar} P = 1/2
X {X; par} P = 1/2
Pero eso no ayuda mucho.
Algunos hechos lógicos sobre los posibles resultados:
X {n:> X} P = 0 P (n> X) = 63/32768
X {n; 1} P = 1 P (n = 1) = 1/64
X = 0 {n;> 0} P = 1 P (X = 0, n> 0) 1/32768 * 63/64
X = impar, n {1 .. 63 impar} P =? P (n = impar) = 1/2
X = impar, n {2 .. 64 par} P = 0 P (n = par) = 1/2
X = par, X> 0, n {2} P = 1; P (n = 2) = 1/64
X = impar, n {2} P = 0; P (n = 2) = 1/64
X = impar, n {par} P = 0; P (n = par) = 1/2
X = impar, n {impar} P =? ; P (n = impar) = 1/2
n = 0 P = 0; P (n = 0) = 1/64
Entonces podemos ver que hay algunos casos especiales.
Ahora cada n descendente tiene un mayor
conjunto de múltiplos que podrían aterrizar en X,
empezando con
63 * 520 = 32760,
entonces 63 será un factor en 520 números.
62 tiene 528 múltiplos <32767
…
31 tiene 1057 múltiplos <32767
…
3 tiene 10922 múltiplos <32767.
2 tiene 16384 múltiplos <32767
1 divide todo.
0 divide solo 0 o nada.
Entonces, hay una suma de las probabilidades de cada [matemática] n [/ matemática] dividiendo un número [matemática] <32768 [/ matemática].
n_____________P________________
0 = 0
1 = 1
2 16384/32768 = 1/2
3 10922/32768 = 1/3
4 8191/32768 = 1/4
5 6553/32768 = 1/5
…
63 520/32767 = 1/63
entonces parece
[matemáticas] P (n | X) = P (X> 0, n> 0) + P (X = 0, n> 0) – P (n> X) – P (n = 0) [/ matemáticas]
[matemáticas] P (X> 0, n> 0) = (\ sum_ {n = 1} ^ {63} 1 / n) / 63 [/ matemáticas]
[matemática] P (X = 0, n> 0) = 1/32768 * 63/64 [/ matemática] (todos [matemática] n> 0 [/ matemática] dividir [matemática] 0 [/ matemática])
[matemáticas] P (n> X) = 62/32766 [/ matemáticas]
[matemáticas] P (n = 0) = 1/64 [/ matemáticas]
