• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

SPOJ upraszczanie ulamków

VPS Starter Arubacloud
0 głosów
376 wizyt
pytanie zadane 26 lipca 2017 w SPOJ przez chucksqll Stary wyjadacz (12,930 p.)

WItam.

Robię zadanie ze spoja(link poniżej) no i niestety dla mnie mam przekroczony limit czasu, także zwracam się do was z prośbą o pomoc. Nie wiem jak bardziej mogę go uprościć, czy trzeba zrobić to zadanie inną drogą pomimo, że jak dla mnie wyraźnie jest napisane, że trzeba tą, która robiłem. Dziękuję za pomoc.

http://pl.spoj.com/problems/FR_06_13/

#include <iostream>


using namespace std;

int skracanie(int a, int b,int ilosc=1)
{
    if(a==b)
        return ilosc;
    if(a>b)

        return skracanie(a-b,b,++ilosc);
    if(b>a)

        return skracanie(a,b-a,++ilosc);
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int a,b;
        char znak;
        cin>>a>>znak>>b;
        if((a==1)||(b==1))
        {
            if(a>b)
                cout<<a<<endl;
            if(b>a)
                cout<<b<<endl;
            if(a==b)
                cout<<"1"<<endl;

        }

        else
            cout<<skracanie(a,b)<<endl;


    }
    return 0;
}


 

2 odpowiedzi

0 głosów
odpowiedź 26 lipca 2017 przez Jedras Maniak (54,860 p.)
Można wykorzystać algorytm Euklidesa, ale zamiast odejmować można kombinować z dzieleniem.
0 głosów
odpowiedź 26 lipca 2017 przez d0n Mądrala (6,440 p.)
edycja 26 lipca 2017 przez d0n

Dalej w treści jest napisane, że " Niestety algorytm ten, oparty na odejmowaniu ma jedną dużą wadę. Czasami liczba odejmowań, jakie trzeba wykonać, jest tak duża, że lepiej pozostawić ułamek w spokoju," I jest to prawda, bo nieistotne, że sprawdziłeś czy a lub b nie są równe 1, skoro a może być równe 10^9, a b równe 2 i twój program wykona ~ miliard operacji, kiedy powinniśmy celować w co najwyżej dziesiątki milionów operacji. Zadanie polega wykorzystaniu operacji dzielenia i dzielenia z resztą ( '%' w c++ ), i polega na dodaniu jednej linijki kodu do algorytmu euklidesa (który z resztą też można zapisać w jednej linijce kodu)

Podobne pytania

0 głosów
1 odpowiedź 1,080 wizyt
pytanie zadane 19 października 2016 w C i C++ przez Paq_93 Początkujący (260 p.)
0 głosów
1 odpowiedź 3,289 wizyt
+1 głos
2 odpowiedzi 551 wizyt
pytanie zadane 1 marca 2016 w C i C++ przez cherubinek Nowicjusz (190 p.)

92,830 zapytań

141,771 odpowiedzi

320,817 komentarzy

62,159 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...