Minimalny obwód prostokąta przy zadanym polu.

gawiellus
Użytkownik
Użytkownik
Posty: 10
Rejestracja: 16 maja 2016, o 00:24
Płeć: Mężczyzna
Lokalizacja: Kielce

Minimalny obwód prostokąta przy zadanym polu.

Post autor: gawiellus » 23 lip 2022, o 21:22

Witam
Piszę funkcję, której zadaniem jest znalezienie minimalnego obwodu prostokąta, przy zadanym polu. Długość i szerokość muszą być różnymi wartościami całkowitymi, tzn. że nie można tego policzyć wyciągając pierwiastek kwadratowy z pola. Poniżej kod.

Kod: Zaznacz cały

typedef unsigned long long ull;

ull minimum_perimeter(ull area) {
  long double a,b;
  for(a = floor(sqrtl(area)),b = ceil(sqrtl(area));a*b!=area;a--)
  {
    ull b_b=b;
    for(;a*b_b<area;b_b++);
    if(a*b_b==area)
      return 2*(a+b_b);
  }
  return 2*(a+b);
}
Dla małych wartości funkcja działa poprawnie, ale nie przechodzi testów z powodu przekroczenia czasu wykonania. Proszę o wskazówki jak zoptymalizować kod. Do jakiego problemu matematycznego można sprowadzić to zadanie?

3a174ad9764fefcb
Użytkownik
Użytkownik
Posty: 99
Rejestracja: 18 lip 2022, o 17:46
Płeć: Mężczyzna
wiek: 34
Podziękował: 2 razy
Pomógł: 7 razy

Re: Minimalny obwód prostokąta przy zadanym polu.

Post autor: 3a174ad9764fefcb » 23 lip 2022, o 22:16

Na pewno ta wewnętrzna pętla jest Ci niepotrzebna. Żeby obliczyć \(\left\lfloor\frac{S}{a}\right\rfloor\) albo \(\left\lceil\frac{S}{a}\right\rceil\), nie trzeba żadnej pętli.

gawiellus
Użytkownik
Użytkownik
Posty: 10
Rejestracja: 16 maja 2016, o 00:24
Płeć: Mężczyzna
Lokalizacja: Kielce

Re: Minimalny obwód prostokąta przy zadanym polu.

Post autor: gawiellus » 23 lip 2022, o 23:05

Funkcje ceil i floor ustawiają tylko początkowe wartości zmiennnych. W pętli szukam takich a i b które spełnią warunek
a * b = area

3a174ad9764fefcb
Użytkownik
Użytkownik
Posty: 99
Rejestracja: 18 lip 2022, o 17:46
Płeć: Mężczyzna
wiek: 34
Podziękował: 2 razy
Pomógł: 7 razy

Re: Minimalny obwód prostokąta przy zadanym polu.

Post autor: 3a174ad9764fefcb » 24 lip 2022, o 11:02

Chodzi mi o tę pętlę.
gawiellus pisze:
23 lip 2022, o 21:22

Kod: Zaznacz cały

    ull b_b=b;
    for(;a*b_b<area;b_b++);
Czemu ona ma służyć, jeśli nie obliczeniu wartości \(\mathrm{b\_b} = \left\lceil \frac{\mathrm{area}}{\mathrm{a}}\right\rceil\)? Nawet jeśli już taką pętlę wykonujesz, to nie wiem po co sprawdzasz te same wartości b_b wielokrotnie. Jeśli dane b_b jest za małe dla jakiegoś a, to tym bardziej będzie za małe dla mniejszego a.

a4karo
Użytkownik
Użytkownik
Posty: 20413
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 27 razy
Pomógł: 3458 razy

Re: Minimalny obwód prostokąta przy zadanym polu.

Post autor: a4karo » 25 lip 2022, o 14:59

Jezeli pole będzie dużą liczbą pierwszą, to takimi pętlami zarobisz się na śmierć (jedynym prostokątem jest `1\times`pole).

Proponuje znaleźć efektywniejszy algorytm rozkładu liczby na czynniki pierwsze.

Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 9836
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 38 razy
Pomógł: 2233 razy

Re: Minimalny obwód prostokąta przy zadanym polu.

Post autor: Dasio11 » 25 lip 2022, o 16:40

Ale jeśli liczba jest złożona, to jej rozkład na czynniki pierwsze chyba w niczym nie pomaga?

ODPOWIEDZ