НОУ ІНТУЇТ | лекція | Прості числа

1. Дивитися лекцію на: ІНТУЇТ | youtube.com
2. Погляд на завдання з вершини гори
3. Прості числа
4. Випускна робота

Наша взаимовыгодная связь https://banwar.org/

Анотація: Прості числа На цьому уроці обговорюється поняття простого числа, алгоритм, що дозволяє визначити, чи є число простим. Розглядається інтуїтивно зрозумілий алгоритм знаходження всіх простих чисел в заданому діапазоні. Детально обговорюється ефективний алгоритм пошуку простих чисел "Решето Ератосфена", придуманий більше двох тисяч років тому видатним давньогрецьким вченим Ератосфеном. Як зазвичай показаний програмний проект, який реалізує алгоритми, розглянуті в лекції.

Дивитися лекцію на: ІНТУЇТ | youtube.com

Якщо проблеми з відео, натисніть вище посилання youtube

Погляд на завдання з вершини гори

Знаходження всіх дільників числа, визначення задуманої комбінації в грі "бики і корови" можна розглядати як окремі випадки загальної задачі, часто зустрічається в нашому житті в самих різних варіаціях. У чому суть цього завдання - серед безлічі об'єктів необхідно знайти один або кілька об'єктів, що володіють необхідними властивостями. Це завдання часто вирішується в два етапи. На першому - формується безліч кандидатів, тобто безліч об'єктів, які можуть мати заданими властивостями. Другий етап - це фільтр. На цьому етапі влаштовується перебір по безлічі кандидатів, кожен з яких проходить фільтр - чи виконала кандидат заданим властивостям.

У чому складність завдання?

Якщо безліч кандидатів звичайно, то рішення задачі можна отримати повним перебором, розглянувши всіх кандидатів в пошуках кращого. Безліч кандидатів може бути великим. Тоді повний перебір може бути практично неможливий. Якщо число кандидатів задається експонентою, наприклад, функцією 2n, то для людини зазвичай перебір неможливий вже при n, що дорівнює 10, сучасний звичайний комп'ютер може справлятися із завданнями при n, рівному 30. Але багато, найважливіші для людства завдання - створення нових зразків техніки , що володіють унікальними властивостями, пошук нових ефективних ліків, інші завдання вимагають перебору куди більшої кількості варіантів. Ось чому так важливо для країни мати в своєму арсеналі суперкомп'ютери, які можуть справлятися із завданнями при n, рівному 60, але можливості суперкомп'ютерів теж обмежені, оскільки і в доступному для огляду майбутньому жоден комп'ютер не зможе впоратися з перебором при n, що дорівнює 100.

Непростий є і завдання фільтрації. Класичним прикладом є притча про "Бурідановим віслюку". Буридан любив свого осла і, бажаючи порадувати осла, поставив перед ним дві торби, - одну з ароматним сіном, іншу - з добірним зерном. Обидва страви були так апетитні, що осів не міг зробити вибір і помер від голоду.

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

Сваха, яка відбирає безліч женихів (кандидатів в чоловіки), говорить нареченій: "Так ухлопоталась! Зате вже яких женихів тобі припасла! Тобто, і стояв світло і буде стояти, а таких ще не було!"

Наречена, вирішуючи проблему вибору, - "Право, таке складне становище - вибір! Якби губи Никанора Івановича та приставити до носа Івана Кузьмича, та взяти скільки-небудь розбещеності, яка у Балтазара Балтазарича, так, мабуть, додати до цього ще огрядності Івана Павловича - я б тоді відразу ж зважилася ".

У завданнях, що з'являються в програмуванні, виникають подібні проблеми.

У грі "Відгадай число" задумане число знаходиться в інтервалі [0, N], де N може бути велике, що не дозволяє людині застосовувати повний перебір. Ефективний фільтр в цьому завданні, заснований на дихотомії безлічі кандидатів, дозволяє з кожним питанням вдвічі зменшувати число кандидатів, яке досить скоро зводиться до єдиного елементу.

У грі "Бики і корови" при задуманої комбінації довжини 6, обраної з 12 фігур, число можливих варіантів одно 126, що також виключає для людини можливість повного перебору. У даній грі побудова ефективного фільтра зовсім не проста справа. Магістр гри може розгадати задуману комбінацію за меншу кількість питань ніж комп'ютер, який використовує не найефективніший фільтр.

У задачі про знаходження всіх дільників числа N в якості безлічі кандидатів природно вибрати безліч чисел з інтервалу [1, N]. Фільтр IsDivisor в цьому завданні досить простий, але зменшення перебору вимагає хорошого математичного і алгоритмічного мислення. Нетривіальною здогадкою є те, що це безліч можна істотно скоротити і звести до інтервалу , Розглядаючи в цьому інтервалі тільки непарні числа.

