Algorytmy i Struktury Danych - NWW - najmniejsza wspólna wielokrotność

Problem

Dla danych liczb naturalnych a i b znaleźć najmniejszą liczbę naturalną c, która jest podzielna bez reszty przez a i przez b.

Liczba naturalna c o takich własnościach nosi nazwę NWW – najmniejszej wspólnej wielokrotności liczb a i b (ang. the least common multiple of a and b). Sposób obliczania NWW jest bardzo prosty:

NWW(a,b) =	a × b
	NWD(a,b)

Jeśli liczby a i b są względnie pierwsze, to NWD(a,b) = 1. Wtedy NWW(a,b) = a × b.

Algorytm wyznaczania najmniejszej wspólnej wielokrotności

Wejście

a,b

–

liczby, których NWW poszukujemy, a,b

Wyjście:

NWW – najmniejsza wspólna wielokrotność liczb a i b.

Zmienne pomocnicze

ab	–	zapamiętuje iloczyn a i b. ab N
t	–	tymczasowo przechowuje dzielnik w algorytmie Euklidesa, t N

Lista kroków:

K01:	ab ← a × b	; zapamiętujemy iloczyn a i b
K02:	Dopóki b ≠ 0 wykonuj kroki K03...K05	; algorytmem Euklidesa znajdujemy NWD(a,b)
K03:	t ← b
K04:	b ← a mod b
K05:	a ← t
K06:	ab ← ab div a	; obliczamy NWW
K07:	Pisz ab
K08:	Zakończ

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program odczytuje z pierwszego wiersza liczby a i b. W następnym wierszu wypisuje NWW(a,b). W programie zastosowano zmienne 64 bitowe.

Free Pascal lub DevPascal 1.9.2

// NWW 
// Data   : 2.04.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

program prg;

var a,b,t,ab : int64;

begin
  readln(a,b);
  ab := a * b;
  while b <> 0 do
  begin
    t := b;
    b := a mod b;
    a := t;
  end;
  ab := ab div a;
  writeln(ab);
  writeln;
end.

Code::Blocks

// NWW
// Data   : 2.04.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>

using namespace std;

int main()
{
  unsigned long long a,b,t,ab;

  cin >> a >> b;
  ab = a * b;
  while(b)
  {
    t = b;
    b = a % b;
    a = t;
  }
  ab /= a;
  cout << ab << endl << endl;
  return 0;
}

Free Basic

' NWW 
' Data   : 2.04.2008
' (C)2012 mgr Jerzy Wałaszek
'----------------------------

Dim As Ulongint a,b,t,ab

Input a,b
ab = a * b
While b <> 0
  t = b
  b = a Mod b
  a = t
Wend
ab = ab \ a
Print ab
Print
End

Wynik

9 6
18

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.

I Liceum Ogólnokształcące
im. Kazimierza Brodzińskiego
w Tarnowie
(C)2013 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Twój email:	(jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga:	← tutaj wpisz wyraz ilo , inaczej list zostanie zignorowany

Najmniejsza wspólna wielokrotność