NWD - programownie strukturalne


(Maryll2) #1

Witam. Od jakiegos czasu zacząłem interesowac sie programowaniem strukturalnym. Kupiłem ksiązke, w której wykonuje rózne cwiczenia. Mam jednak problem nad jednym zadaniem, a odpowiedzi a pomocy nie mogłem znalexc w internecie:

wyznacz nwd czyli największy wpsólnyy dzielnik A i B. wykorzystaj algorytm Eukidesa, opiera sie oin na spostrzezeniu ze jezeli odejmie sie od wiekszej oliczby mniejszą to ta sama mniejsza liczba i otrzymana róznica beda miały taki sam największy wspólnu dzielnik jak pierwotne liczby. Jesli w wynoiku kolejnego odejmowania otrzymamy pare równuch licz to znalazłes NWD

(Borli) #2

Implementacje tego algorytmu można znaleźć chyba wszędzie. Poza tym wszystko jest napisane krok po kroku (w razie wątpliwości jest wikipedia).

Algorytm polega na tym że tak długo jak dwie liczby są różne, od większej odejmujesz większą. Jak w końcu obie są równe, to wartość każdej z nich jest NWD.


(Kruk I) #3

no dobra przy pomocy odejmowania jest to proste a jak muszę to zrobić mnożeniem lub dzieleniem to jak będzie wyglądał algorytm??


(Szczepanskimarek) #4

Podpowiem wiec że używasz operacji modulo (czyli reszt z dzielenia).


(Kruk I) #5

toś podpowiedział :slight_smile: mod div to proste ale jak je ustawić żeby wyszło :slight_smile:


(adpawl) #6

Ło matko, faktycznie tak ciężko znaleźć?

KLIK


(Kruk I) #7

nie nie jest chyba że mam zrobić za pomocą kółek i kwadratów :slight_smile: poza tym tam są w większości odejmowaniem


(Rafal 90) #8

mowiac za pomoca kólek i kwadratow masz chyba na mysli schemat blokowy, wiec oto on:

euklides.gif


(Kruk I) #9

schemat blokowy dobre słowo tylko to jest właśnie za pomocą odejmowania a ja muszę mieć za pomocą mnożenia/ dizelenia


(adpawl) #10

Kruk I , tak z ciekawości ....ile ty masz lat?

http://pl.wikipedia.org/wiki/Algorytm_Euklidesa - sam teraz rusz głową, bo masz wszystko jak na tacy.


(Treker17) #11

Ja znam troche inny, ale nie chce mi się rysować, ten też zadziała:

011_01.gif