Nov 2016
13 / 49
Aug 2018
Feb 2024
loginus
Jul '17
markoyee

Rekurencja !!! -- naprawde !!! -- really !!!

  1. Rekurencja to chyba jedna z najwolniejszych metod . Każde odwołanie to wrzucenie na stos całej masy danych co jest kosztowne . Do tego może się zdarzyć że zabraknie prędzej pamięci niż znajdziesz rozwiązanie . NASA podobno zakazuje stosowania rekurencji w algorytmach które obsługuje sprzęt w kosmosie .

  2. Nazwanie funkcji "rekurencja" to nie najlepszy pomysł - lepiej ją nazwać NWD lub GCD - od razu wiesz co ten kawałek kodu robi .

  3. Ja to zadanie zrobiłem z użyciem SITA - generuje tablice w której dla indeksów liczb pierwszych wstawiam jeden a dla pozostałych najmniejszy dzielnik danej liczby ( indeksu ). Dla takiej metody tylko raz ustalasz która liczba jest pierwsza . Sprawdzenie na jakie kwadraty podzielić działkę to sprawdzenie jednej zmiennej z SITA .

narbej
Jul '17
markoyee

to:

        while (a%i!=0)
        {
            i--;
        }

jest głównym "winowajcą" i powodem tle [time limit ...] - za wolno..

7 months later
5 months later
konradu99
Aug '18
1

Hej, mógłby ktoś zobaczyć, co jest nie tak, podać dodatkowe testy itp…

fulse
Aug '18

Po zastanowieniu nasz bohater doszedł do wniosku, że owszem podziału trzeba dokonać, ale powstałe kwadratowe pola powinny być jak największe.

Musi być podział, dlatego to:

if(a==b)
{
cout << a << endl;
}

nie ma sensu.

konradu99
Aug '18

@fulse dzięki za podpowiedź, rzeczywiście to nie ma sensu, bo dla kwadratu działa, ale po zrobieniu tej korekty dalej daje błędną odpowiedź…

fulse
Aug '18

Ja też dalej szukam :smiley: jak znajdę to dam jakąś wskazówkę :slight_smile:

fulse
Aug '18
1

in
1
6127 6127

out
557

@konradmal
Uwaga na liczby pierwsze oraz na szukanie dzielnika w taki sposób:

i = 2;
while( a % i != 0 )
i++;

konradu99
Aug '18

Właśnie sprawdziłem test 6127 6127 i zarówno na ideone, jak i u mnie w Dev-C++ out wynosi 6127… Co do liczb pierwszych, to możesz mi powiedzieć coś więcej? Bo wg. mnie ten program działa na liczby pierwsze poprawnie? :wink:

fulse
Aug '18

Z liczbą pierwszą chodziło mi o taki przypadek:
1
10007 10007
lub
1
13 13

Jaka będzie maksymalna długość boku działki kwadratowej w tej działce ?

konradu99
Aug '18

Dla dwóch takich samych liczb pierwszych właśnie ta liczba pierwsza. Tyle, że program taką odpowiedź zwraca. Zresztą dla każdego kwadratu odpowiedzią jest właśnie bok tego kwadratu.

fulse
Aug '18

na pewno ?

Po zastanowieniu nasz bohater doszedł do wniosku, że owszem podziału trzeba dokonać, ale powstałe kwadratowe pola powinny być jak największe.

Treść zadania mówi co innego, jeżeli odpowiedzią jest bok tego kwadratu to nie doszło do podziału, prawda ? :smiley:

konradu99
Aug '18

Ach rozumiem… :stuck_out_tongue: Spróbuję coś z tą wiedzą zrobić i później dam znać, co mi wyszło! :wink:

redysz
Aug '18

Parę ciekawszych testów (wyniki różne od 1) do kontroli

In

32
530 795
539 847
442 425
667 828
980 360
716 358
624 768
740 200
665 490
341 713
186 589
684 804
693 396
803 803
38 874
350 854
182 468
525 945
468 576
343 735
104 663
13 962
145 174
960 840
714 483
325 117
627 304
507 247
803 803
570 228
506 836
112 784

Mój out:

265
77
17
23
20
358
48
20
35
31
31
12
99
73
38
14
26
105
36
49
13
13
29
120
21
13
19
13
73
114
22
112
konradu99
Aug '18

Ok, to znowu ja, byłem akurat poza domem przez kilka ostatnich dni, troszkę poprzerabiałem i w końcu zaakceptowało. Dzięki Wam za pomoc!

13 days later
manjaro
Aug '18
fulse

To jest kategoria łatwe i nie trzeba stosować żadnego SITA. Wystarczy sprawdzać a%i z pewnym małym dodatkowym warunkiem :wink:

6 months later
jayman
Mar '19

https://ideone.com/UnQbsM23

Witam,
mam problem z zadaniem MWP3_1C1 - Działka. Mój kod zwarca poprawne wartości, ale sędzia nie chce tego zaakceptować. Stosowałem rózne wskazówki do tego kodu, które znalazłem w internecie lub na tym forum, jednakże sędzia dalej jest nieugięty. Miałbym prośbę, o w miarę możliwości przejrzenie mojego kodu.

Pozdrawiam
Tomasz

czaffik
Mar '19

in:
2
2 2
803 803
etc.
Tj. gdy a == b jest błąd, zadanie dopuszcza chyba i takie przypadki. Mowa o prostokącie ale kwadrat to też prostokąt.