§ 7. Паняцце дапаможнага алгарытму: 7.3. Найбольшы агульны дзельнік двух лікаў

§ 7. Паняцце дапаможнага алгарытму

7.3. Найбольшы агульны дзельнік двух лікаў

Найбольшым агульным дзельнікам (НАД) для двух цэлых лікаў называюць найбольшы з іх агульных дзельнікаў. Прыклад: для лікаў 42 і 24 найбольшы агульны дзельнік роўны 6.

Існуюць некалькі алгарытмаў знаходжання НАД. На ўроках матэматыкі вы пазнаёміліся з наступным алгарытмам:

1) раскласці кожны з лікаў на простыя множнікі;

2) выбраць у раскладаннях агульныя множнікі;

3) перамножыць выбраныя лікі;

(Разгледзім прыклад 7.7.)

На ўроках інфарматыкі ў 8-м класе вы пазнаёміліся з алгарытмам Эўкліда:

1) ад большага ліку аднімаем меншы;

2) калі атрымліваецца 0, то лікі роўныя адзін аднаму і гэта значэнне з’яўляецца НАД;

3) калі вынік адымання не роўны 0, то большы лік замяняем на рознасць большага і меншага;

4) пераходзім да пункта 1.

(Р азгледзім прыклад 7.8.)

Для рэалізацыі алгарытму з курса матэматыкі спатрэбіцца рэалізацыя некалькіх функцый: функцыя для раскладання ліку на множнікі, функцыя для параўнання двух раскладанняў і адбору аднолькавых лікаў, функцыя для перамнажэння лікаў. Акрамя таго, спатрэбіцца дадатковая памяць, каб захоўваць раскладанне лікаў. У той жа час для знаходжання НАД па алгарытме Эўкліда дастаткова адной функцыі, якая будзе працаваць з дзвюма перменнымі.

Прыклад 7.9. Напісаць праграму вылічэння НОД(a, b, c).

Этапы выканання задання

I. Зыходныя даныя: a, b і c (тры лікі).

II. Вынік: НОД (a, b, c).

III. Алгарытм рашэння задачы.

1. Увод лікаў a, b, c.
2. ВВыкарыстаем тое, што НАД (a, b, c)= НОД (НОД (a, b), c). Гэта значыць спачатку вылічым d = НОД (a, b), а затым f = НОД (d, c).
3. Для вылічэння НАД двух лікаў складзём функцыю gcd[1](x, y), якая вылічвае значэнне НАД двух лікаў па алгарытме Эўкліда.
4. Вывад выніку.

IV. Апісанне пераменных: a, b, c, d, f – int.

Прыклад 7.10. На плоскасці зададзены адрэзак, канцы якога маюць цэлалікавыя каардынаты. Колькі пунктаў з цэлалікавымі каардынатамі належаць гэтаму адрэзку? Напрыклад, для адрэзка з канцамі (–5; 5) і (4; –1) такіх пунктаў будзе 4.

Этапы выканання задання

I. Зыходныя данныя: x1, y1, x2, y2 (каардынаты канцаў адрэзка).

II. Вынік: k — колькасць навучэнцаў.

III. Алгарытм рашэння задачы.

1. Увод зыходных даных.
2. Пункты з цэлалікавымі каардынатамі падзеляць адрэзак на часткі. Колькасць такіх частак будзе роўна
$НОД space open parentheses open vertical bar x subscript 1 space minus space x subscript 2 close vertical bar comma space space open vertical bar y subscript 1 space minus space y subscript 2 close vertical bar close parentheses.$
3. Колькасць пунктаў на адну большая, чым колькасць частак.
4. Для вылічэння НАД двух лікаў саставім функцыю gcd(x, y), якая вылічвае значэнне НАД двух лікаў па алгарытме Эўкліда.
5. Вывад выніку.

IV. Апісанне пераменных: x1, y1, x2, y2, k – int.

Прыклад 7.11. Паралель дзясятых класаў напісала кантрольную работу. У выніку роўна a% навучэнцаў атрымалі адзнакі ад 7 да 10, астатнія — ад 1 да 6. Якая мінімальная колькасць навучэнцаў павінна быць у паралелі дзясятых класаў для таго, каб мог атрымацца такі вынік?

