Факультативне заняття з теми
«Рішення задач цілочисельний арифметики (пошук дільників і простих чисел)»
целочисленная арифметика програма програмування
Мета уроку:
? закріплення матеріалу попереднього уроку;
? формування навичок і вмінь складання структурних програм для вирішення практичних завдань по темі «целочисленная арифметика»;
? розвиток пізнавального інтересу, логічного і алгоритмічного мислення, навичок самоконтролю, відповідальності, уваги.
? освоєння різних методів вирішення завдань, що реалізуються на мові програмування
? поглибити знання, вміння та навички розв'язання задач з програмування і алгоритмізації.
Тип уроку: урок засвоєння нових знань.
Учні повинні знати: алгоритм знаходження дільників натурального числа, алгоритм перевірки просте чи число, алгоритм Решета Ератосфена
Учні повинні вміти: виконувати практичні завдання з використанням вивчених алгоритмів
Програмне та методичне забезпечення уроку: система програмування Free Pascal, інтернет на учнівських комп'ютерах
Технічне забезпечення уроку: комп'ютери
Хід уроку
1. Перевірка і закріплення знань і умінь попереднього уроку
До дошки викликаю дві людини написати рішення домашніх завдань:
1) Сайт acmp №383 «Красиві числа - 2»
Будемо називати число красивим, якщо сума його цифр ділиться на кількість цифр в ньому. Необхідно знайти N-ну в порядку зростання красиве число. (1 lt;=N lt;=100000)
Приклад введення: Приклад виведення: 111520
2) Сайт dl.gsu.by розділ «Методи алгоритмізації» завдання «Взаємно прості трійки»
Дано N різних чисел. Визначити яку кількість трійок з цього набору є попарно взаємно простими.
Формат вводу: - кількість чисел. 1 lt;=N lt;=100
Послідовність з N чисел. 2 lt;=A [i] lt;=1000
Приклад введення: Приклад виведення 5 4 лютий 14 липня 92
З іншими учнями проводжу фронтальне опитування по темі попереднього заняття:
- Які числа називають парними? Непарними? Як написати в команді розгалуження умова перевірки на парність?
Що називається найбільшим спільним дільником двох натуральних чисел. Розповісти функцію знаходження НСД двох чисел.
Які числа називають взаємно-простими?
Яке число називають кратним даного числа? Як отримати найменше спільне кратне двох
чисел?
- Як у програмі знайти суму цифр натурального числа і кількість цифр?
З'ясовую, чи пройшли в учнів в домашньому завданні всі тести. Обговорюємо правильність виконання домашнього завдання (на дошці), виявляємо проблеми, з якими зіткнулися учні при виконанні домашнього завдання. Даю рекомендації щодо їх усунення.
2. Актуалізація знань учнів на вивчення навчального матеріалу. Пояснення нового матеріалу. Складання та реалізація алгоритмів (метод проблемного викладу у поєднанні з частково-пошуковим методом, фронтальна форма роботи)
- Що називають дільником числа? Як знайти всі дільники натурального числа?
Задача1. Знайти всі дільники натурального числа X (1 lt; X? 10 9).
Зазвичай хлопці пропонують нераціональний алгоритм, який записуємо і розбираємо його недоліки:
Write (1,, x); d:=2 to x div 2 do
if x mod d=0 then write (, d);
- Яка складність виконання даного алгоритму? Чи встигне він при X=10 9 Тому 1 секунду знайти всі дільники? (Відповідь: О (X/2), не встигне).
Як удосконалити алгоритм?
Зауважимо особливість, що всі дільники у цілого числа парні. Випишемо всі пари дільників, наприклад у числа 100:
, 100 2, 50 4 25 5, 20 10, 10
Зробимо висновок, що шукати подільники у числа потрібно тільки до його кореня.
write (1,, x); :=2; int64 (d) * d lt; x do beginx mod d=0 then write (, d,, x div d);:=d + 1 ;; int64 (d) * d=x then write (, d);
Яка тепер складність виконання даного алгоритму? Чи встигне він при X=109 за 1 секунду знайти всі дільники? (Відповідь:), встигне за 1 ...
