. . , #include, #define .
, , , C++.
.
. , , , .
, :
--
--
-- (Heap),
-- (stack).
:
-
-
-
, .
. , , .
:
point_function.cpp
function.cpp
function.h
- .
. , , #.
C++ :
#pragma, , ;
#include, ;
#if, #else, #elif, #endif, #ifdef, #ifndef, defined;
#define;
#undef
#include :
#include < > #include
, . .
# define . :
# define [ () ]
(). -, .
19.1
, . .
|
|
|
, : , .
, .
, , .
, .
S .
, - .
, , .
, , , - .
, . , .
.
:
1.
( ).
void Rec();
{S; if () Rec();};
2.
( ).
void Rec();
{if () Rec(); S;};
3. , ( , ).
void Rec();
{ S1;
if () Rec();
S2;}
() . 1950-53. ..
, , .
. - , - , .
.
. :1; 1; 2; 3; 5;
. :
int FibR(int n)
{
if ((n == 1) || (n == 2))
return 1;
else
return FibR(n - 1) + FibR(n - 2);
}
int f_nod(int x,y)
{ }
{
if (y>x) return f_nod(y,x);
else if (y<=0) return x;
else return f_nod(y,x mod y);
};
}
void Search_bin(int *a, int l, int r,int x)
int k,p,i,j;
{ k= (l+r) / 2;
if (a[k]==x) return k;
else
{ if (a[k] <=x)
l=k+1;
else r=k-1;
return Search_bin (a,l,r,x); }}
|
|
|
{ }
int mmax (int *a, int i,int n)
{
if (i==n) mmax=a[i];
else
if ((a[i]> mmax(a,i+1) && (i==n))
mmax=a[i];
else mmax= mmax(a,i+1,n);
}
, (Longest Common Subsequence, LCS) ( ).
:
int lcs_length(char * A, char * B)
{
if (*A == '\0' || *B == '\0') return 0;
else if (*A == *B)
return 1 + lcs_length(A+1, B+1);
else
return
max(lcs_length(A+1,B), lcs_length(A,B+1));
}
char* getLongComSub(char *a, char *b)
{
char **max_len,*res;
max_len= (char **) malloc(strlen (a) + 1);
res= (char *) malloc(strlen (b) + 1);
for(int i = 0; i <= strlen (a); i++)
max_len[i]= (char *) malloc(strlen (b) + 1);
for(i = strlen (a)- 1; i >= 0; i--)
{
for(int j = strlen (b) - 1; j >= 0; j--)
{ if(a[i] == b[j])
{
max_len[i][j] = 1 + max_len[i+1][j+1];
}
else
{max_len[i][j] = max(max_len[i+1][j], max_len[i][j+1]);
}
}
}
k++;
i++;
j++;
//
int j,k=0;
for(i = 0, j = 0; max_len[i][j]!= 0;)
{
if(a[i] == b[j])
{
res[k]=a[i];
res[k+1]='\0';
k++; i++; j++;
}
else
{ if(max_len[i][j] == max_len[i+1][j])
i++;
else j++; } }
return res;
}
//
#include <stdlib.h>
#include <string.h>
void insert(int c,char *A,int n)
{
int i=0;
int len=strlen(A);
int t=len;
while(t>=n)
{
A[1+t]=A[t];
--t;
}
A[n]=c;
}
void pal(char *st, int l,int r)
{
int t,i;char ch;
if (l>=r)
return;
else
if (st[l]==st[r])
pal(st,l+1,r-1);
else
//
if (st[l]==st[r-1])
{
ch=st[r];
insert(ch,st,l);
proc(st,l+2,r-1);
}
else
{
ch=st[l];
insert(ch,st,r+1);
proc(st,l+1,r);
} }
void main ()
{
char x[100]="12345";
proc(x, 0,5);
puts (x);
}
N . K. , . S(i) , i. , j 1 i S(j). S(i+1), . , i+1 i, i-1,...,i-k. , S(i+1)=S(i)+S(i-1)+...+S(i-k). , S(1), S(2),..., S(N) , S(N), , N.
A(1),...,A(n), - B(1),..,B(m). , , , .
S.
S:=0;
i:=1;
(i<=N) (C[i]<=S+1)
S:=S+C[i];
i:=i+1
S , , . P=A[1]+...+A[N]-S.
n , 1-, k- . ?
, :
=2:
J(n) = 1,
J(n) = 2J(n/2) - 1, n ,
J(n) = 2J((n - 1)/2) + 1, n .
:
|
|
|
struct people{int number; people *next;};
void Step(people *&top, int k)
{
k--;
for (k; k>1; top=top->next, k--);
people *temp=top->next;
top->next=top->next->next;
top=top->next;
delete temp;
}
//
void main()
{
setlocale(LC_ALL,".1251"); int n, k;
cout<<" ?\n";
cin>>n;
cout<<" ?\n";
cin>>k;
if (k==1)
{
cout<<" "<<n<<endl; return;
}
people *top=new people;
top->number=1;
people *last=top;
for (int i=2; i<=n; i++)
{
people *p=new people;
p->number=i;
last->next=p;
last=p;
}
last->next=top;
for (int i=1; i<n; i++)
Step(top, k);
cout<<" "<<top->number<<endl;
delete top;
}
m 0 m -1, pj cj (j = 0,1,, m -1). , , P , .
, ?
:
, Cmax. ( ), , . Cgreedy , , Cmax Cgreedy, . . k , O (2k). , - , O (kW). . R(s, n) , n, s k. R(s, n). s = 0, R(0, n) = 0 n ( , 0). n = 0, R(s, 0) = 0 s ( s , 0).
//
C : 1,..., s , n. : s s . s n, 1,..., s - 1, , A (s, n) = A (s - 1, n). s, n - w s, s p s. , A (s, n) = A (s - 1, n - w s) + p s. <= n, 1,..., s :
A (s, n) = max (A (s - 1, n),
A (s - 1, n - w s) + p s.
A, B, C. A N , , , . .
H A C, B, , , C , A .
.
|
|
|
void Move(int n, char x,y,z);
// - y - z - C
{ if (n==1) scanf( 1 %d -> %d,x,y);
else
if (n>1)
{
Move(n-1,x,z,y);
printf( %2d %d ->%d,n,x,y);
Move(n-1,z,y,x);
}
1962 . . , , , ( ) , . , . , .. . O(n*logn) . ( , ) O(n2)
void qsort(int a[], int l, int r)
{
int i = l, j = r, p;
int x = a[(l + r)/2];
while (i <= j)
{
while (a[i] < x)
++i;
while (x < a[j])
--j;
if (i <= j)
{ p = a[i]; a[i] = a[j]; a[j] = p; i++; j--; }
}
if (l < j)
qsort(a, l, j);
if (i < r)
qsort(a, i, r);
}
A=(ai), i=1..n, .
void rec_sort(int *a, int i, int n) //
{ if (i < n)
{ int max_el = a[i], max_ind = i;
for (int j = i; j < n; ++j)
if (a[j] > max_el)
{ max_el = a[j]; max_ind = j;}
if (max_ind > i)
{ a[i] ^= a[max_ind]; a[max_ind] ^= a[i]; a[i] ^= a[max_ind];}
rec_sort(a, i+1, n);
}}
: k- ,
k-
n k Cnk ,
k- , , . , , , k- n- ( , n < 10). . , (n k + 1)- . , , k 1 , , . . , .
