Wspólny Mianownik

[loocash]

Witam
chciałbym napisać algorytm liczący wspólny mianownik wielu ułamków np. 100 000. Oczywiście wiem jak to zrobić, ale wydaje mi się, że złożoność mojego programu nie jest zadowalająca i ujawniła by się właśnie przy dużej liczbie ułamków. Można założyć, że liczniki wszystkich ułamków są równe 1. przykład:
\(\displaystyle{ \frac{1}{2} , \frac{1}{3} , \frac{1}{2} , \frac{1}{6}}\) Oczywiste jest, że wynikiem jest 6.
Skoro liczniki równe są 1, do programu wpisywane są tylko mianowniki. program ma wypisać wspólny mianownik. Proszę tylko o wzór. Dla dwóch liczb byłoby to bardzo proste ale co z np. 1000 liczb?
Z góry dziękuję i pozdrawiam.

[matshadow]

ja bym skorzystał ze znanej właściwości, czyli NWW(a,b,c)=NWW(NWW(a,b),c)
int x= NWW (a,b), a potem x=NWW(x,c), x=NWW(x,d) itd

[spajder]

a ja bym skorzystał z algorytmu euklidesa do obliczenia nwd a potem z własności:
\(\displaystyle{ NWW(a,b) = \frac{ab}{NWD(a,b)}}\)

algorytm Euklidesa jest znany i bardzo szybki (ja przynajmniej o lepszym nie słyszałem)

[matshadow]

owszem, ale ten algorytm obliczy tylko NWW dwóch liczb, a mój sposób wielu liczb Czyli podsumowując, trzeba połączyć mój sposób z twoim

[loocash]

Już zaimplementowałem. Wszystko ładnie, pięknie na małych liczbach. ale na dużej ilości oraz zróżnicowanych mianownikach coś go strzela wypisuje trochę za dużą tą liczbę(największą wspólną wielokrotność). Pracuję nad tym cały czas. Podasz mi przykładową Twoją implementację takiego programu? najlepiej w c. program wczytuje n czyli liczbę mianowników, mianowniki, oblicza dla nich NWW i wypisuję wynik.

[matshadow]

W C++

Kod: Zaznacz cały

#include<iostream>
using namespace std;
long long tab[1000000],x;
long long nwd(long long a, long long b)
{
	while(b!=0)
	{
		long long c=a%b;
		a=b;
		b=c;
	}
	return a;
}

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

main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
	 cin>>tab[i];
	x=nww(tab[0],tab[1]);
	for(int i=2;i<n;i++)
	 x=nww(x,tab[i]);
	printf("%lld
",x);
    return(0);
}

[Moraxus]

Kod: Zaznacz cały

#include <iostream>
using namespace std;

unsigned NWW(unsigned a, unsigned b);

int main()
{
  const int size=10000;
  int mianowniki[size];
  memset(mianowniki, 0, size);
  int liczba, i=0;

  while(liczba!=0){
    cin>>liczba;
    mianowniki[i++]=liczba;
  }

  if(i<3)
    return 0;

  int nww=NWW(mianowniki[0], mianowniki[1]);
  for(int n=2;n<i-1;n++)
    nww=NWW(nww, mianowniki[n]);
  
  cout<<nww<<endl;
  return 0;
}

unsigned NWW(unsigned a, unsigned b)
{
 unsigned iloczyn = a*b;
 while(a!=b) if(a>b) a-=b; else b-=a;
 return iloczyn/a;
}

[matshadow]

while(a!=b) if(a>b) a-=b; else b-=a;

Dla dużych liczb się nie wyrobi, za to zastosowany przeze mnie algorytm tak

[Moraxus]

Gwarantuje Ci, że spokojnie wyrobi się dla wszystkich liczb, które zmieszczą się w long long.
Nawet nie zauważysz różnicy.
Chociaz może rzeczywiście lepiej zrobić tak jak ty.
Tak czy siak sam algorytm na NWW 2 liczb skopiowałem gotowy, chodziło mi o pokazanie jak je policzyć dla większej ilości liczb.