Najwiekszy wspolny dzielnik - algorytm

pOwer · Post autor: **pOwer** » 5 paź 2006, o 23:26

Witam, owocem mojej pracy jest program, który oblicza NWD najw. wsp. dzielnik dwóch liczb. Byłbym wdzięczny za wskazówki do programu, który obliczy NWD dowolnej liczby liczb.

Program prezentuje się następująco(C++):

Kod: Zaznacz cały

int a,b,c,d,e,x;
cout << "Program sluzy do oblicz. NWD" << endl << endl;
cout << "podaj NWD w formie NWD(x,y)" << endl;
cout << "x:  ";
cin >> a;
cout << "y:  ";
cin >> b;
cout << endl << endl;
x=0;	
			while(x<=0){
			if(b==0) break;
			c=a/b;       
			d = c * b;
			e=x;
			e = a - d;
			a=b;
			b=e;
			}
		cout << "NWD jest:  " << a << endl;

W celu lepszej przejżystości kodu wycięte/pominięte zostały deklaracje i moduły odpowiedzialne za "głupote" wpisywaną, czyli aby np nie można było wpisać np. litery.

Macie jakieś pomysły, żeby program mógł obliczyć NWD dowolnej ilości liczb?? Bardzo proszę o jakieś wskazówki.

Lorek · Post autor: **Lorek** » 5 paź 2006, o 23:34

pOwer pisze:Macie jakieś pomysły, żeby program mógł obliczyć NWD dowolnej ilości liczb

Może na przykład skorzystaj z tego, że
\(\displaystyle{ 1\leq NWD(a_1,a_2,...a_n)\leq min(a_1,a_2,...a_n)}\)
I sprawdź, czy \(\displaystyle{ min(a_1,a_2,...a_n)}\) dzieli każdą z tych liczb,
jeżeli tak, to \(\displaystyle{ NWD(a_1,a_2,...a_n)= min(a_1,a_2,...a_n)}\)
jeżeli nie, to \(\displaystyle{ NWD(a_1,a_2,...a_n)=1}\)

pOwer · Post autor: **pOwer** » 5 paź 2006, o 23:47

Tyle też wiem, tylko jak to przełożyć na kod...

zastanawiałem się nad czymś takim:
1: podaj ilość liczb, ktorych chcesz obliczyć NWD np(3)
2: po podaniu dwóch, oblicza NWD(x,y) a potem jeszcze tej 3ciej
ale doszedlem do wniosku że to jest pomysł idiotyczny, gdyż zawsze będzie ograniczona liczba zmiennych zadeklarowanych. Więc zostaje tylko zastanowienie się nad praktycznym zastosowaniem tablic... but how? i tu mi przybija ćwieka. A chciałbym skorzystać z w/w funkcji, która z dwu przesyłanych liczb zwraca NWD.

Jeżeli nici z tego, to sobie odpuszczę ten pomysł. To nie jest zadanie ani nic z tych rzeczy. Wpadłem na pomysł tego, kiedy na majcy robiliśmy słupki z NWD. Pomyślałem, że mogę coś takiego zrobić w C++. Noi owocem (mojej) tylko pracy jest ów funkcja, która spisuje się doskonale(pominając wycięte elementy spr. wpisywane liczby). Czysta ciekawość... Ale mam nadzieję, że to forum nie służy tylko pomocą w zadaniach domowych.

kadiii · Post autor: **kadiii** » 6 paź 2006, o 22:19

Z pobierznego przejrzenia twojego problemu zauważam, żę sęk tkwi w tym, że chcesz mieć dużą ilość zmiennych deklarowaną z góry. Najlepszym rozwiązaniem wydaje mi się tu użycie dynamicznej alokacji, czyli najprościej mówiąc operatora new w c++. Będziesz mógł wtedy użyć wielu zmiennych nie deklarując ich z góry - poczytaj sobie o tym. A potem to już tylko zaprogramuj jakiś algorytm(z tym chyba nie będziesz miał problemu) i masz gotowy programik. Pozdrawiam i pisz w razie dalszych wątpliwości

Undre · Post autor: **Undre** » 6 paź 2006, o 23:43

Jeżeli odgórnie będziesz wymagać podania liczby zmiennych, to tak jak pisze kadiii korzystaj z new. Jakbyś chciał po prostu podawać liczbę po liczbie bez informowania programu o ich ilości, musiałbyś zastosować chyba jakąś strukturę danych z dorzucaniem elementów ( np listę ).

pOwer · Post autor: **pOwer** » 7 paź 2006, o 00:31

Dzięki wielkie chłopaki, coraz lepiej to idzie. Już powstał program okienkowy dotyczący tego zagadnienia. Ustaliłem sztywno zakres ilości liczb na od 2 do 10. Gdyż dla więcej niż 10 liczb (przeważnie) NWD wynosi 1. Tak więc chyba doszedłem, do tego, czego chciałem.

Teraz myślę nad kolejnymi "zabawami" w C++...

Pozdrawiam i miłej nocki życzę

kadiii · Post autor: **kadiii** » 7 paź 2006, o 18:06

Do Undre - z operatorem new to był tylko taki obszerny skrót myślowy, wkońcu struktury takie jak stos, lista czy kolejka są oparte na tymże operatorze, więc to też tyczy się sytuacji, w których nie chcemy deklarować z góry. Ale to tylko taka dygresja na marginesie. Pozdrawiam

max · Post autor: **max** » 8 paź 2006, o 15:11

Adams pisze:
pOwer pisze:Macie jakieś pomysły, żeby program mógł obliczyć NWD dowolnej ilości liczb
Może na przykład skorzystaj z tego, że
\(\displaystyle{ 1\leq NWD(a_1,a_2,...a_n)\leq min(a_1,a_2,...a_n)}\)
I sprawdź, czy \(\displaystyle{ min(a_1,a_2,...a_n)}\) dzieli każdą z tych liczb,
jeżeli tak, to \(\displaystyle{ NWD(a_1,a_2,...a_n)= min(a_1,a_2,...a_n)}\)
jeżeli nie, to \(\displaystyle{ NWD(a_1,a_2,...a_n)=1}\)

Ten algorytm chyba nie jest poprawny (np NWD(6, 4, 8, 256) jest różny zarówno od min(6, 4, 8, 256) jak i od 1... )

Lorek · Post autor: **Lorek** » 8 paź 2006, o 15:15

max pisze:Ten algorytm chyba nie jest poprawny

No faktycznie , ale zawsze możesz sprawdzić wszystkie liczby od 1 do min(a,b,c...)

juzef · Post autor: **juzef** » 8 paź 2006, o 16:18

Od strony matematycznej najłatwiej będzie wykorzystać fakt NWD(a,b,c)=NWD(NWD(a,b),c).

max · Post autor: **max** » 8 paź 2006, o 19:20

Bzdury z tego postu usunąłęm, aby nie wprowadzać nikogo w błąd.
(Patrz post juzefa poniżej).

pOwer · Post autor: **pOwer** » 8 paź 2006, o 19:36

No to gotowy program, można pobrać stąd:

wciąż niestety nie ma jeszcze blokady wpisania liter zamiast cyfr.

juzef · Post autor: **juzef** » 8 paź 2006, o 19:57

max pisze:Zdaje się że wydajniejszym algorytmem byłoby:
1. wyszukanie 2 najmniejszych liczb z podanych
2. obliczenie ich NWD algorytmem Euklidesa

Wydajniejszym z pewnością, ale niepoprawnym.

pOwer · Post autor: **pOwer** » 8 paź 2006, o 20:03

Działa wogóle wam, może bez środowiska programistycznego ten program?

Lorek · Post autor: **Lorek** » 8 paź 2006, o 20:44

U mnie działa , (btw zaznaczenie z ilu liczb ma liczyć NWD u mnie w ogóle nie jest brane pod uwagę)