Алгоритмизация и программирование. Язык C++

Слайд 2

Решето Эратосфена

Эратосфен Киренский (Eratosthenes, Ερατοσθδνη) (ок. 275-194 до н.э.)

Новая версия – решето Аткина.

Решето Эратосфена Эратосфен Киренский (Eratosthenes, Ερατοσθδνη) (ок. 275-194 до н.э.) Новая версия
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Алгоритм:
начать с k = 2
«выколоть» все числа через k, начиная с 2·k
перейти к следующему «невыколотому» k
если k <= N , то перейти к шагу 2
напечатать все числа, оставшиеся «невыколотыми»

высокая скорость, количество операций

нужно хранить в памяти все числа от 1 до N

O((N·log N)·log log N )

2

3

k·k

k·k <= N

Слайд 3

Решето Эратосфена

Задача. Вывести все простые числа от 2 до N.

Объявление переменных:

const int

Решето Эратосфена Задача. Вывести все простые числа от 2 до N. Объявление
N = 100;
bool A[N+1];
int i, k;

Сначала все невычеркнуты:

for ( i = 2; i <= N; i++ )
A[i] = true;

выделяем на 1 элемент больше, чтобы начать с A[1]

Слайд 4

Решето Эратосфена

Вычёркивание непростых:

k = 2;
while ( k*k <= N ) {
if

Решето Эратосфена Вычёркивание непростых: k = 2; while ( k*k if (
( A[k] ) {
i = k*k;
while ( i <= N )
{
A[i] = false;
i += k;
}
}
k ++;
}

Слайд 5

Решето Эратосфена

Вывод результата:

for ( i = 2; i <= N; i++ )

Решето Эратосфена Вывод результата: for ( i = 2; i if ( A[i] ) cout
if ( A[i] )
cout << i << " ";

Слайд 6

Наибольший общий делитель (GCD)

gcd⁡(?,?): наибольшее целое число делящее нацело ? и

Наибольший общий делитель (GCD) gcd⁡(?,?): наибольшее целое число делящее нацело ? и
?
Используется очень часто в различных теоретических проблемах
Несколько фактов:
gcd(?,?)=gcd⁡(?,?−?)
gcd(?,0)=?
gcd⁡(?,?) наименьшее положительное число в {??+??⁡|⁡?,?∈?}

Слайд 7

Алгоритм Евклида

Повторение gcd(?,?)=gcd⁡(?,?−?)
gcd(1989,867) =
gcd(1989−2×867,867) =
gcd(255,867) =
gcd(255,867−3×255) =
gcd(255,102) =
gcd(255−2×102,102) =
gcd(51,102) =
gcd(51,102−2×51)

Алгоритм Евклида Повторение gcd(?,?)=gcd⁡(?,?−?) gcd(1989,867) = gcd(1989−2×867,867) = gcd(255,867) = gcd(255,867−3×255) =
=
gcd(51,0) =51
Имя файла: Алгоритмизация-и-программирование.-Язык-C++.pptx
Количество просмотров: 43
Количество скачиваний: 0