Когда учеников впервые учат доказательной технике математической индукции , типичным примером является проблема мозаики 2 ^N × 2. наложения сетки ^N на L-образные тромино , оставляя одно заданное пространство сетки пустым. (N - некоторое неотрицательное целое число.)

Я оставлю это вам, чтобы просмотреть доказательства, если вы еще этого не знаете. Есть много ресурсов, которые обсуждают это.

Ваша задача здесь состоит в том, чтобы написать программу, которая принимает значение для N, а также координаты пространства сетки, чтобы оставить пустым, и печатает ASCII-представление результирующей мозаики Tromino.

Персонаж Oзаполнит пустое пространство, и 4 поворота нашего тромино будут выглядеть так:

|
+-

 |
-+

-+
 |

+-
|

^{(Да, это может быть неоднозначно, что +идет с какой -и |для определенных договоренностей, но это нормально.)}

Ваша программа должна работать при N = 0 (для сетки 1 × 1), по крайней мере, до N = 8 (для сетки 256 × 256). Будут даны значения x и y, которые являются координатами для O:

• х горизонтальная ось. x = 1 - левый край сетки, x = 2 ^N - правый край сетки.
• у вертикальная ось. y = 1 - верхний край сетки, y = 2 ^N - нижний край сетки.

И x, и y всегда находятся в диапазоне [1, 2 ^N ].

Таким образом, для заданных N, x и y ваша программа должна вывести 2 ^N × 2 ^N сетку , полностью покрытую L-образными тромино, за исключением координаты сетки x, y, которая будет являться O.

Примеры

Если N = 0, тогда x и y должны быть равны 1. Выход

O

Если N = 1, x = 1 и y = 2, результат будет

-+
O|

N = 2, x = 3, y = 2:

+--+
||O|
|+-|
+--+

N = 2, x = 4, y = 1:

+-|O
||+-
|+-|
+--+

N = 3, x = 3, y = 6 (например, изображение на этой странице ):

+--++--+
|+-||-+|
||+--+||
+-|-+|-+
+--+||-+
||O|-+||
|+-||-+|
+--++--+

Детали

• Вы можете написать функцию, которая принимает 3 целых числа вместо написания всей программы. Он должен напечатать или вернуть строку сетки.
• Возьмите ввод из стандартного ввода, командной строки (или аргументов функции, если вы пишете функцию).
• Выходные данные могут дополнительно содержать один обучающий перевод строки.
• Вы не обязаны использовать метод листов, который обычно предлагает доказательство. Имеет значение только то, что сетка заполнена L-образными тромино, кроме O. (Тромино нельзя разрезать или выходить за границы сетки.)

Самый короткий код в байтах побеждает. Tiebreaker - более ранний пост. ( Удобный счетчик байтов. )

Haskell, 250 240 236 байт

