Poprawność algorytmu na NWW

W tym miejscu zadajemy pytania na temat języka C, dzielimy się swoją wiedzą, udzielamy wsparcia, rozwiązujemy problemy programistyczne.
Manna5
Posty: 2
Rejestracja: czwartek 30 cze 2022, 15:16

Poprawność algorytmu na NWW

Postautor: Manna5 » czwartek 30 cze 2022, 15:56

Napisałem program w C obliczający największy wspólny dzielnik (NWD) i najmniejszą wspólną wielokrotność (NWW). O ile co do NWD zastosowałem znany algorytm Euklidesa, o tyle sposób wyznaczania NWW wymyśliłem sam i mam do niego pewne wątpliwości. Czy jest on poprawny?

Kod: Zaznacz cały

#include <stdio.h>

int nwd (int a, int b)
{
  while (a != b)
    if (a > b)
      a -= b;
    else
      b -= a;
  return a;
}

int nww (int a, int b)
{
  return a * b / nwd (a, b);
}

int main ()
{
  int a, b;
  printf ("A = ?");
  scanf ("%d", &a);
  printf ("B = ?");
  scanf ("%d", &b);
  printf ("NWD (A, B) = %d\nNWW (A, B) = %d\n",
          nwd (a, b), nww (a, b));
  return 0;
}

Awatar użytkownika
piotrek
User
User
Posty: 149
Rejestracja: niedziela 05 lis 2017, 02:46

Re: Poprawność algorytmu na NWW

Postautor: piotrek » czwartek 30 cze 2022, 21:32

Jakie masz dokładnie te wątpliwości?

Zawsze możesz napisać drugą funkcję, mniej optymalną, która oblicza NWW tej samej pary (a, b) sprawdzając każdą liczbę od 1 do a*b czy się dzieli przez każdą z pary a, b.
Wynik porównać z tym co zwróci ta funkcja, którą napisałeś.

Manna5
Posty: 2
Rejestracja: czwartek 30 cze 2022, 15:16

Re: Poprawność algorytmu na NWW

Postautor: Manna5 » piątek 01 lip 2022, 10:35

Dziękuję za wskazówkę, napisałem program testujący w zakresie 1-1000 i żadnych wyjątków nie znalazłem. Okazuje się też, że sposób był ogólnie poprawny, gdyż jest podany w Wikipedii: https://pl.wikipedia.org/wiki/Najmniejs ... 5%9B%C4%87


Wróć do „Pisanie programów w C”

Kto jest online

Użytkownicy przeglądający to forum: Bing [Bot] i 1 gość