Elektroda.pl
Elektroda.pl
X
Proszę, dodaj wyjątek www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

C++ - Ciąg n liczb rzeczywistych

Werpet 21 Sty 2017 14:36 594 5
  • #1 21 Sty 2017 14:36
    Werpet
    Poziom 4  

    Witam,

    Od razu mówię, że nie liczę na gotowy program. Mam pytanko jak napisać tą funkcję, która jest zamieszczona w poleceniu? Od czego zacząć?

    Pozdrawiam

    0 5
  • #2 21 Sty 2017 19:45
    matej.mistrzu
    Poziom 2  

    Najprościej zacznij od pobierania danych do tablicy. Następnie napisz funkcję sprawdzającą czy i-ty element tablicy jest większy lub równy od sumy elementów od i+1 do końca tablicy. Pozostaje tylko napisać pętlę sprawdzającą kolejne elementy tablicy bez 2 ostatnich.

    Coś w tym stylu http://coliru.stacked-crooked.com/a/d522ac9320f9c38d

    0
  • #3 22 Sty 2017 21:56
    Neojawor2
    Poziom 6  

    Polecam sprawdzanie robić od tyłu, to znaczy od elementu i = n-2. Chodzi o to, że jeśli zaczniesz od elementu zerowego, to za każdym razem musisz zsumować wszystkie elementy następujące po elemencie sprawdzanym. Dodaje nam to złożoności algorytmu z linowej na kwadratową (suma m elementów z tablicy, to tak na prawdę pętla po tej tablicy z m-1 ilością operacji dodawania). Idąc od ostatniego (czyli od n-2), w każdym kroku pętli dodajesz do istniejącej sumy tylko jedną liczbę, więc nie robisz pętli a tylko jedną operację dodawania.
    W Twoim programie to różnica między 100 a 10 mikrosekund, ale przy większym programie taka kosmetyka może przyspieszyć program z 1 godziny do kilkudziesięciu sekund.

    pozdr.
    Neojawor

    0
  • #4 24 Sty 2017 14:59
    matej.mistrzu
    Poziom 2  

    Neojawor2 napisał:
    Polecam sprawdzanie robić od tyłu, to znaczy od elementu i = n-2. Chodzi o to, że jeśli zaczniesz od elementu zerowego, to za każdym razem musisz zsumować wszystkie elementy następujące po elemencie sprawdzanym. Dodaje nam to złożoności algorytmu z linowej na kwadratową (suma m elementów z tablicy, to tak na prawdę pętla po tej tablicy z m-1 ilością operacji dodawania). Idąc od ostatniego (czyli od n-2), w każdym kroku pętli dodajesz do istniejącej sumy tylko jedną liczbę, więc nie robisz pętli a tylko jedną operację dodawania.
    W Twoim programie to różnica między 100 a 10 mikrosekund, ale przy większym programie taka kosmetyka może przyspieszyć program z 1 godziny do kilkudziesięciu sekund.

    pozdr.
    Neojawor


    W tym przypadku nie sprawdzi się zaczynanie od końca chyba, że sumujesz całą tablice i potem będziesz odejmował kolejne elementy.
    Chyba chodziło Ci o to by pamiętać sumę poprzednich elementów by nie musieć ponownie ich sumować.

    0
  • #5 24 Sty 2017 15:47
    Neojawor2
    Poziom 6  

    Dokładnie o to mi chodziło. Choć teraz widzę, ze perla może iść tez od początku. Wystarczy wstępnie zsumować wszystkie elementy, a w kolejnych krokach sumę zmniejszać o wyraz sprawdzany.

    0
  • #6 27 Sty 2017 09:03
    JacekCz
    Poziom 36  

    Werpet napisał:
    Witam,

    Od razu mówię, że nie liczę na gotowy program. Mam pytanko jak napisać tą funkcję, która jest zamieszczona w poleceniu? Od czego zacząć?

    Pozdrawiam


    Wkejka ze zdjęciem tekstu nie jest prawidłowym sposobem zredagowania pytania programowego na portalu IT.

    0