Schreiben Sie ein Programm oder eine Funktion, die bei einem ganzzahligen Radius r die Anzahl der Quadrate zurückgibt, durch die der Kreis mit dem Radius r zentriert ist. Wenn der Kreis genau durch einen Punkt auf dem Raster verläuft, der nicht als Durchlauf durch die benachbarten Einheitsquadrate zählt.

Hier ist eine Illustration für r = 5 :

^{Illustration von Kival Ngaokrajang, gefunden auf OEIS}

Beispiele:

0 → 0
1 → 4
4 → 28
5 → 28
49 → 388
50 → 380
325 → 2540
5524 → 44180
5525 → 44020

Python 2 , 54 Bytes

f=lambda r,x=0:r-x and-~((r*r-x*x)**.5%1>0)*4+f(r,x+1)

Probieren Sie es online!

Weniger Golf (55 Bytes) ( TIO )

lambda r:8*r-4*sum((r*r-x*x)**.5%1==0for x in range(r))

Dies schätzt die Ausgabe als 8*r, korrigiert dann Scheitelpunktkreuzungen. Das Ergebnis ist 8*r-g(r*r), wo g(x)die Anzahl der Schreibweisen xals Summe von zwei Quadraten gezählt wird (außer g(0)=0).

Wenn der Kreis keine Eckpunkte durchläuft, entspricht die Anzahl der berührten Zellen der Anzahl der gekreuzten Kanten. Der Kreis durchläuft 2*rvertikale und 2*rhorizontale Gitterlinien, die jeweils in beide Richtungen verlaufen 8*r.

Jede Kreuzung an einem Scheitelpunkt zählt jedoch als zwei Kantenübergänge, während nur eine neue Zelle eingegeben wird. Wir kompensieren dies, indem wir die Anzahl der Scheitelpunktkreuzungen subtrahieren. Dies beinhaltet die Punkte auf Achsen wie (r,0)auch pythagoreische Tripel wie (4,3)für r=5.

Wir zählen für einen einzelnen Quadranten die Punkte (x,y)mit x>=0und y>0mit x*x+y*y==nund multiplizieren dann mit 4. Dazu zählen wir sqrt(r*r-x*x)die ganze Zahl xim Intervall [0,r).

Mathematica, 48 Bytes

4Count[Range@#~Tuples~2,l_/;Norm[l-1]<#<Norm@l]&

Betrachtet den ersten Quadranten und zählt die Anzahl der Rasterzellen, für die die Eingabe zwischen den Normen der unteren linken und oberen rechten Ecke der Zelle liegt (das Ergebnis wird natürlich mit 4 multipliziert).

Python 2 , 72 Bytes

lambda n:sum(0<n*n-x*x-y*y<2*(x-~y)for x in range(n)for y in range(n))*4

Probieren Sie es online!

Jelly , 21 13 12 11 Bytes

R²ạ²Æ²SạḤ×4

Probieren Sie es online!

Wie es funktioniert

R²ạ²Æ²SạḤ×4  Main link. Argument: r

R            Range; yield [1, 2, ..., r].
 ²           Square; yield [1², 2², ..., r²].
   ²         Square; yield r².
  ạ          Absolute difference; yield [r²-1², r²-2², ..., r²-r²].
    Ʋ       Test if each of the differences is a perfect square.
      S      Sum, counting the number of perfect squares and thus the integer
             solutions of the equation x² + y² = r² with x > 0 and y ≥ 0.
        Ḥ    Un-halve; yield 2r.
       ạ     Subtract the result to the left from the result to the right.
         ×4  Multiply by 4.

Perl 6, 61 Bytes

->\r{4*grep {my &n={[+] $_»²};n(1 X+$_)>r²>.&n},(^r X ^r)}

Wie es funktioniert

->\r{                                                    } # Lambda (accepts the radius).
                                                (^r X ^r)  # Pairs from (0,0) to (r-1,r-1),
                                                           #   representing the bottom-left
                                                           #   corners of all squares in
                                                           #   the top-right quadrant.
       grep {                                 }            # Filter the ones matching:
             my &n={[+] $_»²};                             #   Lambda to calculate the norm.
                              n(1 X+$_)>r²                 #   Top-right corner is outside,
                                          >.&n             #   and bottom-left is inside.
     4*                                                    # Return length of list times 4.

AWK, 90 Bytes

{z=$1*$1
for(x=$1;x>=0;x--)for(y=0;y<=$1;y++){d=z-x*x-y*y
if(d>0&&d<2*(x+y)+2)c++}$0=4*c}1

Verwendung:

awk '{z=$1*$1
    for(x=$1;x>=0;x--)for(y=0;y<=$1;y++){d=z-x*x-y*y
    if(d>0&&d<2*(x+y)+2)c++}$0=4*c}1' <<< 5525

