program zadacha3_8a;

var до, t, про, kto, kot, tok:longint;

Begin

for до:=0 to 9 do

for t:=0 to 9 do

for про:=0 to 9 do

Begin

kto:=k*100+t*10+o;

kot:=k*100+o*10+t;

tok:=t*100+o*10+k;

if (k<>t) and (k<>o) and (t<>o) and (kto+kot=tok) then

writeln(kto,'+',kot,'=',tok);

End;

End.

В даному алгоритмі тіло циклу виконувалося 10•10•10=1000 разів. (говоритимемо складність алгоритму =1000)

Якщо ж для вирішення складніших ребусів буде потрібно написати 8-10 вкладених циклів, то такий повний перебір працюватиме достатньо довго.

Можна трохи спростити даний алгоритм, якщо побачити що 1?k?4, t?2.

for до:=1 to 4 do

for t:=2 to 9 do

for про:=0 to 9 do

Тепер складність алгоритму 4•8•10=320. Просте косметичне виправлення дало збільшення швидкості в 3 рази.

Але і даний алгоритм не є оптимальним. Подивіться, при k=2і t=2 програма перебере всі 10 варіантів про. В таких випадках коли k=t цикл по провзагалі необхідно не виконувати.

Назвемо такий метод - контрольований перебір.

program zadacha3_8c;

var до, t, про, kto, kot, tok:longint;

Begin

for до:=1 to 4 do

for t:=2 to 9 do

if k<>t then

for про:=0 to 9 do

if (k<>o) and (t<>o) then

begin

kto:=k*100+t*10+o;

kot:=k*100+o*10+t;

tok:=t*100+o*10+k;

if kto+kot=tok then writeln(kto,'+',kot,'=',tok);

end;

End.

Такий алгоритм навіть при 8-10 вкладених циклах працює дуже швидко.

Питання для повторення:

1. Чи може у вкладених циклах використовуватися одна і та ж змінна, наприклад i?

2. Чи можна вкладати один в одного різні цикли: FOR в WHILE або REPEAT в FOR?

Завдання для самостійної роботи:

1. Старовинна задача. Скільки можна купити биків, корів і телят, якщо бик коштує 10 рублів, корова – 5 рублів, теля – полтінік (0,5 рублі), за умови, що на 100 рублів треба купити 100 голів худоби.

2. Задане натуральне n. Для всіх чисел від 1 до n знайти:

a) кількість дільників; b) суму парних дільників.

3. Знайти всі рішення наступних числових ребусів:

a) БАБКА+ДЕДКА+РЕПКА=СКАЗКА (4 рішення)

b) КОРОВА+ТРАВА+ДОЯРКА=МОЛОКО (2 рішення)

c) АЛЕНКА+ИВАН+КОЗЛИК=СКАЗКА (1 рішення)

d) ВЕТКА+ВЕТКА+СТВОЛ=ДЕРЕВО (3 рішення)

e) ВОРОТА+ТРАВА=ФУТБОЛ (3 рішення)

Вивчаємо “Цикли”

Тема уроку:

Алгоритми з повтореннями.

Практикум по розв’язуванню задач

з повтореннями.

Мета заняття:

1. Закріпити навики написання алгоритмів з повтореннями;

2. Здійснити проміжний контроль знань;

3. Вдосконалення уміння будувати програми мовою Паскаль. Виховувати уважність, активність на уроці.

Завдання для самостійної роботи:

1. Дано натуральне число n. Обчислити:

.

2. Дані дійсне число а, натуральне число n. Обчислити:

a) an;

b) а(а + 1).(а + n – 1).

3. Дано натуральне число n. Обчислити твір перших n сомножетелей:

a) ;

b) .

4. Обчислити 1 - наступними чотирма способами:

a) послідовно зліва направо;

b) послідовно зліва направо обчислюються і, потім друге значення віднімається з першого;

c) послідовно справа наліво;

d) послідовно справа наліво віднімаються суми, виписані в би), потім віднімання.

