58 lines
1.5 KiB
Java
58 lines
1.5 KiB
Java
import java.math.BigInteger;
|
|
import java.util.HashMap;
|
|
import java.util.Map;
|
|
|
|
public class LahNumbers {
|
|
|
|
public static void main(String[] args) {
|
|
System.out.println("Show the unsigned Lah numbers up to n = 12:");
|
|
for ( int n = 0 ; n <= 12 ; n++ ) {
|
|
System.out.printf("%5s", n);
|
|
for ( int k = 0 ; k <= n ; k++ ) {
|
|
System.out.printf("%12s", lahNumber(n, k));
|
|
}
|
|
System.out.printf("%n");
|
|
}
|
|
|
|
System.out.println("Show the maximum value of L(100, k):");
|
|
int n = 100;
|
|
BigInteger max = BigInteger.ZERO;
|
|
for ( int k = 0 ; k <= n ; k++ ) {
|
|
max = max.max(lahNumber(n, k));
|
|
}
|
|
System.out.printf("%s", max);
|
|
}
|
|
|
|
private static Map<String,BigInteger> CACHE = new HashMap<>();
|
|
|
|
private static BigInteger lahNumber(int n, int k) {
|
|
String key = n + "," + k;
|
|
if ( CACHE.containsKey(key) ) {
|
|
return CACHE.get(key);
|
|
}
|
|
|
|
// L(n,0) = 0;
|
|
BigInteger result;
|
|
if ( n == 0 && k == 0 ) {
|
|
result = BigInteger.ONE;
|
|
}
|
|
else if ( k == 0 ) {
|
|
result = BigInteger.ZERO;
|
|
}
|
|
else if ( k > n ) {
|
|
result = BigInteger.ZERO;
|
|
}
|
|
else if ( n == 1 && k == 1 ) {
|
|
result = BigInteger.ONE;
|
|
}
|
|
else {
|
|
result = BigInteger.valueOf(n-1+k).multiply(lahNumber(n-1,k)).add(lahNumber(n-1,k-1));
|
|
}
|
|
|
|
CACHE.put(key, result);
|
|
|
|
return result;
|
|
}
|
|
|
|
}
|