, - , ( ).
.
) : - X, f(X);
) : - , - ;
) : - , - ;
) : - - , - (, , , . .).
, , . 50 % .
:
1. ( );
2. - ( );
3. ;
4. ;
5. ;
6. (, ) , .
: () ( ), ( ) ( ). , . .
() , ( ). . .
5.1. . : . .
:
: to be or not to be
:
-
be 2
not 1
or 1
to 2
, , - . . , , , . : , , , .
(. 5.1). . () .
| t | kol | ||||
| To | |||||
| dt = 3 | Be | ||||
| │ | Or | ||||
| └ → 3 | Not | ||||
| ... | |||||
| DTMAX | |||||
| . 5.1. c ( not : to be or not to be) |
. , :
|
|
|
t;
, :
/* t */.
, . .
5.1.
#include <stdio.h>
void main ()
{ 1. ;
2. ;
3. ;
4. ;
}
------------------------------------------------------------------------------------------------
:
#define DTMAX 1001 /* x - + 1 ( ) */
#define DSLMAX 21 /* + 1 ('\0') */
/* : t,kol,dt */
/* ( t, kol) */
char t[DTMAX][DSLMAX]; /* */
int kol[DTMAX]; /* */
int dt; /* ( ) */
------------------------------------------------------------------------------------------------
dt = 0; /* 1. */
------------------------------------------------------------------------------------------------
int sim; /* */
char sl[DSLMAX]; /* */
/* 2. */
sim = getchar(); /* 1- */
while (sim!= EOF)
{ sl ( 1- );
;
}
------------------------------------------------------------------------------------------------
int j; /* */
/* sl ( 1- ) */
for (j=0; sim!=' ' && sim!=',' && sim!='.' && sim!='\n'
&& sim!=EOF; sim=getchar())
if (j < DSLMAX-1) sl[j++] = sim;
sl[j] = '\0'; /* */
/* */
while (sim==' ' || sim==',' || sim=='.' || sim=='\n')
sim = getchar();
------------------------------------------------------------------------------------------------
int i; /* */
/* */
/* sl t */
strcpy (t[dt], sl); /* == sl */
for (i=0; strcmp(sl,t[i]); i++);
if (i < dt) /* t[i] == sl */
kol[i]++; /* sl */
else /* */
/* sl */
if (dt < DTMAX-1) /* */
kol[dt++] = 1;
else /* */
{ fprintf (stderr,
"\n: %d"
"\n '%s' \n", DTMAX-1, sl);
}
, , " " - , . - .
|
|
|
---------------------------------------------------------------------------------------------------
int L; /* */
/* 3. */
for (L=dt-1; L>0; L--)
/* t[0]...t[l] */
for (i=0; i<L; i++)
/* t[i] t[i+1] */
if (strcmp(t[i],t[i+1]) > 0)
{ /* t[i] <--> t[i+1] */
strcpy (sl, t[i]); strcpy (t[i], t[i+1]); strcpy (t[i+1], sl);
/* kol[i] <--> kol[i+1] */
j = kol[i]; kol[i] = kol[i+1]; kol[i+1] = j;
}
------------------------------------------------------------------------------------------------
/* 4. () */
printf ("\n%*s%s", DSLMAX, " ", "-\n");
for (i=0; i<dt; i++)
printf ("%-*s %5d\n", DSLMAX, t[i], kol[i]);
5.2. ( 5.1). , .
, 5.1. ( !) . 5.2:
5.2. .
#include <stdio.h>
#include <stdlib.h>
void main ()
{
1. ;
2. ;
3. ;
}
5.1. . . 5.2 .
sled kol sl
pt
baryer
DSLMAX
. 5.2.
( not : to be or not to be)
. , - ( ).
, 5.1. ( ).
, , ! sl, !
, , , , , , .
, (sled kol), - sl ( ).
:
struct el_tab /* () */
{ struct el_tab *sled; /* */
int kol; /* */
char sl[]; /* */
};
struct el_tab *pt; /* */
struct el_tab *baryer; /* */
char *sl; /* ( ) */
----------------------------------------------------------------------------------------------------
.
/* 1. */
baryer = malloc (sizeof(struct el_tab)
+ DSLMAX); /* '\0' */
sl = baryer->sl;
|
|
|
pt = malloc (sizeof(struct el_tab));
pt->sled = baryer; /* */
----------------------------------------------------------------------------------------------------
struct el_tab *i, /* */
ipr; / * */
/* */
/* sl */
i = pt->sled; ipr = pt;
while (strcmp(sl,i->sl) > 0)
{ ipr=i; i = i->sled; /* */
}
if (i!=baryer && strcmp(sl,i->sl)==0) /* i->sl==sl */
i->kol ++; /* sl */
else /* */
{ /* sl */
i = malloc (sizeof(struct el_tab)
+ strlen(sl)+1); /* sl '\0' */
if (i!= NULL) /* */
{ /* */
strcpy (i->sl, sl); /* sl - */
i->kol = 1;
/* *ipr */
i->sled = ipr->sled; ipr->sled = i;
}
else /* */
{ fprintf (stderr,
"\n: , "
" '%s' \n", sl);
}
}
----------------------------------------------------------------------------------------------------
/* 3. */
printf ("\n%*s%s", DSLMAX, " ", "-\n");
i = pt->sled; /* 1- */
while (i!= baryer) /* */
{ printf ("%-*s %5d\n", DSLMAX, i->sl, i->kol);
i = i->sled; /* */
}
- , .
D - . D - D1=1, D2=2,..., Dm=m, m - .
, ( ) X X1,..., Xm
m
X = å Xi*Pi (5.1)
i=1
Pi - , X = Xi;
m
å Pi = P1 +... + Pm = 1 (5.2)
i=1
(5.1)
m m
D = å Di * Pi = å i * Pi = P1 + 2*P2 + 3*P3 +... + m*Pm (5.3)
i=1 i=1
Pi - , D=i, .. i (i=1..m-1); Pm - , m, , ( m ).
, (), , (5.2)
P1 = P2 =... = Pm-1 = Pm/2 = 1/(m+1)
(5.3) ,
D = (1/(m+1))*(1+2+...+m) = (1/(m+1))*m*(m+1)/2 = m/2
.. - :
D = m/2 (5.4)
(5.3) , , ( , ),
P1 ≥ P2 ≥... ≥ Pm.
( )
(, ) , . , : . , m
|
|
|
Dmax = log2 m + 1 (5.5)
5.3. kl t (t[i-1] £ t[i] i=1,..., m-1)
L = 0; R = m; /* */
while (L < R)
{ /* (t[k] < kl k=0,..., L) && (t[k] >= kl k = R,..., m-1) */
i = (L+R) / 2; if (t[i] < kl) L = i+1; else R = i;
}
if (R < m && t[R] == kl)... /* */
5.3:
) :
(t[k]<kl k=0,..., L) && (t[k]>=kl k=R,..., m-1)
) , R - L , . .: L<R; L £ i < R; L i+1, R i. L = R .
) R=m - (. . t[m] !), t[R], .
5.3. kl t (t[i-1] £ t[i] i=1,..., m-1) L, R, j (, 5.3)
L = &t[0]; R = &t[m]; /* */
while (L < R)
{ j = L + (R - L) / 2; /* : j=(L+R)/2 */
if (*j < kl) L = j + 1; else R = j;
}
if (R < &t[m] && *R == kl)... /* */
. , . C , .
, , . , , .
( ) , ; (. 5.3). ( ).
| ) : 7, 8, 4, 9, 2, 6, 5 | ) |
| kl | men | bol | |
| ... | |||
| -1 | |||
| -1 | -1 | ||
| -1 | -1 | ||
| -1 | |||
| -1 | -1 | ||
| ... |
 )
