Форум программистов, компьютерный форум CyberForum.ru

Коллекция алгоритмов от Johna Smith - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Работа с графом (Требуется по заявке клиента предложить способы обмена жилплощади) http://www.cyberforum.ru/cpp-beginners/thread870941.html
В файле записаны предложения по обмену жилплощадью. Имеются варианты размена одной квартиры на две других либо на квартиру и комнату. Требуется по заявке клиента предложить способы обмена. Предусмотреть возможность нахождения обменов, в которых участвуют более двух сторон.
C++ Определить, является ли текст десятичной записью числа, кратного 9 Является ли текст записью десятичного числа,кратного 9 В заданный непустой текст входят только цифры и буквы. Определить. удовлетворяет ли он следующему свойству: 1) текст является десятичной записью числа, кратного 9; http://www.cyberforum.ru/cpp-beginners/thread870934.html
Удаление первых n элементов из vector C++
Почему, к примеру, если k=3 а pop=2, то студия выдаст ошибку(итератор вне допустимого диапазона) при запуске функции erase. По моей логике, необходимо было удалить первый элемент. #include <cstdio> #include <iostream> #include <vector> #define pb push_back #define ull unsigned long long using namespace std; vector<int> t;
Найти сумму квадратов элементов матрицы C++
Помогите пожалуйста!)
C++ Получить целочисленную матрицу http://www.cyberforum.ru/cpp-beginners/thread870928.html
Задание ниже: Nastik23, оформите тему в соответствии с правилами форума: текстовые задания набирайте от руки
C++ Считывание структур из файла #include <stdio.h> #include <string.h> #include <malloc.h> #define Lmax 20 struct student { struct { char name,surname,patronymic; } fio; подробнее

Показать сообщение отдельно
LK
Заблокирован
19.05.2013, 15:15  [ТС]     Коллекция алгоритмов от Johna Smith
Специальные функции

arccos x (x - real)
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//////////////////////////////////////////////////////////////////////////////
//
//  arccos x function calculating.
//  (c) Johna Smith, 1996
//
//  Method description:
//    Calculating arccos x using the following formula:
//                                        2n+1
//              Pi       N  1*3*5..(2n-1)x
//   arccos x = - - x - SUM ------------------ , |x|<1
//              2       n=1 2*4*6..(2n)(2n+1)
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
#define Pi      3.1415926536
#define N       30
double Arccos(double x)
{
  double arccos=x;
  double a=x;
  for (int i=1;i<N;i++)
  {
    a*=x*x*(2*i-1)*(2*i-1)/((2*i+1)*2*i);
    arccos+=a;
  }
  return Pi/2-arccos;
}
void main(void)
{
  printf("C++ arccos(0.5)=%g, this arccos(0.5)=%g.",acos(0.5),Arccos(0.5));
}

arccos z (z - complex)
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//////////////////////////////////////////////////////////////////////////////
//
//  Calculactin function arccos z, where z is a complex value
//  (c) Johna Smith, 1996
//
//  Method description:
//       1            2    2     1            2    2
//    A= - sqrt( (x+1)  + y  ) + - sqrt( (x-1)  + y  )
//       2                       2
//
//       1            2    2     1            2    2
//    B= - sqrt( (x+1)  + y  ) - - sqrt( (x-1)  + y  )
//       2                       2
//                                       2
//    arccos z = acrcos B - i*ln(a+sqrt(a  -1))
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
struct complex
{
  float re;
  float im;
};
void show_complex(complex c) // this functions displays complex value
{
  printf("%f%+fi",c.re,c.im);
}
complex Arccos(complex z)
{
  complex c;
  float A,B;
  A=sqrt((z.re+1)*(z.re+1)+z.im*z.im)/2 +
         sqrt((z.re-1)*(z.re-1)+z.im*z.im)/2;
  B=sqrt((z.re+1)*(z.re+1)+z.im*z.im)/2 -
         sqrt((z.re-1)*(z.re-1)+z.im*z.im)/2;
  c.re=acos(B);
  c.im=-log(A+sqrt(A*A-1));
  return c;
}
complex z={3,2};
void main(void)
{
  printf("Arccos(");
  show_complex(z);
  printf(") = ");
  show_complex(Arccos(z));
}

arch x
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//////////////////////////////////////////////////////////////////////////////
//
//  arcch x function calculating.
//  (c) Johna Smith, 1996
//
//  Method description:
//    Calculating arccos x using the following formula:
//
//                       N  1*3*5..(2n-1)       1
//   arcch x = ln(2x) - SUM --------------- * ------  , x>1
//                      n=1 2*4*6..(2n)(2n)   x^(2n)
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
#define N       30
double Arch(double x)
{
  double arch=1/(2*x*2*x);
  double a=1/(2*x*2*x);
  for (int i=2;i<N;i++)
  {
    a *= (2*i-1)*(2*i-2)/(2*i*2*i*x*x);
    arch += a;
  }
  return log(2*x)-arch;
}
void main(void)
{
  printf("C++ arch(6.13229)=2.5, this arccos(6.13229)=%g.",Arch(6.13229));
}

arch z
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//////////////////////////////////////////////////////////////////////////////
//
//  Calculactin function arccos z, where z is a complex value
//  (c) Johna Smith, 1996
//
//  Method description:
//       1            2    2     1            2    2
//    A= - sqrt( (x+1)  + y  ) + - sqrt( (x-1)  + y  )
//       2                       2
//
//       1            2    2     1            2    2
//    B= - sqrt( (x+1)  + y  ) - - sqrt( (x-1)  + y  )
//       2                       2
//                            2
//    arch z = +/- ln(a+sqrt(a  -1)) +/- i*acrcos B
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
struct complex
{
  float re;
  float im;
};
void show_complex(complex c) // this functions displays complex value
{
  printf("%f%+fi",c.re,c.im);
}
complex Arch(complex z)
{
  complex c;
  float A,B;
  A=sqrt((z.re+1)*(z.re+1)+z.im*z.im)/2 +
         sqrt((z.re-1)*(z.re-1)+z.im*z.im)/2;
  B=sqrt((z.re+1)*(z.re+1)+z.im*z.im)/2 -
         sqrt((z.re-1)*(z.re-1)+z.im*z.im)/2;
  c.re=log(A+sqrt(A*A-1));
  c.im=-acos(B);
  return c;
}
complex z={3,2};
void main(void)
{
  complex c;
  printf("Arch(");
  show_complex(z);
  c=Arch(z);
  printf(") = +/- %f +/-i%f",c.re,c.im);
}

arcsin x
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//////////////////////////////////////////////////////////////////////////////
//
//  arcsin x function calculating.
//  (c) Johna Smith, 1996
//
//  Method description:
//    Calculating arcsin x using the following formula:
//                                      2n+1
//                     N  1*3*5..(2n-1)x
//    arcsin x  = x + SUM ------------------, |x|<1
//                    n=1 2*4*6..(2n)(2n+1)
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
#define N       30
double Arcsin(double x)
{
  double arcsin=x;
  double a=x;
  for (int i=1;i<N;i++)
  {
    a *= x*x*(2*i-1)*(2*i-1)/((2*i+1)*2*i);
    arcsin += a;
  }
  return arcsin;
}
void main(void)
{
  printf("C++ arcsin(0.5)=%g, this arcsin(0.5)=%g.",asin(0.5),Arcsin(0.5));
}

arcsin z
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//////////////////////////////////////////////////////////////////////////////
//
//  Calculactin function arcsin z, where z is a complex value
//  (c) Johna Smith, 1996
//
//  Method description:
//       1            2    2     1            2    2
//    A= - sqrt( (x+1)  + y  ) + - sqrt( (x-1)  + y  )
//       2                       2
//
//       1            2    2     1            2    2
//    B= - sqrt( (x+1)  + y  ) - - sqrt( (x-1)  + y  )
//       2                       2
//                                       2
//    arcsin z = acrsin B + i*ln(a+sqrt(a  -1))
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
struct complex
{
  float re;
  float im;
};
void show_complex(complex c) // this functions displays complex value
{
  printf("%f%+fi",c.re,c.im);
}
complex Arcsin(complex z)
{
  complex c;
  float A,B;
  A=sqrt((z.re+1)*(z.re+1)+z.im*z.im)/2 +
  sqrt((z.re-1)*(z.re-1)+z.im*z.im)/2;
  B=sqrt((z.re+1)*(z.re+1)+z.im*z.im)/2 -
  sqrt((z.re-1)*(z.re-1)+z.im*z.im)/2;
  c.re=asin(B);
  c.im=log(A+sqrt(A*A-1));
  return c;
}
complex z={3,2};
void main(void)
{
  printf("Arcsin(");
  show_complex(z);
  printf(") = ");
  show_complex(Arcsin(z));
}

arctg x
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//////////////////////////////////////////////////////////////////////////////
//
//  arctg x function calculating.
//  (c) Johna Smith, 1996
//
//  Method description:
//    Calculating arctg x using the following formulas:
//                              2n+1
//                  N      n   x
//     arctg x  =  SUM (-1)  --------, |x|<1
//                 n=0         2n+1
//
//
//                  N      n+1       1
//     arctg x  =  SUM (-1)    --------------, |x|>1
//                 n=0         (2n+1)x^(2n+1)
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
#define N       100
#define Pi      3.1415926536
double Arctg(double x)
{
  double arctg;
  double a;
  if (fabs(x)<1)
  {
    a=x;
    arctg=x;
    for (int i=1;i<N;i++)
    {
       a *= -x*x;
       arctg += a/(2*i+1);
    }
  } 
  else
  {
    a=-1/x;
    arctg=-1/x;
    for (int i=1;i<N;i++)
    {
       a *= -1/(x*x);
       arctg += a/(2*i+1);
    }
    arctg += (x>0?Pi/2.0:-Pi/2.0);
  }
  return arctg;
}
void main(void)
{
  printf("C++ arctg(0.5)=%g, this arctg(0.5)=%g.",atan(0.5),Arctg(0.5));
}

arctg z
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//////////////////////////////////////////////////////////////////////////////
//
//  arctg z function calculating, where z is a complex value
//  (c) Johna Smith, 1996
//
//  Method description:
//
//                 1          2x          1    x^2+(y+1)^2
//     arctg z  =  - arctg(---------) + i - ln(-----------)
//                 2       1-x^2-y^2      4    x^2+(y-1)^2
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
struct complex
{
  float re;
  float im;
};
void show_complex(complex c) // this functions displays complex value
{
  printf("%f%+fi",c.re,c.im);
}
complex Arctg(complex z)
{
  complex c;
  
  c.re=atan(2*z.re/(1-z.re*z.re-z.im*z.im))/2;
  c.im=log((z.re*z.re+(z.im+1)*(z.im+1))/(z.re*z.re+(z.im-1)*(z.im-1)))/4;
  return c;
}
complex z={0.3,0.2};
void main(void)
{
  printf("Arctg(");
  show_complex(z);
  printf(") = ");
  show_complex(Arctg(z));
}

arcsh x
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//////////////////////////////////////////////////////////////////////////////
//
//  arsh x function calculating.
//  (c) Johna Smith, 1996
//
//  Method description:
//    Calculating arccos x using the following formula:
//                                          2n+1
//                   N      n 1*3*5..(2n-1)x
//     arsh x = x + SUM (-1)  ------------------ , |x|<1
//                  n=1       2*4*6..(2n)(2n+1)
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
#define N       30
double Arsh(double x)
{
  double arsh=x;
  double a=x;
  for (int i=1;i<N;i++)
  {
    a *= -x*x*(2*i-1)*(2*i-1)/((2*i+1)*2*i);
    arsh += a;
  }
  return arsh;
}
void main(void)
{
  printf("Exact arsh(0.5210953)=0.5, this arsh(0.5)=%g.",Arsh(0.5210953));
}

