Matematyka.pl

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?

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.

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

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.

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.

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

Matematyka.pl

Minimalny obwód prostokąta przy zadanym polu.

Minimalny obwód prostokąta przy zadanym polu.

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

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

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

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

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