ПЯВУ. Основы программирования. Лекция 8. Алгоритм Евклида. “Решето” Эратосфена

Сентябрь 7, 2022

Главная
Алгебра
ПЯВУ. Основы программирования. Лекция 8. Алгоритм Евклида. “Решето” Эратосфена

Содержание

2. Контрольные вопросы Что означает термин “Сортировка” в информатике? Зачем применяется сортировка? От чего и как зависит
3. Содержание Алгоритм поиска НОД (алгоритм Евклида) Алгоритмы задач по простым числам (“решето” Эратосфена) Подсчет количества единиц
4. Контрольные упражнения. Целые int n = 1, i = 0; while (n != 0) { i++;
5. Контрольные упражнения. Целые Что изменится, если заменить != на >? int n = 1, i =
6. Контрольные упражнения. Числа с плавающей запятой (точкой) double b = 1, eps = 1; int i
7. Контрольные упражнения. Числа с плавающей запятой* double b = 1; int i = 0; while (b
8. Алгоритм вычисления НОД. (Алгоритм Евклида) Наибольший Общий Делитель двух натуральных чисел (x, y). Если x ==
9. Алгоритм Евклида while (x != y) { if (x > y) x -= y; else y
10. Выяснить, является ли число простым // Входные данные – N bool isPrimary = true; // Пока
11. Алгоритм поиска простых чисел меньших натурального N “Решето Эратосфена” 1, 2, 3, 4, 5, 6, 7,
12. Алгоритм поиска простых чисел меньших натурального N int N = 5; bool[] prim = new bool[N
13. Контрольные вопросы Какую задачу решают: Алгоритм подсчета количества (элементов, удовлетворяющих условию); Алгоритм нахождения суммы (элементов); Алгоритм
14. Подсчет количества 1 в байте //Входные данные byte x int N = 0; for (int i
15. Подсчет количества 1 в байте //Входные данные byte x int N = 0; for (int i
16. Как посчитать количество 1 в целом? Массив целых займет всю память. Загрузка программы будет очень долгой.
17. Как посчитать количество 1 в целом? int [] n = new int[256]{0,1,1,2,1,2,2,3,…}; uint x = ….
18. Как посчитать количество 1 в целом? Оптимизация int [] n = new int[256]{0,1,1,2,1,2,2,3,…}; uint x =
19. Отладка программ Вывод промежуточных контрольных значений Средства Visual Studio: Точки остановки Выполнение до следующей точки остановки
20. Отладка программ. Вывод контрольных значений Console.WriteLine(…); Преимущества: Универсальность Недостатки: Нужно изменять текст программы Если выведено много,
21. Отладка программ. Точки остановки Добавление и удаление точки остановки
22. Отладка программ. Пошаговое исполнение F5 – начать исполнение программы и остановиться в первой точке остановки. F10
23. Отладка программ. Контрольные значения Добавление: Выделить в тексте программы, когда она остановлена в одной из точек
25. Скачать презентацию

Слайд 2

Контрольные вопросы
Что означает термин “Сортировка” в информатике?
Зачем применяется сортировка?
От чего и

как зависит количество операций при сортировке пузырьком?

Слайд 3

Содержание
Алгоритм поиска НОД (алгоритм Евклида)
Алгоритмы задач по простым числам (“решето” Эратосфена)
Подсчет

количества единиц в байте
Приемы отладки программ

Слайд 4

Контрольные упражнения. Целые
int n = 1, i = 0;
while (n !=

0)
{
i++;
n <<= 1;
}
Console.WriteLine(i);
Что означает операция <<=? Опишите действия в теле цикла.
Что делает эта программа? Почему цикл закончится?
Что означает число, которое будет выведено на консоль программой?
Чему оно будет равно?

Слайд 5

Контрольные упражнения. Целые
Что изменится, если заменить != на >?
int n =

1, i = 0;
while (n > 0) // Было !=
{
i++;
n <<= 1;
}
Console.WriteLine(i);

Слайд 6

Контрольные упражнения. Числа с плавающей запятой (точкой)
double b = 1, eps

= 1;
int i = 0;
while (b != b+eps)
{
i++;
eps /= 2;
}
Console.WriteLine(i);
Опишите действия в теле цикла программы?
Почему цикл закончится?
Что означает появившееся число?

Слайд 7

Контрольные упражнения. Числа с плавающей запятой*
double b = 1;
int i =

0;
while (b != b*2)
{
i++;
b *= 2;
}
Console.WriteLine(i);
Опишите действия в теле цикла программы?
Почему цикл закончится?
Что означает появившееся число?

Слайд 8

Алгоритм вычисления НОД. (Алгоритм Евклида)
Наибольший Общий Делитель двух натуральных чисел (x,

y).
Если x == y, то NOD(x, y)==x==y.
Если x > y, то NOD (x, y) == NOD (x-y, y)
Если x < y, то NOD (x, y) == NOD (x, y-x)
Уменьшая большее из чисел на меньшее, мы обязательно придем к п. 1.

Слайд 9

Алгоритм Евклида
while (x != y)
{
if (x > y)
x -=

y;
else
y -= x;
}
Почему нельзя:
while (x != y)
{
if (x > y)
x %= y;
else
y %= x;
}
?

Слайд 10

Выяснить, является ли число простым
// Входные данные – N
bool isPrimary =

true; // Пока считаем, что делителей нет
for (int i = 2; i < N; i++) // Лучше i <= Math.Sqrt(N)
{
if (N % i == 0)
{
isPrimary = false;
break;
}
}

Слайд 11

Алгоритм поиска простых чисел меньших натурального N
“Решето Эратосфена”
1, 2, 3, 4,

5, 6, 7, 8, 9, 10, 11, 12, 13
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13

Слайд 12

Алгоритм поиска простых чисел меньших натурального N
int N = 5;
bool[] prim

= new bool[N + 1]; // Где алгоритм?
for (int i = 0; i < prim.Length; i++)
prim[i] = true;
for (int i = 2; i < prim.Length; i++)
{
if (prim[i])
for (int j = 2 * i; j < prim.Length; j += i)
prim[j] = false;
}
for (int i = 2; i < prim.Length; i++)
if (prim[i])
Console.Write("{0},", i);

Слайд 13

Контрольные вопросы
Какую задачу решают:
Алгоритм подсчета количества (элементов, удовлетворяющих условию);
Алгоритм нахождения суммы

(элементов);
Алгоритм поиска наибольшего/наименьшего;
Алгоритм вычисления среднего арифметического;
Алгоритм поиска условно наибольшего/наименьшего;
Алгоритм вычисления условной суммы;
Алгоритм поиска заданного элемента массива;
Алгоритм подсчета количества слов в строке;
Алгоритм сортировки массива;
Алгоритм поиска НОД;
Решето Эратосфена;

Слайд 14

Подсчет количества 1 в байте
//Входные данные byte x
int N = 0;
for

(int i = 1; i < 255; i *= 2) // i <<=1;
{
if ((i & x) != 0)
N++;
}

Слайд 15

Подсчет количества 1 в байте
//Входные данные byte x
int N = 0;
for

(int i = 1; i < 255; i *= 2) // i <<=1;
{
if ((i & x) != 0)
N++;
}
//Быстрее:
int [] n = new int[256]{0,1,1,2,1,2,2,3,…};
int N = n[x];

Слайд 16

Как посчитать количество 1 в целом?
Массив целых займет всю память.
Загрузка

программы будет очень долгой.
Заранее вычислить все значения не представляется возможным

Слайд 17

Как посчитать количество 1 в целом?
int [] n = new int[256]{0,1,1,2,1,2,2,3,…};
uint

x = ….
int N = 0;
byte t = (byte) x;
N += n[t];
t = (byte)(x>>8);
N += n[t];
t = (byte)(x >> 16);
N += n[t];
t = (byte)(x >> 24);
N += n[t];

Слайд 18

Как посчитать количество 1 в целом? Оптимизация
int [] n = new int[256]{0,1,1,2,1,2,2,3,…};
uint

x = ….
int N = 0;
while(x != 0)
{
N += n[(byte)(x)];
x >>=8;
}

Слайд 19

Отладка программ
Вывод промежуточных контрольных значений
Средства Visual Studio:
Точки остановки
Выполнение до следующей точки

остановки (F5)
Наблюдаемые величины (контрольные значения)
Пошаговое исполнение (F10)
Переход к исполнению метода (F11)

Слайд 20

Отладка программ. Вывод контрольных значений
Console.WriteLine(…);
Преимущества:
Универсальность
Недостатки:
Нужно изменять текст программы
Если выведено много, то трудно

понять
Если нужно посмотреть дополнительную информацию, то придется изменить программу и выполнить заново.

Слайд 21

Отладка программ. Точки остановки
Добавление и удаление точки остановки

Слайд 22

Отладка программ. Пошаговое исполнение
F5 – начать исполнение программы и остановиться в первой

точке остановки. F10 – переход к следующей команде.

Слайд 23

Отладка программ. Контрольные значения
Добавление:
Выделить в тексте программы, когда она остановлена в одной

из точек остановки, любое выражение и через контекстное меню указать: “Добавить контрольное значение”
Удаление:
В окне контрольных значений удалить ненужные значения

ПЯВУ. Основы программирования. Лекция 8. Алгоритм Евклида. “Решето” Эратосфена

Содержание

Контрольные вопросыЧто означает термин “Сортировка” в информатике?Зачем применяется сортировка?От чего и

СодержаниеАлгоритм поиска НОД (алгоритм Евклида)Алгоритмы задач по простым числам (“решето” Эратосфена)Подсчет

Контрольные упражнения. Целыеint n = 1, i = 0;while (n !=

Контрольные упражнения. ЦелыеЧто изменится, если заменить != на >?int n =

Контрольные упражнения. Числа с плавающей запятой (точкой)double b = 1, eps

Контрольные упражнения. Числа с плавающей запятой*double b = 1;int i =

Алгоритм вычисления НОД. (Алгоритм Евклида)Наибольший Общий Делитель двух натуральных чисел (x,

Алгоритм Евклидаwhile (x != y){ if (x > y) x -=

Выяснить, является ли число простым// Входные данные – Nbool isPrimary =

Алгоритм поиска простых чисел меньших натурального N“Решето Эратосфена”1, 2, 3, 4,

Алгоритм поиска простых чисел меньших натурального Nint N = 5;bool[] prim

Контрольные вопросыКакую задачу решают:Алгоритм подсчета количества (элементов, удовлетворяющих условию);Алгоритм нахождения суммы

Подсчет количества 1 в байте//Входные данные byte xint N = 0;for

Подсчет количества 1 в байте//Входные данные byte xint N = 0;for

Как посчитать количество 1 в целом?Массив целых займет всю память. Загрузка

Как посчитать количество 1 в целом?int [] n = new int[256]{0,1,1,2,1,2,2,3,…};uint

Как посчитать количество 1 в целом? Оптимизацияint [] n = new int[256]{0,1,1,2,1,2,2,3,…};uint

Отладка программВывод промежуточных контрольных значенийСредства Visual Studio:Точки остановкиВыполнение до следующей точки

Отладка программ. Вывод контрольных значенийConsole.WriteLine(…);Преимущества:УниверсальностьНедостатки:Нужно изменять текст программыЕсли выведено много, то трудно

Отладка программ. Точки остановкиДобавление и удаление точки остановки

Отладка программ. Пошаговое исполнениеF5 – начать исполнение программы и остановиться в первой

Отладка программ. Контрольные значенияДобавление:Выделить в тексте программы, когда она остановлена в одной

Похожие презентации

Контрольные вопросы
Что означает термин “Сортировка” в информатике?
Зачем применяется сортировка?
От чего и

Содержание
Алгоритм поиска НОД (алгоритм Евклида)
Алгоритмы задач по простым числам (“решето” Эратосфена)
Подсчет

Контрольные упражнения. Целые
int n = 1, i = 0;
while (n !=

Контрольные упражнения. Целые
Что изменится, если заменить != на >?
int n =

Контрольные упражнения. Числа с плавающей запятой (точкой)
double b = 1, eps

Контрольные упражнения. Числа с плавающей запятой*
double b = 1;
int i =

Алгоритм вычисления НОД. (Алгоритм Евклида)
Наибольший Общий Делитель двух натуральных чисел (x,

Алгоритм Евклида
while (x != y)
{
if (x > y)
x -=

Выяснить, является ли число простым
// Входные данные – N
bool isPrimary =

Алгоритм поиска простых чисел меньших натурального N
“Решето Эратосфена”
1, 2, 3, 4,

Алгоритм поиска простых чисел меньших натурального N
int N = 5;
bool[] prim

Контрольные вопросы
Какую задачу решают:
Алгоритм подсчета количества (элементов, удовлетворяющих условию);
Алгоритм нахождения суммы

Подсчет количества 1 в байте
//Входные данные byte x
int N = 0;
for

Подсчет количества 1 в байте
//Входные данные byte x
int N = 0;
for

Как посчитать количество 1 в целом?
Массив целых займет всю память.
Загрузка

Как посчитать количество 1 в целом?
int [] n = new int[256]{0,1,1,2,1,2,2,3,…};
uint

Как посчитать количество 1 в целом? Оптимизация
int [] n = new int[256]{0,1,1,2,1,2,2,3,…};
uint

Отладка программ
Вывод промежуточных контрольных значений
Средства Visual Studio:
Точки остановки
Выполнение до следующей точки

Отладка программ. Точки остановки
Добавление и удаление точки остановки

Отладка программ. Пошаговое исполнение
F5 – начать исполнение программы и остановиться в первой

Отладка программ. Контрольные значения
Добавление:
Выделить в тексте программы, когда она остановлена в одной