Advertisement
Guest User

akrasuski1 - test dla n=5, zwraca 63.911927%

a guest
Jul 11th, 2016
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.05 KB | None | 0 0
  1. #include <math.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5. #define TEST_N 5
  6. #define START_AT 0.0
  7. #define RUNS 100000000
  8.  
  9. #define PREC 10000
  10. #define SZ 1009
  11. #define false 0
  12. #define true 1
  13. #define bool int
  14.  
  15. double M;
  16. double cache[PREC+1][SZ];
  17. void reset(double r){
  18. static bool done=false;
  19. if(!done){
  20. done=true;
  21. for(int i=0;i<=PREC;i++){
  22. for(int j=0;j<SZ;j++){
  23. cache[i][j]=-1;
  24. }
  25. }
  26. }
  27. M=r;
  28. }
  29.  
  30. double R(double m, int n){
  31. int mint=(int)(m*PREC);
  32. if(n==1){
  33. return 1-m;
  34. }
  35. else if(cache[mint][n]>=0){
  36. return cache[mint][n];
  37. }
  38. else{
  39. double sum=0;
  40. int cnt=0;
  41. for(int i=0;i<=PREC;i++){
  42. double v=(i+0.00001)/PREC;
  43. if( v<m ){ cnt++; }
  44. else{
  45. if(pow(v, n-1)>R(v, n-1)){
  46. sum+=pow(v,n-1);
  47. }
  48. else{
  49. sum+=R(v, n-1);
  50. }
  51. }
  52. }
  53. sum+=cnt*R(m, n-1);
  54. return cache[mint][n]=sum/(PREC+1);
  55. }
  56. }
  57.  
  58. int guess_max(double v, int ntotal, int count){
  59. int N=ntotal-count+1; // Numbers left.
  60. int res;
  61. if(v<M){
  62. res=0;
  63. }
  64. else if(N==1){
  65. res=1; // We fail anyway...
  66. }
  67. else{
  68. res = pow(v, N-1) > R(v, N-1);
  69. }
  70. if(v>M){ M=v; }
  71. return res;
  72. }
  73.  
  74. void print(int n){
  75. for(int nn=1;nn<=n;nn++){
  76. printf("For N=%d: total - %lf%%, other:\nM%% ", nn, R(START_AT, nn)*100);
  77. for(int i=0;i<100;i+=2){
  78. printf("%2d ",i);
  79. }
  80. printf("\nR%% ");
  81. for(int i=0;i<100;i+=2){
  82. printf("%2d ",(int)(99.9999*R(i/100.0, nn)));
  83. }
  84. printf("\n");
  85. }
  86. printf("R(START, N)=%lf%%\n", 100*R(START_AT, n));
  87. }
  88.  
  89. int main(){
  90. //reset(START_AT);
  91. int cnt=0;
  92. int N=TEST_N;
  93. //print(N);
  94. int runs=RUNS;
  95. for(int i=0;i<runs;i++){
  96. reset(START_AT);
  97. srand(i);
  98. double real_max = START_AT;
  99. double your_max = -1;
  100. int done = 0;
  101.  
  102. for(int count=1; count<=N; count++) {
  103. double x=rand()/(double)RAND_MAX;
  104. if (!done && (done = guess_max(x, N, count))) {
  105. your_max = x;
  106. }
  107. if (real_max < x) {
  108. real_max = x;
  109. }
  110. }
  111. if(your_max >= real_max-1e-12) {
  112. cnt++;
  113. }
  114. }
  115. printf("Empirical accuracy for N=%d: %lf%%\n", N, cnt/(double)runs*100);
  116. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement