Как да намерим gcd от две числа? "Turbo Pascal" и малко математика

Често начинаещите програмисти се запознават с Turbo Pascal среда чрез прости задачи. Първите задачи, които потребителят прилага в кода: показва всеки текст, намира GCD и NOC естествени числа изчисли колко дни са в един месец и т.н. Често има задачи с математически пристрастия. Преди да приложите знанията си в програмния код, трябва да изучите допълнителен материал. Например, как да намерите GCD и NOC на две числа в Turbo Pascal.

Намиране на gcd в математиката

Най-големият общ фактор е броят, който се счита за максимум при разлагане на компоненти. Записва се кратката форма на дефиницията като GCD. Например, помислете за чертеж. Тук са дадени числата 140 и 175. Най-големият им делител е 35, т.е. GCD (140.175) = 35.

За да избегнете допълнителни въпроси за това как да намерите GCD от два числа, трябва да следвате този алгоритъм:

• Намерете най-простите делители на първото число.
• Същата операция се извършва с второто число.
• Да се ​​намерят общи индикатори в множеството разделители на първия и втория номер.
• Оградете ги с писалка с различен цвят.
• Умножете общите разделители (ако има няколко) или напишете само един (ако цифрите са прости тогава техният gcd ще бъде равен на 1).

Помислете за следната фигура. Това показва, че дори такива големи числа като 816 и 455 нямат GCD, освен 1.

Има втори начин да намерите задачата. Евклидовият алгоритъм в математиката е както следва:

• Като се имат предвид номерата.
• Изборът трябва да е максималният.
• Той е разделен на минимум.
• Сега вторият посочен номер трябва да бъде разделен на получения баланс.
• Първият баланс се разделя на втория, получен от предишната операция.
• Втората остатъчна част е разделена на третата и т.н.
• Операцията за разделяне се извършва, докато остатъкът е равен на 0.
• Последният разделител отговаря на критерия NOD.

За да се намери GCD повече от три естествени числа, се препоръчва да се следва схемата на работа (вземете числата 140, 96, 64):

• В първата стъпка повторете горния алгоритъм за първите две числа.
• Намерете GCD на открития делител и дадения трети номер.
• Намерете GCD на получения делител и четвъртия номер и т.н.

Намиране на НОК по математика

Ако при програмирането възникне въпросът как да се намери GCD от две числа, то тогава то е задължително свързано с второто: намиране на LCM. Най-малкото общо кратно от две числа е такова минимално естествено число, което може да бъде споделено от първото и второто.

Първият начин:

• Дадени са два или повече номера.
• Запишете всички кратни за всяка позиция.
• Изберете най-малкото общо.

Вторият начин:

• Разпределете всички числа в основни фактори.
• Напишете в реда всички разделители на първото число и добавете тук тези фактори, които са в други разширения, но липсват в първия.
• Изчислете продукта.

GCD в Pascal: алгоритъмът на работа

Как да намерим gcd от две числа? "Pascal" е език за програмиране, в който ще бъде написан кодът. Първо трябва да следвате алгоритъма, споменат по-горе. И тук математиката идва на помощ. Алгоритъмът на задачата ще помогне да се намери GCD от две естествени числа. В Turbo Pascal ще изглежда така:

• Покажете подканата за въвеждане на 2 неотрицателни числа от клавиатурата.
• Стартирайте цикъла while, когато условието е числото 1 <> 2 (условно a и b).
• Тялото на цикъла включва следните действия: ако a> b, тогава a: = a - b, в противен случай b: = b - a.
• Покажете резултата.

NOD в Паскал: Евклидово решение

Как да се намери GCD на две числа чрез прост, но ефективен метод?

• Въвеждане на положителни числа.
• Обаждане към писмена функция, която изчислява gcd. Самата функция изпълнява следните действия: проверка на състоянието, кой номер е по-голям; присвояване на първоначални данни към други променливи; в цикъла с предварително условие (r2 <> 0, т.е. докато променливата е равна на 0), се намира останалата част от делението и резултатите се присвояват на променливите; задаване на името на функцията на крайния резултат.
• Покажете резултата на екрана.

Много програмисти смятат, че и двете възможности за намиране на GCD са много сходни, така че в Интернет първият метод може да бъде издаден като евклидов алгоритъм.

НОК в Паскал: как е подредена програмата?

Вече бяха разгледани 2 алгоритма, обясняващи как да се намери GCD от два числа. Сега остава да научите как изглежда програмата за търсене на NOC в Turbo Pascal. Алгоритъмът на работа при програмиране е както следва:

• Въведете два числа.
• Присвояване на две други променливи на дадените стойности.
• Намиране на продукта от оригиналните елементи.
• В цикъл с предварително условие (докато), подредете условието: ако първото число е по-голямо от второто (n> m), можете да намерите резултата (n: = n - m) чрез изваждане; в противен случай, изпълнете тази операция, но в обратна посока (m: = m - n).
• Покажете резултата, в който намереният продукт ще бъде разделен от функцията div на числото m.

За какво са въведени двете променливи а и б? За правилно показване на резултата. В цикъл с предварително условие, първоначалните стойности на променливите се губят, така че е невъзможно да се изведат стойностите на m, n, посочени от потребителя в скоби. Разбира се, ред 21 може да бъде значително опростен чрез писане само на writeln (произв div m). Но потребителят, който ще бъде запознат с програмата за първи път, няма да разбере какво се показва на екрана.

Ръчно проследяване:

Както виждате, няма нищо трудно в намирането на решение на GCD и NOC: нито в Паскал, нито всъщност по математика.