Optymalizacja programu- jak zrobić to za pomocą rekurencji?

0

Witam, jestem nowy na forum, więc jeśli coś robię źle, to proszę powiedzcie :)
Napisałem kod, jednak po wpisaniu np. 3 2 123456789, program się po prostu zacina :/

  • Jak poprawić kod by używać rekurencji zamiast tych zbędnych? Choćby w pseudokodzie, mniej więcej, o zastosowaniach rekurencji, jakieś przykłady, bo ja jej totalnie nie ogarniam :/ **
    Bo C++ krótko znam, a rekurencja to dla mnie jedynie 'funkcja wywołująca samą siebie' i na tym koniec.

O to mój kod:

#include <stdio.h>
using namespace std;
int main()
{
    int x; 
    long long int y, z, a, b;
    scanf("%d %lld %lld", &x, &y, &z);
    long long int min=z;
    int tab[z+1];
    int il[z+1];
    for (long long int i=0; i<=z; i++) {tab[i]=0; il[i]=0;}
    for (int i=0; i<x; i++) 
    {
        scanf("%lld %lld", &a, &b);
        for (long long int z=a; z<=b; z++) 

        {   
            tab[z]++;
        }
    }
    for (long long int i=0; i<=(z-y)+1; i++)
    {
        for (long long int j=i; j<i+y; j++)
        {
            if (tab[j]<min) min=tab[j];
        }
        for (long long int k=1; k<=min; k++) il[k]++;
        min=z;
    }
    printf("0 %lld \n", (z-y)+1);
    for (long long int i=1; i<=z; i++) if(il[i]!=0) {printf("%lld %d \n", i, il[i]);}
    return 0;
} 

Dzięki wszystkim, którzy mniej więcej ogarną.
I pytanie: czy ++i jest szybsze od i++ ?

*PS. Wczytujemy 3 zmienne, x, y i z, a potem 2x zmiennych.**

0
  1. Może wyjaśnij co próbujesz zrobić?
  2. Nadawanie zmiennym jednoliterowych nazw przeważnie tak się kończy, coś nie działa i nie wiesz czemu.
  3. Jeżeli ++i nie jest szybsze od i++ to tylko dla tego że dobrze zadziałał optymalizator, który to (optymalizator) nawet nie zawsze ma prawo zadziałać.
0
  1. Próbuję napisać ten kod za pomocą rekurencji, a chodzi o to:
    Leniwa sprzątaczka chce odpocząć y godzin, tak, aby nie zauważyły tego inne sprzątaczki. Na szczęście inne sprzątaczki robią sobie przerwy w pewnych godzinach. Nie może odpoczywać dłużej niż do godziny z, bo wtedy przychodzi szef. X to liczba sprzątaczek, y to ilość godzin ile chce odpocząć, z, godzina, o której przychodzi szef. Potem wczytujemy X razy zmienne a i b, oznaczające początek i koniec przerwy sprzątaczki i-tej. I ostatni wyświetlany wynik jest najbezpieczniejszym czasem na przerwę leniwej sprzątaczki (najpierw liczba sprzątaczek ile mają w pewnych godzinach na raz przerwę, a potem ile jest takich godzin).
  2. Wiem, ale niestety mi tak łatwiej, i się w tym nie gubię, chodzi mi o to, jak można to zrobić rekurencją :)
  3. Mógłbyś jaśniej? :/
0

Ad 1. Jeżeli istnieje iteracyjny algorytm to rekurencyjny jest przeważnie gorszy. Czy możesz wyjaśnić po kiego ci ta rekurencja tu? Tak a propos rekurencja = funkcja wywołująca samą siebie jest jak najbardziej poprawne. Żadnej innej tajemnej wiedzy nie istnieje (to znaczy istnieje kilka różnych ciekawych twierdzeń ale oni ci nie pomogą). Jedynie trzeba algorytm "wykręcić" tak aby działał w takiej funkcji.
Ad 2. No to w takim razie Mistrzu przewyższasz zdolnościami prawie każdego na tym forum, więc po kiego wyjeżdżasz tu z takimi drobnostkami?
Ad 3. Gdzie już jaśniej ... Jak będziesz codziennie pluć w windzie to będzie czyściej? Jedynie można powiedzieć że nie będzie brudniej o ile sprzątaczka jest sumienna i szybka.

0

Po prostu szukam najszybszego sposobu na zrobienie tego, a podobno można taki otrzymać przy poocu rekurencji...

0

Chyba nie padła odpowiedz na pytanie czy ++i jest szybsze od i++. Otóż działanie postinkrementacji (i++) jest następujące:
-Wykonaj kopie zmiennej i
-Wykonaj operacje na tej kopii
-Usun kopie z pamięci
-Zwiększ i o 1
Natomiast działanie preinkrementacji (++i):
-Zwiększ i o 1
-Wykonaj operacje na zmiennej i
Zatem od razu widać, ktora metoda jest szybsza. Jednak jak zostało już powiedziane, jeśli żadna operacja oprócz inkrementowania nie ma zostać wykonana, czyli po prostu kod: i++, to dobry optymalizator prawdopodobnie zamieni to na ++i.
Zainteresuj sie bardziej dogłębnym rozumieniem rekurencji. Bedziesz wiedział, dlaczego prawie zawsze jest wolniejsza od iteracji.
EDIT: Jeśli chcesz przyspieszyć działanie algorytmu, to lepiej powiedz, co ten algorytm robi (albo ma robic).

0

Rekurencja może być szybsza od iteracji chyba tylko jak jest ogonowa i napisałeś to w języku dla którego rekurencja jest "naturalnym" rozwiązaniem (tzn dla języka funkcyjnego).

Użyj profilera jeśli chcesz wiedzieć co spowalnia ci program.

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