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

Odpowiedz Nowy wątek
2014-01-03 12:27

Rejestracja: 6 lat temu

Ostatnio: 4 lata temu

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.**

Pozostało 580 znaków

2014-01-03 12:45

Rejestracja: 14 lat temu

Ostatnio: 4 minuty temu

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ć.

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2014-01-03 13:03

Rejestracja: 6 lat temu

Ostatnio: 4 lata temu

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? :/

Pozostało 580 znaków

2014-01-03 15:13

Rejestracja: 14 lat temu

Ostatnio: 4 minuty temu

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.


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2014-01-03 15:18

Rejestracja: 6 lat temu

Ostatnio: 4 lata temu

0

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

Jeszcze raz tłumaczę - rekurencja prawie w 100% przypadkach jest wolniejsza - w tym również. - _13th_Dragon 2014-01-03 15:19

Pozostało 580 znaków

2014-01-03 15:37

Rejestracja: 7 lat temu

Ostatnio: 33 minuty temu

Lokalizacja: Kraków

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).


edytowany 3x, ostatnio: pingwindyktator, 2014-01-03 15:46

Pozostało 580 znaków

2014-01-03 17:17
Moderator

Rejestracja: 16 lat temu

Ostatnio: 1 minuta temu

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.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
edytowany 1x, ostatnio: Shalom, 2014-01-03 17:17
Nie zupełnie :D są też inne przypadki z tym że kontrowersyjne. - _13th_Dragon 2014-01-03 17:43

Pozostało 580 znaków

Odpowiedz

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