c=cycle
z o(#)(x,y)=zipWith o(1#x)(2#y)
f n x y=unlines$(z(+)(\m w->[c[0,m]!!div(w-1)(2^(n-k))|k<-[1..n]])(x,y),"O")%n
(_,x)%0=[x]
((p:o),x)%k=z(++)(\_ q->((o,x):c[(c[3-q],[" |-+| +--+ |+-|"!!(4*p+q)])])!!abs(p-q)%(k-1))=<<[(0,1),(2,3)]

Это следует за индуктивным решением проблемы. Точка для отметки представлена ​​последовательностью чисел от 0 до 3, которые указывают, какой квадрант удерживает точку на каждом уровне масштабирования; это первоначально вычисляется выражением, начинающимся с z (+). Оператор (%) объединяет изображения для четырех квадрантов в одно изображение. Рисунки для немаркированных квадрантов создаются путем рисования отмеченных квадрантов с отметкой где-то посередине, нарисованной с отметкой «+ - |» при необходимости построить центральную L-плитку.

Забавный бизнес: по причинам гольфа, подвыражение

\m w->[c[0,m]!!div(w-1)(2^(n-k))|k<-[1..n]]

(который более или менее вычисляет битовую последовательность для числа) забавно неэффективен - он определяет, является ли w / 2 ^ p нечетным или четным, просматривая (w / 2 ^ p) -й элемент списка.

Редактировать: 10 байтов сохранены путем вставки вычисления битов и замены if / then / else на операцию индексации.

Edit2: еще четыре байта сохранены путем переключения функции обратно на оператор. @randomra, гонка началась!

Демо-версия:

λ> putStr $ f 4 5 6
+--++--++--++--+
|+-||-+||+-||-+|
||+--+||||+--+||
+-|+-|-++-|-+|-+
+-||-+-++--+||-+
||+-O||||-+|-+||
|+-||-+|-+|||-+|
+--++--+||-++--+
+--++-|-+|-++--+
|+-|||+--+|||-+|
||+-|+-||-+|-+||
+-||+--++--+||-+
+-|+-|-++-|-+|-+
||+--+||||+--+||
|+-||-+||+-||-+|
+--++--++--++--+

C, 399 байт

char*T=" |-+ | +-| ",*B;w;f(N,x,y,m,n,F,h,k,i,j){w=B?F=0,w:1<<N|1;char b[N?w*w:6];for(k=w;k--;)b[k*w-1]=10;B=!B?F=1,m=0,n=0,x--,y--,b:B;if(N>1){h=1<<N-1;i=x>--h,j=y>h;while(++k<4)if(k%2-i||k/2-j)f(N-1,!(k%2)*h,!(k/2)*h,m+k%2*(h+1),n+k/2*(h+1));f(1,h&i,h&j,m+h,n+h);h++;f(N-1,x-h*i,y-h*j,m+h*i,n+h*j);}else while(++k<4)B[w*(n+k/2)+m+k%2]=T[5*x+2*y+k];if(F)B[y*w+x]=79,B[w*w-w-1]=0,puts(N?B:"O"),B=0;}

Никто еще ничего не высказал, поэтому я предложу скудное решение. Запомните мои слова, это не конец. Это станет короче.

Мы определяем функцию, fкоторая принимает 10 аргументов, но вам нужно только вызвать ее с помощью f(N, X, Y). Вывод идет в стандартный вывод.

Вот читаемая версия:

char*T=" |-+ | +-| ",*B;
w;
f(N,x,y,m,n,F,h,k,i,j){
    w=B?F=0,w:1<<N|1;
    char b[N?w*w:6];
    for(k=w;k--;)
        b[k*w-1]=10;
    B=!B?F=1,m=0,n=0,x--,y--,b:B;
    if(N>1){
        h=1<<N-1;
        i=x>--h,j=y>h;
        while(++k<4)
            if(k%2-i||k/2-j)
                f(N-1,!(k%2)*h,!(k/2)*h,m+k%2*(h+1),n+k/2*(h+1));
        f(1,h&i,h&j,m+h,n+h);
        h++;
        f(N-1,x-h*i,y-h*j,m+h*i,n+h*j);
    }
    else
        while(++k<4)
            B[w*(n+k/2)+m+k%2]=T[5*x+2*y+k];
    if(F)B[y*w+x]=79,B[w*w-w-1]=0,puts(N?B:"O"),B=0;
}

Вкус продукции для f(3, 2, 7):

+--++--+
|+-||-+|
||+--+||
+-|-+|-+
+--+||-+
|-+|-+||
|O|||-+|
+--++--+

Это довольно простой рекурсивный алгоритм для заполнения сетки. Я могу загрузить анимацию алгоритма рисования тромино, так как я думаю, что это довольно аккуратно. Как обычно, не стесняйтесь задавать вопросы и кричать на меня, если мой код сломается!

Попробуйте онлайн !

Питон 3, 276 265 237 байт

Мой первый Python Golf, так что я уверен, что есть много возможностей для совершенствования.

def f(n,x,y,c='O'):
 if n<1:return c
 *t,l,a='x|-+-|',2**~-n;p=(a<x)+(a<y)*2
 for i in 0,1,2,3:t+=(p-i and f(n-1,1+~i%2*~-a,1+~-a*(1-i//2),l[p+i])or f(n-1,1+~-x%a,1+~-y%a,c)).split(),
 u,v,w,z=t;return'\n'.join(map(''.join,zip(u+w,v+z)))

10 байтов сохранено благодаря @xnor и еще 6 байтов благодаря @ Sp3000.

Функция возвращает строку. Пример использования:

>>>print(f(3,3,6))    
+--++--+
|+-||-+|
||+--+||
+-|-+|-+
+--+||-+
||O|-+||
|+-||-+|
+--++--+

JavaScript (ES6) 317 414

Много работы по гольфу, но все же довольно долго.

T=(b,x,y)=>
  (F=(d,x,y,f,t=[],q=y<=(d>>=1)|0,
      b=d?x>d
       ?q
         ?F(d,x-d,y,0,F(d,1,1,2))
         :F(d,1,d,2,F(d,x-d,y-d))
       :F(d,1,d,1-q,F(d,1,1,q)):0,
      r=d?(x>d
         ?F(d,d,d,1-q,F(d,d,1,q))
         :q
           ?F(d,x,y,1,F(d,d,1,2))
           :F(d,d,d,2,F(d,x,y-d))
      ).map((x,i)=>x.concat(b[i])):[[]]
    )=>(r[y-1][x-1]='|+-O'[f],r.concat(t))
  )(1<<b,x,y,3).join('\n').replace(/,/g,'')

Запустите сниппет для проверки (лучше выглядит при использовании символов блока Unicode - но даже немного дольше)

T=(b,x,y)=>
  (F=(d,x,y,f,t=[],q=y<=(d>>=1)|0,
      b=d?x>d
       ?q
         ?F(d,x-d,y,0,F(d,1,1,6))
         :F(d,1,d,6,F(d,x-d,y-d))
       :F(d,1,d,q,F(d,1,1,q+1)):0,
      r=d?(x>d
         ?F(d,d,d,q+3,F(d,d,1,q+4))
         :q
           ?F(d,x,y,1,F(d,d,1,6))
           :F(d,d,d,6,F(d,x,y-d))
      ).map((x,i)=>x.concat(b[i])):[[]]
    )=>(
    r[y-1][x-1]='┐│┘┌│└─O'[f],r.concat(t)
  ))(1<<b,x,y,7).join('\n').replace(/,/g,'')

loop=_=>{
  var x=X.value|0, y=Y.value|0, n=N.value|0;
  
  var b=1<<n, cur=1<<(n+n);
  (L=_=>{
    --cur;
    O.innerHTML=T(n,(cur&(b-1))+1,(cur>>n)+1);
    cur&&setTimeout(L,100);
  })()
}

tile=_=>{
  var x=X.value|0, y=Y.value|0, n=N.value|0;
  O.innerHTML=T(n,x,y);
}

tile()

input { width: 3em }
pre { font-size: 10px; line-height: 10px }

N: <input id=N value=4> X: <input id=X value=5> Y: <input id=Y value=3>
<button onclick="tile()">Tile</button>
<button onclick="loop()">Loop</button>
<pre id=O></pre>

IDL 8,3+, 293 байта

Это слишком долго, я пытаюсь сократить это, но я еще не получил там.

function t,n,x,y
m=2^n
c=['|','+','-']
b=replicate('0',m,m)
if m eq 1 then return,b
h=m/2
g=h-1
k=[1:h]
o=x gt h
p=y gt h
q=o+2*p
if m gt 2then for i=0,1 do for j=0,1 do b[i*h:i*h+g,j*h:j*h+g]=t(n-1,i+2*j eq q?x-i*h:k[i-1],i+2*j eq q?y-j*h:k[j-1])
b[g+[1-o,1-o,o],g+[p,1-p,1-p]]=c
return,b
end

Выходы:

IDL> print,t(1,1,2)
- +
0 |
IDL> print,t(2,3,2)
+ - - +
| | 0 |
| + - |
+ - - +
IDL> print,t(2,4,1)
+ - | 0
| | + -
| + - |
+ - - +
IDL> print,t(3,3,6)
+ - - + + - - +
| + - | | - + |
| | + - - + | |
+ - | - + | - +
+ - - + | | - +
| | 0 | - + | |
| + - | | - + |
+ - - + + - - +

И ... просто для удовольствия ...

IDL> print,t(6,8,9)
+ - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - +
| + - | | - + | | + - | | - + | | + - | | - + | | + - | | - + | | + - | | - + | | + - | | - + | | + - | | - + | | + - | | - + |
| | + - - + | | | | + - - + | | | | + - - + | | | | + - - + | | | | + - - + | | | | + - - + | | | | + - - + | | | | + - - + | |
+ - | + - | - + + - | - + | - + + - | + - | - + + - | - + | - + + - | + - | - + + - | - + | - + + - | + - | - + + - | - + | - +
+ - | | + - - + + - - + | | - + + - | | + - - + + - - + | | - + + - | | + - - + + - - + | | - + + - | | + - - + + - - + | | - +
| | + - | + - | | - + | - + | | | | + - | + - | | - + | - + | | | | + - | + - | | - + | - + | | | | + - | + - | | - + | - + | |
| + - | | | + - - + | | | - + | | + - | | | + - - + | | | - + | | + - | | | + - - + | | | - + | | + - | | | + - - + | | | - + |
+ - - + + - | - + | - + + - - + + - - + + - | - + | - + + - - + + - - + + - | + - | - + + - - + + - - + + - | - + | - + + - - +
+ - - + + - | 0 | | - + + - - + + - - + + - - + | | - + + - - + + - - + + - | | + - - + + - - + + - - + + - - + | | - + + - - +
| + - | | | + - - + | | | - + | | + - | | - + | - + | | | - + | | + - | | | + - | + - | | - + | | + - | | - + | - + | | | - + |
| | + - | + - | | - + | - + | | | | + - - + | | | - + | - + | | | | + - | + - | | | + - - + | | | | + - - + | | | - + | - + | |
+ - | | + - - + + - - + | | - + + - | - + | - + + - - + | | - + + - | | + - - + + - | + - | - + + - | - + | - + + - - + | | - +
+ - | + - | - + + - | - + | - + + - - + | | - + + - | - + | - + + - | + - | - + + - | | + - - + + - - + | | - + + - | - + | - +
| | + - - + | | | | + - - + | | | - + | - + | | | | + - - + | | | | + - - + | | | | + - | + - | | - + | - + | | | | + - - + | |
| + - | | - + | | + - | | - + | - + | | | - + | | + - | | - + | | + - | | - + | | + - | | | + - - + | | | - + | | + - | | - + |
+ - - + + - - + + - - + + - - + | | - + + - - + + - - + + - - + + - - + + - - + + - - + + - | - + | - + + - - + + - - + + - - +
+ - - + + - - + + - - + + - | - + | - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + | | - + + - - + + - - + + - - +
| + - | | - + | | + - | | | + - - + | | | - + | | + - | | - + | | + - | | - + | | + - | | - + | - + | | | - + | | + - | | - + |
| | + - - + | | | | + - | + - | | - + | - + | | | | + - - + | | | | + - - + | | | | + - - + | | | - + | - + | | | | + - - + | |
+ - | + - | - + + - | | + - - + + - - + | | - + + - | - + | - + + - | + - | - + + - | - + | - + + - - + | | - + + - | - + | - +
+ - | | + - - + + - | + - | - + + - | - + | - + + - - + | | - + + - | | + - - + + - - + | | - + + - | - + | - + + - - + | | - +
| | + - | + - | | | + - - + | | | | + - - + | | | - + | - + | | | | + - | + - | | - + | - + | | | | + - - + | | | - + | - + | |
| + - | | | + - | + - | | - + | | + - | | - + | - + | | | - + | | + - | | | + - - + | | | - + | | + - | | - + | - + | | | - + |
+ - - + + - | | + - - + + - - + + - - + + - - + | | - + + - - + + - - + + - | - + | - + + - - + + - - + + - - + | | - + + - - +
+ - - + + - | + - | - + + - - + + - - + + - | - + | - + + - - + + - - + + - - + | | - + + - - + + - - + + - | - + | - + + - - +
| + - | | | + - - + | | | - + | | + - | | | + - - + | | | - + | | + - | | - + | - + | | | - + | | + - | | | + - - + | | | - + |
| | + - | + - | | - + | - + | | | | + - | + - | | - + | - + | | | | + - - + | | | - + | - + | | | | + - | + - | | - + | - + | |
+ - | | + - - + + - - + | | - + + - | | + - - + + - - + | | - + + - | - + | - + + - - + | | - + + - | | + - - + + - - + | | - +
+ - | + - | - + + - | - + | - + + - | + - | - + + - | - + | - + + - - + | | - + + - | - + | - + + - | + - | - + + - | - + | - +
| | + - - + | | | | + - - + | | | | + - - + | | | | + - - + | | | - + | - + | | | | + - - + | | | | + - - + | | | | + - - + | |
| + - | | - + | | + - | | - + | | + - | | - + | | + - | | - + | - + | | | - + | | + - | | - + | | + - | | - + | | + - | | - + |
+ - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + | | - + + - - + + - - + + - - + + - - + + - - + + - - + + - - +
+ - - + + - - + + - - + + - - + + - - + + - - + + - - + + - | - + | - + + - - + + - - + + - - + + - - + + - - + + - - + + - - +
| + - | | - + | | + - | | - + | | + - | | - + | | + - | | | + - - + | | | - + | | + - | | - + | | + - | | - + | | + - | | - + |
| | + - - + | | | | + - - + | | | | + - - + | | | | + - | + - | | - + | - + | | | | + - - + | | | | + - - + | | | | + - - + | |
+ - | + - | - + + - | - + | - + + - | + - | - + + - | | + - - + + - - + | | - + + - | - + | - + + - | + - | - + + - | - + | - +
+ - | | + - - + + - - + | | - + + - | | + - - + + - | + - | - + + - | - + | - + + - - + | | - + + - | | + - - + + - - + | | - +
| | + - | + - | | - + | - + | | | | + - | + - | | | + - - + | | | | + - - + | | | - + | - + | | | | + - | + - | | - + | - + | |
| + - | | | + - - + | | | - + | | + - | | | + - | + - | | - + | | + - | | - + | - + | | | - + | | + - | | | + - - + | | | - + |
+ - - + + - | + - | - + + - - + + - - + + - | | + - - + + - - + + - - + + - - + | | - + + - - + + - - + + - | - + | - + + - - +
+ - - + + - | | + - - + + - - + + - - + + - | + - | - + + - - + + - - + + - | - + | - + + - - + + - - + + - - + | | - + + - - +
| + - | | | + - | + - | | - + | | + - | | | + - - + | | | - + | | + - | | | + - - + | | | - + | | + - | | - + | - + | | | - + |
| | + - | + - | | | + - - + | | | | + - | + - | | - + | - + | | | | + - | + - | | - + | - + | | | | + - - + | | | - + | - + | |
+ - | | + - - + + - | + - | - + + - | | + - - + + - - + | | - + + - | | + - - + + - - + | | - + + - | - + | - + + - - + | | - +
+ - | + - | - + + - | | + - - + + - | + - | - + + - | - + | - + + - | + - | - + + - | - + | - + + - - + | | - + + - | - + | - +
| | + - - + | | | | + - | + - | | | + - - + | | | | + - - + | | | | + - - + | | | | + - - + | | | - + | - + | | | | + - - + | |
| + - | | - + | | + - | | | + - | + - | | - + | | + - | | - + | | + - | | - + | | + - | | - + | - + | | | - + | | + - | | - + |
+ - - + + - - + + - - + + - | | + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + | | - + + - - + + - - + + - - +
+ - - + + - - + + - - + + - | + - | - + + - - + + - - + + - - + + - - + + - - + + - - + + - | - + | - + + - - + + - - + + - - +
| + - | | - + | | + - | | | + - - + | | | - + | | + - | | - + | | + - | | - + | | + - | | | + - - + | | | - + | | + - | | - + |
| | + - - + | | | | + - | + - | | - + | - + | | | | + - - + | | | | + - - + | | | | + - | + - | | - + | - + | | | | + - - + | |
+ - | + - | - + + - | | + - - + + - - + | | - + + - | - + | - + + - | + - | - + + - | | + - - + + - - + | | - + + - | - + | - +
+ - | | + - - + + - | + - | - + + - | - + | - + + - - + | | - + + - | | + - - + + - | + - | - + + - | - + | - + + - - + | | - +
| | + - | + - | | | + - - + | | | | + - - + | | | - + | - + | | | | + - | + - | | | + - - + | | | | + - - + | | | - + | - + | |
| + - | | | + - | + - | | - + | | + - | | - + | - + | | | - + | | + - | | | + - | + - | | - + | | + - | | - + | - + | | | - + |
+ - - + + - | | + - - + + - - + + - - + + - - + | | - + + - - + + - - + + - | | + - - + + - - + + - - + + - - + | | - + + - - +
+ - - + + - | + - | - + + - - + + - - + + - | - + | - + + - - + + - - + + - | + - | - + + - - + + - - + + - | - + | - + + - - +
| + - | | | + - - + | | | - + | | + - | | | + - - + | | | - + | | + - | | | + - - + | | | - + | | + - | | | + - - + | | | - + |
| | + - | + - | | - + | - + | | | | + - | + - | | - + | - + | | | | + - | + - | | - + | - + | | | | + - | + - | | - + | - + | |
+ - | | + - - + + - - + | | - + + - | | + - - + + - - + | | - + + - | | + - - + + - - + | | - + + - | | + - - + + - - + | | - +
+ - | + - | - + + - | - + | - + + - | + - | - + + - | - + | - + + - | + - | - + + - | - + | - + + - | + - | - + + - | - + | - +
| | + - - + | | | | + - - + | | | | + - - + | | | | + - - + | | | | + - - + | | | | + - - + | | | | + - - + | | | | + - - + | |
| + - | | - + | | + - | | - + | | + - | | - + | | + - | | - + | | + - | | - + | | + - | | - + | | + - | | - + | | + - | | - + |
+ - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - + + - - +

Ruby Rev 1, 288

Как анонимный лямбда-литерал. Показано в тестовой программе (лямбда-литерал есть ->(n,a,b){...})

g=
->(n,a,b){
$x=a-1
$y=b-1
$a=Array.new(m=2**n){"|"*m}
def t(u,v,m,r,f)
(m/=2)==1?$a[v+1-r/2%2][u,2]='-+-'[r%2,2]:0
if m>1 
4.times{|i|i==r ?t(u+m/2,v+m/2,m,r,0):t(u+i%2*m,v+i/2*m,m,3-i,0)}
f>0?t(u+r%2*m,v+r/2*m,m,2*$x/m&1|$y*4/m&2,1):0
end
end
t(0,0,m,2*$x/m|$y*4/m,1) 
$a[$y][$x]='O'
$a
}

n=gets.to_i
a=gets.to_i
b=gets.to_i
puts(g.call(n,a,b))

Ruby Rev 0, 330 без золота

В настоящее время я требую только игры в гольф - это исключение комментариев, ненужных новых строк и отступов.

Это мой первый правильный алгоритм, закодированный в Ruby, и это была тяжелая работа. Я уверен, что есть как минимум 50 символов, которые можно убрать, но я сделал достаточно на данный момент. Есть некоторые реальные ужасы, например, вход. Вероятно, это можно исправить с помощью функции или лямбды вместо программы, но внутренняя функция, tкоторая рисует тромино, все еще нуждается в доступе к глобальным переменным. Я должен выяснить синтаксис для этого.

Особенностью моего ответа, которого нет в других, является то, что я инициализирую массив строк |символами. Это означает, что мне нужно только нарисовать +-или -+, которые находятся рядом друг с другом на одной линии.

m=2**gets.to_i                                         #get n and store 2**n in m
$x=gets.to_i-1                                         #get x and y, and...
$y=gets.to_i-1                                         #convert from 1-indexed to 0-indexed
$a=Array.new(m){"|"*m}                                 #array of m strings length m, initialized with "|"

def t(u,v,m,r,f)                                       #u,v=top left of current field. r=0..3= quadrant containing O. f=flag to continue surrounding O
  m/=2
  if m==1 then $a[v+1-r/2%2][u,2] ='-+-'[r%2,2];end    #if we are at char level, insert -+ or +- (array already initialized with |'s)
  if m>1 then                                          #at higher level, 4 recursive calls to draw trominoes of next size down 
    4.times{|i| i==r ? t(u+m/2,v+m/2,m,r,0):t(u+i%2*m,v+i/2*m,m,3-i,0)}
    f>0?t(u+r%2*m,v+r/2*m,m,2*$x/m&1|$y*4/m&2,1):0     #then one more call to fill in the empty quadrant (this time f=1)
  end
end

$a[$y][$x]='O'                                         #fill in O
t(0,0,m,2*$x/m&1|$y*4/m&2,1)                           #start call. 2*x/m gives 0/1 for left/right quadrant, similarly 4*y/m gives 0/2 for top/bottom 

puts $a                                                #dump array to stdout, elements separated by newlines.

Haskell, 170 байт

r=reverse
g n s x y|n<1=[s]|x>k=r<$>g n s(2^n+1-x)y|y>k=r$g n s x$2^n+1-y|0<1=zipWith(++)(h s x y++h"-"k 1)$h"|"1 k++h"+"1 1 where m=n-1;k=2^m;h=g m
f n x=unlines.g n"O"x

Запустить онлайн на Ideone

Пример выполнения:

*Main> putStr(f 3 3 6)
+--++--+
|+-||-+|
||+--+||
+-|-+|-+
+--+||-+
||O|-+||
|+-||-+|
+--++--+