programs/n0.c

   1 #include <stdio.h>
   2
   3 #define MAX 13
   4
   5 // Faktorial
   6 int f(int n)
   7 {
   8   static int ff[MAX] = { 1 };
   9   if (!ff[n])
  10     ff[n] = n*f(n-1);
  11   return ff[n];
  12 }
  13
  14 // Kombinacni cislo
  15 int c(int n, int k)
  16 {
  17   if (k > n/2)
  18     k = n-k;
  19   long long int r = 1;
  20   for (int i=1; i<=k; i++)
  21     {
  22       r *= n--;
  23       r /= i;
  24     }
  25   return r;
  26 }
  27
  28 // Satnarka
  29 int s(int d)
  30 {
  31   int r = 0;
  32   int sg = 1;
  33   for (int k=0; k<=d; k++)
  34     {
  35       r += sg*f(d)/f(k);
  36       sg = -sg;
  37     }
  38   return r;
  39 }
  40
  41 // Castecne restrikce
  42 int n0(int z, int d)
  43 {
  44   static int nn[MAX][MAX];
  45   if (!nn[z][d])
  46     {
  47       if (!z)
  48         nn[z][d] = f(d);
  49       else if (z == d)
  50         nn[z][d] = s(d);
  51       else
  52         nn[z][d] = z*n0(z-1,d-1) + (d-z)*n0(z,d-1);
  53     }
  54   return nn[z][d];
  55 }
  56
  57 // Vzorecek ze Stanleyho
  58 int s0(int z, int d)
  59 {
  60   int r = 0;
  61   int p = 1;
  62   for (int k=0; k<=z; k++)
  63     {
  64       r += p * f(d-k) * c(z,k);
  65       p = -p;
  66     }
  67   return r;
  68 }
  69
  70 // Satnarciny pomerny
  71 double alpha(int n)
  72 {
  73   double x = 1;
  74   int sg = -1;
  75   for (int i=1; i<=n; i++)
  76     {
  77       x += sg*(1. / f(i));
  78       sg = -sg;
  79     }
  80   return x;
  81 }
  82
  83 int main(void)
  84 {
  85   printf("Satnarka obema zpusoby:\n");
  86   for (int i=1; i<MAX; i++)
  87     printf("%d\t%d\t%f\n", i, s(i), f(i)*alpha(i));
  88   putchar('\n');
  89
  90   printf("n0(i-1,i) pomoci alpha(i) a s(i):\n");
  91   for (int i=2; i<MAX; i++)
  92     printf("%d\t%f\t%f\n", i, f(i-1) * (i*alpha(i-1) + alpha(i-2)), s(i)*(1+1./i));
  93   putchar('\n');
  94
  95   printf("Rekurence pro n0 dava:\n");
  96   for (int i=0; i<MAX; i++)
  97     printf("\t%d", i);
  98   putchar('\n');
  99   for (int i=0; i<MAX; i++)
 100     {
 101       printf("%d\t", i);
 102       for (int j=0; j<MAX; j++)
 103         {
 104           if (j >= i)
 105             printf("%d", n0(i, j));
 106           putchar('\t');
 107         }
 108       putchar('\n');
 109     }
 110   putchar('\n');
 111
 112   printf("Totez podle vzorecku ze Stanleyho:\n");
 113   for (int i=0; i<MAX; i++)
 114     {
 115       printf("%d\t", i);
 116       for (int j=0; j<MAX; j++)
 117         {
 118           if (j >= i)
 119             printf("%d", s0(i, j));
 120           putchar('\t');
 121         }
 122       putchar('\n');
 123     }
 124   putchar('\n');
 125
 126   printf("Rozdily:\n");
 127   for (int i=0; i<MAX; i++)
 128     {
 129       printf("%d\t", i);
 130       for (int j=0; j<MAX; j++)
 131         {
 132           if (j >= i && i > 0)
 133             printf("%d", n0(i-1,j)-n0(i,j));
 134           putchar('\t');
 135         }
 136       putchar('\n');
 137     }
 138
 139   printf("Pomery:\n");
 140   for (int i=0; i<MAX; i++)
 141     {
 142       printf("%d\t", i);
 143       for (int j=0; j<MAX; j++)
 144         {
 145           if (j >= i && i > 0)
 146             {
 147               double d = (double)n0(i-1,j)/(n0(i-1,j)-n0(i,j));
 148               printf("%2.4f", d);
 149             }
 150           putchar('\t');
 151         }
 152       putchar('\n');
 153     }
 154
 155   return 0;
 156 }