• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Program wypisujący Największy Wspólny Dzielnik z n liczb.

0 głosów
632 wizyt
pytanie zadane 28 marca 2017 w C i C++ przez Kenzy Obywatel (1,160 p.)
Witam. Mam napisać program który wypisze największy wspólny dzielnik liczb na wejściu, kompletnie nie mam pomysłu jak się za to zabrać, jakim mam iść tokiem myślenia. Byłbym wdzięczny za każdy sposób pomocy :)

3 odpowiedzi

+3 głosów
odpowiedź 28 marca 2017 przez Aisekai Nałogowiec (42,270 p.)
Algorytm euklidesa + możesz skorzystać ze wzoru: NWD(a,b,c) = NWD(NWD(a,b),C)
0 głosów
odpowiedź 28 marca 2017 przez Evelek Nałogowiec (29,060 p.)
#include <iostream>
using namespace std;

size_t funkcja(size_t liczba_a, size_t liczba_b) {
	size_t temp = liczba_b;
	liczba_b = liczba_a % liczba_b;
	liczba_a = temp;

	if (liczba_b == 0) {
		return liczba_a;
	}
	funkcja(liczba_a, liczba_b);
}

int main()
{
	size_t liczba_a, liczba_b;
	cout << "Podaj pierwsza liczbe: ";
	(cin >> liczba_a).get();
	cout << "Podaj druga liczbe: ";
	(cin >> liczba_b).get();
	cout << "NWD tych liczb wynosi: " << funkcja(liczba_a, liczba_b);

	cin.get();
}

 

komentarz 28 marca 2017 przez Kenzy Obywatel (1,160 p.)
Dziękuję za odpowiedź, jednak w tytule napisałem że ma to być dzielnik z "n" liczb, Pański program liczy NWD wyłącznie z dwóch liczb niestety :/
komentarz 28 marca 2017 przez Evelek Nałogowiec (29,060 p.)
edycja 29 marca 2017 przez Evelek

Ach dobrze. W takim razie sprawdź takie rozwiązanie. smiley

#include <iostream>
using namespace std;

size_t &funkcja(size_t &liczba_a, size_t &liczba_b) {
	size_t temp = liczba_b;
	liczba_b = liczba_a % liczba_b;
	liczba_a = temp;

	if (liczba_b == 0) {
		return liczba_a;
	}
	funkcja(liczba_a, liczba_b);
}

int main()
{
	cout << "Podaj ilosc liczb: ";
	int ilosc_liczb;
	cin >> ilosc_liczb;

	size_t *tab = new size_t[ilosc_liczb];
	for (int i = 0; i < ilosc_liczb; i++) {
		cout << "Podaj " << i + 1 << " liczbe: ";
		cin >> tab[i];
	}

	while (cin.get() != '\n')
		continue;

	size_t wynik = funkcja(tab[0], tab[1]);
	for (int i = 2; i < ilosc_liczb; i++) {
		wynik = funkcja(wynik, tab[i]);
	}

	cout << wynik << endl;
    delete[] tab;
	cin.get();
}

 

komentarz 29 marca 2017 przez mokrowski VIP (148,260 p.)
Co do zasady, dobrze było by posprzątać tab bo teraz pamięć cieknie.
komentarz 29 marca 2017 przez Evelek Nałogowiec (29,060 p.)
Racja. ;)
0 głosów
odpowiedź 29 marca 2017 przez mokrowski VIP (148,260 p.)
edycja 29 marca 2017 przez mokrowski

#include <iostream>
#include <iterator>
#include <numeric>
#include <algorithm>
#include <vector>

unsigned gcd(unsigned a1, unsigned a2) {
    while ( a2 != 0) {
        unsigned temp = a1 % a2;
        a1 = a2;
        a2 = temp;
    }
    return a1;
}

std::vector<unsigned> czytajWartosci() {
    using input_stream_t = std::istream_iterator<unsigned>;
    std::cout << "Podaj ile liczb chcesz wczytać: ";
    // Tu już nie będę sprawdzał czy wczytane dane to liczba... 
    // sam to zrobisz... 
    size_t ilosc;
    std::cin >> ilosc;
    std::vector<unsigned> wartosci(ilosc);
    std::copy_n(input_stream_t(std::cin), ilosc, wartosci.begin());
    return wartosci;
}

int main() {
    auto dane = czytajWartosci();
    std::cout << "Dla podanych danych, wspólny dzielnik to: ";
    std::cout << std::accumulate(std::next(dane.begin()), dane.end(), *(dane.begin()),
            [](unsigned a1, unsigned a2) {
                return gcd(a1, a2);
    }) << '\n';
}

Tu można uniknąć rekurencji i zastosować std::accumulate dla przejścia po kontenerze wczytywanych liczb.

 

komentarz 29 marca 2017 przez Evelek Nałogowiec (29,060 p.)

Hm... MSVC i MinGW pokazuje ten sam błąd w wierszu:

using input_stream_t = std::istream_iterator<unsigned>;

.. o treści: element namespace "std" nie ma elementu członkowskiego "istream_iterator"
... a MinGW dodatkowo:  input_stream_t was not declared in this scope.

komentarz 29 marca 2017 przez mokrowski VIP (148,260 p.)
edycja 29 marca 2017 przez mokrowski
Sprawdź czy masz wczytany nagłówek <iterator>. gcc go potrzebuje a clang z którym pracuję, wczytał go sobie w którymś nagłówku zależnym.

Jeśli kompilator nie obsługuje using to using można zastąpić typedef'em.

Podobne pytania

0 głosów
1 odpowiedź 709 wizyt
pytanie zadane 6 marca 2017 w C i C++ przez styrczu Obywatel (1,050 p.)
0 głosów
2 odpowiedzi 423 wizyt
pytanie zadane 16 listopada 2017 w C i C++ przez maciek45 Nowicjusz (120 p.)
0 głosów
1 odpowiedź 2,808 wizyt
pytanie zadane 3 kwietnia 2018 w C i C++ przez mietek_arduino Początkujący (330 p.)

88,720 zapytań

137,331 odpowiedzi

306,818 komentarzy

58,907 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Sklep oferujący ćwiczenia JavaScript, PHP, rozmowy rekrutacyjne dla programistów i inne materiały

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...