Estoy trabajando en algunas tareas y se supone que estamos haciendo una función combinada en F #. Tengo baja la función factorial, pero parece desbordarse una vez que obtengo un gran número para usar factorial. (Digamos 20) Entiendo que puedo usar un int64 o un flotante, pero eso cambiaría todas las entradas en el código. ¿Qué tipo de datos debo usar?

let rec Fact (a:int)=
   if (a = 0) then 1 else a*Fact(a-1);;

let combo (n:int) (k:int)=
   if (n = 0) then 0 else (Fact n)/((Fact k)*(Fact (n-k)));;

En el código en este momento, cuando hago combo 20 5 ;; me da 2147. Lo cual es claramente la respuesta incorrecta. Miré la función factorial y cuando puse 20 allí me dio un gran número negativo. Cualquier ayuda sería muy apreciada. Gracias por adelantado.

2
user999999 16 ene. 2017 a las 23:08

2 respuestas

La mejor respuesta

En primer lugar, si desea evitar sorpresas, puede abrir el módulo Checked en la parte superior de su archivo. Esto redefinirá los operadores numéricos para que realicen comprobaciones de desbordamiento, y obtendrá una excepción en lugar de un número inesperado:

open Microsoft.FSharp.Core.Operators.Checked

Como Fyodor señala en el comentario, no puede caber factorial de 20 en int y necesita int64. Sin embargo, su función combo realiza una división que hará que el resultado de combo 20 5 sea lo suficientemente pequeño como para caber en int.

Una opción es cambiar Fact para usar int64, pero mantener combo como una función que toma y devuelve enteros; deberá convertirlos a int64 antes de llamar a { {X4}} y luego de vuelta a int después de realizar la división:

let rec Fact (a:int64) =
   if (a = 0L) then 1L else a * Fact(a-1L)

let combo (n:int) (k:int) =
   if (n = 0) then 0 else int (Fact (int64 n) / (Fact (int64 k) * Fact (int64 (n-k))))

Ahora puede llamar a combo 20 5 y obtendrá 15504 como resultado.

EDITAR: Como señaló @pswg en la otra respuesta, int64 también es bastante limitado, por lo que necesitará BigInteger para factoriales más grandes. Sin embargo, el mismo método debería funcionar para usted con BigInteger. Puede mantener la función combo como una función que devuelve int mediante la conversión de BigInteger a int.

3
Tomas Petricek 16 ene. 2017 a las 22:19

Simplemente no podrá hacer eso con un entero de 32 bits (int). Un entero de 64 bits le llevará hasta 20!, pero fallará en 21!. Los números simplemente se vuelven demasiado grandes, demasiado rápido. Para ir más allá, deberá usar System.Numerics.BigInteger (abreviado bigint en F #).

El parámetro probablemente puede permanecer como int para ser razonable, pero debe devolver un bigint:

let rec Fact (n : int) = 
    if n = 0 then bigint.One else (bigint n) * Fact (n - 1)

O para ser un poco más idiomática:

let rec Fact = function | 0 -> bigint.One | n -> (bigint n) * Fact (n - 1)

Y ahora, en su función Combo, necesitará usar estos bigint internamente para todas las matemáticas (afortunadamente, la división de enteros es todo lo que necesita en este caso).

let Combo (n : int) (k : int) =
    if n = 0 then bigint.Zero else (Fact n) / ((Fact k) * (Fact (n - k)))

Si realmente desea hacer que Combo devuelva un int, puede hacer esa conversión aquí:

let Combo (n : int) (k : int) =
    if n = 0 then 0 else (Fact n) / ((Fact k) * (Fact (n - k))) |> int

Ejemplos:

Combo 20 5 // --> 15504
Combo 99 5 // --> 71523144 (would break if you used int64)

Editar : Al repensar su implementación de Combo, puede obtener grandes mejoras de rendimiento. Consulte esta pregunta en Math.SE para conocer la base de esto. implementación:

let ComboFast (n : int) (k : int) =
    let rec Combo_r (n : int) = function 
        | 0 -> bigint.One 
        | k -> (bigint n) * (Combo_r (n - 1) (k - 1)) / (bigint k)
    Combo_r n (if (2 * k) > n then n - k else k)

Un punto de referencia rápido mostró que esto era significativamente más rápido que la versión anterior basada en Fact:

Function             Avg. Time (ms)
Combo 99 5            30.12570 
ComboFast 99 5         0.72364
2
Community 13 abr. 2017 a las 12:19