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]Skracanie czasu wykonywania programu

deveaux 11 Gru 2010 12:44 1503 5
  • #1 11 Gru 2010 12:44
    deveaux
    Poziom 7  

    Kurcze mam kody, które myślę, że działają prawidłowo, ale na spoju wyskakuje mi: "przekroczono limit czasu". Czy ktoś mógłby mi pomóc skrócić czas wykonywania poniższych programów?

    Kalkulator ułamków:

    Code:

    #include <stdio.h>
    #include <string.h>


    int NWD(int x, int y)
    {
        int i;
        if (x>y)
        {
        for(i=y;i>1;i--)
        {
            if ((y%i==0) && (x%i==0))
            {
                break;
            }
        }
        return i < 0 ? -i : i;
        }
        else if (x<y)
        {
            for(i=x;i>1;i--)
            {
                if ((y%i==0) && (x%i==0))
                {
                    break;
                }
            }
        return i < 0 ? -i : i;
        }
        else
        {
             return x;
        }
    }
    int main()
    {
        int a,b,c,d,i,tmp,mian;
        char znak,znak1;
        char operacja[3];
        while(scanf("%d%c%d %s %d%c%d",&a,&znak,&b,operacja,&c,&znak1,&d)==7)
        {
       
            switch(operacja[0])
            {
            if ((b!=0) && (d!=0))
            {
                case '+':
                          {
                              tmp = (a*d)+(c*b);
                              mian = b*d;
                              i = NWD(tmp,mian);
                              printf("%d/%d\n",tmp/i,mian/i);
                          }
                break;

                case '-':




                          {
                              tmp = (a*d)-(c*b);
                              mian = b*d;
                              i = NWD(tmp,mian);
                              printf("%d/%d\n",tmp/i,mian/i);
                          }
                break;
               
                case '*':
                          {
                              tmp = a*c;
                              mian = b*d;
                              i = NWD (tmp,mian);
                              printf("%d/%d\n",tmp/i,mian/i);
                          }
                break;
            }
                case '/': if ((b!=0) && (c!=0))
                          {
                              tmp = a*d;
                              mian = b*c;
                              i = NWD (tmp,mian);
                              printf("%d/%d\n",tmp/i,mian/i);
                          }
                          else if ((b!=d) && (b!=0) && (d!=0))
                break;
            }
        }
        return 0;
    }



    Tłumacz:
    Code:

    #include <stdio.h>

    int rown(const char *w1, const char *w2)
    {
      int i;
      int wyn;
     
      wyn = 1;
      i = -1;
      do
      {
        i++;
        if (w1[ i ] != w2[ i ])
       {
         wyn = 0;
         break;
       }
      } while (w1[ i ] != 0 && w2[ i ] != 0);
      return wyn;
    }

    int main(int argc, char **argv)
    {
      char w1[ 21 ], w2[ 21 ];
      char jezykzr_dane[ 5000 * 21 ], jezykcel_dane[ 5000 * 21 ];
      char *jezykzr[ 5000 ], *jezykcel[ 5000 ];
      char *zr, *cel, *liniaptr, *tlum;
      int licz, i, j;
      char linia[ 2100 ], wyraz[ 100 ];
     
      licz = 0;
      zr = jezykzr_dane;
      cel = jezykcel_dane;
     
      while(gets(linia))
      {
        if (!linia[ 0 ])
         break;
        
        if (sscanf(linia, "%s %s", w1, w2) != 2)
         break;
       jezykzr[ licz ] = zr;
       jezykcel[ licz ] = cel;
       for(i = 0; w1[ i ] != 0 && i < 20; i++)
         *(zr++) = w1[ i ];
       *(zr++) = 0;
       for(i = 0; w2[ i ] != 0 && i < 20; i++)
         *(cel++) = w2[ i ];
       *(cel++) = 0;
       licz++;
      }
     
      while(gets(linia))
      {
       liniaptr = linia;
       while (*liniaptr)
       {
           if (*liniaptr < 'a' || *liniaptr > 'z')
          {
            printf("%c", *(liniaptr++));
            continue;
          }
          
          i = 0;
          while(*liniaptr >= 'a' && *liniaptr <= 'z')
          {
            wyraz[ i++ ] = *(liniaptr++);
          }
          wyraz[ i ] = 0;
          
          tlum = wyraz;
          for(j = 0; j < licz; j++)
          {
            if (rown(wyraz, jezykzr[ j ]))
            {
             tlum = jezykcel[ j ];
             break;
            }
          }
          printf(tlum);
        }
        printf("\n");
      }
    }

    0 5
  • #2 11 Gru 2010 17:01
    Dżyszla
    Poziom 42  

    Upewnij się przede wszystkim czy opcje kompilacji umożliwiają zadziałanie optymalizatora kodu (czyli generalnie czy jest to tzw kompilacja release).
    Po drugie, jeśli funkcja NWD faktycznie liczy NWD to jakiś złożony ten algorytm. Przyjrzyj się choćby temu: http://cpp.koderzy.pl/art6-1/Obliczanie_NWD.php
    Możesz opisać słowami działanie drugiego programu?

    0
  • #3 11 Gru 2010 18:41
    przemo_wielki
    Poziom 23  

    NWD jest ciekawe, dzieli każdą liczbę przez taką samą zmienną aż znajdzie wspólną :) dla przykładu (136,26) będzie sobie dzielił przez 26,25,24 ... 2, mnie bardziej interesuje przypadek w którym

    Code:
    for(i=y;i>1;i--)
    
        {
            if ((y%i==0) && (x%i==0))
            {
                break;
            }
        }
        return i < 0 ? -i : i;


    i < 0 przy pętli for( ; i>1 ; ) zwróci -i ... pewnie chodzi o ujemne więc proszę sprawdzić NWD(-4,-12), 12? nie sądzę.

    0
  • #4 12 Gru 2010 14:38
    deveaux
    Poziom 7  

    Dżyszla napisał:
    Upewnij się przede wszystkim czy opcje kompilacji umożliwiają zadziałanie optymalizatora kodu (czyli generalnie czy jest to tzw kompilacja release).
    Po drugie, jeśli funkcja NWD faktycznie liczy NWD to jakiś złożony ten algorytm. Przyjrzyj się choćby temu: http://cpp.koderzy.pl/art6-1/Obliczanie_NWD.php
    Możesz opisać słowami działanie drugiego programu?


    spoj korzysta z gcc 4.3.2

    A drugi program to "mechaniczny tłumacz"

    Code:

    Napisz program, który wyraz po wyrazie tłumaczy tekst napisany w jednym języku na drugi język.

    Wejście

    Na wejście programu podany zostanie słownik oraz tekst do przetłumaczenia składający się z wyrazów (wyraz = ciąg małych liter), spacji, znaku nowej linii i znaków interpunkcyjnych. Słownik składa się z par postaci w t, gdzie w jest wyrazem w pierwszym języku, a t jego tłumaczeniem na drugi język. Wyrazy w parze zostaną rozdzielone spacją, a poszczególne pary znakiem nowej linii. Pomiędzy słownikiem, a tekstem do przetłumaczenia znajduje się pojedyńcza pusta linia. Można przyjąć, że żaden z wyrazów nie ma więcej niż 20 znaków, a słownik zawiera co najwyżej 5.000 par.

    Wyjście

    Na wyjściu programu ma się pojawić tłumaczenie tekstu, który został wczytany z wejścia. Przetłumaczyć należy tylko te wyrazy, które znajdują się w słowniku. Wyrazy, których tam nie ma, odstępy, znaki interpunkcyjne itd. należy przepisać nie zmieniając ich.

    Przykład

    Wejście:

        zdanie sentence
        jest is
        bardzo very

        to jest bardzo proste zdanie.

    Wyjście:

        to is very proste sentence.

    0
  • #5 12 Gru 2010 17:33
    Dżyszla
    Poziom 42  

    Miałeś opisać algorytm realizujący zadanie ;) Ale już zasugeruję, abyś pomyślał o tworzeniu słownika w sposób alfabetyczny i zastosował wyszukiwanie binarne, albo utwórz drzewo tłumaczeń z podziałem na litery - przemieszczanie się po drzewie wgłąb doprowadzało by do liścia, który zawierałby tłumaczenie (albo i nie).

    0
  • #6 10 Maj 2011 01:43
    asembler
    Poziom 32  

    Podpowiem. Metoda bisekcji skróci czas wykonywania zdecydowanie teoretycznie przy tych załozeniach 192 razy szybciej.

    0