Этапы выканання задання

I. Зыходныя даныя: а — колькасць працэнтаў паспяховых работ.

II. Вынік: k — количество учащихся.

III. Алгарытм рашэння задачы.

1. Увод зыходных даных.
2. Калі а — колькасць працэнтаў работ, выкананых на 7—10, то колькасць працэнтаў астатніх работ:
b = 100 – а.
3. Мінімальная колькасць: $k space equals space fraction numerator 100 over denominator НОД left parenthesis straight а comma space straight b right parenthesis end fraction$ .
4.Для вылічэння НОД двух лікаў складзём функцыю gcd (x, y), якая вылічвае значэнне НАД двух лікаў па алгарытму Эўкліда.
5. Вывад выніку.

IV. Апісанне пераменных: a, b, k — int.

[1] gcd — от англ. greatest common divisor (найбольшы агульны дзельнік).

Пример 7.7. Знаходжанне найбольшага агульнага дзельніка для лікаў 42 і 24:

1) $begin mathsize 14px style 42 space equals space 2 space times space 3 space times space 7 comma space space space 24 space equals space 2 space times space 2 space times space 3 colon end style$

2) агульныя множнікі: 2 і 3;

3) $begin mathsize 14px style НОД space equals space 2 space times space 3 space equals space 6. end style$

Прыклад 7.8. Алгарытм Эўкліда для лікаў 42 і 24:

a	b
42	24
18 (42−24)	24
18	6 (24−18)
12 (18−6)	6
6 (12−6)	6

Аналізуючы дзеянні, якія выконваюцца ў алгарытме Эўкліда, можна заўважыць, што можна замяніць большы лік на астачу ад дзялення большага ліку на меншы. Карэктнасць дадзенага факту вынікае з наступнага сцверджання: калі a = b · q + r, то НОД(a, b) = НОД(b, r). Пры такой арганізацыі вылічэнняў алгарытм скончыць сваю работу, калі адзін з лікаў стане роўным нулю. Тады значэнне НАД будзе роўна іншаму ліку, паколькі НОД(r, 0) = r для любога ненулявога r (паколькі 0 дзеліцца на любы цэлы лік).

Прыклад 7.9.

V. Праграма:

#include <iostream>

using namespace std;

int gcd (int x, int y)

{

while (y != x){

if (x > y)

x -= y;

else

y -= x;

}

return x;

}

int main()

{

int a, b, c;

cout << "vvedi 3 chisla" << endl;

cin >> a >> b >> c;

int d = gcd(a, b);

int f = gcd(d, c);

cout << "NOD = " << f << endl;

return 0;

}

VI. Тэсціраванне.

Для кампілятара MinGW, які ўстанаўліваецца разам з Code::Bloks, рэалізавана функцыя __gcd(n, m). Яна знаходзіць НАД двух лікаў. Выкарыстоўваць гэту функцыю можна пасля падключэння бібліятэкі algorithm.

Прыклад 7.10.

V. Праграма:

#include <iostream>

#include <cmath>

using namespace std;

int gcd (int x, int y)

{

while (x && y){

if (x > y)

x %= y;

else

y %= x;

}

return (x + y);

}

int main()

{

int x1, y1, x2, y2;

cout << "koncy otrezka" << endl;

cin >> x1 >> y1 >> x2 >> y2;

int a = abs(x1 - x2);

int b = abs(y1 - y2);

int k = gcd(a, b) + 1;

cout << "kol-vo = " << k;

return 0;

}

VI. Тэсціраванне.

Прыклад 7.11.

V. Праграма:

#include <iostream>

using namespace std;

int gcd (int x, int y)

{

while (x && y){

x %= y;

swap(x, y);

}

return (x + y);

}

int main()

{

int a;

cout << "kol-vo %" << endl;

cin >> a;

int b = 100 - a;

int k = 100 / gcd(a, b);

cout << "kol-vo = " << k << endl;

return 0;

}

VI. Тэсціраванне.

У дадзенай рэалізацыі алгарытму Эўкліда выкарыстана наступная ўласцівасць: НОД (x, y) = НОД (y, x). Функцыя swap(x, y) мяняе месцамі значэнні пераменных x і y.