NWD z ciągu liczb

0

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;
}
0

Najprościej będzie Ci po prostu zapamiętywać tylko potrzebne liczby.

int ostatnia;
int przedostatnia;
int aktualna;

Czytasz aktualną, jeśli nie jest jedynką lub zerem, to przypisujesz ją do ostatnia, wcześniej przepisawszy zawartość ostatnia</code> do <code>przedostatnia.
W ten sposób masz cały czas trzymane potrzebne dwie ostatnio występujące "niejedynkowe" i "niezerowe" liczby.
Jeśli aktualna będzie jedynką, to liczysz NWD dla przedostatniej i ostatniej, po czym wynik dokładasz do jakiejś wcześniej ustalonej zmiennej oznaczającej sumę. Tak najtrywialniej bym to rozwiązał.

0

Taki właśnie program napisałem pod w/w (http://wklej.org/id/612835/) linkiem, wychodziłem z takiego samego założenia. ale jednak pojawiły się komplikacje.
1.) trzeba uwzględnić liczby tylko z przedziału o 0 - 30000
2.) trzeba wykluczyć pojawienie się jedynki przy pierwszych dwóch wczytaniach od uruchomienia programu.
3.) jeżeli występują trzy jedynki, to NWD trzeba policzyć razy trzy tj. w przykładzie na wejściu mamy ... 4 4 1 1 1 - NWD dla 4 i 4 to 4, ale do sumy wszystkich nwd dodajemy, nie jedną czwórkę tylko trzy czwórki-tyle ile jedynek - Musi tak być bo nie otrzymamy na wyjściu 22.
4.) ... itp.

przez te "dodatki" które kolejno wkładałem w prosty początkowy kod wyszedł mi rozbudowany program w którym się pogubiłem ...

0

W tego typu zadaniach zazwyczaj nakazuje się uwzględnić poprawność wprowadzanych danych.
Zresztą w zadaniu masz jasno pokazane:

Twoje zastrzeżenie nr 1:

Każda liczba przyjmuje wartość od 0 do 30000

Twoje zastrzeżenie nr 2:

Dwie pierwsze liczby są zawsze większe od 1 (czyli liczb na wejściu jest co najmniej 3).

Twoje zastrzeżenie nr 3:
Tym nie masz się co martwić, jeśli zrobisz jak mówiłem.
Tu masz gotowca, który liczy poprawnie sumę jako 22 - zajrzyj na własną odpowiedzialność ( to jak się poddać ;-P ), albo pomęcz się jeszcze chwilę i sam napisz.
http://wklej.org/id/612875/

PS: To jakiś konkurs, czy system spoj-podobny? Rzucisz linka?

0

Dziękuje Ci bardzo za pomoc, z przyjemnością rozdepcze to zadanie w drobny mak, z satysfakcją, że mi pomogłeś, a nie rozwiązałeś, dla mnie to jest cenniejsze. W końcu jak będzie projekt na zaliczenie też sam będę robił, wiec lepiej już teraz uczyć się na własnych błędach.

P.S

Jestem na pierwszym roku informatyki na uam'ie to jest jedno z zadań które mamy rozwiązać. Trochę to jest śmieszne bo zajęcia są po angielsku i materiały też, bo jest chłopak z erasmusa, praktycznie zero tłumaczenia teorii czy omawiania zadań, ja zawsze interesowałem się budową sieci, głównie w modelu TCP/IP ale oczywiście sesji i prezentacji tam też sie obiły o uszy przy multimediach i kryptografii, programowanie tylko po drodze parę rozdziałów z jednej książki "szkoły programowania-S.Prady" helionu, z tego co pamiętam to chyba tylko dobrnąłem do 6 rozd. A to jest jedno z zadań które mamy do rozwiązania z wcześniejszymi sobie w miarę radziłem, ale jak na moją wiedzę to i tak jest dobrze.

aha co do linka to nie bardzo bo trzeba przejść przez autoryzację uam'u aby zobaczyć zadania, jak chcesz to mogę parę skopiować i ci podesłać na PW albo maila, NIE MA problemu.

1 użytkowników online, w tym zalogowanych: 0, gości: 1