Você pode escrever um programa ou função que receba um número inteiro positivo e ímpar, n onde n >= 3, como argumento de função, argumentos de linha de comando ou em STDIN (ou equivalente para o seu sistema), e imprime em STDOUT (ou equivalente do sistema) uma espiral ASCII que gira para dentro no sentido horário, onde a borda superior tem exatamente ncaracteres. A primeira borda direita deve ter n+1caracteres longos, obviamente. Por exemplo,

Entrada:

11

Resultado:

***********
          *
********* *
*       * *
* ***** * *
* *   * * *
* * * * * *
* * *** * *
* *     * *
* ******* *
*         *
***********

As capturas:

• Seu programa não deve usar mais que O(log n)memória .
• Seu programa pode imprimir apenas os caracteres *(ASCII 42), (ASCII 32), <CR>(ASCII 13) e <LF>(ASCII 10).
• Seu programa deve imprimir a sequência, não retorná-la da função.
• A restrição Big-O está apenas na memória , não há restrições no tempo de execução .
• Uma nova linha à direita é opcional.
• Se seu idioma não suportar tipos inteiros grandes, você não precisará oferecer suporte superior ao que ele suporta, mas não poderá usar isso como um truque para dizer "oh, bem, eu não tenho que suportar acima de X, então eu pode fazer com que uma matriz enorme tenha o tamanho máximo toda vez "

As brechas padrão são proibidas, como de costume.

C, 125 121 bytes

Versão Golfed Isso não tem variável k. A variável ké usada na versão ungolfed apenas para facilitar a legibilidade. Também forcondicionais ansa são rearranjadas e um conjunto de desnecessário {}removido. Outro conjunto de {}pode ser removido migrando para puts("")dentro dos colchetes do jloop na posição de inicialização, mas isso significaria uma nova linha no início da saída, por isso não o fiz.

f(n){int i,j;n/=2;for(i=-n-2;i++-n-1;){if(i){for(j=-n-1;j++-n;)putchar(32+10*(n+(j*j<i*i?i:j+(i!=j|i>0))&1));puts("");}}}

Imprime uma espiral nlarga por n+1alta, como no exemplo.

Explicação

Basicamente eu reduzir pela metade o valor de n(arredondando para baixo) e executar dois loops: um externo ia partir -n/2-1de n/2+1imprimir as linhas ( i=0é suprimida então temos n+1linhas) e outra interna ja partir de ( -n/2a n/2Usamos para imprimir os caracteres.) expression & 1Para imprimir listras , e a condição j*j<i*ipara decidir se as listras verticais ou horizontais devem ser impressas (verticais nas laterais onde a magnitude absoluta ié maior e horizontal nas partes superior e inferior). É necessário um ajuste +npara ajudar na terminação correta, dependendo se n/2é ímpar ou até.

ké normalmente 1 e fornece um ajuste para o fato de que os valores absolutos ivariam de 1 a n/2+1enquanto os valores absolutos jvariam de 0 a n/2. Se kfosse sempre 1, obteríamos retângulos concêntricos, mas é invertido para 0 quando, i==j&i<=0para que uma linha diagonal de células seja invertida, produzindo a espiral.

ungolfed no programa de teste

f(n){
  int i,j,k;
  n/=2;
  for(i=-n-1;i<=n+1;i++){
    if(i){
       for(j=-n;j<=n;j++){
           k=i!=j|i>0;
           putchar(32+10*(n+(j*j<i*i?i:k+j)&1));
         }
       puts("");
     }
  }
} 

int m;
main(){
  scanf("%d",&m);
  f(m);
}

Resultado

11
***********
          *
********* *
*       * *
* ***** * *
* *   * * *
* * * * * *
* * *** * *
* *     * *
* ******* *
*         *
***********

9
*********
        *
******* *
*     * *
* *** * *
* * * * *
* *   * *
* ***** *
*       *
*********

3
***
  *
* *
***

1
*
*

C, 118 bytes

m,p,x,y,d;f(n){for(m=n++/2;p<n*n;x=p%n-m,y=p++/n-m,d=y==x+1&x<0,y-=y>0,d+=x*x>y*y?x:y,putchar(x>m?10:(d+m)%2?32:42));}

Código antes do golfe final:

#include <stdio.h>

int m, p, x, y, d;