arcsh z
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//////////////////////////////////////////////////////////////////////////////
//
//  Calculactin function arcsh z, where z is a complex value
//  (c) Johna Smith, 1996
//
//  Method description:
//       1            2    2     1            2    2
//    A= - sqrt( (x+1)  + y  ) + - sqrt( (x-1)  + y  )
//       2                       2
//
//       1            2    2     1            2    2
//    B= - sqrt( (x+1)  + y  ) - - sqrt( (x-1)  + y  )
//       2                       2
//                         2
//    arcsh z = ln(a+sqrt(a  -1)) - i*acrsin B
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
struct complex
{
  float re;
  float im;
};
void show_complex(complex c) // this functions displays complex value
{
  printf("%f%+fi",c.re,c.im);
}
complex Arcsh(complex z)
{
  complex c;
  float A,B,swp;
  swp=z.im;    // calculating arsh(z) as -arcsin(iz)
  z.im=z.re;
  z.re=-swp;
  A=sqrt((z.re+1)*(z.re+1)+z.im*z.im)/2 +
         sqrt((z.re-1)*(z.re-1)+z.im*z.im)/2;
  B=sqrt((z.re+1)*(z.re+1)+z.im*z.im)/2 -
         sqrt((z.re-1)*(z.re-1)+z.im*z.im)/2;
  c.re=log(A+sqrt(A*A-1));
  c.im=-asin(B);
  return c;
}
complex z={3,2};
void main(void)
{
  printf("Arcsh(");
  show_complex(z);
  printf(") = ");
  show_complex(Arcsh(z));
}

arth x
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//////////////////////////////////////////////////////////////////////////////
//
//  arth x function calculating.
//  (c) Johna Smith, 1996
//
//  Method description:
//    Calculating arth x using the following formulas:
//                       2n+1
//                  N   x
//      arth x  =  SUM -------
//                 n=0  2n+1
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
#define N       30
double Arth(double x)
{
  double arth=x;
  double a=x;
  for (int i=1;i<N;i++)
  {
    a *= x*x;
    arth += a/(2*i+1);
  }
  return arth;
}
void main(void)
{
  printf("Exact arth(0.4621171)=0.5, this arth(0.4621171)=%g.",Arth(0.4621171));
}

arth z
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//////////////////////////////////////////////////////////////////////////////
//
//  arctg z function calculating, where z is a complex value
//  (c) Johna Smith, 1996
//
//  Method description:
//
//                   1    x^2+(y+1)^2    1          2x
//     arctg z  =    - ln(-----------) -i- arctg(---------)
//                   4    x^2+(y-1)^2    2       1-x^2-y^2
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
struct complex
{
  float re;
  float im;
};
void show_complex(complex c) // this functions displays complex value
{
  printf("%f%+fi",c.re,c.im);
}
complex Arth(complex z)
{
  complex c;
  float swp;
  swp=z.im;    // calculating arth(z) as -arctg(iz)
  z.im=z.re;
  z.re=-swp;
  c.re=log((z.re*z.re+(z.im+1)*(z.im+1))/(z.re*z.re+(z.im-1)*(z.im-1)))/4;
  c.im=-atan(2*z.re/(1-z.re*z.re-z.im*z.im))/2;
  return c;
}
complex z={0.3,0.2};
void main(void)
{
  printf("Arth(");
  show_complex(z);
  printf(") = ");
  show_complex(Arth(z));
}

Функция Бесселя
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//////////////////////////////////////////////////////////////////////////////
//
//  Bessel functions calculating.
//  (c) Johna Smith, 1996
//
//  Method description:
//    Bessel functions are solutions of the followind eqation:
//         2                     2
//        d w     1 dw          v
//        ---- +  - -- + ( 1 - --- )w = 0
//          2     x dx           2
//        dx                    x
//
//    This program calculates Bessel functions for integer v as infinite sum
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
// this function returns value of Jn(x)
double Jn(int n,double x)
{
  float nfact=1,ifact=1,nifact=1,sum=0,x2,element;
  int i;
  if (n>1) for (i=0;i<n;i++) nfact*=(i+1);  // n factorial
  x2=x*x/4;
  i=0;
  do
  {
    i++;
    ifact*=i;
    nifact*=(n+i);
    element=(i%2==0?1:-1)*pow(x2,i)/(ifact*nifact);
    sum+=element;
  } while (fabs(element)>1e-9);
  return pow(x/2,n)*(sum+1)/nfact;
}
// this function returns value of In(x)
double In(int n, double x)
{
  float nfact=1,ifact=1,nifact=1,sum=0,x2,element;
  int i;
  if (n>1) for (i=0;i<n;i++) nfact*=(i+1);  // n factorial
  x2=x*x/4;
  i=0;
  do
  {
    i++;
    ifact*=i;
    nifact*=(n+i);
    element=pow(x2,i)/(ifact*nifact);
    sum+=element;
  } while (fabs(element)>1e-9);
  return pow(x/2,n)*(sum+1)/nfact;
}
void main(void)
{
  // Examples
  printf("J0(0.5)=%f\n",Jn(0,0.5));
  printf("J30(20)=%f\n",Jn(30,20));
  printf("I0(2)=%f\n",In(0,2));
  printf("I1(2)=%f\n",In(1,2));
}

Гамма-функция
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//////////////////////////////////////////////////////////////////////////////
//
//  Gamma function calculating.
//  (c) Johna Smith, 1996
//
//  Method description:
//             infinity  -t  x-1
//   Gamma(x)= Integral e   t    dt
//                0
//
//   This integral is approximated and calculated by Stirling's formula:
//                A
//             (A)    1/12A
//      Gamma= (-)  e       D sqrt(2 Pi A)
//             (e)
//
//   This algorithm is oriented for -10<x<=70
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
#define E  2.7182818285
#define Pi  3.1415926536
// this function returns value of Gamma(x)
double Gamma(double x)
{
  double A,z,g,c,D;
  int b;
  A=x-1;
  z=A-64;
  if (z<0)
  {
    b=abs((int)(z-1));
    c=A;
    A+=b;
    D=1;
    for(int i=b;i>0;i--)
    {
       c++;
       D/=c;
    }
  } else D=1;
  g=pow(A/E,A)*exp(1/(12*A))*D*sqrt(2*Pi*A);
  return g;
}
void main(void)
{
  // Examples
  printf("Gamma(-1.5)=%f, exact value is 2.363271801\n",Gamma(-1.5));
  printf("Gamma(-0.5)=%f, exact value is -3.544907702\n",Gamma(-0.5));
  printf("Gamma(1.5)=%f, exact value is 0.886226926\n",Gamma(1.5));
  printf("Gamma(40)=%f, exact value is 2.039788208E+046\n",Gamma(40));
}

Бета-функция
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//////////////////////////////////////////////////////////////////////////////
//
//  Beta function calculating.
//  (c) Johna Smith, 1996
//
//  Method description:
//                 1      x-1      w-1
//   Beta(x,w)= Integral t    (1-t)   dt
//                 0
//              Gamma(x) Gamma(w)
//   Beta(x,w)= -----------------
//                 Gamma(x+w)
//
//   This algorithm is oriented for -10 < x,w,x+w <= 70
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
#define E       2.7182818285
#define Pi      3.1415926536
// this function returns value of Gamma(x)
double Gamma(double x)
{
  double A,z,g,c,D;
  int b;
  A=x-1;
  z=A-64;
  if (z<0)
  {
     b=abs((int)(z-1));
     c=A;
     A+=b;
     D=1;
     for(int i=b;i>0;i--)
     {
        c++;
        D/=c;
     }
  } else D=1;
  g=pow(A/E,A)*exp(1/(12*A))*D*sqrt(2*Pi*A);
  return g;
}
double Beta(double x, double w)
{
  return(Gamma(x)*Gamma(w)/Gamma(x+w));
}
void main(void)
{
  // Examples
  printf("Beta(1,2)=%f, exact value is 0.5\n",Beta(1,2));
}

ch x (x - real)
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//////////////////////////////////////////////////////////////////////////////
//
//  ch x function calculating.
//  (c) Johna Smith, 1996
//
//  Method description:
//    Calculating sh x using the following formulas:
//                      2n
//                  N  x
//        ch x  =  SUM ---
//                 n=0 2n!
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
#define N       30
double Ch(double x)
{
  double ch=1;
  double a=1;
  for (int i=0;i<N;i++)
  {
    a *= x*x/((2*i+2)*(2*i+1));
    ch += a;
  }
  return ch;
}
void main(void)
{
  printf("Exact ch(0.5)=%g, this ch(0.5)=%g.",(exp(0.5)+exp(-0.5))/2,Ch(0.5));
}

ch z (z - complex)
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//////////////////////////////////////////////////////////////////////////////
//
//  Calculactin function Ch(z), where z is a complex value
//  (c) Johna Smith, 1996
//
//  Method description:
//
//  ch z = ch x cos y + ish x sin y
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
struct complex
{
  float re;
  float im;
};
#define N       30  // precision
double Ch(double x)
{
  double ch=1;
  double a=1;
  for (int i=0;i<N;i++)
  {
    a*=x*x/((2*i+2)*(2*i+1));
    ch+=a;
  }
  return ch;
}
double Sh(double x)
{
  double sh=x;
  double a=x;
  for (int i=1;i<N;i++)
  {
    a*=x*x/((2*i)*(2*i+1));
    sh+=a;
  }
  return sh;
}
void show_complex(complex c) // this functions displays complex value
{
  printf("%f%+fi",c.re,c.im);
}
complex complexCh(complex z)
{
  complex c;
  c.re=Ch(z.re)*cos(z.im);
  c.im=Sh(z.re)*sin(z.im);
  return c;
}
complex z={3,2};
void main(void)
{
  printf("Ch(");
  show_complex(z);
  printf(") = ");
  show_complex(complexCh(z));
}

cosec x (x - real)
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//////////////////////////////////////////////////////////////////////////////
//
//  Cosecans function calculating.
//  (c) Johna Smith, 1996
//
//  Method description:
//    Calculating cosec x using the following formula:
//
//            1   1     7    3    31    5    127    7
//  cosec x = - + - x + --- x  + ----- x  + ------ x  + ...
//            x   6     360      15120      604800
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
double Cosec(double x)
{
  double cosec=0;
  double coefficient[]={1, 1/6.0, 7/360.0, 31/15120.0, 127/604800.0};
  double a=1/x;
  for (int i=0;i<sizeof(coefficient)/sizeof(double);i++)
  {
    cosec+=a*coefficient[i];
    a*=x*x;
  }
  return cosec;
}
void main(void)
{
  printf("C++ cosec(0.5)=%g, this cosec(0.5)=%g.",1/sin(0.5),Cosec(0.5));
}

cos x
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//////////////////////////////////////////////////////////////////////////////
//
//  Cosine function calculating.
//  (c) Johna Smith, 1996
//
//  Method description:
//    Calculating cos x using the following formula:
//                  2     4     6     8
//                 x     x     x     x
//    cos x = 1 - --- + --- - --- + --- - ...
//                 2!    4!    6!    8!
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
#define N       300
double Cos(double x)
{
  double cos=0;
  double a=1;
  for (int i=1;i<N;i++)
  {
    cos+=a;
    a=-a*x*x/((2*i-1)*2*i);
  }
  return cos;
}
void main(void)
{
  printf("C++ Cos(0.5)=%g, this Cos(0.5)=%g.",cos(0.5),Cos(0.5));
}

cos z (z - complex)
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//////////////////////////////////////////////////////////////////////////////
//
//  Calculactin function cos(z), where z is a complex value
//  (c) Johna Smith, 1996
//
//  Method description:
//
//  cos z = cos x ch y + isin x sh y
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
struct complex
{
  float re;
  float im;
};
#define N       30  // precision
double Ch(double x)
{
  double ch=1;
  double a=1;
  for (int i=0;i<N;i++)
  {
    a*=x*x/((2*i+2)*(2*i+1));
    ch+=a;
  }
  return ch;
}
double Sh(double x)
{
  double sh=x;
  double a=x;
  for (int i=1;i<N;i++)
  {
    a*=x*x/((2*i)*(2*i+1));
    sh+=a;
  }
  return sh;
}
void show_complex(complex c) // this functions displays complex value
{
  printf("%f%+fi",c.re,c.im);
}
complex Cos(complex z)
{
  complex c;
  c.re=cos(z.re)*Ch(z.im);
  c.im=sin(z.re)*Sh(z.im);
  return c;
}
complex z={3,2};
void main(void)
{
  printf("Cos(");
  show_complex(z);
  printf(") = ");
  show_complex(Cos(z));
}

