Ubin persegi unit

8

Latar Belakang

Dengan memperluas dan membatalkan persyaratan, mudah untuk menunjukkan identitas berikut:

masukkan deskripsi gambar di sini

Namun, ini merupakan masalah terbuka apakah semua persegi panjang 1 / n-oleh-1 / (n + 1) dapat membentuk kotak unit.

Tugas

Program Anda harus mengambil bilangan bulat positif N sebagai input dengan cara yang mudah, dan kemas semua persegi panjang 1 / n-by-1 / (n + 1) dengan n antara 1 dan N termasuk ke dalam unit square, sehingga tidak ada dua tumpang tindih .

Untuk setiap kotak Anda harus membuat bilangan bulat berikut secara berurutan:

  • 1 jika tepi horisontal lebih panjang dari tepi vertikal, kalau tidak 0
  • Pembilang dan penyebut koordinat-x sudut kiri bawah
  • Pembilang dan penyebut koordinat y dari sudut kiri bawah

Perhatikan bahwa kita mengambil unit square menjadi (0, 1) x (0, 1), dengan nilai x berjalan dari kiri ke kanan, dan nilai y berjalan dari bawah ke atas.

Hasil akhir yang diharapkan adalah gabungan bilangan bulat ini untuk setiap persegi panjang dalam urutan peningkatan n, dalam format apa pun yang nyaman (misalnya dicetak ke stdout, atau sebagai daftar yang dikembalikan dari suatu fungsi).

Contoh Input dan Output

Memasukkan:

3

Keluaran:

0 0 1 0 1 1 1 2 0 1 1 1 2 1 3

Ini mem-parsing sebagai berikut:

0 (0/1, 0/1)  1 (1/2, 0/1)  1 (1/2, 1/3)

Mencetak gol

Ini adalah tantangan kode-golf, jadi jawabannya dengan byte paling sedikit menang. Namun, algoritma Anda juga harus cukup efisien; itu harus bisa berjalan untuk semua N<=100dalam total sekitar 10 menit.

Solusi Anda harus memberikan solusi yang valid untuk semua N<=100, tetapi algoritme yang lengkap dan lengkap juga dapat diterima meskipun itu bukan yang terpendek.

pengguna1502040
sumber
Melihat ini adalah masalah terbuka, apakah ada batasan pada nilai terbesar $ N $ yang algoritme kami harus dijamin berfungsi?
Greg Martin
@GregMartin Anda harus berhasil menjalankan program Anda untuk N dari 1 hingga 20. Brownie poin jika algoritma Anda dapat terbukti berhasil atau menyangkal dugaan.
user1502040
Untuk N≤20 output hanya bisa dikodekan ... apakah itu niat Anda untuk mengizinkannya? Ada algoritma sederhana yang diterbitkan yang memungkinkan setidaknya N = 1.000.000.000 ....
Greg Martin
OK, saya mengubah ambang batas dari 20 menjadi 100.
user1502040
Oh kebaikan. Saya belum belajar jumlah hingga tak terbatas, jadi saya tidak mengerti ini sama sekali.
Matthew Roh

Jawaban:

2

Haskell, 263 262 byte

import Data.Ratio;f m=let{(#)n z|n>m=[[]]|True=[a:y|(a,j)<-[((o,x,y),[c|c<-(u&w,h-v,x,g):(w-u,h&v,a,y):z,c/=b])|b@(w,h,x,y)<-z,(o,u,v)<-[(o,1%(n+1-o),1%(n+o))|o<-[0,1]],(a,g)<-[(x+u,y+v)|u<=w,v<=h],let(&)p q|w>h=p|True=q],y<-(n+1)#j]}in(1#[(1%1,1%1,0%1,0%1)])!!0

Ini mengikuti algoritma yang dijelaskan dalam Paulhus 1997, Algoritma untuk Kotak Pengemasan , doi: 10.1006 / jcta.1997.2836 . Pengamatan utama dalam makalah, yang secara empiris jika tidak diverifikasi secara teoritis, adalah bahwa daerah yang tersisa setelah menempatkan persegi panjang dalam kotak dapat dibagi menjadi dua sub-kotak yang isiannya kemudian dapat dianggap independen.

Daripada menemukan sub-kotak lebar terkecil yang sesuai dengan persegi panjang berikutnya, kode melakukan pencarian di semua sub-kotak yang mungkin; dalam praktiknya ini tidak membuat perlambatan yang cukup besar untuk n <100.

Keluaran dalam bentuk daftar entri sebagai tupel dengan penanda fraksi %masih disertakan. Bilangan bulat dalam output yang diformat berada dalam urutan yang diinginkan, tetapi secara tegas beberapa post-processing akan diperlukan untuk menghasilkan daftar bilangan bulat saja.

Contoh dijalankan:

*Main> f 5 (0,0 % 1,0 % 1),(0,1 % 2,0 % 1),(0,1 % 2,1 % 2),(0,3 % 4,1 % 2),(1,1 % 2,5 % 6)

Sunting: menghapus ruang yang salah setelah a let.

halfflat
sumber