Nur eine einfache Suche durch Quadrant 1, um alle Kästchen zu finden, die den Kreis schneiden. Symmetrie ermöglicht die Multiplikation mit 4. Könnte gehen -$1 to $1, aber das würde mehr Bytes dauern und weniger effizient sein. Offensichtlich ist dies nicht der zeiteffizienteste Algorithmus, aber es dauert nur ungefähr 16 Sekunden, um den 5525-Fall auf meinem Computer auszuführen.

Haskell, 74 Bytes

f n=sum[4|x<-[0..n],y<-[0..n],(1+n-x)^2+(1+n-y)^2>n^2,(n-x)^2+(n-y)^2<n^2]

Zählen Sie ganz einfach die Anzahl der Quadrate zwischen (0,0) und (n, n), wobei sich links unten innerhalb des Kreises und rechts oben außerhalb des Kreises befindet, und multiplizieren Sie dann mit 4.

Pyth , 29 Bytes

Lsm*ddb*4lf}*QQrhyTym+1dT^UQ2

Versuch es!

Erläuterung

Lsm*ddb*4lf}*QQrhyTym+1dT^UQ2  # implicit input: Q
Lsm*ddb                        # define norm function
 s                             # sum
  m   b                        #     map each coordinate to
   *dd                         #                            its square
                         ^UQ2  # cartesian square of [0, 1, ..., Q - 1]
                               #     -> list of coordinates of all relevant grid points
          f                    # filter the list of coordinates T where:
           }*QQ                # square of Q is in
               r               #     the range [
                hyT            #         1 + norm(T),
                               #                  ^ coordinate of lower left corner
                   ym+1dT      #         norm(map({add 1}, T))
                               #              ^^^^^^^^^^^^^^^ coordinate of upper right corner
                               #     ) <- half-open range
         l                     # size of the filtered list
                               #     -> number of passed-through squares in the first quadrant
       *4                      # multiply by 4
                               # implicit print

Batch, 147 Bytes

@set/an=0,r=%1*%1
@for /l %%i in (0,1,%1)do @for /l %%j in (0,1,%1)do @set/a"i=%%i,j=%%j,a=i*i+j*j-r,i+=1,j+=1,a&=r-i*i-j*j,n-=a>>31<<2
@echo %n%

Etwas inspiriert von den Antworten von AWK und Haskell.

Bash + Unix-Dienstprogramme, 127 Bytes

c()(d=$[(n/r+$1)**2+(n%r+$1)**2-r*r];((d))&&echo -n $[d<0])
r=$1
bc<<<`for((n=0;n<r*r;n++));{ c 0;c 1;echo;}|egrep -c 01\|10`*4

Probieren Sie es online!

Gehen Sie einfach alle Punkte im ersten Quadranten durch, zählen Sie sie hoch und multiplizieren Sie sie mit 4. Es kann sehr langsam sein, aber es funktioniert.

JavaScript (ES7), 76 Byte

n=>4*(G=k=>k<n?Math.ceil((n**2-k++**2)**0.5)-(0|(n**2-k**2)**0.5)+G(k):0)(0)