ctg x
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//////////////////////////////////////////////////////////////////////////////
//
//  Cotangent function calculating.
//  (c) Johna Smith, 1996
//
//  Method description:
//    Calculating ctg x using the following formula:
//
//            1   1     1   3    2   5    1    7
//    ctg x = - - - x - -- x  - --- x  - ---- x  - ...
//            x   3     45      945      4725
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
double Ctg(double x)
{
  double ctg=0;
  double coefficient[]={1, -1/3.0, -1/45.0, -2/945.0, -1/4725.0};
  double a=1/x;
  for (int i=0;i<sizeof(coefficient)/sizeof(double);i++)
  {
    ctg += a*coefficient[i];
    a *= x*x;
  }
  return ctg;
}
void main(void)
{
  printf("C++ ctg(0.5)=%g, this ctg(0.5)=%g.",1/tan(0.5),Ctg(0.5));
}

e^x (x - real)
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//////////////////////////////////////////////////////////////////////////////
//
//  e^x function calculating.
//  (c) Johna Smith, 1996
//
//  Method description:
//    Calculating e^x using the following formula:
//                   2    3
//     x       x    x    x  
//    e  = 1 + -- + -- + -- + ...
//             1!   2!   3!
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
#define N       300
double Exp(double x)
{
  double exp=0;
  double a=1;
  for (int i=1;i<N;i++)
  {
    exp+=a;
    a*=x/i;
  }
  return exp;
}
void main(void)
{
  printf("C++ exp(10)=%g, this exp(10)=%g.",exp(10),exp(10));
}

e^z (z - complex)
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//////////////////////////////////////////////////////////////////////////////
//
//  Calculactin function e^z, where z is a complex value
//  (c) Johna Smith, 1996
//
//  Method description:
//
//  e^z = e^x cos y + i e^x sin y
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
struct complex
{
  float re;
  float im;
};
void show_complex(complex c) // this functions displays complex value
{
  printf("%f%+fi",c.re,c.im);
}
complex Exp(complex z)
{
  complex c;
  c.re=exp(z.re)*cos(z.im);
  c.im=exp(z.re)*sin(z.im);
  return c;
}
complex z={3,2};
void main(void)
{
  printf("Exp(");
  show_complex(z);
  printf(") = ");
  show_complex(Exp(z));
}

tg x (x - real)
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//////////////////////////////////////////////////////////////////////////////
//
//  Tangent function calculating.
//  (c) Johna Smith, 1996
//
//  Method description:
//    Calculating tg x using the following formula:
//
//                1  3   2   5   17   7   62    9
//     tg x = x + - x  + -- x  + --- x  + ---- x  + ...
//                3      15      315      2835
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
double Tg(double x)
{
  double tg=0;
  double coefficient[]={1,1/3.0,2/15.0,17/315.0,62/2835.0};
  double a=x;
  for (int i=0;i<sizeof(coefficient)/sizeof(double);i++)
  {
    tg+=a*coefficient[i];
    a*=x*x;
  }
  return tg;
}
void main(void)
{
  printf("C++ Tg(0.5)=%g, this Tg(0.5)=%g.",tan(0.5),Tg(0.5));
}

tg z (z - complex)
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//////////////////////////////////////////////////////////////////////////////
//
//  Calculactin function tg(z), where z is a complex value
//  (c) Johna Smith, 1996
//
//  Method description:
//
//             sin(2x)             sh(2y)
//  tg z = --------------- + i --------------
//         cos(2x)+ch(2*y)     cos(2x)+ch(2y)
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
struct complex
{
  float re;
  float im;
};
#define N       30  // precision
double Ch(double x)
{
  double ch=1;
  double a=1;
  for (int i=0;i<N;i++)
  {
    a*=x*x/((2*i+2)*(2*i+1));
    ch+=a;
  }
  return ch;
}
double Sh(double x)
{
  double sh=x;
  double a=x;
  for (int i=1;i<N;i++)
  {
    a*=x*x/((2*i)*(2*i+1));
    sh+=a;
  }
  return sh;
}
void show_complex(complex c) // this functions displays complex value
{
  printf("%f%+fi",c.re,c.im);
}
complex Tg(complex z)
{
  complex c;
  c.re=sin(2*z.re)/(cos(2*z.re)+Ch(2*z.im));
  c.im=Sh(2*z.im)/(cos(2*z.re)+Ch(2*z.im));
  return c;
}
complex z={3,2};
void main(void)
{
  printf("Tg(");
  show_complex(z);
  printf(") = ");
  show_complex(Tg(z));
}

th x (x - real)
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//////////////////////////////////////////////////////////////////////////////
//
//  th x function calculating.
//  (c) Johna Smith, 1996
//
//  Method description:
//    Calculating th x using the following formula:
//
//                1  3   2   5   17   7    62   9                Ї
//    sec x = x - - x  + -- x  - --- x  + ---- x  - ... ,  |x| < -
//                3      15      315      2835                   2
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
double Th(double x)
{
  double th=0;
  double coefficient[]={1, -1/3.0, 2/15.0, -17/315.0, 62/2835.0};
  double a=x;
  for (int i=0;i<sizeof(coefficient)/sizeof(double);i++)
  {
    th += a*coefficient[i];
    a *= x*x;
  }
  return th;
}
void main(void)
{
  printf("Exact th(0.5)=%g, this th(0.5)=%g.",
         (exp(0.5)-exp(-0.5))/(exp(0.5)+exp(-0.5)),Th(0.5));
}

th z (z - complex)
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//////////////////////////////////////////////////////////////////////////////
//
//  Calculactin function th(z), where z is a complex value
//  (c) Johna Smith, 1996
//
//  Method description:
//
//              sh(2x)             sin(2y)
//  th z = --------------- + i --------------
//         ch(2x)+cos(2*y)     ch(2x)+cos(2y)
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
struct complex
{
  float re;
  float im;
};
#define N       30  // precision
double Ch(double x)
{
  double ch=1;
  double a=1;
  for (int i=0;i<N;i++)
  {
    a*=x*x/((2*i+2)*(2*i+1));
    ch+=a;
  }
  return ch;
}
double Sh(double x)
{
  double sh=x;
  double a=x;
  for (int i=1;i<N;i++)
  {
    a*=x*x/((2*i)*(2*i+1));
    sh+=a;
  }
  return sh;
}
void show_complex(complex c) // this functions displays complex value
{
  printf("%f%+fi",c.re,c.im);
}
complex complexTh(complex z)
{
  complex c;
  c.re=Sh(2*z.re)/(Ch(2*z.re)+cos(2*z.im));
  c.im=sin(2*z.im)/(Ch(2*z.re)+cos(2*z.im));
  return c;
}
complex z={3,2};
void main(void)
{
  printf("Th(");
  show_complex(z);
  printf(") = ");
  show_complex(complexTh(z));
}

sin x (x- real)
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//////////////////////////////////////////////////////////////////////////////
//
//  Sine function calculating.
//  (c) Johna Smith, 1996
//
//  Method description:
//    Calculating sin x using the following formula:
//                  3     5     7     9
//                 x     x     x     x
//    sin x = x - --- + --- - --- + --- - ...
//                 3!    5!    7!    9!
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
#define N       300
double Sin(double x)
{
  double sin=0;
  double a=x;
  for (int i=1;i<N;i++)
  {
    sin+=a;
    a=-a*x*x/((2*i+1)*2*i);
  }
  return sin;
}
void main(void)
{
  printf("C++ Sin(0.5)=%g, this Sin(0.5)=%g.",sin(0.5),Sin(0.5));
}

sin z (z - complex)
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//////////////////////////////////////////////////////////////////////////////
//
//  Calculactin function sin(z), where z is a complex value
//  (c) Johna Smith, 1996
//
//  Method description:
//
//  sin z = sin x ch y + icos x sh y
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
struct complex
{
  float re;
  float im;
};
#define N       30  // precision
double Ch(double x)
{
  double ch=1;
  double a=1;
  for (int i=0;i<N;i++)
  {
    a*=x*x/((2*i+2)*(2*i+1));
    ch+=a;
  }
  return ch;
}
double Sh(double x)
{
  double sh=x;
  double a=x;
  for (int i=1;i<N;i++)
  {
    a*=x*x/((2*i)*(2*i+1));
    sh+=a;
  }
  return sh;
}
void show_complex(complex c) // this functions displays complex value
{
  printf("%f%+fi",c.re,c.im);
}
complex Sin(complex z)
{
  complex c;
  c.re=sin(z.re)*Ch(z.im);
  c.im=cos(z.re)*Sh(z.im);
  return c;
}
complex z={3,2};
void main(void)
{
  printf("Sin(");
  show_complex(z);
  printf(") = ");
  show_complex(Sin(z));
}

sec x (x - real)
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//////////////////////////////////////////////////////////////////////////////
//
//  Secans function calculating.
//  (c) Johna Smith, 1996
//
//  Method description:
//    Calculating sec x using the following formula:
//
//                1  2   5   4   61   6   277   8
//    sec x = 1 + - x  + -- x  + --- x  + ---- x  + ...
//                2      24      720      8064
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
double Sec(double x)
{
  double sec=0;
  double coefficient[]={1, 1/2.0, 5/24.0, 61/720.0, 277/8064.0};
  double a=1;
  for (int i=0;i<sizeof(coefficient)/sizeof(double);i++)
  {
    sec+=a*coefficient[i];
    a*=x*x;
  }
  return sec;
}
void main(void)
{
  printf("C++ Sec(0.5)=%g, this Sec(0.5)=%g.",1/cos(0.5),Sec(0.5));
}

sh x (x - real)
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//////////////////////////////////////////////////////////////////////////////
//
//  sh x function calculating.
//  (c) Johna Smith, 1996
//
//  Method description:
//    Calculating sh x using the following formulas:
//                       2n-1
//                  N   x
//        sh x  =  SUM -------
//                 n=1 (2n-1)!
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
#define N       30
double Sh(double x)
{
  double sh=x;
  double a=x;
  for (int i=1;i<N;i++)
  {
    a*=x*x/((2*i)*(2*i+1));
    sh+=a;
  }
  return sh;
}
void main(void)
{
  printf("Exact sh(0.5)=%g, this sh(0.5)=%g.",(exp(0.5)-exp(-0.5))/2,Sh(0.5));
}

sh z (z - complex)
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//////////////////////////////////////////////////////////////////////////////
//
//  Calculactin function Sh(z), where z is a complex value
//  (c) Johna Smith, 1996
//
//  Method description:
//
//  sh z = sh x cos y + ich x sin y
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
struct complex
{
  float re;
  float im;
};
#define N       30  // precision
double Ch(double x)
{
  double ch=1;
  double a=1;
  for (int i=0;i<N;i++)
  {
    a*=x*x/((2*i+2)*(2*i+1));
    ch+=a;
  }
  return ch;
}
double Sh(double x)
{
  double sh=x;
  double a=x;
  for (int i=1;i<N;i++)
  {
    a*=x*x/((2*i)*(2*i+1));
    sh+=a;
  }
  return sh;
}
void show_complex(complex c) // this functions displays complex value
{
  printf("%f%+fi",c.re,c.im);
}
complex complexSh(complex z)
{
  complex c;
  c.re=Sh(z.re)*cos(z.im);
  c.im=Ch(z.re)*sin(z.im);
  return c;
}
complex z={3,2};
void main(void)
{
  printf("Sh(");
  show_complex(z);
  printf(") = ");
  show_complex(complexSh(z));
}

