Podziel n X nkwadrat na wiele nie przystających prostokątów o liczbach całkowitych. a(n)jest najmniejszą możliwą różnicą między największym a najmniejszym obszarem.

 ___________
| |S|_______|
| | |   L   |
| |_|_______|
| |     |   |
| |_____|___|
|_|_________| (fig. I)

Największy prostokąt ( L) ma powierzchnię 2 * 4 = 8, a najmniejszy prostokąt ( S) ma powierzchnię 1 * 3 = 3. Dlatego różnica jest taka 8 - 3 = 5.

Biorąc pod uwagę liczbę całkowitą n>2, wyprowadzaj najmniejszą możliwą różnicę.

Wszystkie znane wartości sekwencji w momencie publikacji:

2, 4, 4, 5, 5, 6, 6, 8, 6, 7, 8, 6, 8, 8, 8, 8, 8, 9, 9, 9, 8, 9, 10, 9, 10, 9, 9, 11, 11, 10, 12, 12, 11, 12, 11, 10, 11, 12, 13, 12, 12, 12

Tak a(3)=2, a(4)=4...

OEIS A276523

Powiązane - to powiązane wyzwanie umożliwia nieoptymalne rozwiązania, ma ograniczenia czasowe i nie jest golfem kodowym.

Aby uzyskać więcej informacji, obejrzyj ten film autorstwa Numberphile

CJam, 178

ri_1a*a*L{_:+1&{_[3{_\zW%}*]{_z}%:e<_@={:A0=_1#:X0<{;A1>j}{X>0+0#AzX=0+0#,\,m*1ff+{[_$\~1a*0aX*\+a*A\..-_])s'-&{;}&}%{~j\:X;{Xa&!},Xaf+:$~}%_&}?}{j}?}{;La}?}j{,(},{::*$)\0=-}%:e<

Wypróbuj online . Jest jednak bardzo powolny, nie zalecałbym przekraczania 6.

Aby sprawdzić, czy naprawdę działa, możesz sprawdzić ten nieco zmodyfikowany program, który drukuje wszystkie możliwe partycje (każda partycja jest pokazana jako tablica par wymiarów prostokątnych).

Befunge, 708 bajtów

p&>:10p1-:>20p10g:20g\`v`\g02:-1\p00+1g<>g-#v_10g:*30p"~":40p50p060p070p$>^
1#+\#1<\1_^# !`0::-1$  _:00g3p\:00g2p00^^00:>#:


>>:2-#v_$30p50p60p70g1-70p
^<<<<<:#<<<<<<$$$_v#:!g87g78g79$  _v#!\-1:g88$<_ 98p87g97g*00 v:+!\`*84g++7<
^>$1-:77p1g:2g\3g1>78p97p87p10g97g->88p10g87g-0^!\-1:g89_v#-!\_$1-:v>/88g+7^
^|!-3$<   >\87g/88g+77++p:#v_$
^>:5->v   ^+g89%g78:\g77:-1<>98g88g48*577g387g97g98g88v ^>77g87g97v:^g78\+g<
^ v-4:_$77p88p98p:97p\:87p*^^g79g7>#8\#$_40pv5+"A"g77g< ^14g88g89g<>:87g%98^
^v_$88p98p97p87p:77p60g50g-:40g\`#^_$$>>>>>>>
 >#4!_::80p2g\3g*:90p30g`!v>>>#@>#.>#g^#0
^v:g06p03:-g09\2:g03g05g06_^^_7#<0#<g#<3#<1#<<`g04_$00g1->:#-8#10#\g#1`#:_>$
^>90g\-:0`*+:60p50g:90g-:0`*-:50p-80g70g:1+70p1p\!^

Wypróbuj online!

To oczywiście nie zdobędzie żadnych nagród za rozmiar, ale w rzeczywistości jest dość szybki, biorąc pod uwagę, że jest to podstawowa implementacja bruce force w ezoterycznym języku. W tłumaczu referencyjnym Befunge może obsłużyć do n = 6 w ciągu kilku sekund. Dzięki kompilatorowi może obsłużyć do n = 8, zanim zacznie się leniwie; n = 9 zajmuje kilka minut, a n = 10 jest zamykane przez 2 godziny.

Teoretycznie górna granica wynosi n = 11, zanim zabraknie nam pamięci (tj. Nie ma wystarczającej ilości miejsca na boisku, aby zmieścić większy kwadrat). Jednak w tym momencie czas obliczenia optymalnego rozwiązania jest prawdopodobnie dłuższy niż ktokolwiek byłby skłonny czekać, nawet po skompilowaniu.

Najlepszym sposobem, aby zobaczyć, jak działa algorytm, jest uruchomienie go w jednym z „wizualnych debuggerów” Befunge. W ten sposób możesz oglądać, jak próbuje dopasować różne rozmiary prostokąta do dostępnej przestrzeni. Jeśli chcesz „przewinąć do przodu” do punktu, w którym ma dobre dopasowanie, możesz umieścić punkt przerwania 4w sekwencji w $_40ppobliżu środka dziesiątej linii (9, jeśli zero). Wartość na górze stosu w tym punkcie jest bieżącą różnicą powierzchni.

Poniżej znajduje się animacja pokazująca kilka pierwszych klatek tego procesu dla n = 5:

Każdy odrębny prostokąt jest reprezentowany przez inną literę alfabetu. Należy jednak pamiętać, że końcowy prostokąt nigdy nie jest zapisywany, więc sekcja kwadratu będzie po prostu pusta.

Napisałem również wersję debugowania kodu, która wyświetla bieżący układ za każdym razem, gdy znajdzie nowe najlepsze dopasowanie ( Wypróbuj online! ). W przypadku mniejszych rozmiarów pierwsze dopasowanie jest często optymalnym rozwiązaniem, ale gdy miniesz n = 6, prawdopodobnie zobaczysz kilka prawidłowych, ale nieoptymalnych układów, zanim osiądzie na ostatecznym rozwiązaniu.

Najlepszy układ znaleziony dla n = 10 wygląda następująco:

H F F F A A A C C I
H F F F A A A C C I
H J G G A A A C C I
H J G G A A A C C I
H J D D D D D C C I
H J D D D D D C C I
H J K K K K K K K I
H J B B B E E E E I
H J B B B E E E E I
H J B B B L L L L L

12 - 4 = 8