|
. 5.3.
 |
. , . : , . ( ), . , -1 (. 5.3).
. : (. 5.4). (. 5.4, 5.5).
5.4. t b
/* */
struct el_tab /* */
{ _ kl; /* */
_ inf; /* */
struct el_tab *men, *bol; / * */
};
struct el_tab *t; /* */
struct el_tab *b; /* */
...
/* */
/* */
b = malloc (sizeof(struct el_tab)); t = b; /* "" */
5.5.
{kl, inf} t b
_ kl; /* */
_ inf; /* */
struct el_tab *i, *ip; /* - - - */
...
/* kl t */
b->kl = kl; /* = kl */
for (i = t; kl!= i->kl;)
{ ip = i;
if (kl < i -> kl) i = i-> men;
else i = i-> bol;
|
|
|
}
if (i == b) /* ( ) */
{ /* kl t */
i = malloc (sizeof (struct el_tab));
if (i == NULL)... /* */
else /* */
{ i->kl=kl; i->inf=inf; /* */
i->men = i->bol = b; /* "" */
/* */
if (t == b) /* */
t = i; /* - */
else /* *ip */
if (kl < ip->kl) ip -> men = i; else ip->bol = i;
}
}
else ... /* i->kl == kl */
5.6. t b ( )
void pech_tab (struct el_tab *t)
{ if (t!= b) /* b - "" */
{ pech_tab (t -> men);
t->kl, t -> inf;
pech_tab (t -> bol);
}
}
. 1. , b - NULL.
2. 0.
. 5.5. , , , 6, . ( ).
, , 7. , , ( ) , . . 5.7 - ( 6) .
 | |||
. 5.5. 7
) ; ) ; "", "" -
( ).
5.7. b
struct el_tab **i, /* - */
*u, /* */
**r; /* - - */
...
u = *i; /* */
if (u->men == b) *i = u->bol; /* */
else if (u->bol == b) *i = u->men; /* */
else /* */
{ /* */
r=&(u->men); u=u->men;
while (u->bol!= b) { r=&(u->bol); u=u->bol; }
/* */
(*i)->kl=u->kl; (*i)->inf=u->inf;
*r=u->men; /* C */
}
free (u); /* *u */
, . , , , :
D = m / 2, (m - ).
( ) :
D = 1.39 log2 m (5.6)
(). : (. 5.6).
( ) , (. 5.5). , :
D max = log2 m + 1 (5.7)
.. - .. : (-) - , 1 (. 5.5 ). -. - , 44% :
Dmax = 1.44 log2 m (5.8)
 | |||
 | |||
. 5.6.
) ) (-)
