#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <conio.h>
#include <string.h>
void move(int i, int j, int d)
{
int m;
for(m = 0; m < d; m++) printf(" ");
printf("(%d,%d)\n", i, j);
}
void hanoy(int i, int j, int k, int d)
{
//
//int m;
//for (m = 0; m < d; m++) printf(" ");
//printf("hanoy(%d,%d,%d)\n", i, j, k);
if (k == 1)
move(i, j, d);
else
{
hanoy(i, 6-i-j, k-1, d+1);
hanoy(i, j, 1, d+1);
hanoy(6-i-j, j, k-1, d+1);
}
}
int main()
{
int n = 4;
printf(" : ");
scanf("%d",&n);
printf("\n %d :\n", n);
hanoy(1, 3, n, 0);
getch();
// system ("pause");
}
: 4
4 :
(1,2)
(1,3)
(2,3)
(1,2)
(3,1)
(3,2)
(1,2)
(1,3)
(2,3)
(2,1)
(3,1)
(2,3)
(1,2)
(1,3)
(2,3)
13. -. .
:
x3+a*x2+b*x+c=0.
, , :
Q = (a2-3b)/9
R = (2a3-9ab+27c)/54.
, R2 < Q3, , ():
= acos(R/sqrt(Q3))/3,
x1 = -2*sqrt(Q)cos(t)-a/3,
x2 = -2*sqrt(Q)cos(t+(2*pi/3))-a/3,
x3 = -2*sqrt(Q)cos(t-(2*pi/3))-a/3.
, R2 >= Q3, ( ) ( ). , -. ( ):
A = -sign(R)[|R|+sqrt(R2-Q3)]1/3,
B = Q/A A!= 0 B = 0 A = 0.
:
x1 = (A+B)-a/3.
- :
x2,3 = -(A+B)/2-a/3 + i*sqrt(3)*(A-B)/2
, A = B, - :
x2=-A-a/3.
, , , ( -).
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <conio.h>
#include <string.h>
#define M_PI (3.141592653589793)
#define M_2PI (2.*M_PI)
|
|
|
/*
int Cubic(double *x,double a,double b,double c);
:
a, b, c -
x - (size 3).
:
3 -> x ;
1 + 2 -> x[0] - , x[1] , x[2] - .
:
1 - 1 + 2 ;
2 - 1 + , 0 (.. 2 ).
3 - 3 ;
*/
int Cubic (double *x, double a, double b, double c)
{
double q, r, r2, q3;
q = (a * a - 3. * b) / 9.;
r = (a * (2. * a * a - 9. * b) + 27.*c) / 54.;
r2 = r * r;
q3 = q * q * q;
if (r2 < q3)
{
double t = acos(r / sqrt (q3));
a /= 3.;
q = -2. * sqrt (q);
x[0] = q * cos (t / 3.) - a;
x[1] = q * cos ((t + M_2PI) / 3.) - a;
x[2] = q * cos ((t - M_2PI) / 3.) - a;
return (3);
}
else
{
double aa, bb;
if (r <= 0.) r =- r;
aa = -pow (r + sqrt (r2 - q3), 1. / 3.);
if(aa!= 0.) bb = q / aa;
else bb = 0.;
a /= 3.;
q = aa + bb;
r = aa - bb;
x[0] = q - a;
x[1] = (-0.5) * q - a;
x[2] = (sqrt (3.) * 0.5) * fabs (r);
if (x[2] == 0.) return (2);
return (1);
}
}
14. (- (LU) ).
- , -, .
A A=L*U, L - , U - , , . , -, .
LU- , "" -. , A, ; U ; L , L 1 ( ) .
:
1. Lii=1 i=0,...,N-1 ( , ;
2. j=0,1,...,N-1 :
1. i=0,...,j Uij:
Uij=Aij - SUM(0<=k<i)(Lik*Uik) ( i=0 );
2. i=j+1,...,N-1 :
Lij = Aij - SUM(0<=k<j)(Lik*Uik))/Uii
j.
j .2 . .2 j , , j, j. , . .
|
|
|
, - ( ), - . , .
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <conio.h>
#include <string.h>
#define TINY 1.e-30
/*
LU- .
:
int LU_decompos(double **a,int n,int *indx,int *d,double *vv);
:
a - (n x n) ;
n - ;
indx - ( n) ;
d - , +1 -1 .
vv - (size n).
:
0 - ( ),
1 - .
, LU- .
:
void LU_backsub(double **a,int n,int *indx,double *b);
:
a - , ;
n - ;
indx - , ;
b - ( n).
: a indx .
LU- .
:
void LU_invert(double **a,int n,int *indx,double **inv,double *col);
:
a - , ;
n - ;
indx - , ;
inv - ;
col - ( n).
, LU-
:
double LU_determ(double **a,int n,int *indx,int *d);
:
a - , ;
n - ;
indx - , ;
d - (+1 -1) .
: .
*/
/* */
int LU_decompos (double **a, int n, int *indx, int *d, double *vv)
{
register int i, imax, j, k;
double big, sum, temp;
for (i = 0; i < n; i++)
{
big = 0.;
for (j = 0; j < n; j++)
if ((temp = fabs (a[i][j])) > big) big = temp;
if (big == 0.) return (0);
vv[i] = big;
}
/* */
for (j = 0; j < n; j++)
{ /* a) , i==j */
for (i = 0; i < j; i++)
{
sum = a[i][j];
for (k = 0; k < i; k++) sum -= a[i][k] * a[k][j];
a[i][j] = sum;
}
/* */
big = 0.;
imax = j;
for (i = j; i < n; i++)
{
sum = a[i][j];
for (k = 0; k < j; k++) sum -= a[i][k] * a[k][j];
a[i][j] = sum;
if ((temp = vv[i] * fabs (sum)) >= big)
{
big = temp;
imax = i;
}
}
/* , , */
if (imax!= j)
{
for (k = 0; k < n; k++)
{
temp = a[imax][k];
a[imax][k] = a[j][k];
a[j][k] = temp;
}
*d =- (*d);
vv[imax] = vv[j];
}
/* */
indx[j] = imax;
if (a[j][j] == 0.) a[j][j] = TINY;
if (j < n - 1)
{
temp = 1. / a[j][j];
for (i = j+1; i < n; i++) a[i][j] *= temp;
}
}
return (1);
}
/* */
void LU_backsub (double **a, int n, int *indx, double *b)
{
register int i, j, ip, ii = -1;
double sum;
/* */
for (i = 0; i < n; i++)
{
ip = indx[i];
sum = b[ip];
b[ip] = b[i];
if (ii >= 0)
for (j = ii; j < i; j++) sum -= a[i][j] * b[j];
else if (sum) ii = i; /* */
|
|
|
b[i] = sum;
}
/* */
for (i = n - 1; i >= 0; i--)
{
sum = b[i];
for (j = i + 1; j < n; j++) sum -= a[i][j] * b[j];
b[i] = sum / a[i][i];
}
}
/* */
void LU_invert (double **a, int n, int *indx, double **inv, double *col)
{
register int i, j;
for (j = 0; j < n; j++)
{
for (i = 0; i < n; i++) col[i] = 0.;
col[j] = 1.;
LU_backsub (a, n, indx, col);
for (i = 0; i < n; i++) inv[i][j] = col[i];
}
}
/* */
double LU_determ (double **a, int n, int *indx, int *d)
{
register int j;
double res = (double)(*d);
for (j = 0; j < n; j++) res *= a[j][j];
return (res);
}
15. .
, . . , f(x) [a,b], f(a) f(b) . , f(x), - . [a,b] .
, ( ). , . , .
, .
1. x0, f0=f(x0), D d>1.
2. a=x0-D, b=x0+D; fa=f(a), fb=f(b).
3. : D=D*d. , .
3.a. fa f0 , [a,x0] -> .
3.b. fb f0 , [x0,b] -> .
3.c. f0 > 0 ( ) :
4. , fa fb . , 4a ( ), fb - 4b, - 4c.
4.a. a=a-D, b=b+D, fa=f(a), fb=f(b), 3.
4.b. a=x0, x0=b, fa=f0, f0=fb; b=b+D, fb=f(b), 3.
4.c. 4b, - .
, . :
1. , ;
2. , , , .
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <conio.h>
#include <string.h>
/*
, .
int BracketRoot (double x0, double *a, double *b, double d0, double di, double dmax, double (*fun)(double));
|
|
|
:
x0 - ;
a - ;
b - ;
d0 - ;
di - ( );
dmax - ;
fun - .
:
1 - ;
0 -
*/
int BracketRoot (double x0, double *a, double *b, double d0,
double di, double dmax, double (*fun)(double))
{
double fa, fb, f0;
f0 = (*fun)(x0);
*a = x0 - d0;
*b = x0 + d0;
fa = (*fun)(*a);
fb = (*fun)(*b);
while ((d0 *= di) < dmax)
{
if (f0 >= 0.)
{
if (fa < 0.)
{
*b = x0;
return (1);
}
if (fb < 0.)
{
*a = x0;
return (1);
}
if (fa > fb)
{
*a = x0;
x0 = (*b);
*b += d0;
fa = f0;
f0 = fb;
fb = (*fun)(*b);
}
else
if (fa < fb)
{
*b = x0;
x0 = (*a);
*a -= d0;
fb = f0;
f0 = fa;
fa = (*fun)(*a);
}
else
{
*a -= d0;
*b += d0;
fa = (*fun)(*a);
fb = (*fun)(*b);
}
}
else
if (f0 < 0.)
{
if (fa >= 0.)
{
*b = x0;
return (1);
}
else
if (fb >= 0.)
{
*a = x0;
return (1);
}
if (fa < fb)
{
*a = x0;
x0 = (*b);
*b += d0;
fa = f0;
f0 = fb;
fb = (*fun)(*b);
}
else
if (fa > fb)
{
*b = x0;
x0 = (*a);
*a -= d0;
fb = f0;
f0 = fa;
fa = (*fun)(*a);
}
else
{
*a -= d0;
*b += d0;
fa = (*fun)(*a);
fb = (*fun)(*b);
}
}
}
return (0);
}
16. ( ).
- , . n + 1 (x_0, y_0), (x_1, y_1) \ dots (x_n, y_n), xi , L(x) n, L(xi) = yi.
(n = 1) - , - , .
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <conio.h>
#include <string.h>
//
float x[6] = {1.5, 1.54, 1.56, 1.60, 1.63, 1.70};
float y[6] = {3.873, 3.924, 3.950, 4.00, 4.037, 4.123};
/* ,
x -
n - ( x-)
i -
*/
float L(float xp, int n, int i)
{
//
float Chesl;
float Znam;
Chesl = 1;
Znam = 1;
int k;
//
for (k = 0; k!= n; k++)
{
if (k == i) continue;
// x - x(i)
Chesl *= xp - x[k];
}
//
for (k= 0; k!= n; k++)
{
if (x[i] == x[k]) continue;
// ,
Znam *= x[i] - x[k];
}
return Chesl / Znam;
}
int main()
{
//
int n = sizeof(y) / sizeof(float);
//
float R = 0;
//
float px = 1.55;
// 3. 937075
for (int i = 0; i!= n; i++)
{
R += y[i] * L(px,n,i);
}
printf(": %f \n",R);
system ("pause");
}
: 3.937075
17. .
. - - . [0.5,2] ( [1,16]). -, .
, , . , , . , , , frexp() ldexp(). , -. , [0.5,1). , 2, [0.5,2). 1. ldexp() .
- 16, [1,16]. 1, . 2. 4 , .
|
|
|
a = Sqroot(x) ( ) : ai+1=0.5*(ai+x/ai), i - .
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <conio.h>
#include <string.h>
/* 4 */
#define ITNUM 4
/*
( ):
float Sqroot (float x);
(, -):
float Sqroot1 (float x);
(x<0.) 0 .
*/
/* / [0.5,1] */
float Sqroot (float x)
{
int expo, i;
float a, b;
if (x <= 0.F) return (0.F);
/* x [0.5,1) .
- . */
x = frexp (x, &expo);
/* : 2 , .
[0.5,2.) */
if (expo & 1)
{
x *= 2.F;
expo--;
}
/* */
a = 1.F;
for (i = ITNUM; i > 0; i--)
{
b = x / a;
a += b;
a *= 0.5F;
}
/* 2 .
ldexp() frexp. */
a = ldexp(a, expo / 2);
return (a);
}
/* . [1,16].
16 . */
float Sqroot1 (float x)
{
int sp = 0, i, inv = 0;
float a, b;
if (x <= 0.F) return (0.F);
/* 1: */
if (x < 1.F)
{
x = 1.F / x;
inv = 1;
}
/* 16 <16 */
while (x > 16.F)
{
sp++;
x /= 16.F;
}
/* */
a = 2.F;
/* */
for (i = ITNUM; i > 0; i--)
{
b = x / a;
a += b;
a *= 0.5F;
}
while (sp > 0)
{
sp--;
a *= 4.F;
}
/* */
if (inv) a = 1.F / a;
return (a);
}
int main()
{
float x;
printf (" : ");
scanf ("%f", &x);
printf ("\n : %f\n", Sqroot(x));
printf (" : %f\n", Sqroot1(x));
system ("pause");
}
: 35
: 5.916080
: 5.916080
