fork(3) download
copy 
  1. // the average amount of information in bits obtained in a single query
  2. // version for large sizes
  3. import core.bitop;
  4. import std.algorithm;
  5. import std.math;
  6. import std.range;
  7. import std.stdio;
  8.  
  9. int n;
  10. int k;
  11.  
  12. real shannon (R) (R range)
  13.     if (is (typeof (range.front) : real))
  14. {
  15. 	real res = 0.0;
  16. 	foreach (real element; range)
  17. 	{
  18. 		res -= element * log2 (element);
  19. 	}
  20. 	return res;
  21. }
  22.  
  23. void main ()
  24. {
  25. 	readf (" %s", &n);
  26. 	assert (1 <= n && n <= 10_000);
  27. 	readf (" %s", &k);
  28. 	assert (1 <= k && k <= n);
  29.  
  30. 	auto c = new real [] [n + 1];
  31. 	foreach (i; 0..n + 1)
  32. 	{
  33. 		c[i] = new real [i + 1];
  34. 		c[i][0] = 1.0;
  35. 		foreach (j; 1..i)
  36. 		{
  37. 			c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
  38. 		}
  39. 		c[i][i] = 1.0;
  40. 	}
  41.  
  42. 	auto p2 = new real [n + 1];
  43. 	p2[0] = 1.0;
  44. 	foreach (i; 1..n + 1)
  45. 	{
  46. 		p2[i] = p2[i - 1] * 2.0;
  47. 	}
  48.  
  49. 	real [] p;
  50. 	for (int v = k; v <= n; v++)
  51. 	{
  52. 		p ~= c[v - 1][k - 1] / p2[v];
  53. 	}
  54. 	real s = 0.0;
  55. 	for (int v = 0; v < k; v++)
  56. 	{
  57. 		s += c[n][v];
  58. 	}
  59. 	s /= p2[n];
  60. 	p ~= s;
  61.  
  62. 	writefln ("%.10g", p.shannon);
  63. }
  64.  
Success #stdin #stdout 0.76s 2992KB
comments (?)
stdin
copy 
5000 2000
stdout
copy 
8.029717158
https://ideone.com/Pgu0hH
language:
D (dmd 2.085.0)
created:
8 years ago
visibility:
secret

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!