Sie können ein Programm oder eine Funktion schreiben , das eine empfängt ungeradee positive ganze Zahl n ist , wo n >= 3, entweder als ein Funktionsargument, Befehlszeilenargumente oder auf STDIN (oder gleichwertig für Ihr System) und druckt auf STDOUT (oder System - Äquivalent) eine ASCII - Spirale , das nach innen dreht im Uhrzeigersinn , wo der obere Rand genau nZeichen lang. Der erste rechte Rand sollte n+1offensichtlich Zeichen lang sein. Zum Beispiel,

Eingang:

11

Ausgabe:

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

Die Fänge:

• Ihr Programm darf nicht mehr als O(log n)Speicher verwenden .
• Ihr Programm druckt möglicherweise nur die Zeichen *(ASCII 42), (ASCII 32), <CR>(ASCII 13) und <LF>(ASCII 10).
• Ihr Programm muss die Zeichenfolge drucken und darf sie nicht von der Funktion zurückgeben.
• Die Big-O Beschränkung ist nur auf Speicher , gibt es keine Einschränkungen für Laufzeit .
• Ein abschließender Zeilenumbruch ist optional.
• Wenn Ihre Sprache keine großen Integer-Typen unterstützt, müssen Sie keine höheren als die unterstützten unterstützen, aber Sie können dies möglicherweise nicht als Trick verwenden, um zu sagen: "Oh, nun, ich muss nicht über X unterstützen, also ich kann nur jedes Mal ein riesiges Array auf die maximale Größe bringen "

Standardlücken sind wie gewohnt verboten.

C 125 121 Bytes

Golf Version Dies hat keine Variable k. Die Variable kwird in der ungolfed-Version nur verwendet, um die Lesbarkeit zu verbessern. Auch forLoop-Bedingungen werden neu geordnet und ein unnötiger Satz {}entfernt. Ein weiterer Satz von {}kann entfernt werden, indem Sie puts("")in die Klammern der jSchleife in der Initialisierungsposition migrieren. Dies würde jedoch bedeuten, dass am Anfang der Ausgabe eine neue Zeile eingefügt wird, sodass ich dies nicht getan habe.

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("");}}}

Druckt eine nbreite durch n+1hohe Spirale wie im Beispiel.

Erläuterung

Im Wesentlichen halbieren I den Wert von n(Abrunden) , und führen zwei Schleifen: eine äußere eine ivon -n/2-1bis n/2+1die Zeilen drucken ( i=0unterdrückt wird , so erhalten wir n+1Zeilen) und einer inneren jaus ( -n/2zu n/2verwenden wir die Zeichen zu drucken.) expression & 1Streifen zu drucken , und die Bedingung j*j<i*i, um zu entscheiden, ob vertikale oder horizontale Streifen gedruckt werden sollen (vertikal an den Seiten, an denen die absolute Größe igrößer ist, und horizontal oben und unten.) Eine Anpassung +nist erforderlich, um die korrekte Terminierung zu unterstützen, je nachdem, obn/2 ungerade oder ungerade sogar.

kist normalerweise 1 und bietet eine Anpassung für die Tatsache, dass die absoluten Werte ivon 1 bis reichen, n/2+1während die absoluten Werte jvon 0 bis reichen n/2. Wenn kimmer 1 wäre, würden wir konzentrische Rechtecke erhalten, die jedoch bei 0 invertiert werdeni==j&i<=0 sodass eine diagonale Reihe von Zellen invertiert wird und die Spirale entsteht.

im Testprogramm ungolfed

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

Ausgabe

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

Code vor dem endgültigen Golfen:

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

Die Schlüsselbeobachtung ist, dass das Muster fast eine Reihe konzentrischer Quadrate ist. Mit ein paar leichten Falten:

• Die y-Größe ist eine Nummer größer als die x-Größe. Dies wird durch Subtrahieren von 1 von y für die untere Hälfte korrigiert, wodurch die mittlere Reihe im Wesentlichen wiederholt wird.
• Um die Rechtecke in eine Spirale zu verwandeln, müssen die Pixel entlang der y = x + 1Diagonale bis zur Mitte der Form invertiert werden.

Im Übrigen durchläuft der Code einfach alle Positionen, berechnet die Chebyshev-Entfernung vom Zentrum für jede Position und gibt eines der beiden Zeichen aus, je nachdem, ob die Entfernung gerade oder ungerade ist. Und eine neue Zeile für die letzte Position jeder Zeile ausgeben.

Da es nur wenige skalare Variablen gibt und die Zeichen einzeln ausgegeben werden, ist die Speichernutzung offensichtlich konstant.

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

Dies ist nicht elegant, nimmt aber nicht viel Speicher für große n in Anspruch. Darüber hinaus gibt es (mit ziemlicher Sicherheit) ungefähr 20 Charaktere, die weiter golfen werden können, aber ich kann es nicht mehr ertragen, es mir anzusehen.

Kurze Erklärung:

Dies teilt die Linien in den Spiralen in zwei Typen auf: die mit ****** in der Mitte und die mit \ s \ s \ s \ s in der Mitte. Dann ist klar, dass jede Zeile aus mehreren "*", der Mitte und einigen "*" besteht. Es ist einfach herauszufinden, wie viele von jeder Sache genau sind, wenn Sie sich das Muster lange genug ansehen. Das Knifflige war, die Mitte der Spirale zu drucken, die ich im Grunde genommen mit einer Bedingung hart codiert habe. Dies erwies sich als nützlich, da die Zeilen *** und \ s \ s \ s dort ungerade / gerade wechseln.

Tests:

Input: 55 (Ich finde die Großen sehen am coolsten aus)

Ausgabe:

*************************************************** *****
                                                      *
*************************************************** *** *
* * *
* ************************************************** * *
* * * * *
* * ********************************************* * * *
* * * * * * *
* * * ***************************************** * * * *
* * * * * * * * *
* * * * ************************************* * * * * *
* * * * * * * * * * *
* * * * * ********************************* * * * * * *
* * * * * * * * * * * * *
* * * * * * ***************************** * * * * * *
* * * * * * * * * * * * * * *
* * * * * * * ************************* * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * ********************* * * * * * * * *
* * * * * * * * * * * * * * * * * *
* * * * * * * * * **************** * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * ************ * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * ******** * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * ***** * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * {- Mein Programm fügt hier übrigens ein Leerzeichen hinzu
* * * * * * * * * * * * * *** * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * ******* * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * ********** * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * ************** * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * *
* * * * * * * * * ******************* * * * * * * * *
* * * * * * * * * * * * * * * * *
* * * * * * * * *********************** * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * *************************** * * * * * *
* * * * * * * * * * * * * *
* * * * * * ******************************* * * * * * *
* * * * * * * * * * * *
* * * * * *********************************** * * * * *
* * * * * * * * * *
* * * * *************************************** * * * *
* * * * * * * *
* * * ******************************************* * * *
* * * * * *
* * ************************************************** *
* * * *
* ************************************************** ** *
* *
*************************************************** *****

Eingang: 3

Ausgabe:

***
  *
* * 
***

Hinweis: Ich bin kein Informatiker / CS-Student und kann nicht nachweisen, dass dies O (log n) -Speicher belegt. Ich kann nur anhand der Links in der Frage herausfinden, was zu tun ist. Ich wäre dankbar, wenn jemand bestätigen / ablehnen könnte, ob diese Antwort gültig ist. Meine Logik für die Gültigkeit dieser Antwort ist, dass sie niemals eine Variable der Größe basierend auf n außer der Eingabe selbst speichert. Stattdessen berechnet eine for-Schleife, die n-mal ausgeführt wird, ganzzahlige Werte basierend auf n. Es gibt unabhängig von der Eingabe die gleiche Anzahl dieser Werte.

Anmerkung 2: Dies funktioniert bei n = 1 nicht, da ich mit der Mitte umgehe. Dies lässt sich leicht mit Bedingungen beheben. Wenn sich also jemand innerhalb einiger Zeichen meiner Antwort befindet, werde ich das Problem beheben.

Spiel damit auf 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)

Anwendungsbeispiel:

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

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

Dank Haskells Faulheit läuft dies in ständiger Erinnerung. Es nutzt den offensichtlichen Ansatz, Looping , dh über yund xund die Wahl zwischen *und je nach

• wenn die aktuelle Position über oder unter einer Diagonale liegt
• xbzw. yist gerade oder ungerade
• n/2 ist gerade oder ungerade

Common Lisp - 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 @))))

Iterative Lösung mit konstanter Speichernutzung. Die oben genannten macht starken Gebrauch von#n= und #n#Reader-Variablen. Obwohl es direktere Ansätze gibt, habe ich hier mit einer rekursiven Funktion begonnen und sie modifiziert, um eine Rekursion mit gotoAnweisungen zu simulieren : Dies ist wahrscheinlich nicht lesbar.

Ausgabe für alle Eingabewerte von 0 bis 59 .

Ursprüngliche rekursive Version mit Debugging-Informationen

(Anmerkung: terpribedeutet 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"))
    ))

Beispielsweise:

(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

Siehe auch diese Paste mit allen Ergebnissen von 0 bis 59 (nicht dasselbe wie oben, diese ist ausführlicher).

Iterative Version mit Debugging-Informationen

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

Dies ist eine ziemlich direkte Konvertierung meiner C-Lösung in CJam. Nicht so kurz, wie Sie es normalerweise von einer CJam-Lösung erwarten würden, aber diese leidet wirklich unter der Speicherbeschränkung. Die allgemeinen Vorteile des Aufbaus von Ergebnissen auf dem Stapel, der am Ende automatisch ausgegeben wird, und der Verwendung von ausgefallenen Listen- / Zeichenfolgenoperationen gehen alle aus dem Fenster. Dadurch wird die Lösung zeichenweise generiert und ausgegeben. Der Stack enthält zur Laufzeit nur wenige Ganzzahlen und ist am Ende leer.

Auch wenn die Verwendung einer Golfsprache nicht besonders gut ist, ist sie doch erheblich kürzer als der C-Code, nur weil die Notation kompakter ist.

Erläuterung:

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.