Факториал (формула Стирлинга)
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//////////////////////////////////////////////////////////////////////////////
//
//  Factorial calculation (Stirling solution)
//  (c) Johna Smith, 1996
//
//  Method description:
//   We just use Stirling method, improving it by using fast method
//  of calculating n^n.
//   !! Warning! this formula gives best results ONLY if n>>10
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
#define Pi 3.1415926536
long double factorial (long int n)
{
  long double factorial,b=1,tmp;
  long int k;
  factorial=sqrt(2*Pi*n)*exp(-n+(1-1/(30*n))/(12*n));
  // quick powering n^n
  tmp=n;
  k=n;
  while (k!=0)
  {
    if (k%2!=0) b*=tmp;
    k/=2;
    tmp*=tmp;
  }
  factorial*=b;
  return factorial;
}
void main(void)
{
  printf("5! = %Lf\n35! = %Lf\n100! = %Lf\n",factorial(5L),
                        factorial(35L),factorial(100L));
}

sqrt(z), where z is a complex value
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//////////////////////////////////////////////////////////////////////////////
//
//  Calculactin function sqrt(z), where z is a complex value
//  (c) Johna Smith, 1996
//
//  Method description:
//
//  sqrt(z) = +/- sqrt((x+sqrt(x^2+y^2))/2) +/- i*sqrt(-x+sqrt(x^2+y^2))/2)
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
struct complex
{
  float re;
  float im;
};
void show_complex(complex c) // this functions displays complex value
{
  printf("%f%+fi",c.re,c.im);
}
complex Sqrt(complex z)
{
  complex c;
  c.re=sqrt((z.re+sqrt(z.re*z.re+z.im*z.im))/2);
  c.im=sqrt((-z.re+sqrt(z.re*z.re+z.im*z.im))/2);
  return c;
}
complex z={3,2};
void main(void)
{
  printf("Sqrt(");
  show_complex(z);
  z=Sqrt(z);
  printf(") = +/- %f +/- i*%f",z.re,z.im);
}

ln x (x - real)
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//////////////////////////////////////////////////////////////////////////////
//
//  ln x function calculating.
//  (c) Johna Smith, 1996
//
//  Method description:
//    Calculating ln x using the following formula:
//
//               N     (x-1)^(2n+1)
//    ln x  = 2 SUM ------------------
//              n=0 (2n+1)(x+1)^(2n+1)
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
#define N       300
double Ln(double x)
{
  double ln=0;
  double a=(x+1)/(x-1);
  for (int i=0;i<N;i++)
  {
    a*=(x-1)*(x-1)/((x+1)*(x+1));
    ln+=a/(2*i+1);
  }
  return 2*ln;
}
void main(void)
{
  printf("C++ ln(10)=%g, this ln(10)=%g.",log(10),Ln(10));
}

ln z (z - complex)
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//////////////////////////////////////////////////////////////////////////////
//
//  Calculactin function ln z, where z is a complex value
//  (c) Johna Smith, 1996
//
//  Method description:
//         1   2   2             y
//  ln z = - (x + y ) + i*(arctg - +2kЇ), k=0, +/-1, +/-2, ...
//         2                     x
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <math.h>
struct complex
{
  float re;
  float im;
};
void show_complex(complex c) // this functions displays complex value
{
  printf("%f%+fi",c.re,c.im);
}
complex Ln(complex z)
{
  complex c;
  c.re=log(z.re*z.re+z.im*z.im)/2;
  c.im=atan(z.im/z.re); // you can add 2kЇ here (we assume that k=0)
  return c;
}
complex z={3,2};
void main(void)
{
  printf("Ln(");
  show_complex(z);
  printf(") = ");
  show_complex(Ln(z));
}


Динамические структуры данных

Bidirectional cycled list
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
//////////////////////////////////////////////////////////////////////////////
//
//  Dynamic structures (bidirectional cycled list)
//  (c) Johna Smith, 1996
//
//  Method description:
// .................
// -> * -> * -> * ->
// <- * <- * <- * <-
// .  A    B    C  .
// .................
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <alloc.h>
struct item
{
  int element;
  item *prev;
  item *next;
};
item *list; // base element of the list
// this function removes element pointed by i from list
void Remove(item* i)
{
  i->next->prev=i->prev;
  i->prev->next=i->next;
  free(i);
}
// this function inserts element after
// element pointed by i
void Insert(item *i, int element)
{
  item *tmp;
  // creating new item
  tmp=(item*)malloc(sizeof(item));
  tmp->element=element;
  tmp->next=i->next;
  tmp->prev=i->next->prev;
  // correcting nearest elements pointers
  i->next->prev=tmp;
  i->next=tmp;
}
// this function searches element in the list
item* Search(int element)
{
  item *p,*q,*result=NULL;
  char found=0;
  p=list;
  q=list->next;
  
  while (p!=q && found==0)
  {
    if (q->element==element)
    {
      found=1;
      result=q;
    }
    q=q->next;
  }
  return result;
}
// this function prints the list
void printlist(void)
{
  item *p;
  p=list->next;
  while (p!=list)
  {
    printf("%d ",p->element);
    p=p->next;
  }
}
void main(void)
{
  // creating first element of the list
  list=(item*)malloc(sizeof(item));
  list->element=0;
  list->next=list;
  list->prev=list;
  printf("Adding elements 1,2,4 & 5\n");
  Insert(list,5);
  Insert(list,4);
  Insert(list,2);
  Insert(list,1);
  printlist();
  printf("\nSearching element 2\n");
  item *tmp=Search(2);
  printf("Inserting element 3 after it\n");
  Insert(tmp,3);
  printlist();
  printf("\nDeleting element 1\n");
  Remove(list->next);
  printlist();
  // destroying list
  while (list->next!=list) Remove(list->next);
  free(list);
}

Binary tree
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
//////////////////////////////////////////////////////////////////////////////
//
//  Dynamic structures (binary tree)
//  (c) Johna Smith, 1996
//
//  Method description:
//               *
//            /     \
//           *       *
//         /   \   /   \
//        *     * *     *
//
//   From current element X left element is less than X and right element
// is greater than X. All elements in the must be different.
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <alloc.h>
#include <conio.h>
#include <math.h>
struct item
{
  int element;
  item *left;
  item *right;
};
item *tree; // base element of the list
// this function searches element in the tree and returns 0 if element wasn't
// found and 1 - if element was found, result is address of element
char Search(int element, item** result)
{
  item *p,*q;
  char found=0;
  p=tree;
  if (tree!=NULL)
  do
  {
    q=p;
    if (p->element==element) found=1;
    else
    {
      q=p;
      if (element<p->element) p=p->left;
      else p=p->right;
    }
  }
  while (!found && p!=NULL);
  *result=q;
  return found;
}
// this function adds an element to the tree
void Add(int element)
{
  item *r,*s;
  if (Search(element,&r)==0)
  {
    s=(item*)malloc(sizeof(item));
    s->element=element;
    s->left=NULL;
    s->right=NULL;
    if (tree==NULL) tree=s; // if tree is empty make s=top of the tree
    else
    {
      if (element<r->element) r->left=s;
      else r->right=s;
    }
  }
}
// this is auxulary function for Remove procedure
void Del(item **r, item **q)
{
  item *tmp;
  if ((*r)->right==NULL)
  {
    (*q)->element=(*r)->element;
    *q=*r;
    *r=(*r)->left;
  } 
  else Del(&((*r)->right),q);
}
// this function removes element with value 'element' from the tree
void Remove(int element, item **d)
{
  item *q;
  if (*d==NULL)
  printf("There is not element %d in the tree.\n",element);
  else
  if (element<(*d)->element) Remove(element, &((*d)->left)); else
  if (element>(*d)->element) Remove(element, &((*d)->right)); else
  {
    // element found
    q=*d;
    if (q->right==NULL) *d=q->left; else
    if (q->left==NULL) *d=q->right; else
    Del(&(q->left),&q);
    free(q);
  }
}
// this function prints the tree
void printtree(item *t, int offset=40, int depth=2)
{
  gotoxy(offset,depth);
  cprintf("%d",t->element);
  if (t->left!=NULL) printtree(t->left,offset-pow(2,6-depth),depth+1);
  if (t->right!=NULL) printtree(t->right,offset+pow(2,6-depth),depth+1);
}
void main(void)
{
  item *tmp;
  // creating tree
  Add(100);
  Add(20);
  Add(120);
  Add(15);
  Add(50);
  Add(130);
  Add(30);
  Add(55);
  Add(28);
  Add(35);
  Add(60);
  Add(33);
  // printing tree
  clrscr();
  printf("Press a key to delete element 50...\n");
  printtree(tree);
  getch();
  clrscr();
  Remove(50,&tree);
  printtree(tree);
  gotoxy(1,20);
  // searching
  cprintf("Element 20 is%s found",(Search(20,&tmp)?"":"n't"));
  printf("\nElement 25 is%s found\n",(Search(25,&tmp)?"":"n't"));
  // removing all elements
  Remove(100,&tree);
  Remove(20,&tree);
  Remove(120,&tree);
  Remove(15,&tree);
  Remove(35,&tree);
  Remove(130,&tree);
  Remove(30,&tree);
  Remove(55,&tree);
  Remove(28,&tree);
  Remove(33,&tree);
  Remove(60,&tree);
}

Stack
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//////////////////////////////////////////////////////////////////////////////
//
//  Dynamic structures (stack)
//  (c) Johna Smith, 1996
//
//  Method description:
//    Stack is the queue with LIFO structure (Last In First Out)
//    There is only one accesible element in the stack - its top
//    Two operations defined for stack - pushing element to stack
//    and popping element feom stack
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <alloc.h>
struct item
{
  int element;
  item *next;
};
item *stack=NULL; // base element of the stack
// this function pushes an to stack
void Push(int element)
{
  item *q;
  
  q=(item*)malloc(sizeof(item));
  q->element=element;
  q->next=stack;
  stack=q;
}
// this function pops an element from stack
int Pop(void)
{
  int result;
  item *q;
  
  if (stack==NULL)
    printf("!POP error: stack is EMPTY");
  else
  {
    result=stack->element;
    q=stack;
    stack=stack->next;
    free(q);
  }
  return result;
}
// this function prints the stack
void printstack(void)
{
  item *p;
  p=stack;
  while (p!=NULL)
  {
    printf("%d ",p->element);
    p=p->next;
  }
}
void main(void)
{
  printstack();
  printf("Pushing elements 1,2,3\n");
  Push(1);
  Push(2);
  Push(3);
  printstack();
  printf("\nPopping 2 elements\n");
  printf("%d ",Pop());
  printf("%d\n",Pop());
  printstack();
  // destroying stack
  while (stack!=NULL) Pop();
}

List
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
//////////////////////////////////////////////////////////////////////////////
//
//  Dynamic structures (list)
//  (c) Johna Smith, 1996
//
//  Method description:
//    * -> * -> * -> nil
//    A    B    C
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <alloc.h>
struct item
{
  int element;
  item *next;
};
item *list; // base element of the list
item *p; // current pointer
// this function adds an element to the end of list
void Add(int element)
{
  p->next=(item*)malloc(sizeof(item));
  p=p->next;
  p->element=element;
  p->next=NULL;
}
// this function removes element from list
// after element pointed by i
void Remove(item* i)
{
  item *tmp;
  if (i->next!=NULL)
  {
    tmp=i->next;
    i->next=(i->next)->next;
    free(tmp);
  }
}
// this function inserts element after
// element pointed by i
void Insert(item *i, int element)
{
  item *tmp;
  tmp=(item*)malloc(sizeof(item));
  tmp->element=element;
  tmp->next=i->next;
  i->next=tmp;
}
// this function searches element in the list
item* Search(int element)
{
  item *i,*result=NULL;
  char found=0;
  i=list->next;
  while (i!=NULL && found==0)
  {
    if (i->element==element)
    {
      found=1;
      result=i;
    }
    i=i->next;
  }
  return result;
}
// this function prints the list
void printlist(void)
{
  item *p;
  p=list->next;
  while (p!=NULL)
  {
    printf("%d ",p->element);
    p=p->next;
  }
}
void main(void)
{
  // creating first element of the list
  list=(item*)malloc(sizeof(item));
  list->element=0;
  list->next=NULL;
  p=list;
  printf("Adding elements 1,2 & 4\n");
  Add(1);
  Add(2);
  Add(4);
  printlist();
  printf("\nSearching element 2\n");
  item *tmp=Search(2);
  printf("Inserting element 3 after it\n");
  Insert(tmp,3);
  printlist();
  printf("\nDeleting element 1\n");
  Remove(list);
  printlist();
  // destroying list
  while (list->next!=NULL) Remove(list);
  free(list);
}