Чому при обчисленнях кожним з цих способів виходять різні результати?

5. Знайти всі двозначні числа, які містять цифру N.

6. Складіть програму зведення натурального числа в квадрат, використовуючи наступну закономірність:

12 = 1

22 = 1 + 3

32 = 1 + 3 + 5

42 = 1 + 3 + 5 + 7

. . .

n2 = 1 + 3 + 5 + 7 + 9 + . + (2n – 1).

7. Скласти програму зведення заданого числа в третій ступінь, використовуючи наступну закономірність:

13 = 1

23 = 3 + 5

33 = 7 + 9 + 11

43 = 13 + 15 +17 + 19

53 = 21 + 23 + 25 + 27 + 29

8. Серед двозначних чисел знайти ті, сума квадратів цифр яких ділиться на задане число n.

9. Написати програму пошуку двозначних чисел, що задовольняють наступній умові: якщо до суми цифр числа додати квадрат цієї суми, то вийде саме число.

10. Написати програму пошуку тризначних чисел, квадрат яких закінчується трьома цифрами, що становлять початкове число.

11. Написати програму пошуку чотиризначного числа, яке при розподілі на З дає в залишку B, а при розподілі на B дає в залишку D.

12. Знайти суму позитивних непарних чисел, менших N.

13. Знайти суму цілих позитивних чисел з проміжку від А до В, кратних до (значення змінних А і У вводяться з клавіатури).

14. Знайти суму цілих позитивних чисел, великих А, менших B, кратних 3 і що закінчуються на 2, 4 або 8.

15. В тризначному числі закреслювали старшу цифру, коли отримане двозначне число помножили на 7, то отримали дане число. Знайти це число.

16. Сума цифр тризначного числа кратна 7, саме число також ділиться на 7. Знайти всі такі числа.

17. Серед чотиризначних чисел вибрати ті, у яких всі чотири цифри різні.

18. Дано натуральне число. Знайти всіх його дільників і їх суму.

19. В 1626 році індійці продали острів Манхеттен за 20$. Якби ці гроші були поміщені в банк на поточний рахунок і щорічний приріст склав k%, то була яка б сума в поточному році?

20. Серед двозначних чисел знайти ті, які діляться на число q, а сума їх цифр рівна n (0 < n £ 18).

21. Знайти мінімальне число, більше N, яке без остачі ділиться на До (До, N - натуральні числа).

22. Приписати по цифрі 1 в початок і в кінець запису числа n.

(Наприклад, введення n = 923, висновок 19231).

23. Поміняти місцями першу і останню цифри числа.

(Наприклад, введення n = 9423, висновок 3429).

24. Приписати до початкового числа n таке ж число.

(Наприклад, введення n = 423, висновок 423423).

25. З'ясувати, скільки разів в натуральному числі зустрічається його максимальна цифра.

(Наприклад, введення 4423, висновок 2 рази; введення 9077, висновок 1 разів).

26. З'ясувати, чи є різниця максимальної і мінімальної цифр числа парної.

27. Дано натуральне число n. Вимагається з'ясувати, чи можна відрекомендувати його у вигляді суми квадратів трьох натуральних чисел? Якщо можна, то:

вказати трійку x, у, z таких натуральних чисел, що

x2 ⁺ y2 ⁺ z2 = n;

вказати всі трійки таких чисел, що x2 + y2 + z2 = n.

28. Скласти програму, друкуючу к-ю цифру послідовності:

- 12345678910., в якій виписані підряд всі натуральні числа;

- 14916253649., в якій виписані підряд квадрати всіх натуральних чисел;

29. Скласти програму для знаходження всіх натуральних чисел n, m, до з інтервалу [а, b], удовлеовторяющих співвідношенню n2 + m2 = k2 (а і b задані).

30. Сторони прямокутника задані натуральними числами M і N. Скласти програму, яка знаходитиме, на скільки квадратів, сторони яких виражені натуральними числами, можна розрізати даний прямокутник, якщо від нього кожного разу відрізується квадрат максимально можливої площі.

Вивчаємо “Масиви”

Тема уроку:

Двомірні масиви: опис, введення і висновок масивів по рядках.

Приклади розв’язування задач з використанням двомірних масивів.

Мета заняття:

1. Отримати навики розробки програм по роботі з елементами двомірного масиву;

2. Практична робота з масивами на комп'ютері;

3. Вдосконалення уміння будувати програми мовою Паскаль. Виховувати уважність, активність на уроці.

Двомірні масиви мають рядки і стовпці. Елемент масиву задається номером рядка і номером стовпця, на перетині яких він знаходиться

Якщо кількість рядків = кількості стовпців масив називається квадратною матрицею, в особливому випадку - прямокутної.

Задана прямокутна матриця розміру n рядків і m стовпців.

Заповнити її цілими числами. Роздрукувати по рядках. Знайти і вивести суму всіх елементів і їх середнє арифметичне значення.

program zadacha5_3_1;

var

i, j, s,m,n : integer;

sr : real;

а:array[1..10, 1..20] integer; {опис масиву}

Begin

Write('Кіл. рядків, кіл. стовпців?');

readln( n,m);

for i:=1 to n do

for j:=1 to m do

begin

write('Введіть а[', i, ',', j, ']'); {Введення елементів

readln (а[ i, j ]); масиву}

end;

writeln('Введенний масив');

for i:=1 to n do {Висновок ел. масиву}

begin

for j:=1 to m do

write (а[ i, j ],’ ’); {Висновок ел. масиву}

writeln;

end;

s:=0;

for i:=1 to n do

for j:=1 to m do {Знаходження суми}

s:=s + а[ i, j ];

writeln('Сума =', s);

sr:=s / (n*m); {Знаходження середнього}

writeln('Середнє =', sr:8:3)

End.

Задача. Серед непарних стовпців заданої цілочисельної матриці розмірністю n*m знайти стовпець з максимальною сумою модулів елементів.

program zadacha5_3_2;

var

i, j, m, n, до, s, max :integer;

а : array[1..10, 1..20] integer; {опис масиву}

Begin

Write('Кіл. рядків, кіл. стовпців?'); readln( n,m);

{Заповнити таблицю}

{Вивести таблицю по рядках}

{Спочатку рахуватимемо суму модулів елементів першого стовпця максимальної}

s:=0;

for i:=1 to n do {Знаходження суми першого стовпця}

max := s ;

до:=1; j :=3;

while j <= m do

begin

s := 0;

for i:=1 to n do

s := s + abs ( а[ i,j ]);

if s > max

then begin

max := s; до:=j;

end;

j := j+2; {Перехід до чергового непарного

end; індексу стовпця }

writeln( 'Номер стовпця з максим. сумою модулів елементів ='

до, 'знач. макс.=', max);

end.

Завдання для самостійної роботи:

1. Є цілочисельний масив n*m елементів. Знайти номер рядка з мінімальною сумою модулів елементів.

2. Є цілочисельний масив n*m елементів. Знайти

індекси максимального елемента таблиці і значення

максимуму.

3. Є цілочисельний масив n*m елементів.

Яких елементів в масиві більше негативних або позитивних?

4. Є цілочисельний масив n*m елементів. Повідомити чи є в таблиці негативні елементи.

5. Є цілочисельний масив n*m елементів. Знайти середнє

арифметичне елементів масиву. Визначити і вивести

кількість елементів масиву, значення яких перевищує

це середнє значення.

Вивчаємо “Масиви”

Тема уроку:

Пошук в масиві елементів із заданими властивостями.

Пошук максимального (мінімального) елемента.

Мета заняття:

1. Отримати навики розробки програм по роботі з елементами масиву;

2. Познайомитися із способами пошуку елементів із заданими властивостями;

3. Практична робота з масивами на комп'ютері.

