Wyzwanie

Origami (składany papier) to kreatywna forma sztuki. O ile mi wiadomo, mistrz Origami woli kwadratowy papier. Zacznijmy od początku - zamień prostokątny papier na kwadratowy.

Więc papier jest podzielony na kwadraty. Usuwamy największy kwadrat, który dzieli jedną krótszą krawędź z bieżącym kształtem, krok po kroku (patrz obrazek poniżej). A jeśli pozostała część po jednym kroku jest mniejsza lub równa 0.001 * (area of the original paper), papier nie może być dalej dzielony. Możliwe, że w końcu nic nie pozostaje.

Twoim zadaniem jest obliczyć, ile kwadratów powstaje podczas procesu. Kwadrat w ostatnim kroku, który uniemożliwia podział papieru, jest liczony do wyniku.

Przykład (papier o 1.350szerokości / wysokości), wydajność wynosi 10:

Wejście i wyjście

Dane wejściowe: stosunek szerokości do wysokości dla papieru prostokątnego, jedna dziesiętna (lub liczba całkowita bez kropki) od 1.002do 1.999z minimalnym krokiem 0.001. Możesz także użyć dowolnego innego rozsądnego formatu opisującego stosunek. Po prostu wspomnij o tym w swojej odpowiedzi.

Wyjście: liczba kwadratowa, jedna liczba całkowita.

Przykład I / O

Format mapowania jest używany, aby utrzymać porządek na stronie, podczas gdy twój kod nie musi obsługiwać danych wejściowych listy ani być funkcją mapowania.

1.002 => 251
1.003 => 223
1.004 => 189
1.005 => 161
1.006 => 140
1.007 => 124
1.008 => 111
1.009 => 100

Lista wszystkich odpowiedzi

Dzięki @LuisMendo, oto wykres odpowiedzi.

Uwagi

• To jest golf golfowy, więc wygrywa najkrótszy kod
• Zwróć uwagę na standardowe luki
• To Ty decydujesz, jak postępować z wejściami i wyjściami, ale powinny one przestrzegać standardowych ograniczeń.

Tak poza tym...

• Skomentuj, jeśli masz coś niejasnego na temat wyzwania
• Osobiście sugerowałbym, że twoja odpowiedź zawiera wyjaśnienie, jeśli używasz języka golfowego
• Dzięki @GregMartin, przeczytaj jego odpowiedź na dobre matematyczne wyjaśnienie wyzwania.

Przykładowy kod

Oto nieoznakowana wersja kodu C ++:

#include <iostream>
#include <utility>

int f (double m)
{
    double n = 1, k = 0.001;
    int cnt = 0;
    k *= m;                       // the target minimum size
    while(m*n >= k)
    {
        m -= n;                   // extract a square
        if(n > m)
            std::swap(n, m);      // keep m > n
        ++ cnt;
    }
    return cnt;
}

int main()
{
    double p;
    std::cin >> p;
    std::cout << f(p);
    return 0;
}

Wszystkie obliczenia związane z przykładowym kodem wymagają dokładności 6 cyfr dziesiętnych, co jest objęte float.

MATL , 19 bajtów

`SZ}y-htG/p1e-3>}x@

Dane wejściowe to tablica z dwiema liczbami określającymi oryginalny stosunek, np [1, 1.009]. (Nie jest konieczne, aby liczby były sortowane lub aby jeden z nich był 1.)

Wypróbuj online!

Wyjaśnienie

`        % Do...while loop
  S      %   Sort array. Takes 1×2 array as input (implicit) the first time
  Z}     %   Split array into its 2 elements: first the minimum m, then the maximum M
  y      %   Duplicate m onto the top of the stack. The stack now contains m, M, m
  -      %   Subtract. The stack now contains m, M-m
  h      %   Concatenate into [m, M-m]. This is the remaining piece of paper
  t      %   Duplicate
  G/     %   Divide by input, element-wise
  p      %   Product of array. Gives ratio of current piece's area to initial area
  1e-3>  %   True if this ratio exceeds 1e-3. In that case the loop continues
}        % Finally (execute after last iteration, but still within the loop)
  x      %   Delete last piece of paper
  @      %   Push current loop counter. This is the result
         % End (implicit)
         % Display (implicit)

Haskell , 71 70 65 63 62 61 58 56 bajtów

Dzięki @xnor za kilka genialnych ulepszeń!

