Коллекция алгоритмов, в помощь начинающим Опции

[Ахинея]

Выложенные здесь алгоритмы преследуют исключительно учебные цели.
Код неоптимизирован, местами морально устарел и показывает только принцип решения той или иной задачи. Однако он вполне рабочий и может быть использован с соответствующей дорботкой под Ваши собственные нужды.

Буду рада, если не только я буду их пополнять)


Содержание:
Перевод из ... в ...
Сортировка массивов
Графика
Матрицы
Специальные функции
Методы поиска
Решение систем линейных уравнений
Решение нелинейных уравнений
Решение диф. уравнений

Будет еще дополнено.

Спасибо

[Ахинея]

Решение нелинейных уравнений

Метод хорд

» Кликните сюда для просмотра оффтоп текста.. «

Код

//////////////////////////////////////////////////////////////////////////////
//  Solving nonlinear equations (chords method)
//  (c) Johna Smith, 1996
//
//  Method description:
//    given: f(x)=0, [a;b], f(a)*f(b)<0
//    find x0: f(x0)=0
//    We approximate curve by chord between its borders and get
//    point where the chord crosses X axe as a new border of
//    interval with the root. When interval becomes small enough
//    we can take one of its borders as a solution.
//
//////////////////////////////////////////////////////////////////////////////

#include <stdio.h>
#include <math.h>

// this function returns value of f(x)
double f(double x)
{
// sin 2x - ln x = 0
return sin(2*x)-log(x);
}

double Solve(double a, double b, double epsilon)
{
double u,v,x,y;

u=f(a); v=f(b);
do
{
   // x - new border
   x=(a*v-b*u)/(v-u);
   y=f(x);
   // determine whether x is left or right border
   // f(a)*f(b)<0 condition must be true
   if (y*u<0)
   {
     b=x;
     v=y;
   } else
   {
     a=x;
     u=y;
   }
} while (b-a>epsilon);
return x;
}

void main(void)
{
printf("sin 2x - ln x = 0, [a;b]=[1.3;1.5]");
printf("\nx0=%f",Solve(1.3,1.5,1e-9));
}

Метод дихотомии

» Кликните сюда для просмотра оффтоп текста.. «

Код

//////////////////////////////////////////////////////////////////////////////
//  Solving nonlinear equations (dichotomia method)
//  (c) Johna Smith, 1996
//
//  Method description:
//    given: f(x)=0, [a;b], f(a)*f(b)<0
//    find x0: f(x0)=0
//    We split interval into two parts and select that part that
//    contains root of the equation by checking condition
//    f(a)*f(b)<0 We take middle point of the interval as a new border of
//    interval with the root. When interval becomes small enough
//    we can take one of its borders as a solution.
//
//////////////////////////////////////////////////////////////////////////////

#include <stdio.h>
#include <math.h>

// this function returns value of f(x)
double f(double x)
{
// sin 2x - ln x = 0
return sin(2*x)-log(x);
}

double Solve(double a, double b, double epsilon)
{
double x;

do
{
   // x - new border
   x=(b+a)/2;
   // determine whether x is left or right border
   // f(a)*f(b)<0 condition must be true
   if (f(x)*f(a)<0) b=x;
   else a=x;
} while (b-a>epsilon);
return x;
}

void main(void)
{
printf("sin 2x - ln x = 0, [a;b]=[1.3;1.5]");
printf("\nx0=%f",Solve(1.3,1.5,1e-9));

Метод Эйткена-Стеффенсона

» Кликните сюда для просмотра оффтоп текста.. «

Код

//////////////////////////////////////////////////////////////////////////////
//  Solving nonlinear equations (Eitken-Steffenson method)
//  (c) Johna Smith, 1996
//
//  Method description:
//    This method is used for solving equations like x=f(x)
//    (see also iterations method)
//    Here we use the following iterations:
//     x(n+1)=(x0*x2-x1^2)/(x0-2x1+x2)
//
//////////////////////////////////////////////////////////////////////////////

#include <stdio.h>
#include <math.h>


// this function returns value of f(x)
double f(double x)
{
// x = x + 0.37(sin 2x - ln x)
return x+0.37*(sin(2*x)-log(x));
}

double Solve(double x, double epsilon)
{
double x1,x2,xold,tmp;

do
{
   xold=x;
   x1=f(x);
   x2=f(x1);
   tmp=x-2*x1+x2;
   x=(x*x2-x1*x1)/tmp;
} while (fabs(xold-x)>epsilon && tmp!=0);

return x;
}

void main(void)
{
printf("sin 2x - ln x = 0, [a;b]=[1.3;1.5]");
printf("\nx0=%f",Solve(1.4,1e-6));
}

Метод итераций

» Кликните сюда для просмотра оффтоп текста.. «

Код

//////////////////////////////////////////////////////////////////////////////
//  Solving nonlinear equations (iterations method)
//  (c) Johna Smith, 1996
//
//  Method description:
//    This method is used for solving equations like x=f(x)
//    We should set first approximation of the root and then
//    make some iterations x=f(x). When the difference between
//    two consequental iterations will be less than epsilon we
//    can say that we found the root.
//    To apply this method to equations like F(x)=0 we should
//    transform it into iterational form x=f(x), where f(x):
//      1) defined on [a;b]
//      2) for every point on [a;b] exists f'(x)
//      3) for every x from [a;b] f(x) is in [a;b]
//      4) exists number q : |f'(x)|<=q<1 for all x from [a;b]
//
//////////////////////////////////////////////////////////////////////////////

#include <stdio.h>
#include <math.h>

// this function returns value of f(x)
double f(double x)
{
// x = x + 0.37(sin 2x - ln x)
return x+0.37*(sin(2*x)-log(x));
}

double Solve(double x, double epsilon)
{
double x1;

do
{
   x1=x;
   x=f(x);
} while (fabs(x1-x)>epsilon);

return x;
}

void main(void)
{
printf("sin 2x - ln x = 0");
printf("\nx0=%f",Solve(1.4,1e-6));
}

Метод Ньютона

» Кликните сюда для просмотра оффтоп текста.. «

Код

//////////////////////////////////////////////////////////////////////////////
//  Solving nonlinear equations (Newton method)
//  (c) Johna Smith, 1996
//
//  Method description:
//    Here we use the following iterations:
//     x(n+1)=xn-f(xn)/f'(xn)
//
//////////////////////////////////////////////////////////////////////////////

#include <stdio.h>
#include <math.h>


// this function returns value of f(x)
double f(double x)
{
// sin 2x - ln x = 0
return sin(2*x)-log(x);
}

double Solve(double x, double epsilon)
{
double x1;

do
{
   x1=x;
   x=x-f(x)*epsilon/(f(x+epsilon)-f(x));
} while (fabs(x1-x)>epsilon);

return x;
}

void main(void)
{
printf("sin 2x - ln x = 0, [a;b]=[1.3;1.5]");
printf("\nx0=%f",Solve(1.4,1e-9));
}

Метод Лобачевского

» Кликните сюда для просмотра оффтоп текста.. «

Код

//////////////////////////////////////////////////////////////////////////////
//  Solving nonlinear equations (Lobachevsky method)
//  (c) Johna Smith, 1996
//
//  Method description:
//   Given: a0+a1x+a2x^2+...+anx^n=0
//   This method allows to find modulus of the greatest root of this equation
//   even if it's complex. But in last case there can appear several messages
//   about impossibilty of calculation root of negative number.
//   The main idea of this method is to change given equation to other
//   equation which roots equals to powered roots of given equation. For example
//   if roots of the given equation are x0,x1,.. xn then roots of new equation
//   will be x0^2, x1^2, ..., xn^2. Repeating this operation we get an equation
//   where one root is much greater than other ones. So we can easily
//   obtain modulus of the greatrest root of the given equation.
//   To obtain other roots of equation we need to divide given equation
//   by (x-x0) (where x0 is found root) and apply this method to result.
//
//////////////////////////////////////////////////////////////////////////////

#include <stdio.h>
#include <math.h>

#define N   4
#define N1  N+1
#define Iterations  15  // number of iterations

double a[N1]={24,-50,35,-10,1};

void main(void)
{
double r,b[N1],c[N1],g,bi,d;
int z,k;

// printing given equation
printf("%f",a[0]);
for(int i=1;i<N1;i++) printf("%+fx^%d",a[i],i);
printf("=0\n\n");

// preparing auxiliary arrays b and c
for (i=0;i<N1;i++)
{
   b[i]=a[i]/a[N];
   c[i]=0;
}

// setting required parameters
r=1/2.0;
g=1;

// make all iterations
for(int y=0;y<Iterations;y++)
{
   // calculate coefficients c[i] (coefficients of new equation)
   z=1;
   for(i=0;i<N1;i++)
   {
     bi=z*b[i];
     k=(i+1)/2;
     for(int j=i%2;j<N1;j+=2)
     {
       c[k]+=bi*b[j];
       k++;
     }
     z=-z;
   }
   d=z*c[N-1];
   // check whether we could calculate root of d
   if(d>0)
   {
     // calculating and printing new iteration
     g*=powl(d,r);
     printf("%f\n",g);
     for (i=0;i<N1;i++)
     {
       // preparing data for next iteration
       b[i]=c[i]/powl(d,N-i);
       c[i]=0;
     }
     b[N-1]=z;
     b[N]=-z;
   } else
   {
     // d is negative - can't calculate root
     for(i=0;i<N1;i++)
     {
       // preparing data for next iteration
       b[i]=c[i];
       c[i]=0;
     }
     printf("no iteration (can't calculate root from negative number)\n");
   }
   r/=2.0;
}
}