Сортировка массивов

Binary insertions
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//////////////////////////////////////////////////////////////////////////////
//
//  Binary insertion (array sorting)
//  (c) Johna Smith, 1996
//
//  Method description:
//    Split our array into two parts - sorted (left) and unsorted (right)
//    Initially sorted part contains only one element - first array element
//    Take an element from the unsorted part and put it in the right place in
//    the sorted part (using binary search to find this right place). So
//    sorted part contains now two elements. Repeat this process until
//    no elements left in the unsorted part.
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
const N=     10;  // array size
int array[N]={100,15,234,11,63,78,4,200,0,4}; // array of N integers
int element; // value of the element we want to insert
unsigned int right,left,middle; // auxulary variables for binary search
void show_array(void) // displays array
{
  for (int i=0;i<N;i++)
    printf("%d ",array[i]);
}
void main(void)
{
  // Display unsorted array
  printf("Unsorted array: ");
  show_array();
  // Sorting
  for (int i=1;i<N;i++) // main loop
  {
    // Searching place for element i (binary search)
    left=0;
    right=i;
    element=array[i];
    while (left<right)
    {
      middle=(left+right)/2;
      if (array[middle]<=element) left=middle+1; else right=middle;
    }
    // Inserting element i into the right place
    for (int j=i;j>right;j--) array[j]=array[j-1];
    array[right]=element;
  }
  // Display sorted array
  printf("\nSorted array: ");
  show_array();
}
Straight insertion
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//////////////////////////////////////////////////////////////////////////////
//
//  Straight insertion (array sorting)
//  (c) Johna Smith, 1996
//
//  Method description:
//    Split our array into two parts - sorted (left) and unsorted (right)
//    Initially sorted part contains only one element - first array element
//    Take an element from the unsorted part and put it in the right place in
//    the sorted part. So sorted part contains now two elements. Repeat
//    this process until no elements left in the unsorted part.
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
const N = 10;  // array size
int array[N]={100,15,234,11,63,78,4,200,0,4}; // array of N integers
int element; // value of the element we want to insert
unsigned int index; // index of the right position of the element
void show_array(void) // displays array
{
  for (int i=0;i<N;i++)
    printf("%d ",array[i]);
}
void main(void)
{
  // Display unsorted array
  printf("Unsorted array: ");
  show_array();
  // Sorting
  for (int i=1;i<N;i++) // main loop
  {
    index=0;
    // Searching place for element i
    while (array[index]<array[i]) index++;
    // Inserting element i into the right place
    element=array[i];
    for (int j=i;j>index;j--) array[j]=array[j-1];
    array[index]=element;
  }
  // Display sorted array
  printf("\nSorted array: ");
  show_array();
}

Heap sort
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
//////////////////////////////////////////////////////////////////////////////
//
//  Heap sort
//  (c) Johna Smith, 1996
//
//  Method description:
//    This algorithm sorts array using pyramids. The pyramid is the
//    sequence of characters h(L), h(L+1),...,h(R) with the following
//    properties:
//          h(i)<=h(2i);  h(i)<=h(2i+1), i=L..R/2
//                        h1
//                     /     \               This is an example of
//                   h2       h3                   pyramid
//                 /    \   /    \
//               h4     h5 h6     h7
//              .....................
//    There are two steps in this algorythm:
//    1) Building pyramid from the given array using Floyd method of
//    building pyramid "on the same place".
//    2) Sorting built pyramid:
//       Swap last pyramid element (x) with the top one and shift x
//       to the right place using Floyd method
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
const N = 10;  // array size
int array[N]={100,15,234,11,63,78,4,200,0,4}; // array of N integers
int swp; // auxulary variable for swapping
int left,right; // indexes for left and right bounds of the sorted part of the array
void show_array(void) // this function displays array
{
  for (int i=0;i<N;i++)
    printf("%d ",array[i]);
}
// this function shifts element in the pyramid to the right place
// it helps to build pyramid "on the same place" (using Floyd method)
void shift(int left, int right)
{
  int i,j;
  int swp;
  int element;
  i=left;
  j=2*left+1;
  element=array[left];
  if (j<right && array[j]<array[j+1]) j++;
  while (j<=right && element<array[j])
  {
    // swapping elements
    swp=array[i];
    array[i]=array[j];
    array[j]=swp;
    // now i-th element is on j-th place:
    i=j;
    element=array[i];
    // and j-th element is lower (see pyramid picture)
    j=2*j+1;
    if (j<right && array[j]<array[j+1]) j++;
  }
}
void main(void)
{
   // Displaying unsorted array
   printf("Unsorted array: ");
   show_array();
   // Sorting
   left=N/2;
   right=N-1;
   // building pyramid from array
   while (left>0)
   {
     left--;
     shift(left,N-1);
   }
   // sorting built pyramid
   while (right>0)
   {
     // swapping elements
     swp=array[0];
     array[0]=array[right];
     array[right]=swp;
     // shifting element to the right place
     right--;
     shift(0,right);
   }
   // Displaying sorted array
   printf("\nSorted array: ");
   show_array();
}

Straight selections
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//////////////////////////////////////////////////////////////////////////////
//
//  Straight selections (array sorting)
//  (б) Johna Smith, 1996
//
//  Method description:
//    searching for smallest element in array, swapping with first element,
//    repeat this operation starting search from second element and so on
//    array become sorted when we'll start search from (n-1)-th element
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
const N = 10;  // number of elements in array
int array[N]={100,15,234,11,63,78,4,200,0,4};
int min; // smallest element in array
int index; // index of the smallest element in array
int swp; // auxulary variable for swapping
void show_array(void) // this function prints array
{
  for (int i=0;i<N;i++)
    printf("%d ",array[i]);
}
void main(void)
{
   // Printing unsorted array
   printf("Unsorted array: ");
   show_array();
   // Sorting
   for (int i=0;i<N-1;i++) // main loop
   {
     // searching for smallest element from i-th
     min=array[i]; // setting i-th elementas smallest
     index=i;
     for (int j=i+1;j<N;j++)
       if (array[j]<min)  // if there is element less than smallest
       {
          min=array[j];  // then remember its value
          index=j;       // and index
       }
     // swapping i-th and smallest element
     swp=array[index];
     array[index]=array[i];
     array[i]=swp;
   }
   // Printing sorted array
   printf("\nSorted array: ");
   show_array();
}

Shaker sort
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
//////////////////////////////////////////////////////////////////////////////
//
//  Shaker sort
//  (c) Johna Smith, 1996
//
//  Method description:
//    Advanced bubble sort.
//    There are two main steps:
//     1) Move greatest element to the end, moving forward and
//        remembering place of the last elements exchange
//        this place will be right bound of the unsorted part
//     2) Move smallest element to the beginning, moving backward and
//        remembering place of the last elements exchange
//        this place will be left bound of the unsorted part
//    Repeat this two steps while right bound is greater than left
//    This method is useful when almost all elements in the array
//    are sorted.
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
const N=     10;  // array size
int array[N]={100,15,234,11,63,78,4,200,0,4}; // array of N integers
int index; // auxulary variable (the place of last swap)
int swp; // auxulary variable for swapping
int left,right; // indexes for left and right bounds of the sorted part of the array
void show_array(void) // this function displays array
{
  for (int i=0;i<N;i++)
     printf("%d ",array[i]);
}
void main(void)
{
   // Displaying unsorted array
   printf("Unsorted array: ");
   show_array();
   // Sorting
   left=0;
   right=N-1;
   do
   {
     // moving smallest element to the beginning (moving backward)
     for (int i=right;i>left;i--)
     {
        if (array[i-1]>array[i])
        {
          // swapping a(i) and a(i+1)
          swp=array[i];
          array[i]=array[i-1];
          array[i-1]=swp;
          index=i; // save index
        }
     }
     left=index;
     // moving greatest element to the end (moving forward)
     for (i=left;i<right;i++)
     {
       if (array[i]>array[i+1])
       {
         // swapping a(i) and a(i+1)
         swp=array[i];
         array[i]=array[i+1];
         array[i+1]=swp;
         index=i; // save index
       }
     }
     right=index;
} while (left<right);
   // Displaying sorted array
   printf("\nSorted array: ");
   show_array();
}

Shell sort
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//////////////////////////////////////////////////////////////////////////////
//
//  Shell sort (array sorting)
//  (c) Johna Smith, 1996
//
//  Method description:
//    1) Sort elements (0,4,8,12,...) (step=4) using straight insertions method
//    2) Sort elements (0,2,4,6,8,...) (step=2) using straight insertions method
//    3) Sort all elements (step=1) using straight insertions method
//    Shell sort is faster than simple straight insertions because at each
//    step more and more elements are already sorted (productivity increased
//    by ~300% for random array of 256 elements & about 700% (!) for random array
//    of 2048 elements (N. Wirth, Algoritms and data structures)
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
const T = 4;   // number of distances
const N = 20;  // array size
int array[N]={100,15,234,11,63,78,4,200,0,4,14,32,44,58,1,2,3,9,8,7}; // array of N integers
int interval[T]={9,5,3,1}; // last interval must be 1
int step; // current step
int element; // value of the element we want to insert
unsigned int index; // index of the right position of the element
void show_array(void) // displays array
{
  for (int i=0;i<N;i++)
    printf("%d ",array[i]);
}
void main(void)
{
  // Display unsorted array
  printf("Unsorted array: ");
  show_array();
  // Sorting
  for (int m=0;m<T;m++)  // main loop (by all distances)
  {
    step=interval[m];
    // sorting (0,step,2*step,3*step,...) elements using straight insertions
    for (int i=0;i<N;i+=step)
    {
      index=0;
      // Searching place for element i
      while (array[index]<array[i]) index+=step;
      // Inserting element i into the right place
      element=array[i];
      for (int j=i;j>index;j-=step) array[j]=array[j-step];
      array[index]=element;
    }
  }
  // Display sorted array
  printf("\nSorted array: ");
  show_array();
}

Quick sort (recursive)
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//////////////////////////////////////////////////////////////////////////////
//
//  Quick sort (recursive)
//  (c) Johna Smith, 1996
//
//  Method description:
//    1) Split array into two parts and remember middle element
//    2) Scan left part for element greater than middle
//    3) Scan right part for element less than middle
//    4) Swap these elements
//    So we have an array where all left elements are less than right elements
//    Apply these four steps to each part (left and right) of the array
//    until we have parts that contain only one element.
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
const N=     10;  // array size
int array[N]={100,15,234,11,63,78,4,200,0,4}; // array of N integers
void show_array(void) // this function displays array
{
  for (int i=0;i<N;i++)
    printf("%d ",array[i]);
}
void sort(int left,int right)
{
  int i,j;
  int element; // auxulary variable for middle element in the interval
  int swp; // auxulary variable for swapping
  i=left;  // index for left part
  j=right;  // index for right part
  element=array[(left+right)/2]; // middle element
  do
  {
    while (array[i]<element) i++; // scanning left part
    while (element<array[j]) j--; // scanning right part
    if (i<=j)
    {
      // swapping elements
      swp=array[i];
      array[i]=array[j];
      array[j]=swp;
      i++; j--;
    }
  } while (i<=j);
  if (left<j) sort(left,j); // applying the same procedure to the left part
  if (i<right) sort(i,right); // applying the same procedure to the right part
}
void main(void)
{
  // Displaying unsorted array
  printf("Unsorted array: ");
  show_array();
  // Sorting
  sort(0,N-1);
  // Displaying sorted array
  printf("\nSorted array: ");
  show_array();
}