(n#m)e|e>n*m*1e3=0|n<m=m#n$e|d<-n-m=(d#m)e+1
n!m=n#m$n*m

Wypróbuj online!

JavaScript (ES6), 59 58 bajtów

f=(m,n=!(k=m/1e3,c=0))=>m*n<k?c:(c++,m-=n)<n?f(n,m):f(m,n)

Test

f=(m,n=!(k=m/1e3,c=0))=>m*n<k?c:(c++,m-=n)<n?f(n,m):f(m,n)

console.log(f(1.002))
console.log(f(1.003))
console.log(f(1.004))
console.log(f(1.005))
console.log(f(1.006))
console.log(f(1.007))
console.log(f(1.008))
console.log(f(1.009))

Matematyka, niekonkurujące ze sobą (21 bajtów)

Ta odpowiedź nie jest konkurencyjna, ponieważ nie odpowiada na faktycznie zadane pytanie! Ale odpowiada na wariant pytania i stanowi pretekst do podkreślenia interesującej matematyki.

Tr@*ContinuedFraction

Funkcja symboliczna przyjmująca dodatnią liczbę wymierną jako dane wejściowe (której licznik i mianownik reprezentują wymiary oryginalnego papieru) i zwracająca dodatnią liczbę całkowitą. Na przykład Tr@*ContinuedFraction[1350/1000]zwraca 10. ( ContinuedFractiondziała inaczej na liczbach zmiennoprzecinkowych ze względu na problemy z precyzją, dlatego w tym kontekście potrzebna jest liczba wymierna).

Interesującą interpretacją procedury geometrycznej opisanej w tym problemie (wielokrotne wycinanie kwadratów z prostokąta) jest to, że jest to implementacja algorytmu euklidesowego do znajdowania największych wspólnych dzielników! Rozważ przykład w samym pytaniu ze współczynnikiem1.35, który można by wymodelować, mając kawałek papieru o wymiarach (1350,1000). Za każdym razem, gdy kwadrat jest odcinany, mniejsza liczba jest odejmowana od większej liczby; więc powstałe prostokąty w tym przykładzie mają wymiary (350,1000), następnie (350,650), następnie (350,300), następnie (50,300), następnie (50,250) i (50,200) i (50,150) i (50,100) i (50, 50), a także (50,0) po odebraniu od siebie ostatniego kwadratu. Dokładnie tak działa algorytm euklidesowy (modulo różnica między dzieleniem a powtarzanym odejmowaniem), i rzeczywiście widzimy, że 50 to rzeczywiście GCD 1350 i 1000.

Zazwyczaj w algorytmie euklidesowym śledzi się te pośrednie wymiary i odrzuca liczbę odejmowań; można jednak naprzemiennie rejestrować, ile razy odejmowaliśmy jedną liczbę od drugiej, zanim różnica stanie się zbyt mała, i musimy zmienić to, co odejmujemy. Ta metoda zapisu jest właśnie ciągłym ułamkiem liczby wymiernej. (Ciągłe ułamki liczb niewymiernych, które nigdy się nie kończą, są również super fajne, ale tutaj nie mają znaczenia.) Na przykład w przykładzie 1350/1000 odjęliśmy 1000 1razy, potem 350 2razy, potem 300 razy, a 1potem 50 6razy; dlatego ciągła część 1350/1000 wynosi {1,2,1,6}. Matematycznie przepisaliśmy 1350/1000 na 1+ 1 / ( 2+ 1 / ( 1+ 1 /6)), które możesz zweryfikować.

Jeśli chodzi o ten problem, jeśli nie przestaniesz, gdy kwadraty będą mniejsze niż pewien próg, ale po prostu policzy wszystkie skończone wiele kwadratów przed zatrzymaniem, wówczas całkowita liczba kwadratów będzie równa całkowitej liczbie odejmowań, to znaczy suma wszystkich liczb całkowitych w ułamku ciągłym - i dokładnie to Tr@*ContinuedFractionoblicza skład funkcji ! (W podanym przykładzie 1.35 otrzymuje odpowiedź, której pragnie OP, ponieważ ostatni kwadrat jest wystarczająco duży, aby policzyć wszystkie kwadraty. Ale Tr@*ContinuedFraction[1001/1000], na przykład, daje 1001, ponieważ liczy jeden wielki kwadrat i wszystkie 1000 małych 1x1000 kwadratów .)

Mathematica, 64 53 bajtów

({t=1,#}//.{a_,b_}/;1000a*b>#:>Sort@{++t;a,b-a};t-1)&

Rozwiązanie imperatywne (w stylu C) ma dokładnie taką samą długość:

(For[t=a=1;b=#,1000a*b>#,If[a>b,a-=b,b-=a];++t];t-1)&

C (GCC / Clang), 61 59 bajtów

c,k;f(m,n){for(k=m*n;m*n/k;m>n?(m-=n):(n-=m))++c;return c;}

Dane wejściowe to dwie liczby całkowite (szerokość i wysokość) bez kropki, takie jak f(1999,1000).

Mam nadzieję, że ktoś uratuje jeden bajt pchając C do 58-bajtowego klubu. ;)

C, 59 bajtów

s,a,n=1e3;C(m){for(a=m;m*n>a;s++)m>n?m-=n:(n-=m);return s;}

Wypróbuj online

Dane wejściowe to liczba całkowita, która jest stosunkiem szerokości do wysokości w tysięcznych częściach (np. 1002 dla 1,002: 1).

Wersja bez golfa

int C(int m)
{
    int n = 1000;
    int a = m;
    int s = 0;

    while (m * n > a)
    {
        if (m > n)
            m -= n;
        else
            n -= m;

        s++;
    }

    return s;
}