Зразки використання допоміжних процедур
Задача № 1
Дано два цілих числа a і b. Знайти їх найбільший спільний дільник (НСД).
Контрольні приклади
Введення
|
a= 12, b= 4
|
a= 12, b= 30
|
a= 11, b= 27
|
a= 0, b= 80
|
Виведення
|
4
|
6
|
1
|
80
|
мм
Для знаходження НСД використаємо алгоритм Евкліда, який формулюється так:
1) НСД(a, b) = a (або b), якщо a=b;
2) інакше ми шукаємо НСД між меншим числом та різницею між більшим і меншим, тобто
1) НСД(a, b) = a (або b), якщо a=b;
2) інакше ми шукаємо НСД між меншим числом та різницею між більшим і меншим, тобто
НСД(a, b) = НСД (a - b, b), якщо a>b.
Наприклад. а=12, b= 30.
НСД(12, 30) = НСД(18, 12) = НСД(6, 12) = НСД (6, 6) = 6.
НСД(12, 30) = НСД(18, 12) = НСД(6, 12) = НСД (6, 6) = 6.
Опишемо допоміжний алгоритм
алг НСД (ціл x, y, ціл rez)
арг x, y
рез rez
поч поки x<>y
пц
якщо x>y
то x:= x - y
інакше y:= y - x
все
кц
rez : = x
кін
алг НСД (ціл x, y, ціл rez)
арг x, y
рез rez
поч поки x<>y
пц
якщо x>y
то x:= x - y
інакше y:= y - x
все
кц
rez : = x
кін
Перед тим, як описати основний алгоритм розглянемо приклад: а=12, b=0.
НСД(12, 0) = НСД(12, 0) = НСД(12, 0) = ...
Бачимо, що алгоритм не діє, якщо хоч одне з чисел дорівнює нулеві. Цей випадок потрібно розглянути окремо. Причому, якщо одне з чисел 0, то НСД дорівнює другому числу. Це можна записати так: якщо (a=0) або (b=0), то r =a+b.
алг НСДаb (ціл а, b, ціл r)
арг а, b
рез r
поч
якщо (a=0) або (b=0)
то r: =a+b
інакше НСД(а, b, r)
все
кін
НСД(12, 0) = НСД(12, 0) = НСД(12, 0) = ...
Бачимо, що алгоритм не діє, якщо хоч одне з чисел дорівнює нулеві. Цей випадок потрібно розглянути окремо. Причому, якщо одне з чисел 0, то НСД дорівнює другому числу. Це можна записати так: якщо (a=0) або (b=0), то r =a+b.
алг НСДаb (ціл а, b, ціл r)
арг а, b
рез r
поч
якщо (a=0) або (b=0)
то r: =a+b
інакше НСД(а, b, r)
все
кін
1. Введіть через пропуск НСД таких пар чисел: 1) 18 і 81; 2) 131 і 11; 3) 123 і 0.
2. Нехай a= 90 і b= 56. Використовуючи алгоритм Евкліда (НСД(a, b) = НСД (a - b, b), якщо a>b), з якими числами ми працюватимемо на 5-ому кроці, якщо на 1-ому маємо НСД(34, 56)? Числа ведіть через пропуск.
3. Чи можна в алгоритмі НСД фрагмент
поки x<>y
пц якщо x>y
то x : = x - y
інакше y : = y - x
все кцзамінити на
поки x<>y
пц якщо x>y
то rez:= x - y
інакше rez:= y - x
все
кц
поки x<>y
пц якщо x>y
то x : = x - y
інакше y : = y - x
все кцзамінити на
поки x<>y
пц якщо x>y
то rez:= x - y
інакше rez:= y - x
все
кц
4. Чи можна в алгоритмі НСДаb замінити умову якщо (a=0) або (b=0) на якщо (a=0) і (b=0)?
5. Чи можна фрагмент
якщо (a=0) або (b=0)
то r: = a + b
інакше НСД(а, b, r)
всезамінити на
якщо a=0
то r = b
інакше якщо b=0
то r: = а
інакше НСД(а, b, r)
все
все
якщо (a=0) або (b=0)
то r: = a + b
інакше НСД(а, b, r)
всезамінити на
якщо a=0
то r = b
інакше якщо b=0
то r: = а
інакше НСД(а, b, r)
все
все
ПРОГРАМА
Program НСДаb;
Uses Crt;
Var а, b, r : integer;
procedure NSD (x, y : integer; Var rez : integer);
begin
While x<>y do
begin
if x>y
then x : = x - y
else y : = y - x;
end;
rez : = x;
end;
Uses Crt;
Var а, b, r : integer;
procedure NSD (x, y : integer; Var rez : integer);
begin
While x<>y do
begin
if x>y
then x : = x - y
else y : = y - x;
end;
rez : = x;
end;
Begin
Write (‘a, b =>');
Readln (a, b);
if (a=0) or (b=0)
then r : = a + b
else NSD (а, b, r);
Write (‘NSD(', a, ‘,', b, ‘)= ', r);
Readkey;
End.
Write (‘a, b =>');
Readln (a, b);
if (a=0) or (b=0)
then r : = a + b
else NSD (а, b, r);
Write (‘NSD(', a, ‘,', b, ‘)= ', r);
Readkey;
End.
Задача № 2
Дано 2 цілих невід'ємних числа а і b. Визначити, у якого числа більша сума цифр.
Контрольні приклади
Введення
|
a= 1000, b= 23
|
a= 118, b=81
|
a= 1, b= 0
|
a= 67, b= 123
|
Виведення
|
23
|
118
|
1
|
67
|
Розв'язання
Для розв'язування задачі потрібно написати допоміжний алгоритм знаходження суми цифр. Фрагмент алгоритму, який дозволяє працювати з цифрами числа, ми розглядали на Уроці_9:
поки х<> 0
пц
c : = m mod 10 {знаходимо цифру}
х : = х div 10 {відкидаємо останню цифру}
кц
поки х<> 0
пц
c : = m mod 10 {знаходимо цифру}
х : = х div 10 {відкидаємо останню цифру}
кц
Потрібно ще ввести змінну s, до якої в циклі додавати знайдені цифри.
6. Сконструюйте алгоритм, ввівши порядок вказаних кроків за зразком: 123456789.
1) рез s
2) s:= s + с {додаємо знайдену цифру до попередньої суми цифр}
х : = х div 10 {відкидаємо останню цифру}
3) c : = х mod 10 {знаходимо цифру}
4) поч
ціл с
5) алг Сума_цифр (ціл x, ціл s)
6) s:= 0
7) поки х<> 0
пц
8) арг x
9) кц
кін
1) рез s
2) s:= s + с {додаємо знайдену цифру до попередньої суми цифр}
х : = х div 10 {відкидаємо останню цифру}
3) c : = х mod 10 {знаходимо цифру}
4) поч
ціл с
5) алг Сума_цифр (ціл x, ціл s)
6) s:= 0
7) поки х<> 0
пц
8) арг x
9) кц
кін
У основному алгоритмі потрібно за допомогою допоміжного алгоритму Сума_цифр знайти суми цифр чисел а і b, а потім порівняти їх.
АЛГОРИТМ
алг Порівняння (ціл а, b, ціл rez)
арг a, b
рез rez
поч
ціл Sa, Sb
Сума_цифр (a, Sa)
Сума_цифр (b, Sb)
якщо Sa>Sb
то rez : = a
інакше rez : = b
все
кін
арг a, b
рез rez
поч
ціл Sa, Sb
Сума_цифр (a, Sa)
Сума_цифр (b, Sb)
якщо Sa>Sb
то rez : = a
інакше rez : = b
все
кін
ПРОГРАМА
Program Comparison;
Uses Crt;
Var
a, b, Sa, Sb, rez : integer;
Uses Crt;
Var
a, b, Sa, Sb, rez : integer;
procedure Sym_cifr (x : integer; Var s : integer);
Var
c : byte;
begin
s: = 0;
While x<> 0 do
begin
c: = x mod 10;
s: = s + x;
x : = x div 10;
end;
end;
Var
c : byte;
begin
s: = 0;
While x<> 0 do
begin
c: = x mod 10;
s: = s + x;
x : = x div 10;
end;
end;
BEGIN
ClrScr;
Write (‘a, b =>');
Readln (a, b);
Sym_cifr (a, Sa);
Sym_cifr (b, Sb);
if Sa>Sb
then rez : = a
else rez : = b;
Write (‘rez= ', rez);
Readkey;
END.
ClrScr;
Write (‘a, b =>');
Readln (a, b);
Sym_cifr (a, Sa);
Sym_cifr (b, Sb);
if Sa>Sb
then rez : = a
else rez : = b;
Write (‘rez= ', rez);
Readkey;
END.
7. Якщо суми цифр в обох числах рівні, то програма виведе:
8. Змінні х, s є:
9. Що виведе програма, якщо замість
procedure Sym_cifr (x : integer; Var s : integer);написати
procedure Sym_cifr (Var x : integer; s : integer);
procedure Sym_cifr (x : integer; Var s : integer);написати
procedure Sym_cifr (Var x : integer; s : integer);
Задача № 3
Дано 3 цілих числа a, b, c. За допомогою допоміжного алгоритму Обмін розставити значення змінних у порядку неспадання, тобто так, щобa<=b<=c.
Контрольні приклади
Введення
|
a= 11, b= -6, c= 7
|
a= -9, b= 4 , c= 5
|
a= 6, b= -1, c= 6
|
a= 11 b= 11, c= 9
|
Виведення
|
a= -6, b= 7, c= 11
|
a= -9, b= 4 , c= 5
|
a= -1, b= 6, c= 6
|
a= 9, b= 11, c= 11
|
Розв'язання
Зрозуміло, що якщо a>b, то потрібно поміняти їх місцями. Тому спочатку розглянемо допоміжний алгоритм Обмін (х, у), який забезпечуватиме перестановку 2-ох значень змінних. Запис типу х:= у призведе до того, що обидві змінні (х і у) одночасно міститимуть первинне значення змінної у, тоді як значення змінної х буде втрачено. Тому потрібно використовувати деяку допоміжну змінну, в якій зберігати значення однієї зі змінних.
Допоміжний алгоритм
алг Обмін (ціл x, y)
арг x, y
рез x, y
поч
ціл z
z : = x
x : = y
y : = z
кін
арг x, y
рез x, y
поч
ціл z
z : = x
x : = y
y : = z
кін
10. Чи коректна буде заміна фрагменту
z : = x
x : = y
y : = z
на
х : = х + у
у : = х - у
х : = х - у
z : = x
x : = y
y : = z
на
х : = х + у
у : = х - у
х : = х - у
Розглянемо ідею застосування алгоритму Обмін. Нехай у нас є контрольні приклади: 9, 4, 6 ; -1, 14, 3; 6, 6, -5.
1 ідея. Порівнюємо 1-ий з 2-им і 2-ий із 3-ім та обмінюємо їх, якщо вони стоять в неправильному порядку.
1 ідея. Порівнюємо 1-ий з 2-им і 2-ий із 3-ім та обмінюємо їх, якщо вони стоять в неправильному порядку.
9, 4, 6: 1) 9, 4 => 4, 9 Маємо: 4, 9, 6
2) 9, 6 => 6, 9 Маємо: 4, 6, 9
2) 9, 6 => 6, 9 Маємо: 4, 6, 9
Аналогічно з -1, 14, 3.
Але 6, 6, -5:
1) 6, 6 - не змінюємо Маємо: 6, 6, -5
2) 6, -5 => -5, 6 Маємо: 6, -5, 6 - невірно
Отже, вказаних умов недостатньо.
1) 6, 6 - не змінюємо Маємо: 6, 6, -5
2) 6, -5 => -5, 6 Маємо: 6, -5, 6 - невірно
Отже, вказаних умов недостатньо.
2 ідея. На розглянутих прикладах помічаємо, що при вказаних порівняннях найбільше число стає на своє місце. Тому ще потрібно виконати 1 крок: ще раз перевірити, чи в правильній послідовності знаходяться 1-ий і 2-ий елементи.
6, 6, -5:
1) 6, 6 - не змінюємо Маємо: 6, 6, -5
2) 6, -5 => -5, 6 Маємо: 6, -5, 6
3) 6, -5 => -5, 6 Маємо: -5, 6, 6
1) 6, 6 - не змінюємо Маємо: 6, 6, -5
2) 6, -5 => -5, 6 Маємо: 6, -5, 6
3) 6, -5 => -5, 6 Маємо: -5, 6, 6
Основний алгоритм
алг Впорядкування (ціл a, b, c)
арг a, b, c
рез a, b, c
поч
якщо a>b
то Обмін (a, b)
все
якщо b >c
то Обмін (b, c)
все якщо a>b
то Обмін (a, b)
все
кін
арг a, b, c
рез a, b, c
поч
якщо a>b
то Обмін (a, b)
все
якщо b >c
то Обмін (b, c)
все якщо a>b
то Обмін (a, b)
все
кін
11. Сконструюйте програму, ввівши порядок вказаних кроків за зразком: 123456789.
1) procedure Obmin (Var x, y:integer);
Var
z : integer;
2) if b>c
then Obmin (b, c);
3) Begin
Write (‘a, b, c =>');
Readln (a, b, c);
4) begin
z : = x;
x : = y;
y : = z;
end;
5) if a>b
then Obmin (a, b);
6) Program Vporjadkyvannja;
Uses Crt;
7) if a>b
then Obmin (a, b);
Write (a,‘ ', b, ‘ ', c);
8) Readkey;
End.
9) Var
a, b, c: integer;
1) procedure Obmin (Var x, y:integer);
Var
z : integer;
2) if b>c
then Obmin (b, c);
3) Begin
Write (‘a, b, c =>');
Readln (a, b, c);
4) begin
z : = x;
x : = y;
y : = z;
end;
5) if a>b
then Obmin (a, b);
6) Program Vporjadkyvannja;
Uses Crt;
7) if a>b
then Obmin (a, b);
Write (a,‘ ', b, ‘ ', c);
8) Readkey;
End.
9) Var
a, b, c: integer;
Примітка. Використання службового слова Var у procedure Obmin (Var x, y : integer); перед змінними x, y є обов'язковим, інакше обмін відбудеться лише з формальними змінними (копіями тих, які використовуються в основній програмі), а самі змінні залишаться такими, як були.
Немає коментарів:
Дописати коментар