Послідовний пошук— елементи масиву є видимими послідовно один за іншим, при цьому проводиться перевірка відповідності елемента заданій властивості.

Є n цілих чисел. Необхідно знайти число (елемент), значення якого рівно К.Якщотакий елемент в послідовності є, то вказати його порядковий номер.

program zadacha5_1;

var

к,i,n,p:integer;

а:array[1..30] integer; {опис масиву}

Begin

Write('Кіл. елем. масива');

readln(n);

for i:=1 to n do

begin

write('Введіть а[',i,']'); {Введення елементів масиву}

readln (а[i]);

end;

writeln('Введений массив');

for i:=1 to n do {Висновок ел. масиву}

write (а[i],’ ’);

writeln;

write('Введіть К');

readln(k);

p:=0;

for i:=1 to n do {Знаходження суми}

if а[i]=k then p:=i;

if p=0

then writeln('елемента в табліці немає')

else writeln('елемент знайдений, індекс =',p)

End.

В даній задачі у разі наявності в таблиці декількох елементів, рівних До буде виданий найбільший індекс. Для пошуку першого такого елемента в таблиці використовують цикл:

While (i<=n) and (а[i]<>k) do

i:=i+1;

Вирішимо задачу пошуку найбільшого елементав таблиці А з N дійсних чисел. Знайти максимум і індекс цього елемента.

var а: array[1..30] real;

max: real;

n, j, I : integer;

Begin

Write('Кіл. елем. массива'); readln(n);

{Введення елементів масиву}

{Введення елементів масиву}

max:=a[1]; j:=1;

for i:=2 to n do {Пошук максимуму}

if max<a[i] then

begin

max:=a[i];

j:=i;

end;

writeln;

writeln('Макс. елемент масиву =', max );

writeln('Індекс макс. елемента =', j );

End.

Алгоритм:

1. Умовно вважаємо перший елемент найбільшим (максимальним). Запам'ятовуємо його значення (а[1]) і його індекс (=1).

2. Порівнюємо значення максимального з черговим елементом таблиці (i), починаючи з другим елементом і до останнього.

3. При знаходженні елемента з великим значенням міняємо значення максимального на знайдений елемент і запам'ятовуємо його індекс.

4. За наявності в таблиці декількох мінімальних і за умови max<a[i] буде знайдений максимальний елемент з якнайменшим індексом (що перший зустрівся в таблиці), а якщо умова буде max<=a[i], то - з великим індексом.

Завдання для самостійної роботи:

1. Є цілочисельний масив, що складається з 15 елементів. Знайти мінімальний елемент і його індекс.

2. В масиві зберігається інформація про кількість опадів (цілі числа), випавших за кожний день минулого тижня. Вивести номери днів, коли опадів не було.

3. Даний масив цілих чисел з n елементів. Знайти і вивести номери елементів, що закінчуються цифрою 0.

4. Зростання N учнів класу представлено у вигляді масиву. Знайти кількість учнів, зростання яких не перевищує значення R.

5. В масиві записані результати N ігор футбольної команди (якщо гра закінчилася виграшем даної команди, то записано число 3, програшем - число 2, внічию - 1). Визначити кількість виграшів, програшів, нічиїх.

6. В масиві зберігається інформація про зростання N людина. Визначити, на скільки зростання найвищої людини перевищує зростання найнижчого.

7. В масиві зберігається інформація про вартість 1 кг N видів цукерок. Визначити порядковий номер найдешевшого виду цукерок. Якщо таких дещо, то повинен бути знайдений індекс:

А) першого з них;

Б) останнього з них.

8. В масиві зберігається інформація про вартість кожної з M книг. Визначити кількість найдешевших книг (з однаковою мінімальною ціною).

Література

1. Науково-методичний журнал «Інформатика в школі»

2. Газета Шкільний світ «Інформатика»

3. «Intel» - навчання для майбутнього

4. Підручник «Інформатика», Зарецька та інші ч.2.