Zadanie Suma NWD
Dany jest następujący problem: pewien generator wyrzuca z siebie ciąg losowych liczb naturalnych. Co jakiś czas na wejściu pojawia się liczba 1. Należy wówczas wyliczyć największy wspólny dzielnik dwóch ostatnich liczb większych od 1, aby na końcu móc podać sumę wszystkich obliczonych w ten sposób wartości. Gdy na wejściu pojawia się 0, oznacza to, że generator zakończył swe działanie.
Wejście
Wejście składa się z ciągu liczb całkowitych. Każda liczba przyjmuje wartość od 0 do 30000, gdzie liczby od 2 do 30000 oznaczają kolejne wartości dane przez generator, liczba 1 oznacza rozkaz wyznaczenia NWD ostatnich dwóch liczb większych od 1, a 0 jest zawsze ostatnią liczbą pojawiającą się na wejściu.
Dwie pierwsze liczby są zawsze większe od 1 (czyli liczb na wejściu jest co najmniej 3).
Na wejściu nie pojawi się więcej niż 1 000 000 000 liczb.
Wyjście
Na wyjściu należy wypisać jedną liczbę całkowitą, która oznacza sumę wszystkich wyznaczonych największych wspólnych dzielników.
Przykład
Wejście:
5 5 4 4 1 5 5 1 4 4 1 1 1 5 4 3 2 1 0
Wyjście:
22
Problem polega na tym, że niemożna użyć tablicy ponieważ, wartość 1 000 000 000 jest za duża. Dlatego nie bardzo wiedząc jak to zrobić postanowiłem stworzyć program który będzie się opierał na tablicy, w nadziei, że potem mnie natchnie, ale niestety w tym krótkim w miarę czystym kodzie jest tablica więc odpada (nie dopracowałem, jeszcze zmiennej temp, zeruje mi się po każdym przejściu przez for, ale i tak jest tam tablica więc takie coś nie przejdzie)
kod nr. dwa nie jest oparty na tablicy ale jest dłuższy, bardziej chaotyczny, mniej czytelny i zrozumiały-poplątałem się tam, więc nawet NIE MA potrzeby go zamieszczać (chyba, że będzie odważny to proszę bardzo: http://wklej.org/id/612835/) to ten pierwszy - mniejszy, tablicowy kod:
#include <cstdlib>
#include <iostream>
using namespace std;
int main()
{
int suma=0,temp=0;
int tab[100];
tab[0]=0;
for (int i=1,licznik=2;licznik>i;licznik++,i++)
{
cin>>tab[i];
if(tab[i]==0)
{
cout<<suma<<endl;
system("PAUSE");
return 0;
}
if (tab[i]==1 && tab[i-1]!=1)
{
while (tab[i-1]!=0)
{
tab[i]=tab[i-2]%tab[i-1];
tab[i-2]=tab[i-1];
tab[i-1]=tab[i];
}
temp=tab[i-2];
suma=suma+temp;
}
if (tab[i]==1 && tab[i-1]==1)
suma=suma+temp;
}
system("PAUSE");
return 0;
}