Quick sort (non-recursive)
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
//////////////////////////////////////////////////////////////////////////////
//
//  Quick sort (non-recursive)
//  (c) Johna Smith, 1996
//
//  Method description:
//    1) Split array into two parts and remember middle element
//    2) Scan left part for element greater than middle
//    3) Scan right part for element less than middle
//    4) Swap these elements
//    So we have an array where all left elements are less than right elements
//    Apply these four steps to each part (left and right) of the array
//    until we have parts that contain only one element.
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
const N = 10;         // array size
const STACK_SIZE = 4; // stack size must be >=log N
int array[N]={100,15,234,11,63,78,4,200,0,4}; // array of N integers
void show_array(void) // this function displays array
{
  for (int i=0;i<N;i++)
    printf("%d ",array[i]);
}
struct {int left; int right;} stack[STACK_SIZE]; // stack emulation
unsigned int ss; // current stack size
int i,j;
int element; // auxulary variable for middle element in the interval
int swp; // auxulary variable for swapping
int left,right; // interval bounds
void main(void)
{
  // Displaying unsorted array
  printf("Unsorted array: ");
  show_array();
  // Sorting
  ss=1;
  stack[0].left=0;
  stack[0].right=N-1;
  do
  {
    // pushing from stack last request
    left=stack[ss-1].left;
    right=stack[ss-1].right;
    ss--;
    do
    {
      // splitting array[left]..array[right] interval
      i=left;  // index for left part
      j=right;  // index for right part
      element=array[(left+right)/2]; // middle element
      do
      {
        while (array[i]<element) i++; // scanning left part
        while (element<array[j]) j--; // scanning right part
        if (i<=j)
        {
          // swapping elements
          swp=array[i];
          array[i]=array[j];
          array[j]=swp;
          i++; j--;
        }
      } while (i<=j);
      // pushing request into stack
      // (we select longest part and push request for it to reduce stack size)
      if (j-left<right-i)
      {
        if (i<right) // push request for the right part (because it's longer than left)
        {
          ss++;
          stack[ss-1].left=i;
          stack[ss-1].right=right;
        }
        right=j; // continue sorting left part
      } else
      {
        if (left<j) // push request for the left part (because it's longer than right)
        {
          ss++;
          stack[ss-1].left=left;
          stack[ss-1].right=j;
        }
        left=i; // continue sorting right part
      }
    } while(left<right);
  } while(ss!=0);
  // Displaying sorted array
  printf("\nSorted array: ");
  show_array();
}

Exchanges
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//////////////////////////////////////////////////////////////////////////////
//
//  Exchanges (array sorting)
//  (б) Johna Smith, 1996
//
//  Method description:
//    Using linear search find smallest i with the following property:
//    a(i)>a(i+1), swap a(i) and a(i+1) and repeat this process searching
//    from a(i+1). After one pass greatest number will be placed at right
//    place. We'll decrease amount of acting elements on each pass.
//    When 2 elements will left we'll say that array is sorted
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
const N=     10;  // number of array elements
int array[N]={100,15,234,11,63,78,4,200,0,4};
int swp; // auxulary variable for swapping
int m; // number of active elements on current pass
void show_array(void) // this function prints array
{
  for (int i=0;i<N;i++)
    printf("%d ",array[i]);
}
void main(void)
{
   // Printing unsorted array
   printf("Unsorted array: ");
   show_array();
   // Sorting
   m=N; // All elements acting at first pass
   while (m>1) // repeat passes while there is more than one element
   {
     for (int i=0;i<m-1;i++) // main loop
     {
       // searching for smallest element
       if (array[i]>array[i+1]) // if a(i)>a(i+1)
       {
         // swapping a(i) and a(i+1)
         swp=array[i];
         array[i]=array[i+1];
         array[i+1]=swp;
       }
     }
     m--; // decreasing amount of acting elements
   }
   // Printing sorted array
   printf("\nSorted array: ");
   show_array();
}


Сортировка файлов

Straight merge
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
//////////////////////////////////////////////////////////////////////////////
//
//  File sort (straight merge)
//  (c) Johna Smith, 1996
//
//  Method description:
//   This program reads data from file 1.dat and writes sorted data to 1.srt
//   Format of 1.dat: i1 i2 i3 i4 i5 i6 ..., where i(k) is integer
//   It also creates four temporary files: 1.tmp, 2.tmp, 3.tmp, 4.tmp
//   We use four files to sort given sequence of data.
//     1) Split file into 2 parts (A and B)
//     2) Combine A and B to C, sorting 2-element groups
//     3) Repeat these steps for file C, sorting 4-element groups,
//        8-elements,... while size of group less than file size.
//     We can optimize this method by uniting splitting and combining:
//     we just need to change destination on each step: combine one
//     group to C another to D, next group again to C and so on
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
int copy(FILE *A, FILE *B, FILE *C, int n)
{
  int a,b,q,r,m=0;
  q=r=0;
  // combining to C
  if (!feof(A)) fread(&a,sizeof(int),1,A);
  if (!feof(B)) fread(&b,sizeof(int),1,B);
  while (!feof(A) && !feof(B) && q<n && r<n)
  {
    if (a<b)
    {
      fwrite(&a,sizeof(int),1,C);m++;q++;
      if (q<n) fread(&a,sizeof(int),1,A);
    } 
    else
    {
      fwrite(&b,sizeof(int),1,C);m++;r++;
      if (r<n) fread(&b,sizeof(int),1,B);
    }
  }
  // writing remainders
  while (!feof(A) && q<n)
  {
    fwrite(&a,sizeof(int),1,C);m++;q++;
    if (q<n) fread(&a,sizeof(int),1,A);
  }
  while (!feof(B) && r<n)
  {
    fwrite(&b,sizeof(int),1,C);m++;r++;
    if (r<n) fread(&b,sizeof(int),1,B);
  }
  return m;
}
void main(void)
{
  FILE *A,*B,*C,*D,*input,*output;
  int N=0,c,m,p,l;
  // opening needed files (file1.dat must exist)
  input=fopen("1.dat","rb");
  output=fopen("1.srt","wb");
  l=0;
  A=fopen("1.tmp","w+b");
  B=fopen("2.tmp","w+b");
  C=fopen("3.tmp","w+b");
  D=fopen("4.tmp","w+b");
  // reading from source and splitting data into A & B
  while (!feof(input))
  {
    fscanf(input,"%d ",&c);
    fwrite(&c,sizeof(int),1,(N%2==0?A:B));
    N++;
  }
  rewind(A);
  rewind(B);
  p=1;
  while (p<N)
  {
    m=N;
    while (m!=0)
    {
      // uniting splitting and combining
      // here we combine from A and B to C and D
      m-=copy(A,B,C,p);
      m-=copy(A,B,D,p);
    }
    // swap A,B and C,D
    // now we'll combine from C and D and split to A and B
    fclose(A);
    fclose(B);
    fclose(C);
    fclose(D);
    A=fopen((l?"1.tmp":"3.tmp"),"rb");
    B=fopen((l?"2.tmp":"4.tmp"),"rb");
    C=fopen((!l?"1.tmp":"3.tmp"),"wb");
    D=fopen((!l?"2.tmp":"4.tmp"),"wb");
    l=!l;
    // groups will be larger twice
    p*=2;
  }
  fread(&c,sizeof(int),1,A);
  while (!feof(A))
  {
    fprintf(output,"%d ",c);
    fread(&c,sizeof(int),1,A);
  }
  fclose(A);
  fclose(B);
  fclose(C);
  fclose(D);
  fclose(input);
  fclose(output);
}

Natural merge
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
//////////////////////////////////////////////////////////////////////////////
//
//  File sort (natural merge)
//  (c) Johna Smith, 1996
//
//  Method description:
//   This program reads data from file 1.dat and writes sorted data to 1.srt
//   Format of 1.dat: i1 i2 i3 i4 i5 i6 ..., where i(k) is integer
//   It also creates four temporary files: 1.tmp, 2.tmp, 3.tmp
//   We use three files to sort given sequence of data.
//
//   Series - is a sequence of numbers with the following property: a(i)<=a(i+1)
//   1) Divide copy of the given file C into parts A and B, writing first
//      series from C to A, second one to B, third - to C, and so on
//   2) Combine files A and B into C, sorting distributed series
//   3) Repeat first two steps until there is more than one series
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
void main(void)
{
  FILE *A,*B,*C,*input,*output;
  int sorted,a,b,c,old;
  // opening needed files (file1.dat must exist)
  input=fopen("1.dat","rb");
  output=fopen("1.srt","wb");
  A=fopen("1.tmp","w+b");
  B=fopen("2.tmp","w+b");
  C=fopen("3.tmp","w+b");
  // reading from source and copying data into C
  while (!feof(input))
  {
    fscanf(input,"%d ",&c);
    fwrite(&c,sizeof(int),1,C);
  }
  rewind(C);
  do
  {
    // reopeneing files A and B
    fclose(A);
    fclose(B);
    A=fopen("1.tmp","w+b");
    B=fopen("2.tmp","w+b");
    rewind(C);
    // distributing series from C to A and B
    fread(&c,sizeof(int),1,C);
    sorted=1;
    while (!feof(C))
    {
      // series to A
      do
      {
         old=c;
         fwrite(&c,sizeof(int),1,A);
         fread(&c,sizeof(int),1,C);
      } while (!feof(C) && old<=c);
      old=c;
      // series to B
      while (!feof(C) && old<=c)
      {
        old=c;
        fwrite(&c,sizeof(int),1,B);
        fread(&c,sizeof(int),1,C);
        sorted=0; // if there are more than 1 series then sequence isn't sorted
      }
    }
    // reopening file C
    fclose(C);
    C=fopen("3.tmp","w+b");
    rewind(A);
    rewind(B);
    // combining A and B back to C
    fread(&a,sizeof(int),1,A);
    fread(&b,sizeof(int),1,B);
    while (!feof(A) && !feof(B))
    {
      if (a<b)
      {
        old=a;
        fwrite(&a,sizeof(int),1,C);
        fread(&a,sizeof(int),1,A);
        if (feof(A) || a<old)
        do
        {
          old=b;
          fwrite(&b,sizeof(int),1,C);
          fread(&b,sizeof(int),1,B);
        } while(!feof(B) && b>=old);
      } 
      else
      {
        old=b;
        fwrite(&b,sizeof(int),1,C);
        fread(&b,sizeof(int),1,B);
        if (feof(B) || b<old)
        do
        {
          old=a;
          fwrite(&a,sizeof(int),1,C);
          fread(&a,sizeof(int),1,A);
        } while(!feof(A) && a>=old);
      }
    }
    // copying remainder from A (or B) to C
    while (!feof(A))
    {
      fwrite(&a,sizeof(int),1,C);
      fread(&a,sizeof(int),1,A);
    }
    while (!feof(B))
    {
      fwrite(&b,sizeof(int),1,C);
      fread(&b,sizeof(int),1,B);
    }
  } while (!sorted);  // sort until there will be only one series
  // writing sorted sequence
  rewind(C);
  fread(&c,sizeof(int),1,C);
  while (!feof(C))
  {
    fprintf(output,"%d ",c);
    fread(&c,sizeof(int),1,C);
  }
  // closing all opened files
  fclose(A);
  fclose(B);
  fclose(C);
  fclose(input);
  fclose(output);
}

