#include <stdio.h> #define N 18 #define M 524288

main()  {
        float a[M][2];
        int i , j , k, n, min_index, locmin,  power[N+2], bitcount=0, lastcount=0;
    float min_ratio;
       float  locrat;
       float average;

a[0][0] = 0; a[0][1]=0; a[1][0] = 0; a[1][1] = 0; power[0] = 1;
power[1]=2; average = 0; /* the n loop stratifies the recursion by
levels of the tree */ for (n=1; n <= N; n++) {
  power[n+1] = 2*power[n];
  /* the i loop indexes vertices inside a level */
  for (i=power[n]; i < power[n+1]; i++)
  {
    bitcount = 0; lastcount=0; a[i][0] = 0; a[i][1] = 0;
    for (j=0; j <= n; j++)
    {
      k = i^(power[j]);
      if (k < i)
      {
        /* k < i iff there is a 1 in position k */
        k = power[j+1]*(i / (power[j+1])) + power[j+1] - 1 - i % power[j+1];
        a[i][0] += a[k][0];
        a[i][1] += a[k][1];
        bitcount++;
    }
      else lastcount=bitcount;
      /* lastcount will eventually say how many 1's after the leftmost zero */
    }
    a[i][1]++;
    a[i][0] += bitcount - lastcount - 1;
    a[i][0] = a[i][0] / bitcount;
    a[i][1] = a[i][1] / bitcount;
    /* a particular choice of the set B is given in literal form */
    if (  i==2  ||  i==4  ||  i==5  || i==8  ||
          i==9  ||  i==10 ||  i==11 ||
          i==18 || i==19  ||  i==20 ||  i==21 || i==22 || i==23 ||
          i==36 ||  i==37 || i==38 ||
          i==40  ||  i==41 || i==42 || i==43 ||  i==44 || i==45 || i==46 || i==47 ||
          i==73 || i==74|| i==75 ||
          i==80 || i==81 || i==82 || i==83 || i==84 ||  i==85 || i==86 || i==87 ||
          i==88 || i==89  || i==90 || i==91 ||
          i==160 || i==161 || i==162 || i==163 || i==164 || i==165 || i==166 || i==167 ||
      i==168 || i==169 || i==170 || i==171 || i==172 || i==173 || i==174 ||  i==175 || i==178 ||
      i==180 || i==181 || i==182 || i==183 ||
          i==324 || i==325 || i==326 || i==328 || i==329 ||
          i==330 || i==331 || i==332 || i==333 || i==334 || i==335 ||
          i==336 || i==337 || i==338 || i==339 || i==340 || i==341 || i==342 || i==343 ||
          i==344 || i==345 || i==346 || i==347 || i==348 || i==349 ||
          i==350 || i==351 ||
          i==361 || i==362 || i==363 ||
          i==656 || i==657 || i==658 || i==659 || i==660 || i==661 ||  i==662 || i==663 ||
      i==672 || i==673 || i==674 || i==675 || i==676 || i==677 || i==678 || i==679 ||
          i==680 || i==681 || i==682 || i==683 ||
          i==684 || i==685 || i==686 || i==687 || i==688 || i==689 ||
          i==690 || i==691 || i==692 || i==693 || i==694 || i==695 || i==697 ||  i==698 || i==699||
          i==1322 || i==1323 ||
          i==1346 || i==1347 || i==1348 || i==1349 ||
          i==1350 || i==1351 || i==1352 || i==1353 || i==1354|| i==1355 ||
          i==1356 || i==1357 || i==1358 || i==1359 ||
          i==1360 || i==1361 || i==1362 || i==1363 || i==1364 || i==1365 ||
          i==1366 || i==1367 || i==1368 || i==1369 || i==1370 || i==1371 ||
          i==1372 || i==1373 || i==1374 || i==1375 || i==1380 || i==1381 ||
          i==1384 || i==1385 || i==1386 || i==1387 || i==1388 || i==1389 || i==1390 || i==1391 ||
          i==2704 || i==2705 || i==2706 || i==2707 || i==2708 || i==2709 || i==2710 || i==2711 ||
          i==2720 || i==2721 || i==2722 || i==2723 || i==2724 || i==2725 || i==2726 || i==2727 ||
          i==2728 || i==2729 || i==2730 || i==2731 || i==2732 || i==2733 || i==2734 || i==2735 ||
          i==2736 || i==2737 || i==2738 || i==2739 || i==2740 || i==2741 || i==2742 || i==2743 ||
          i==2745 || i==2746 || i==2747 ||
          i==5456 || i==5457 || i==5458 || i==5459 || i==5467 ||
          i==5460 || i==5461 || i==5462 || i==5463 || i==5465 || i==5466  )
      {
        a[i][0] = 0; a[i][1] = 0;
      }
    if(i == (M/2))
      {
    min_index = i;
    min_ratio = a[i][0]/a[i][1];
      }

      if(i > (M/2))
      {
    if((a[i][0]/a[i][1]) < min_ratio)
      {
        min_index = i;
        min_ratio = a[i][0]/a[i][1];
      }
       }
      if  (i > (M/2))
       {
           average = average + (a[i][0]/a[i][1]);
           }
      if(i == 3)
      {
    locmin = i;
    locrat = a[i][0]/a[i][1];
      }
      if(i < (M/2))
    {  if (i > 71)
          {
        if(a[i][1] > 0)
             { if  ((a[i][0]/a[i][1]) < locrat)
           {
            locmin = i;
            locrat = (a[i][0])/(a[i][1]);
           }
         }
           }
        }
  }
  printf("\n");
  }
 printf("Row with minimum ratio is:\n");
 printf("min_index=%i,exp. reward=%f, exp. time=%f, ratio=%f\n",min_index,
      a[min_index][0], a[min_index][1], a[min_index][0]/a[min_index][1]);
 printf("Row with local minimum ratio is:\n");
 printf("locmin=%i,exp. reward=%f, exp. time=%f, ratio=%f\n", locmin, locrat, average, M);
    }}