Minimalny obwód prostokąta przy zadanym polu.

gawiellus
Użytkownik
Użytkownik
Posty: 19
Rejestracja: 16 maja 2016, o 00:24
Płeć: Mężczyzna
Lokalizacja: Kielce
Podziękował: 1 raz

Minimalny obwód prostokąta przy zadanym polu.

Post autor: gawiellus »

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: 287
Rejestracja: 18 lip 2022, o 17:46
Płeć: Mężczyzna
wiek: 40
Podziękował: 3 razy
Pomógł: 41 razy

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

Post autor: 3a174ad9764fefcb »

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: 19
Rejestracja: 16 maja 2016, o 00:24
Płeć: Mężczyzna
Lokalizacja: Kielce
Podziękował: 1 raz

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

Post autor: gawiellus »

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: 287
Rejestracja: 18 lip 2022, o 17:46
Płeć: Mężczyzna
wiek: 40
Podziękował: 3 razy
Pomógł: 41 razy

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

Post autor: 3a174ad9764fefcb »

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: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

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

Post autor: a4karo »

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: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

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

Post autor: Dasio11 »

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