Balanced merge
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
//////////////////////////////////////////////////////////////////////////////
//
//  File sort (balanced merge)
//  (c) Johna Smith, 1996
//
//  Method description:
//   This program reads data from file 1.dat and writes sorted data to 1.srt
//   Format of 1.dat: i1 i2 i3 i4 i5 i6 ..., where i(k) is integer
//   It also creates four temporary files: 1.tmp, 2.tmp, 3.tmp
//   We use N files to sort given sequence of data.
//
//   Series - is a sequence of numbers with the following property: a(i)<=a(i+1)
//   1) Divide copy of the given file C into N files, writing first
//      series from C to F1, second one to F2, third - to F3, and so on
//   2) Combine files F1,F2,F3,...,Fn, sorting distributed series
//   3) Repeat first two steps until there is more than one series
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N   10  // number of temporary files (must be even and greater than 2)
#define Nh  N/2 // must be an integer
struct ExtFile
{
  FILE *F;
  int first; // current element of this file
  char eor; // indicates end of series
};
// this function copies data element from x to y, updating (.first) members
void copy(ExtFile *x, ExtFile *y)
{
  y->first=x->first;
  fwrite(&y->first,sizeof(int),1,y->F);
  fread(&x->first,sizeof(int),1,x->F);
  x->eor=x->first<y->first;
}
void main(void)
{
  FILE *input,*output;
  ExtFile F[N];
  int l,old,j,mx,tx,min,x,t[N],ta[N],k1,k2;
  char name[13];
  // opening needed files (file1.dat must exist)
  input=fopen("1.dat","rb");
  output=fopen("1.srt","wb");
  for (int i=0;i<N;i++)
  {
    gcvt(i,8,name);
    strcat(name,".tmp");
    F[i].F=fopen(name,"w+b");
    F[i].eor=0;
  }
  // distributing given data
  j=Nh;
  l=0;
  fscanf(input,"%d ",&x);
  while (!feof(input))
  {
    if (j<Nh-1) j++; else j=0;
    do
    {
      old=x;
      fwrite(&x,sizeof(int),1,F[j].F);
      fscanf(input,"%d ",&x);
    } while (!feof(input) && x>=old);
    l++;
  }
  if (x<old)
  {
    if (j<Nh-1) j++; else j=0;
    l++;
  }
  fwrite(&x,sizeof(int),1,F[j].F);
  for (i=0;i<N;i++) t[i]=i;
  do
  {
    // merging t[0]..t[Nh-1] to t[Nh]..t[N-1]
    if(l<Nh) k1=l-1; else k1=Nh-1;
    for(i=0;i<=k1;i++)
    {
      rewind(F[t[i]].F);
      ta[i]=t[i];
      fread(&F[t[i]].first,sizeof(int),1,F[t[i]].F);
    }
    l=0; // number of input series
    j=Nh; // index of input sequence
    // merging input series to t[j]
    do
    {
      l++;
      k2=k1;
      // selecting minimal element from F1..Fn
      do
      {
        i=1;
        mx=0;
        min=F[ta[0]].first;
        while (i<=k2)
        {
          x=F[ta[i]].first;
          if(x<min)
          {
            min=x;
            mx=i;
          }
          i++;
        }
        copy(&F[ta[mx]],&F[t[j]]);
        if (feof(F[ta[mx]].F))
        {
          // excluding file
          fclose(F[ta[mx]].F);
          gcvt(ta[mx],8,name);
          strcat(name,".tmp");
          F[ta[mx]].F=fopen(name,"w+b");
          F[ta[mx]].eor=0;
          ta[mx]=ta[k2];
          ta[k2]=ta[k1];
          k1--;
          k2--;
        } else
        if (F[ta[mx]].eor)
        {
          // closing series
          tx=ta[mx];
          ta[mx]=ta[k2];
          ta[k2]=tx;
          k2--;
        }
      } while(k2>=0);
      if(j<N-1) j++; else j=Nh;
    } while(k1>=0);
    for(i=0;i<Nh;i++)
    {
      tx=t[i];
      t[i]=t[i+Nh];
      t[i+Nh]=tx;
    }
  } while (l!=1);
  // writing sorted sequence
  rewind(F[0].F);
  fread(&x,sizeof(int),1,F[0].F);
  while (!feof(F[0].F))
  {
    fprintf(output,"%d ",x);
    fread(&x,sizeof(int),1,F[0].F);
  }
  // closing all opened files
  for (i=0;i<N;i++) fclose(F[i].F);
  fclose(input);
  fclose(output);
}

Polyphase merge
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
//////////////////////////////////////////////////////////////////////////////
//
//  File sort (polyphase merge)
//  (c) Johna Smith, 1996
//
//  Method description:
//   This program reads data from file 1.dat and writes sorted data to 1.srt
//   Format of 1.dat: i1 i2 i3 i4 i5 i6 ..., where i(k) is integer
//   It also creates four temporary files: 1.tmp, 2.tmp, 3.tmp
//   We use N files to sort given sequence of data.
//
//   Series - is a sequence of numbers with the following property: a(i)<=a(i+1)
//   1) Divide copy of the given file C into N-1 files, writing first
//      series from C to F1, second one to F2, third - to F3, and so on
//   2) Combine series from files F1,F2,F3,...,F(n-1) to Fn,
//      sorting distributed series
//   3) When we reach the end of one of F1..F(n-1) files we turn sequences
//      and will combine series to this new empty file. For example if we reach
//      end of F3 we will gather data from F1,F2,F4,..Fn to F3
//   4) Repeat first three steps until there is more than one series
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define N   6  // number of temporary files (must be greater than 2)
struct ExtFile
{
  FILE *F;
  int first; // current element of this file
  char eor; // indicates end of series
};
  FILE *output;
  ExtFile input;
  ExtFile F[N];  // array of files
  int level,i,j,k,mx,tx,xmin,x,t[N],ta[N],a[N],d[N],z,tn,dn;
  char name[13];
// this functions sets new value of variable j
// on the next step of data distribution we'll write to sequence #j
void select(void)
{
  if (d[j]<d[j+1]) j++;  // d[j] shows number of series in sequence #j
  else
  {
    if (d[j]==0)
    {
      level++;
      z=a[0];
      for (int i=0;i<N-1;i++)
      {
        d[i]=z+a[i+1]-a[i];
        a[i]=z+a[i+1];
      }
    }
    j=0;
  }
  d[j]--;
}
// this function copies data element from x to y, updating (.first) members
void copy(ExtFile *x, ExtFile *y)
{
  y->first=x->first;
  fwrite(&y->first,sizeof(int),1,y->F);
  fread(&x->first,sizeof(int),1,x->F);
  x->eor=(x->first<y->first || feof(x->F));
}
// this function copies series from input to f[j]
void copyrun(void)
{
  do
  {
    F[j].first=input.first;
    fwrite(&F[j].first,sizeof(int),1,F[j].F);
    fscanf(input.F,"%d",&input.first);
    input.eor=input.first<F[j].first;
  } while (!input.eor && !feof(input.F));
  if (feof(input.F))
  {
    if (input.first<F[j].first) select();
    F[j].first=input.first;
    fwrite(&F[j].first,sizeof(int),1,F[j].F);
    d[j]++;
  }
}
void main(void)
{
  // opening required files (file 1.dat must exist)
  input.F=fopen("1.dat","rb");
  fscanf(input.F,"%d ",&input.first);
  F[t[N-1]].eor=0;
  output=fopen("1.srt","wb");
  for (int i=0;i<N-1;i++)
  {
    gcvt(i,8,name);
    strcat(name,".tmp");
    F[i].F=fopen(name,"w+b");
    fread(&F[i].first,sizeof(int),1,F[i].F);
    F[i].eor=0;
    a[i]=1;
    d[i]=1;
  }
  // initializing variables
  level=1;
  j=0;
  a[N-1]=0;
  d[N-1]=0;
  // distributing data from input to first N-1 sequences
  do
  {
    select();
    copyrun();
  } while (!feof(input.F) && j!=N-2);
  while (!feof(input.F))
  {
    select();
    if (F[j].first<=input.first)
    {
      copyrun();
      if (feof(input.F)) d[j]++; else copyrun();
    } else copyrun();
  }
  // preparing first N-1 series for reading
  for (i=0;i<N-1;i++)
  {
    t[i]=i;
    rewind(F[i].F);
    fread(&F[i].first,sizeof(int),1,F[i].F);
    F[i].eor=0;
  }
  t[N-1]=N-1;
  // main loop
  do
  {
    // gathering data from t[0]..t[N-2] into t[N-1]
    z=a[N-2];
    d[N-1]=0;
    // preparing file to write
    fclose(F[t[N-1]].F);
    gcvt(t[N-1],8,name);
    strcat(name,".tmp");
    F[t[N-1]].F=fopen(name,"w+b");
    F[t[N-1]].eor=0;
    do
    {
      // gathering one series
      k=-1;
      for (i=0;i<N-1;i++)
      {
        if (d[i]>0) d[i]--;
        else
        {
          k++;
          ta[k]=t[i];
        }
      }
      if (k==-1) d[N-1]++;
      else
      {
        // gathering one real series from t[0]..t[k] into t[N-1]
        do
        {
          i=0;
          mx=0;
          xmin=F[ta[i]].first;
          // selecting series with minimal element to place it first
          while (i<k)
          {
            i++;
            x=F[ta[i]].first;
            if (x<xmin)
            {
              xmin=x;
              mx=i;
            }
          }
          // copying smallest element to output series
          copy(&F[ta[mx]],&F[t[N-1]]);
          // if we reach the end of the current input sequence
          // or end of series in it then close this source
          if (F[ta[mx]].eor)
          {
            // closing this source
            ta[mx]=ta[k];
            k--;
          }
        } while (k!=-1);
      }  
      z--;
    } while (z!=0);
    // swapping sequences
    rewind(F[t[N-1]].F);
    fread(&F[t[N-1]].first,sizeof(int),1,F[t[N-1]].F);
    F[t[N-1]].eor=0;
    tn=t[N-1];
    dn=d[N-1];
    z=a[N-2];
    for(i=N-1;i>0;i--)
    {
      t[i]=t[i-1];
      d[i]=d[i-1];
      a[i]=a[i-1]-z;
    }
    t[0]=tn;
    d[0]=dn;
    a[0]=z;
    // preparing file F[t[N-1]] to write
    fclose(F[t[N-1]].F);
    gcvt(t[N-1],8,name);
    strcat(name,".tmp");
    F[t[N-1]].F=fopen(name,"w+b");
    F[t[N-1]].eor=0;
    level--;
  } while (level!=0); // while there are more than one series
  // writing sorted sequence from F[t[0]]
  rewind(F[t[0]].F);
  fread(&x,sizeof(int),1,F[t[0]].F);
  while (!feof(F[t[0]].F))
  {
    fprintf(output,"%d ",x);
    fread(&x,sizeof(int),1,F[t[0]].F);
  }
  // closing all opened files
  for (i=0;i<N;i++) fclose(F[i].F);
  fclose(input.F);
  fclose(output);
}


Методы поиска

Binary search in sorted string
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//////////////////////////////////////////////////////////////////////////////
//
//  Binary search in sorted string
//  (c) Johna Smith, 1996
//
//  Method description:
//     1) Split string into two parts
//     2) If the middle symbol of the string is greater than searched one -
//        select left part else select right part
//     3) Split selected part into two parts (see 1)
//   When in the selected part will be only one symbol compare it with
//   searched one.
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
char string[]="0245789AAABDFHJKLXYZ"; // sorted ASCIIZ string
char symbol='J'; // symbol to find
unsigned int left,right; // bounds of the area where we search
unsigned int middle; // center of the area where we search
unsigned int length=sizeof(string)/sizeof(char); // string length
void main(void)
{
  printf("String: %s\n",string);
  left=0;
  right=length-1;
  // Here we avoid checking condition 'string[middle]==symbol'
  // because maximum number of steps is log N (where N is length
  // of the string) and some auxulary steps will be more effective
  // than comparing elements each step.
  while (left<right)
  {
    middle=(left+right)/2;
    if (string[middle]<symbol) left=middle+1; else right=middle;
  }
  // We'll stop when left==right => if there is searched symbol in
  // the string both bounds will point at it
  if (string[right]==symbol) printf("Symbol '%c' found at position %d.",symbol,right+1);
  else printf("Symbol '%c' not found.",symbol);
}

Substring search. Boyer-Moore algorithm
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//////////////////////////////////////////////////////////////////////////////
//
//  Substring search. Boyer-Moore algorithm
//  (c) Johna Smith, 1996
//
//  Method description:
//    1) Build auxulary array D. D contains 256 elements (it's
//    amount of symbols in ASCII table. D(i) equals to length
//    of the substring if it doesn't contain character with code i.
//    And if substring contains character with code i then D(i)
//    equals to the distance between end of string and position of
//    this character closest to the end of string.
//    2) Scan string from the start, comparing it with the substring
//    If diferrence found we can skip next d(string(i)) positions,
//    where string(i) is the code of i-th character of the string and
//    i is the current position in the string.
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
char string[]="Unsorted string. ABCBBCBCA."; // ASCIIZ string
char substring[]="string"; // substring to find
const unsigned int string_length=sizeof(string)/sizeof(char)-1; // string length
const unsigned int substring_length=sizeof(substring)/sizeof(char)-1; // substring length
int i,j,k;
int d[256]; // auxulary array
void main(void)
{
  printf("String: %s\n",string);
  // Analysing substring, building array d
  for (int i=0;i<256;i++) d[i]=substring_length;
  for (i=0;i<substring_length-1;i++) d[substring[i]]=substring_length-i-1;
  // Searching
  i=substring_length;
  do
  {
    j=substring_length; k=i;
    do // search difference between string and substring
    {
      k--;
      j--;
    } while (j>=0 && string[k]==substring[j]);
    i+=d[string[i-1]]; // skip next d(string(i)) positions
  } while (j>=0 && i<string_length);
  // condition j<0 means that substring is found
  if (j<0) printf("Substring \"%s\" found.",substring);
  else printf("Substring \"%s\" not found.",substring);
}