У задачі про розкладанні числа на прості подільники знову-таки потрібно алгоритмічне мислення для розуміння того, що завдання можна звести до пошуку мінімального подільника. Знову-таки потрібно бути трохи математиком, щоб довести, що мінімальний дільник є простим числом.

Кожне завдання має свої особливості, свою специфіку вирішення пов'язаних з нею проблем. Але загальний погляд, сама постановка питань: "як скоротити безліч кандидатів", зменшуючи перебір варіантів? "," Як побудувати ефективний фільтр відбору кандидатів? ", Сприяє знаходженню ефективного вирішення завдання.

Прості числа

Розглянемо алгоритми, пов'язані з простими числами. Число N просте, якщо у нього тільки два дільника - 1 і саме число N.

З визначення випливає, що функцію IsPrime (int N) можна написати в один рядок, якщо використовувати раніше написані функції.

Робота біля дошки

/// <summary> /// n - просте число? /// </ summary> /// <param name = "n"> число </ param> /// <returns> true, якщо n просте </ returns> public static bool IsPrime (int n) {List <int > list = AllDivisors (n); return list.Count == 2; // List <int> list = PrimeDivisors (n); // return list.Count == 1; }

Це рішення можна записати в один рядок, не вводячи додаткової змінної:

public static bool IsPrime (int n) {return AllDivisors (n) .Count == 2; }

А як знайти всі прості числа? Постановка завдання некоректна, оскільки безліч простих чисел нескінченно. Чи можна довести цей факт? Так, і доказ досить просте.

Використовуємо метод докази "від протилежного".

Припустимо, що безліч простих чисел звичайно. Тоді існує найбільше просте число - pk. Розглянемо число N, що представляє твір всіх простих чисел, починаючи від двох до pk. Додамо до цього твору 1. Отримане число є простим числом. Як раніше було показано, всяке складене число M може бути розкладено на твір простих дільників, великих 1 і менших M. Число N остачі не ділиться ні на одне просте число, отже, воно просте і більше ніж pk. Прийшли до суперечності. Наше припущення про кінцівки безлічі простих чисел невірно. Безліч простих чисел нескінченно.

Коректна постановка задачі: знайти всі прості числа в інтервалі [3, N]. Є сенс шукати їх в цьому інтервалі, оскільки тоді можна вести пошук тільки серед непарних чисел, вдвічі скорочуючи безліч кандидатів. Виникає очевидне алгоритм. Безліччю кандидатів є безліч непарних чисел в інтервалі [3, N]. Фільтром є побудована функція IsPrime. Перебір елементів безлічі кандидатів і відбір кандидатів, що пройшли фільтр, дає рішення задачі.

Робота біля дошки:

Наведу варіацію цього алгоритму, яка обчислює всі прості числа в інтервалі [min, max].

/// <summary> /// Всі прості числа в інтервалі [min, max] /// </ summary> /// <param name = "min"> нижня межа </ param> /// <param name = "max"> верхня межа </ param> /// <returns> список всіх простих чисел в заданому інтервалі </ returns> public static List <int> Prime_Iterator (int min, int max) {List <int> list = new List <int> (); int cand; if (IsEven (min)) cand = min + 1; else cand = min; while (cand <= max) {if (IsPrime (cand)) list.Add (cand); cand + = 2; } Return list; }

У нашому алгоритмі досить складний фільтр, що вимагає для кожного кандидата обчислення всіх його подільників. Виникає законне питання, а чи можна запропонувати кращий за паливною ефективністю алгоритм. Такий алгоритм був придуманий приблизно 2300 років тому грецьким вченим Ератосфеном.

Ератосфен вважається батьком науки географії, придумав сам термін "географія". Перший, хто досить точно обчислив розмір Землі. (Як можна обчислити розмір Землі?)

Керував знаменитою бібліотекою в Олександрії, дружив і багато років вів переписку з Архімедом. Знайшов все прості числа до 1000, придумавши метод, який отримав назву "Решето Ератосфена".

У чому його суть. Випишемо поспіль всі числа від 2-х до N. (Для простоти можна виписати тільки непарні числа). Перше число в цьому ряду (3) - просте. Пройдемо по ряду з кроком, рівним знайденим простим числом і замінимо числа нулями. Це означає, що ми видаляємо з безлічі кандидатів, числа кратні даному простому числу. Число, наступне за раніше знайденим простим числом, не рівне нулю, буде наступним простим числом. Будемо повторювати цей процес, поки ряд не буде вичерпаний. Алгоритм заснований на тому факті, що мінімальне число, яке не ділиться на попередні прості числа, є простим.

Алгоритм названий "Решетом", оскільки Ератосфен записував числа на восковій табличці і, видаляючи кратні числа, просто проколював їх, залишаючи дірки. В результаті "просіювання" в решеті залишалися тільки прості числа.

