Tantangan

Origami (kertas lipat) adalah bentuk seni kreatif. Sejauh yang saya tahu, penguasa Origami lebih suka kertas persegi. Mari kita mulai dari awal - mengkonversi kertas persegi panjang menjadi persegi.

Jadi kertas itu dibagi menjadi kotak. Kami menghapus persegi terbesar yang berbagi satu tepi lebih pendek dengan bentuk saat ini, langkah demi langkah (lihat gambar di bawah). Dan jika bagian yang tersisa setelah satu langkah kurang atau sama dengan 0.001 * (area of the original paper), kertas tidak dapat dibagi lebih jauh. Mungkin akhirnya tidak ada yang tersisa.

Tugas Anda adalah menghitung berapa banyak kotak yang dibuat selama proses. Kuadrat pada langkah terakhir yang membuat kertas tidak dapat dibagi dihitung ke dalam output.

Contoh (kertas 1.350lebar / tinggi), outputnya 10:

Masukan dan keluaran

Input: rasio / tinggi lebar untuk kertas persegi panjang, satu desimal (atau integer tanpa dot) dari 1.002ke 1.999dengan langkah minimal 0.001. Anda juga dapat menggunakan format wajar lainnya yang menjelaskan rasio. Sebut saja dalam jawaban Anda.

Output: jumlah kuadrat, satu bilangan bulat.

Contoh I / O

Format pemetaan digunakan untuk menjaga halaman tetap rapi, sementara kode Anda tidak perlu mendukung input daftar atau menjadi fungsi pemetaan.

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

Daftar semua jawaban

Berkat @LuisMendo, berikut adalah grafik jawaban.

Catatan

• Ini adalah kode-golf sehingga kode terpendek menang
• Perhatikan celah standar
• Adalah kebebasan Anda untuk memutuskan bagaimana menangani input dan output tetapi mereka harus mengikuti batasan standar.

Ngomong-ngomong...

• Beri komentar jika Anda memiliki sesuatu yang tidak jelas tentang tantangannya
• Secara pribadi saya menyarankan jawaban Anda berisi penjelasan jika Anda menggunakan bahasa golf
• Terima kasih kepada @GregMartin, bacalah jawabannya untuk penjelasan matematika yang bagus untuk tantangannya.

Kode Contoh

Berikut ini adalah kode C ++ versi ungolfed:

#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;
}

Semua perhitungan yang terkait dalam kode contoh membutuhkan akurasi 6 angka desimal, yang tercakup dalam float.

MATL , 19 byte

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

Input adalah array dengan dua angka yang mendefinisikan rasio asli, seperti [1, 1.009]. (Tidak perlu bahwa angka-angka disortir atau salah satu dari mereka 1.)

Cobalah online!

Penjelasan

`        % 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 byte

Terima kasih kepada @xnor untuk peningkatan yang cerdik!

(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

Cobalah online!

JavaScript (ES6), 59 58 byte

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

Uji

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))

Mathematica, non-non-pesaing (21 byte)

Jawaban ini tidak bersaing karena tidak menjawab pertanyaan aktual yang diajukan! Tapi itu menjawab varian pertanyaan, dan memberikan alasan untuk menyoroti beberapa matematika yang menarik.

Tr@*ContinuedFraction

Fungsi simbolik mengambil bilangan rasional positif sebagai input (yang pembilang dan penyebutnya mewakili dimensi kertas asli) dan mengembalikan bilangan bulat positif. Misalnya, Tr@*ContinuedFraction[1350/1000]kembali 10. ( ContinuedFractionbertindak berbeda pada bilangan floating-point karena masalah presisi, itulah sebabnya bilangan rasional diperlukan sebagai input dalam konteks ini.)

Penafsiran yang menarik dari prosedur geometris yang dijelaskan dalam masalah (memotong kotak dari persegi panjang berulang kali) adalah bahwa itu merupakan implementasi dari algoritma Euclidean untuk menemukan pembagi umum terbesar! Pertimbangkan contoh dalam pertanyaan itu sendiri, dengan rasio1.35, yang dapat dimodelkan dengan memiliki selembar kertas dengan dimensi (1350.1000). Setiap kali kotak dipotong, jumlah yang lebih kecil dikurangi dari jumlah yang lebih besar; jadi persegi panjang yang dihasilkan dalam contoh ini memiliki dimensi (350.1000), lalu (350.650), lalu (350.300), lalu (50.300), kemudian (50.250) dan (50.200) dan (50.150) dan (50.150) dan (50.100) dan (50, 50), dan juga (50,0) begitu kita mengambil kuadrat terakhir dari dirinya sendiri. Inilah tepatnya bagaimana algoritma Euclidean beroperasi (modulo perbedaan antara pembagian dan pengurangan berulang), dan memang kita melihat bahwa 50 memang GCD dari 1350 dan 1000.

Biasanya dalam algoritma Euclidean, orang melacak dimensi menengah ini dan membuang jumlah pengurangan; namun, satu dapat secara bergantian mencatat berapa kali kita mengurangi satu nomor dari yang lain sebelum perbedaannya menjadi terlalu kecil dan kita harus mengganti apa yang kita kurangi. Metode pencatatan itu justru merupakan pecahan lanjutan dari bilangan rasional. (Fraksi lanjutan dari bilangan irasional, yang tidak pernah berakhir, juga sangat keren, tetapi tidak relevan di sini.) Misalnya, dalam contoh 1350/1000, kami mengurangi 1000 1kali, lalu 350 2kali, lalu 300 1kali, kemudian 50 6kali; Oleh karena itu fraksi lanjutan dari 1350/1000 adalah {1,2,1,6}. Secara matematis, kami telah menulis ulang 1350/1000 sebagai 1+ 1 / ( 2+ 1 / ( 1+ 1 /6)), yang dapat Anda verifikasi.

Jadi untuk masalah ini, jika Anda tidak berhenti ketika kuadrat menjadi lebih kecil dari ambang tertentu, tetapi cukup hitung semua kuadrat yang jauh sebelum berhenti, maka jumlah total kuadrat sama dengan jumlah total pengurangan, artinya jumlah semua bilangan bulat dalam fraksi lanjutan — dan itulah yang dihitung oleh komposisi fungsi Tr@*ContinuedFraction! (Untuk contoh yang diberikan 1.35, ia mendapatkan jawaban keinginan OP, karena kuadrat terakhir cukup besar sehingga semua kotak dihitung. Tetapi Tr@*ContinuedFraction[1001/1000], misalnya, menghasilkan 1001, karena menghitung satu kotak besar dan semua 1000 dari kotak 1x1000 kecil .)

Mathematica, 64 53 byte

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

Solusi imperatif (gaya-C) memiliki panjang yang persis sama:

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

C (GCC / Dentang), 61 59 byte

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

Input adalah dua bilangan bulat (lebar & tinggi) tanpa titik, seperti f(1999,1000).

Saya harap seseorang bisa menyimpan satu byte mendorong C ke klub 58-byte. ;)

C, 59 byte

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

Cobalah online

Input adalah bilangan bulat yang merupakan rasio lebar / tinggi dalam seperseribu (mis. 1002 untuk 1,002: 1).

Versi tidak disatukan

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;
}