Linear substring search
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//////////////////////////////////////////////////////////////////////////////
//
//  Linear substring search
//  (c) Johna Smith, 1996
//
//  Method description:
//    Simple search method.
//    1) Compare string and substring from first symbol of the string
//    2) If difference found compare string and substring from
//       second symbol of the string
//    Repeat these steps until no differencies found or end of string reached
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
char string[]="Unsorted string"; // ASCIIZ string
char substring[]="ring"; // substring to find
unsigned int position; // comparing from this position of the string
unsigned int subposition; // compared position of the substring
unsigned int string_length=sizeof(string)/sizeof(char); // string length
unsigned int substring_length=sizeof(substring)/sizeof(char); // substring length
void main(void)
{
  printf("String: %s\n",string);
  position=0;
  // finish compare when all symbols of substring compared (substring found)
  // or there left less than substring_length uncompared symbols
  // in the string (substring not found)
  while (subposition!=substring_length && position!=string_length-substring_length+1)
  {
    subposition=0; // comparing from the beginning of the substring
    while (subposition<substring_length &&
              string[position+subposition]==substring[subposition])
      subposition++;
    // compare from next position of the string
    position++;
  }
  if (subposition==substring_length) printf("Substring \"%s\" found from position %d.",substring,position);
  else printf("Substring \"%s\" not found.",substring);
}

Substring search. Knuth-Morris-Pratt algorithm
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
//////////////////////////////////////////////////////////////////////////////
//
//  Substring search. Knuth-Morris-Pratt algorithm
//  (c) Johna Smith, 1996
//
//  Method description:
//    1) Build auxulary array D. D contains "substring_length" elements.
//    D(i) equals to the length of longest sequence of characters
//    of the substring with such properties:
//         ss(0)..ss(d(i)-1)==ss(i-d(i))..p(i-1);  (ss is a substring)
//         p(d(i))!=p(i);
//    2) Scan string from the start, comparing it with the substring
//    If diferrence found we can skip next d(string(i)) positions,
//    where string(i) is the code of i-th character of the string and
//    i is the current position in the string.
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
char string[]="Unsorted string. ABCBBCBCA."; // ASCIIZ string
char substring[]="BCB"; // substring to find
const unsigned int string_length=sizeof(string)/sizeof(char)-1; // string length
const unsigned int substring_length=sizeof(substring)/sizeof(char)-1; // substring length
int i,j,k;
int d[substring_length]; // auxulary array
void main(void)
{
  printf("String: %s\n",string);
  // Analysing substring, building array d
  j=0; k=-1; d[0]=-1;
  while (j<substring_length-1)
  {
    while (k>=0 && substring[j]!=substring[k]) k=d[k];
    j++; k++;
    if (substring[j]==substring[k]) d[j]=d[k]; else d[j]=k;
  }
  // Searching
  i=j=k=0;
  while (j<substring_length && i<string_length)
  {
    // here j is the current position in the substring and i is
    // the current position in the string
    while (j>=0 && string[i]!=substring[j]) j=d[j]; //skip next d[j] positions
    i++; j++;
  }
  // Condition j==substring length means that substring is found
  if (j==substring_length) printf("Substring \"%s\" found.",substring);
  else printf("Substring \"%s\" not found.",substring);
}

Linear search in the string
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//////////////////////////////////////////////////////////////////////////////
//
//  Linear search
//  (c) Johna Smith, 1996
//
//  Method description:
//    Simple search method. Take first element - if it is what we
//   need - stop searh else take next element.
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
char string[]="Unsorted string"; // ASCIIZ string
char symbol='d'; // symbol to find
char *p;
unsigned int position; // position of the found symbol
unsigned int length=sizeof(string)/sizeof(char); // string length
void main(void)
{
  printf("String: %s\n",string);
  // changing last (terminating) symbol of the string
  // to the symbol that we search allows us to avoid
  // checking condition 'end of string' - we always
  // will find symbol in the modified string
  string[length-1]=symbol;
  for (p=string,position=1;*p!=symbol;p++,position++);
  string[length-1]='\0'; //restoring last symbol
  
  if (position!=length) printf("Symbol '%c' found at position %d.",symbol,position);
  else printf("Symbol '%c' not found.",symbol);
}


Матрицы

Определитель
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
//////////////////////////////////////////////////////////////////////////////
//
//  Calculating det A, where A is matrix N x N
//  (c) Johna Smith, 1996
//
//  Method description:
//    This method based on two statements:
//    1) det A = a11, if A is matrix 1 x 1
//    2) |a11 a12 a13 ... a1n|                       |a11 a12 .. a1(i-1) a1(i+1) .. a1n |
//       |a21 a22 a23 ... a2n|    n     i+1          |a21 a22 .. a2(i-1) a2(i+1) .. a2n |
// det A=|a31 a32 a33 ... a3n| = SUM (-1)  a1i * det |a31 a32 .. a3(i-1) a3(i+1) .. a3n |
//       |...................|   i=1                 |................................  |
//       |...................|                       |an1 an2 .. an(i-1) an(i+1) .. ann |
//       |an1 an2 an3 ... ann|
//
//////////////////////////////////////////////////////////////////////////////
#include <stdio.h>
#include <alloc.h>
#define N       5  // matrix size
int matrix[N][N]={{1,2,3,4,5},{2,1,3,4,5},{3,2,1,4,5},{4,3,2,1,5},{5,4,3,2,1}};
void show_matrix(int *matrix, int size) // this functions displays matrix
{
 for(int i=0;i<size;i++)
 {
   for(int j=0;j<size;j++)
     printf("%d ",*(matrix+i*size+j));
   printf("\n");
 }
 printf("\n");
}
int Det(int *matrix, int const size)
{
  int *submatrix;
  int det=0;
  if (size>1)
  {
    submatrix=(int *)malloc(sizeof(int)*(size-1)*(size-1));
    for (int i=0;i<size;i++)
    {
      // creating new array (submatrix)
      for (int j=0;j<size-1;j++)
        for (int k=0;k<size-1;k++)
          *(submatrix+j*(size-1)+k)=*(matrix+(j+1)*size+(k<i?k:k+1));
      // calling recursively function Det using submatrix as a parameter
      // and adding the result to final value
      det+=*(matrix+i)*(i/2.0==i/2?1:-1)*Det(submatrix,size-1);
    }
    free(submatrix);
  } else det=*matrix;
  return det;
}
void main(void)
{
  // show given matrix
  show_matrix(matrix[0],N);
  // calculating determinante and displaying the result
  printf("det A = %d",Det(matrix[0],N));
}

Обращение
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//////////////////////////////////////////////////////////////////////////////
//
//  Matrix operations (inversion)
//  (c) Johna Smith, 1996
//
//  Given: A (N x N), det A != 0                 -1
//  This algorithm inverts matrix A and returns A  .
//      -1
//   A*A  = E
//  We simply convert matrix A into matrix E, and do the same operations
//  over matrix B (initially B=E). Finally A=E, B=A^(-1).
//
//////////////////////////////////////////////////////////////////////////////
#define N               3
#include <stdio.h>
float a[N][N]={{4,8,0},{8,8,8},{2,0,1}};
void Invert(float *matrix)
{
  float e[N][N];
  // initializing matrix e
  for (int i=0;i<N;i++)
    for (int j=0;j<N;j++)
      e[i][j]=(i==j?1:0);
  // converting matrix to e
  for(i=0;i<N;i++)
  {
    // normalizing row (making first element =1)
    float tmp=*(matrix+i*N+i);
    for(int j=N-1;j>=0;j--)
    {
      e[i][j]/=tmp;
      *(matrix+i*N+j)/=tmp;
    }
    // excluding i-th element from each row except i-th one
    for(j=0;j<N;j++)
      if (j!=i)
      {
        tmp=*(matrix+j*N+i);
        for(int k=N-1;k>=0;k--)
        {
          e[j][k]-=e[i][k]*tmp;
          *(matrix+j*N+k)-=*(matrix+i*N+k)*tmp;
        }
      }
  }
  // now e contains inverted matrix so we need only to copy e to matrix
  for(i=0;i<N;i++)
    for(int j=0;j<N;j++)
      *(matrix+i*N+j)=e[i][j];
}
void show_matrix(float *matrix) // this functions displays matrix
{
 for(int i=0;i<N;i++)
 {
   for(int j=0;j<N;j++)
     printf("%f ",*(matrix+i*N+j));
   printf("\n");
 }
 printf("\n");
}
void main(void)
{
  // display matrix A
  show_matrix(a[0]);
  // Invert it
  Invert(a[0]);
  // display the inverted matrix
  show_matrix(a[0]);
  // Invert it again
  Invert(a[0]);
  // display the inversion of the inverted matrix
  show_matrix(a[0]);
}

Сложение
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//////////////////////////////////////////////////////////////////////////////
//
//  Matrix operations (addition)
//  (c) Johna Smith, 1996
//
//  Given: A,B - matrixes M x N
//  This algorithm sum these matrixes and display the result.
//
//////////////////////////////////////////////////////////////////////////////
#define M    5
#define N    6
#include <stdio.h>
int a[N][M]={{1,2,3,4,5},{5,4,3,2,1},{1,2,3,4,5},{5,4,3,2,1},{1,2,3,4,5},{0,1,0,1,0}};
int b[N][M]={{5,4,3,2,1},{1,2,3,4,5},{5,4,3,2,1},{1,2,3,4,5},{5,4,3,2,1},{1,0,1,0,1}};
int c[N][M];
void show_matrix(int *matrix) // this functions displays matrix
{
 for(int i=0;i<N;i++)
 {
    for(int j=0;j<M;j++)
      printf("%d ",*(matrix+i*M+j));
    printf("\n");
 }
 printf("\n");
}
void main(void)
{
  // display matrixes A and B
  show_matrix(a[0]);
  show_matrix(b[0]);
  // sum these matrixes
  for(int i=0;i<N;i++)
    for(int j=0;j<M;j++)
      c[i][j]=a[i][j]+b[i][j];
  // display the sum
  show_matrix(c[0]);
}

Умножение
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//////////////////////////////////////////////////////////////////////////////
//
//  Matrix operations (multiplication)
//  (c) Johna Smith, 1996
//
//  Given: A (M x N) and B (N x P)
//  This algorithm multiplies these matrixes and display the result.
//
//////////////////////////////////////////////////////////////////////////////
#define M     3
#define N     4
#define P     2
#include <stdio.h>
int a[M][N]={{2,0,3,1},{5,1,2,0},{0,0,4,1}};
int b[N][P]={{1,3},{2,1},{4,0},{3,5}};
int c[M][P];
void show_matrix(int *matrix, int n, int m) // this functions displays matrix
{
 for(int i=0;i<n;i++)
 {
   for(int j=0;j<m;j++)
     printf("%d ",*(matrix+i*m+j));
   printf("\n");
 }
 printf("\n");
}
void main(void)
{
  // display matrixes A and B
  show_matrix(a[0],M,N);
  show_matrix(b[0],N,P);
  // substract these matrixes
  for(int i=0;i<M;i++)
    for(int j=0;j<P;j++)
    {
      c[i][j]=0;
      for (int k=0;k<N;k++) c[i][j]+=a[i][k]*b[k][j];
    }
  // display the difference
  show_matrix(c[0],M,P);
}
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru