Możesz napisać program lub funkcję, która otrzyma nieparzystą, dodatnią liczbę całkowitą n , gdzie n >= 3jako argument funkcji, argument wiersza poleceń lub na STDIN (lub odpowiedniku dla twojego systemu) i wypisze na STDOUT (lub odpowiedniku systemu) spiralę ASCII która obraca się do wewnątrz zgodnie z ruchem wskazówek zegara, gdzie górna krawędź ma dokładnie ndługość znaków. n+1Oczywiście pierwsza prawa krawędź powinna być długa. Na przykład,

Wejście:

11

Wynik:

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

Połowy:

• Twój program nie może wykorzystywać więcej niż O(log n)pamięć .
• Twój program może drukować tylko znaki *(ASCII 42), (ASCII 32), <CR>(ASCII 13) i <LF>(ASCII 10).
• Twój program musi wydrukować ciąg, a nie zwrócić go z funkcji.
• Ograniczenie Big-O dotyczy tylko pamięci , nie ma żadnych ograniczeń dotyczących czasu wykonywania .
• Końcowy znak nowej linii jest opcjonalny.
• Jeśli twój język nie obsługuje dużych typów liczb całkowitych, nie musisz obsługiwać wyższych wartości niż obsługuje, ale nie możesz użyć tego jako sztuczki, by powiedzieć „och, cóż, nie muszę obsługiwać powyżej X, więc może po prostu stworzyć ogromną tablicę o maksymalnym rozmiarze za każdym razem ”

Standardowe luki są jak zwykle zakazane.

C, 125 121 bajtów

Wersja golfowa To nie ma zmiennej k. Zmienna kjest używana w wersji bez golfa, aby poprawić czytelność. forZmieniono również warunki warunkowe pętli i {}usunięto jeden zestaw niepotrzebnych . Kolejny zestaw {}można usunąć, migrując puts("")wewnątrz nawiasów jpętli w pozycji inicjalizacji, ale oznaczałoby to nowy wiersz na początku danych wyjściowych, więc tego nie zrobiłem.

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

Drukuje nszeroką przez n+1wysoką spiralę jak na przykładzie.

Wyjaśnienie

Zasadniczo połowę wartości n(zaokrąglając w dół) i uruchomić dwie pętle: zewnętrzną jednego iz -n/2-1do n/2+1drukowania wierszy ( i=0jest tłumione dzięki czemu otrzymujemy n+1wiersze) i wewnętrzną jednego jz ( -n/2do n/2Używamy wydrukować znaki). expression & 1Drukować paski , oraz warunek j*j<i*idecydujący o tym, czy wydrukować pionowe czy poziome paski (pionowe po bokach, gdzie bezwzględna wielkość ijest większa, i poziome u góry i na dole). Konieczne +njest dostosowanie, aby pomóc w prawidłowym zakończeniu w zależności od tego, czy n/2jest nieparzysty, czy parzysty.

kwynosi zwykle 1 i zapewnia korektę faktu, że wartości bezwzględne imieszczą się w zakresie od 1 do, n/2+1natomiast wartości bezwzględne jmieszczą się w zakresie od 0 do n/2. Gdyby kzawsze było 1, otrzymalibyśmy koncentryczne prostokąty, ale jest on odwracany do 0, gdy i==j&i<=0tak, że przekątny rząd komórek jest odwrócony, tworząc spiralę.

nie wziął udziału w programie testowym

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

Wynik

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

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

3
***
  *
* *
***

1
*
*

C, 118 bajtów

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

Kod przed końcowym golfem:

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

Kluczową obserwacją jest to, że wzór jest prawie serią koncentrycznych kwadratów. Z kilkoma drobnymi zmarszczkami:

• Rozmiar y jest większy niż rozmiar x. Jest to korygowane przez odjęcie 1 od y dla dolnej połowy, co zasadniczo powtarza środkowy rząd.
• Aby zamienić prostokąty w spiralę, piksele wzdłuż y = x + 1przekątnej należy odwrócić do środka kształtu.

Poza tym kod po prostu zapętla wszystkie pozycje, oblicza odległość Czebyszewa od środka dla każdej pozycji i emituje jeden z dwóch znaków w zależności od tego, czy odległość jest parzysta czy nieparzysta. I emitowanie nowego wiersza dla ostatniej pozycji każdej linii.

Ponieważ istnieje tylko kilka zmiennych skalarnych, a znaki są emitowane jeden po drugim, użycie pamięci jest oczywiście stałe.

C ++, 926 bajtów

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

To nie jest eleganckie, ale nie zajmuje dużo pamięci dla dużej liczby n. Ponadto istnieje (prawie na pewno) około 20 postaci, które można dalej grać w golfa, ale nie mogę już dłużej na to patrzeć.

Krótkie wyjaśnienie:

To dzieli linie w spiralach na dwa typy: te z ****** pośrodku i te z \ s \ s \ s \ s \ s w środku. Wtedy jasne jest, że każda linia składa się z kilku „*”, środka i niektórych „*”. Dokładne ustalenie, ile z każdej rzeczy jest proste, jeśli spojrzysz na wzór wystarczająco długo. Trudną rzeczą było wydrukowanie środka spirali, który właściwie zakodowałem na stałe za pomocą warunkowego. Okazało się to przydatne, ponieważ linie *** i \ s \ s \ s przełączają się na nieparzyste / nawet tam.

Testy:

Wejście: 55 (Myślę, że te duże wyglądają najfajniej)

Wynik:

************************************************** *****
                                                      *
************************************************** *** *
* * *
* ************************************************* * *
* * * * *
* * ********************************************* * * *
* * * * * * *
* * * ***************************************** * * * *
* * * * * * * * *
* * * * ************************************* * * * * *
* * * * * * * * * * *
* * * * * ********************************* * * * * * *
* * * * * * * * * * * * *
* * * * * * ***************************** * * * * * * *
* * * * * * * * * * * * * * *
* * * * * * * ************************* * * * * * * * *
* * * * * * * * * * * * * * * * *
* * * * * * * * ********************* * * * * * * * * *
* * * * * * * * * * * * * * * * * * *
* * * * * * * * * ******************* * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * ************* * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * ********* * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * ***** * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * * * * {- mój program dodaje tutaj spację
* * * * * * * * * * * * * *** * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * ******* * * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * *********** * * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * *************** * * * * * * * * * *
* * * * * * * * * * * * * * * * * * * *
* * * * * * * * * ********************* * * * * * * * * *
* * * * * * * * * * * * * * * * * *
* * * * * * * * *********************** * * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * *************************** * * * * * * *
* * * * * * * * * * * * * *
* * * * * * ******************************* * * * * * *
* * * * * * * * * * * *
* * * * * *********************************** * * * * *
* * * * * * * * * *
* * * * *************************************** * * * *
* * * * * * * *
* * * ******************************************* * * *
* * * * * *
* * *********************************************** * *
* * * *
* ************************************************* ** *
* *
************************************************** *****

Wejście: 3

Wynik:

***
  *
* * 
***

Uwaga: nie jestem informatykiem / studentem CS i nie wiem, jak udowodnić, że używa to pamięci O (log n). Mogę tylko ustalić, co zrobić na podstawie linków w pytaniu. Byłbym wdzięczny, gdyby ktoś mógł potwierdzić / zaprzeczyć, jeśli ta odpowiedź jest prawidłowa. Moją logiką dla ważności tej odpowiedzi jest to, że nigdy nie przechowuje żadnej zmiennej wielkości opartej na n, z wyjątkiem samego wejścia. Zamiast tego pętla for, która działa n razy, oblicza wartości całkowite na podstawie n. Istnieje taka sama liczba tych wartości, niezależnie od danych wejściowych.

Uwaga 2: To nie działa dla n = 1 z powodu mojej metody radzenia sobie ze środkiem. Łatwo byłoby to naprawić za pomocą warunkowych, więc jeśli ktoś znajdzie się w odległości kilku znaków od mojej odpowiedzi, naprawię to;)

Graj z nim na ideone.

Haskell, 151 bajtów

(#)=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)

Przykład użycia:

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

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

Dzięki lenistwu Haskella działa to w stałej pamięci. Wykorzystuje oczywiste podejście, czyli zapętlenie nad yi x, a wybór między *i , w zależności od

• jeśli bieżąca pozycja jest powyżej lub poniżej przekątnej
• xodpowiednio yjest parzysty lub nieparzysty
• n/2 jest parzysty lub nieparzysty

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

Iteracyjne rozwiązanie ze stałym zużyciem pamięci. Powyższe powoduje intensywne wykorzystanie zmiennych #n=i #n#czytników. Chociaż istnieją bardziej bezpośrednie podejścia, tutaj zacząłem od funkcji rekurencyjnej i zmodyfikowałem ją tak, aby symulowała rekurencję za pomocą gotoinstrukcji: jest to prawdopodobnie nieczytelne.

Wyjście dla wszystkich wartości wejściowych od 0 do 59 .

Oryginalna wersja rekurencyjna z informacjami o debugowaniu

(uwaga: terprioznacza 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"))
    ))

Na przykład:

(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

Zobacz także tę pastę ze wszystkimi wynikami od 0 do 59 (to nie to samo co powyżej, ta jest bardziej szczegółowa).

Wersja iteracyjna z informacjami debugowania

(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 bajty

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

Jest to dość bezpośrednia konwersja mojego rozwiązania C do CJam. Nie tak krótki, jak zwykle można oczekiwać od rozwiązania CJam, ale ten naprawdę cierpi z powodu ograniczenia pamięci. Wspólne zalety tworzenia wyników na stosie, który jest automatycznie zrzucany na końcu, i korzystania z fantazyjnych operacji na listach / ciągach, wszystko to wychodzi poza okno. To generuje i wysyła rozwiązanie po jednym znaku na raz. Stos zawiera tylko kilka liczb całkowitych w czasie wykonywania i jest pusty na końcu.

Mimo że nie jest to świetny sposób wyświetlania języka golfowego, jest on znacznie krótszy niż kod C tylko dlatego, że notacja jest bardziej zwarta.

Wyjaśnienie:

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.