fork download
copy 
  1. import java.math.BigInteger;
  2. import java.util.LinkedHashMap;
  3.  
  4. class CountStrings2 {
  5.  
  6. 	// cache. key: N:M
  7. 	private LinkedHashMap<String, BigInteger> sNM = new LinkedHashMap<String, BigInteger>();
  8. 	private final int P;
  9.  
  10. 	public CountStrings2(int P, int N, int M) {
  11. 		this.P = P;
  12. 		BigInteger S = computeS(N, M);
  13. 		System.out.println("P=" + P + " N=" + N + " M=" + M + " S=" + S);
  14. 		//outputCaches();
  15. 		computeAsympt(N,M);
  16. 	}
  17.  
  18. 	private BigInteger computeS(int N, int M) {
  19. 		String k = N + ":" + M;
  20. 		if (!sNM.containsKey(k)) {
  21. 			BigInteger b = BigInteger.ZERO;
  22. 			if (N < M) {
  23. 				b = BigInteger.valueOf(P).pow(N);
  24. 			} else {
  25. 				for (int i= 1; i < M; i++) {
  26. 					b = b.add(computeS(N-i, M));
  27. 				}
  28. 				b = b.multiply(BigInteger.valueOf(P-1));
  29. 			}
  30. 			sNM.put(k, b);
  31. 		}
  32.  
  33. 		return sNM.get(k);
  34. 	}
  35.  
  36. 	public void outputCaches() {
  37. 		System.out.println("============== SNM ====  (P=" + P + ")");
  38. 		for (String k : sNM.keySet()) {
  39. 			System.out.println("SNML " + k + "=" + sNM.get(k));
  40. 		}
  41. 	}
  42.  
  43. 	public void computeAsympt(int N, int M) { // asympotic approximation 
  44. 		double theta = 1.0 / P;
  45. 		double probasympt =  Math.pow(1 - Math.pow(theta, M - 1),N * (1 - theta));
  46. 		BigInteger S = computeS(N, M);
  47. 		BigInteger cc = BigInteger.valueOf(P).pow(N).multiply(BigInteger.valueOf(1000000)).divide(S);
  48. 		double probexact = 1000000.0/cc.doubleValue();
  49. 		System.out.printf("prob:%.4f asymptotic:%.4f\n" ,probexact, probasympt);
  50. 	}
  51.  
  52. 	public static void main(String[] args) {
  53. 		new CountStrings2(4, 50, 5);
  54.  
  55. 	}
  56. }
Success #stdin #stdout 0.04s 245632KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
P=4 N=50 M=5 S=1104822076420345943562167435148
prob:0.8716 asymptotic:0.8635
https://ideone.com/zw1wO
language:
Java (HotSpot 12)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!