int f(int n) {
    for (m = n++ / 2; p < n * n; ) {
        x = p % n - m;
        y = p++ / n - m;
        d = y == x + 1 && x < 0;
        y -= y > 0;
        d += x * x > y * y ? x : y;
        if (x > m) {
            putchar(10);
        } else if ((d + m) % 2) {
            putchar(32);
        } else {
            putchar(42);
        }
    }

    return 0;
}

A observação principal é que o padrão é quase uma série de quadrados concêntricos. Com algumas rugas leves:

• O tamanho y é um tamanho maior que o tamanho x. Isso é corrigido subtraindo 1 de y para a metade inferior, que basicamente repete a linha do meio.
• Para transformar os retângulos em espiral, os pixels ao longo da y = x + 1diagonal precisam ser invertidos até o meio da forma.

De resto, o código é simplesmente repetido em todas as posições, calculando a distância Chebyshev do centro para cada posição e emitindo um dos dois caracteres, dependendo da distância ser par ou ímpar. E emitindo uma nova linha para a última posição de cada linha.

Como existem apenas algumas variáveis ​​escalares e os caracteres são emitidos um por um, o uso de memória é obviamente constante.

C ++, 926 bytes

#include<iostream>
#include<string>
#include<math.h>
#define S string
using namespace std;S N(S x,int y){S z="";for(int q=0;q<y;q++){z+=x;}return z;}int main(){int n=0,t=0,g=0,fi=1;cin>>n;int t1[]={0,0,n,0};int t2[]={0,n-2,n-2,1};for(int k=0;k<n+1;k++){if((k>(n-2)/2)&&(k<(n+5)/2)){if(g==0){S d,e;if(!((n+1)%4)){cout<<N("* ",t2[0])<<"  *"<<N(" *",t2[0])<<endl<<N("* ",(n+1)/2)<<endl<<N("* ",t2[0])<<"***"<<N(" *",t2[0])<<endl;t2[2]=n-8-(n-11);t1[2]=n-4-(n-11);t1[0]--;t2[3]--;t1[3]-=2;}else{cout<<N("* ",t1[0])<<"***"<<N(" *",t2[0])<<endl<<N("* ",(n+1)/2)<<endl<<N("* ",t1[0])<<"*  "<<N(" *",t2[0])<<endl;t2[0]--;t1[2]+=2;t2[2]+=6;t1[3]--;t2[1]-=2;t2[3]-=2;}fi=0;}g=5;}else{t=1-t;int*tR;tR=t?t1:t2;cout<<N("* ",tR[0])<<N(t?"*":" ",tR[2])<<N(" *",tR[3])<<endl;if(fi){if(t){t1[0]+=k==0?0:1;t1[2]-=k==0?2:4;t1[3]++;}else{t2[0]++;t2[2]-=4;t2[3]++;}}else{if(t){t1[0]--;t1[2]+=4;t1[3]--;}else{t2[0]--;t2[2]+=4;t2[3]--;}}}}return 0;}

Isso não é elegante, mas não ocupa muita memória para grandes n. Além disso, existem (quase certamente) cerca de 20 caracteres que podem ser jogados ainda mais, mas eu não aguento mais olhar para ele.

Breve explicação:

Isso divide as linhas nas espirais em dois tipos: aqueles com ****** no meio e aqueles com \ s \ s \ s \ s \ s no meio. Então fica claro que cada linha é composta por vários "*" s, o meio e alguns "*". Descobrir exatamente quantas coisas é simples se você observar o padrão por tempo suficiente. O difícil era imprimir o centro da espiral que eu basicamente codifiquei usando uma condicional. Isso acabou sendo útil porque as linhas *** e \ s \ s \ s alternam sendo ímpares / pares.

Testes:

Entrada: 55 (Eu acho que os grandes parecem mais legais)

Resultado:

**************************************************** *****
                                                      *
**************************************************** ***
* * *
* *************************************************** * *
* * * * *
* * ********************************************* * * *
* * * * * * *
* * * ***************************************** * * * *
* * * * * * * * *
* * * * ************************************* * * * * *
* * * * * * * * * * *
* * * * * ********************************* * * * * * *
* * * * * * * * * * * * *
* * * * * * ***************************** * * * * * * * *
* * * * * * * * * * * * * * *
* * * * * * * ************************* * * * * * * * * *
* * * * * * * * * * * * * * * * *
* * * * * * * * ********************* * * * * * * * * * *
* * * * * * * * * * * * * * * * * * *
* * * * * * * * * ***************** * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * *
* * * * * * * * * ************* * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * ********* * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * ***** * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * {- meu programa adiciona um espaço aqui entre
* * * * * * * * * * * * *** * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * ******* * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * *********** * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * *************** * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * *
* * * * * * * * * ******************* * * * * * * * * * *
* * * * * * * * * * * * * * * * * *
* * * * * * * * *********************** * * * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * ***************************** * * * * * * *
* * * * * * * * * * * * * *
* * * * * * ******************************* * * * * * *
* * * * * * * * * * * *
* * * * * *********************************** * * * * *
* * * * * * * * * *
* * * * *************************************** * * * *
* * * * * * * *
* * * ******************************************* * * *
* * * * * *
* * *********************************************** * *
* * * *
* *************************************************** ** *
* *
**************************************************** *****

Entrada: 3

Resultado:

***
  *
* * 
***

Nota: Eu não sou um cientista da computação / estudante de CS e não sei como provar que isso usa memória O (log n). Só consigo descobrir o que fazer com base nos links da pergunta. Ficaria muito grato se alguém pudesse confirmar / negar se esta resposta é válida. Minha lógica para a validade dessa resposta é que ela nunca armazena nenhuma variável de tamanho com base em n, exceto na própria entrada. Em vez disso, um loop for que executa n vezes calcula valores inteiros com base em n. Há o mesmo número desses valores, independentemente da entrada.

Nota2: Isso não funciona para n = 1 por causa do meu método de lidar com o meio. Isso seria fácil de corrigir com condicionais; portanto, se alguém tiver alguns caracteres da minha resposta, eu o corrigirei;)

Brinque com ele no ideone.

Haskell, 151 bytes

(#)=mod
f n=[[if y<= -(abs$x+1)||y>abs x then r$y#2/=n#2 else r$x#2==n#2|x<-[-n..n]]|y<-[-n-1..n+1],y/=0]
r b|b='*'|1<2=' '
p=putStr.unlines.f.(`div`2)

Exemplo de uso:

*Main> p 9
*********
        *
******* *
*     * *
* *** * *
* * * * *
* *   * *
* ***** *
*       *
*********

*Main> p 11
***********
          *
********* *
*       * *
* ***** * *
* *   * * *
* * * * * *
* * *** * *
* *     * *
* ******* *
*         *
***********

Graças à preguiça de Haskell, isso ocorre na memória constante. Ele usa a abordagem óbvia, ou seja, looping sobre ye xe escolher entre *e , dependendo

• se a posição atual estiver acima ou abaixo de uma diagonal
• xresp. yé par ou ímpar
• n/2 é par ou ímpar

Lisp comum - 346

(lambda(n &aux(d 0))(tagbody $ #6=(#7=dotimes(i n)#4=(princ"*"))#2=(#7#(i d)#5=(princ" ")#4#)#3=(terpri)#1=(#7#(i d)#4##5#)(when(> n 0)(#7#(i(1- n))#5#)#4#)#2##3#(when(> n 3)#1##4##4#(incf d)(decf n 4)(go $))(go /)@(decf d)(incf n 4)(when(> n 3)#2##5##4##3#)/ #1#(when(> n 0)#4#)(when(> n 1)(#7#(i(- n 2))#5#)#4#)#2##3##1##6#(when(> d 0)(go @))))

Solução iterativa com uso constante de memória. O exemplo acima faz uso pesado de variáveis #n=e de #n#leitor. Embora existam abordagens mais diretas, aqui comecei com uma função recursiva e a modifiquei para simular recursão com gotodeclarações: isso provavelmente é ilegível.

Saída para todos os valores de entrada de 0 a 59 .

Versão recursiva original, com informações de depuração

(nota: terprisignifica newline)

(defun spiral (n &optional (d 0) )
  (flet ((prefix ()
           (format t "~4d~4d | " n d)
           (dotimes (i d)
             (princ "a ")))
         (postfix ()
           (dotimes (i d)
             (princ " b"))))
    (when (= d 0) (prefix))
    (dotimes (i n) (princ "c"))
    (postfix)
    (terpri)

    (prefix)
    (when (> n 0)
      (dotimes (i (1- n)) (princ " "))
      (princ "d"))
    (postfix)
    (terpri)

    (when (> n 3)
      (prefix)
      (princ "**")
      (spiral (- n 4) (1+ d))
      (postfix)
      (princ " f")
      (terpri))

    (prefix)
    (when (> n 0)
      (princ "g"))

    (when (> n 1)
      (dotimes (i (- n 2)) (princ " "))
      (princ "h"))
    (postfix)
    (terpri)

    (prefix)
    (dotimes (i n) (princ "i"))
    ))

Por exemplo:

(spiral 8)

   8   0 | cccccccc
   8   0 |        d
   8   0 | **cccc b
   4   1 | a    d b
   4   1 | a ** b b
   0   2 | a a  b b
   0   2 | a a  b b
   0   2 | a a  b f
   4   1 | a g  h b
   4   1 | a iiii f
   8   0 | g      h
   8   0 | iiiiiiii

Veja também esta pasta com todos os resultados de 0 a 59 (não é o mesmo que acima, este é mais detalhado).

Versão iterativa, com informações de depuração

(defun spiral (n &aux (d 0) )
  (flet ((prefix ()
           (format t "~4d~4d | " n d)
           (dotimes (i d)
             (princ "a ")))
         (postfix ()
           (dotimes (i d)
             (princ " b"))))
    (tagbody
     step-in
       (when (= d 0) (prefix))
       (dotimes (i n) (princ "c"))
       (postfix)
       (terpri)

       (prefix)
       (when (> n 0)
         (dotimes (i (1- n)) (princ " "))
         (princ "d"))
       (postfix)
       (terpri)

       (when (> n 3)
         (prefix)
         (princ "**")

         (incf d)
         (decf n 4)
         (go step-in))

       (go skip)

     step-out
       (decf d)
       (incf n 4)
       (when (> n 3)
         (postfix)
         (princ " f")
         (terpri))

     skip
       (prefix)
       (when (> n 0)
         (princ "g"))

       (when (> n 1)
         (dotimes (i (- n 2)) (princ " "))
         (princ "h"))
       (postfix)
       (terpri)

       (prefix)
       (dotimes (i n) (princ "i"))
       (when(> d 0)(go step-out)))))

CJam, 72 bytes

li_2/:M;)__*{1$mdM-\M-_2$)=2$0<*@_*@_0>-_*e>mQ_M>2*@@+M+2%+'#S+N+N+=o}/;

Esta é uma conversão bastante direta da minha solução C para CJam. Não é tão curto quanto você normalmente esperaria de uma solução CJam, mas essa realmente sofre com a restrição de memória. Os benefícios comuns da criação de resultados na pilha que são descartados automaticamente no final e do uso de operações sofisticadas de lista / sequência de caracteres, todos saem pela janela. Isso gera e gera a solução, um caractere por vez. A pilha contém apenas alguns números inteiros em tempo de execução e está vazia no final.

Embora não seja uma ótima exibição do uso de uma linguagem de golfe, ainda é consideravelmente mais curta que o código C, apenas porque a notação é mais compacta.

Explicação:

li    Get input n.
_2/   Calculate n/2.
:M;   Store it in variable M
)__*  Calculate (n+1)*(n+1), which is the total number of output characters.
      Also keep a copy of n+1 on the stack.
{     Start loop over output character positions.
  1$md  Calculate divmod of position with n+1. This gives y and x of position.
  M-    Subtract M from x.
  \M-   Subtract M from y.
  _     Copy y.
  2$)   Calculate x+1.
  =     Check if y == x+1
  2$0<  Check if x < 0.
  *     Multiply the two check results. This is the result of the flip
        condition for the top-left diagonal to turn the rectangles into a spiral.
  @_*   Calculate x*x.
  @_    Get y to top of stack, and copy it.
  0>-   Subtract 1 from y if it is in the bottom half.
  _*    Calculate y*y.
  e>    Take maximum of x*x and y*y...
  mQ    ... and calculate the square root. This is the absolute value of the
        larger of the two.
  _M>   Check if the value is greater M, which means that this is the
        position of a line end.
  2*    Multiply by 2 so that we can add another condition to it later.
  @     Get result of diagonal flip condition to the stack top.
  @     Get max(x,y) to the top.
  +M+   Add the two, and add M to the whole thing. This value being even/odd
        determines if the output is a # or a space.
  2%    Check if value is odd.
  +     Add to line end condition to get a single ternary condition result.
  '#S+N+N+
        Build string "# \n\n".
  =     Use the condition result to pick the output character out of the string.
  o     Output the character.
}/    End loop over output characters.
;     Pop n+1 value off stack, to leave it empty.