Ось можлива реалізація цього алгоритму:

/// <summary> /// Решето Ератосфена /// Формування списку всіх простих чисел /// в інтервалі [3, N] /// </ summary> /// <param name = "N"> </ param > /// <returns> список простих чисел в заданому інтервалі </ returns> public static List <int> Eratosfen_Sieve (int N) {List <int> simple_numbers = new List <int> (); int m = (int) ((N - 3) / 2) + 1; // розмір масиву непарних чисел int [] odd_numbers = new int [m]; simple_numbers.Add (2); // Перший простий число int i = 0; while (i <m) {odd_numbers [i] = 2 * i + 3; // заповнюємо масив непарними числами i ++; } Int k = 0; int last; int j; while (k <m) // цикл по числу простих чисел {while (k <m && odd_numbers [k] == 0) k ++; // пропускаємо нулі if (k <m) {last = odd_numbers [k]; // наступне просте число simple_numbers.Add (last); // просіювання кратних last j = k + last; while (j <m) {odd_numbers [j] = 0; j + = last; } K ++; }} Return simple_numbers; }

Робота в класі:

Створіть проект за таким зразком:

Зверніть увагу, користувачеві виводиться не тільки список простих чисел в заданому інтервалі, але і щільність простих чисел і час, витрачений алгоритмом, обчислює список простих чисел. Обидва алгоритми будують один і той же список, але алгоритм Ератосфена працює в 200 разів швидше алгоритму Ітератор! (Молодець Ератосфен!)

Наведу обробник події "Click" для кнопки "Eratosphen Sieve":

private void buttonSieve_Click (object sender, EventArgs e) {DateTime start, finish; double sieve_time; textBoxMessageSieve.Text = ""; int max = int.Parse (textBoxMax.Text); int min = int.Parse (textBoxMin.Text); start = DateTime.Now; List <int> simple_numbers = Numbers.Eratosfen_Sieve (max); finish = DateTime.Now; sieve_time = (finish - start) .TotalMilliseconds; listBoxSimple.Items.Clear (); int N = simple_numbers.Count; int n = 0; for (int i = 0; i <N; i ++) if (simple_numbers [i]> = min) {listBoxSimple.Items.Add (simple_numbers [i]); n ++; } Double density = Convert.ToDouble (n) / (max- min); string mes1 = "В інтервалі [" + min.ToString () + "-" + max.ToString () + "] простих чисел -" + n.ToString () + "\ r \ n"; string mes2 = "Щільність простих чисел =" + density.ToString () + "\ r \ n"; string mes3 = "Час обчислень Решетом Ератосфена (миллисекундах) =" + sieve_time.ToString (); textBoxMessageSieve.Text = mes1 + mes2 + mes3; }

Домашнє завдання: Закінчити проект, розпочатий в класі.

Випускна робота

Наші заняття в цьому році закінчаться 25 квітня через два тижні. На останньому занятті бажано розглянути випускну роботу, яку потрібно спробувати виконати. Робота не проста, і не у всіх вона може вийти. Але спробувати виконати її слід.

Завдання 1

Написати гру "One-armed gangster" - "Однорукий бандит".

Суть гри: При натисканні кнопки "Гра" з'являються 3 картинки із заданого набору 12 картинок. Картинки можуть бути ті ж, що і в грі "Бики і корови". Вибір картинок генерується випадковим чином. Виграш гравця можливий в трьох випадках:

• Всі три картинки збігаються (ціна виграшу - N, наприклад, 100 рублів);
• Збігаються кольори у всіх картинок (ціна виграшу - M, наприклад, 20 рублів);
• Збігаються геометричні фігури - три кола або три ромба ((ціна виграшу - M, наприклад, 20 рублів);

За кожну гру з гравця стягується плата P (наприклад, 10 рублів).

Спочатку гравець вносить деяку суму і грає до тих пір, поки не програє всі внесені гроші або не натисне кнопку Stop.

Вказівка: Розбір гри "Бики і корови" "допоможе написати гру" однорукий бандит ". Проте завдання залишається досить складною для початківців програмістів.

завдання 2

Написати функцію GoodPupil. На вхід функції подаються два масиви Fam і Marks. Масив Fam містить прізвища учнів, масив Marks - їх оцінки з математики та інформатики. Функція GoodPupil як результат повертає список учнів, які мають оцінки 4 або 5 з обох предметів.

Наведу заголовок функції GoodPupil:

List <string> GoodPupil (string [] Fam, int [] Marks]

(Приклад вихідних даних: Fam = { "Петров В. А", "Михайлов Н. В", ​​"Чистяков А. П."} Marks = {5, 3, 4, 4, 5, 4}. В результаті повинен бути сформований список, що містить двох учнів - Михайлова і Чистякова)

завдання 3

Реалізувати один з проектів, розглянутих протягом курсу