Jak znaleźć gcd dwóch liczb? "Turbo Pascal" i odrobina matematyki

Często początkujący programiści poznają środowisko Turbo Pascal poprzez proste zadania. Pierwsze zadania, które użytkownik implementuje w kodzie: wyświetlaj dowolny tekst, znajdź GCD i NOC liczby naturalne obliczyć, ile czwartków przypada w miesiącu itp. Często zdarzają się zadania z matematycznym nastawieniem. Zanim zastosujesz swoją wiedzę w kodzie programu, musisz przestudiować dodatkowe materiały. Na przykład, jak znaleźć GCD i NOC dwóch liczb w Turbo Pascal.

Znalezienie gcd w matematyce

Największy wspólny czynnik to liczba, która jest uważana za maksymalną przy rozkładaniu na komponenty. Zapisuje się krótką formę definicji jako GCD. Weźmy na przykład rysunek. Podano tu numery 140 i 175. Ich największy dzielnik to 35, czyli GCD (140.175) = 35.

Aby uniknąć dodatkowych pytań o to, jak znaleźć GCD o dwóch liczbach, należy postępować zgodnie z tym algorytmem:

• Znajdź najprostsze dzielniki pierwszego numeru.
• Ta sama operacja jest wykonywana z drugim numerem.
• Aby znaleźć wspólne wskaźniki w zestawie dzielników pierwszego i drugiego numeru.
• Koło je piórem w innym kolorze.
• Pomnożyć wspólne dzielniki (jeśli jest ich kilka) lub napisać tylko jeden (jeśli liczby są pierwsze wtedy ich gcd będzie równe 1).

Rozważ poniższą ilustrację. Pokazuje, że nawet tak duża liczba jak 816 i 455 nie ma GCD, z wyjątkiem 1.

Istnieje drugi sposób na znalezienie zadania. Euklidesowy algorytm w matematyce wygląda następująco:

• Biorąc pod uwagę liczby.
• Wybierz powinno być maksimum.
• Jest on podzielony na minimum.
• Teraz druga podana liczba musi zostać podzielona przez wynikowe saldo.
• Pierwsze saldo jest dzielone przez drugie, wynikające z poprzedniej operacji.
• Druga część resztkowa jest dzielona przez trzecią itd.
• Operacja dzielenia jest przeprowadzana, dopóki reszta nie będzie równa 0.
• Ostatni dzielnik i spełniają kryterium NOD.

Aby znaleźć GCD więcej niż trzy liczby naturalne, zaleca się przestrzeganie schematu pracy (wziąć numery 140, 96, 64):

• W pierwszym kroku powtórz powyższy algorytm dla pierwszych dwóch liczb.
• Znajdź GCD znalezionego dzielnika i podaną trzecią liczbę.
• Znajdź GCD wynikowego dzielnika i czwartą liczbę itd.

Znalezienie NOC w matematyce

Jeśli pojawi się programowanie, jak znaleźć GCD z dwóch liczb, to koniecznie jest to związane z drugim: znalezienie LCM. Najmniejszą wspólną wielokrotnością dwóch liczb jest taka minimalna liczba naturalna, którą można dzielić między pierwszą a drugą.

Pierwszy sposób:

• Biorąc pod uwagę dwie lub więcej liczb.
• Napisz wszystkie wielokrotności dla każdej pozycji.
• Wybierz najmniejszą wspólną wielokrotność.

Drugi sposób:

• Rozłóż wszystkie liczby na czynniki pierwsze.
• Zapisz w linii wszystkie dzielniki pierwszej liczby i dodaj tutaj te czynniki, które są w innych rozszerzeniach, ale brakuje ich w pierwszym.
• Oblicz produkt.

GCD w Pascal: algorytm pracy

Jak znaleźć gcd dwóch liczb? "Pascal" to język programowania, w którym zostanie zapisany kod. Najpierw musisz postępować zgodnie z algorytmem wspomnianym powyżej. A tu matematyka przychodzi na ratunek. Algorytm zadania pomoże znaleźć GCD dwóch liczb naturalnych. W Turbo Pascal będzie wyglądać tak:

• Wyświetl monit o wprowadzenie 2 liczb nieujemnych z klawiatury.
• Uruchom pętlę while, gdzie warunkiem jest liczba 1 <> numer 2 (warunkowo, a i b).
• Ciało cyklu zawiera następujące działania: jeśli a> b, to a: = a - b, inaczej b: = b - a.
• Wyświetl wynik.

NOD w Pascal: rozwiązanie euklidesowe

Jak znaleźć GCD dwóch liczb za pomocą prostej, ale skutecznej metody?

• Wprowadzanie liczb dodatnich.
• Wywołanie funkcji pisanej, która oblicza gcd. Sama funkcja wykonuje następujące działania: sprawdzanie warunku, którego liczba jest większa; przydział początkowych danych do innych zmiennych; w cyklu z warunkiem wstępnym (r2 <> 0, tj. do momentu, gdy zmienna będzie równa 0), zostanie znaleziona pozostałość podziału, a wyniki zostaną przypisane do zmiennych; przypisanie nazwy funkcji końcowego wyniku.
• Wyświetl wynik na ekranie.

Wielu programistów uważa, że ​​obie możliwości znalezienia GCD są bardzo podobne, więc w Internecie pierwszą metodę można podać jako algorytm Euklidesa.

NOC w języku Pascal: w jaki sposób jest ustawiony program?

Już rozważono 2 algorytmy wyjaśniające, jak znaleźć GCD dwóch liczb. Teraz pozostaje dowiedzieć się, jak wygląda program wyszukiwania NOC w Turbo Pascal. Algorytm pracy podczas programowania jest następujący:

• Wprowadź dwie liczby.
• Przypisywanie dwóch innych zmiennych do podanych wartości.
• Znalezienie produktu oryginalnych elementów.
• W pętli z warunkiem wstępnym (while) ustaw warunek: jeśli pierwsza liczba jest większa niż druga (n> m), wówczas możesz odszukać wynik (n: = n - m) odejmując; w przeciwnym razie wykonaj tę operację, ale w przeciwnym kierunku (m: = m - n).
• Wyświetl wynik, w którym znaleziony produkt zostanie podzielony przez funkcję div przez liczbę m.

Do czego są wprowadzone dwie zmienne a i b? Aby poprawnie wyświetlić wynik. W cyklu z warunkiem wstępnym tracone są oryginalne wartości zmiennych, więc nie można wyprowadzić wartości m, n określonych przez użytkownika w nawiasach. Oczywiście wiersz 21 można znacznie uprościć, pisząc tylko writeln (proizv div m). Ale użytkownik, który po raz pierwszy zapozna się z programem, nie zrozumie tego, co jest wyświetlane na ekranie.

Ręczne śledzenie:

Jak widać, nie ma nic trudnego w znalezieniu rozwiązania dla GCD i NOC: ani w języku Pascal, ani w rzeczywistości w matematyce.