Gambar berikut menunjukkan masalah:

Tulis fungsi yang, diberi bilangan bulat sebagai jari-jari lingkaran, menghitung jumlah titik kisi di dalam lingkaran pusat (termasuk batas).

Gambar menunjukkan:

f[1] = 5  (blue points)
f[2] = 13 (blue + red points)  

nilai lain untuk pemeriksaan / debugging Anda:

f[3]    = 29
f[10]   = 317
f[1000] = 3,141,549
f[2000] = 12,566,345  

Seharusnya memiliki kinerja yang wajar. Katakanlah kurang dari satu menit untuk f [1000].

Kode terpendek menang. Aturan Golf-Aturan Biasa berlaku.

Silakan kirim perhitungan dan waktu f [1001] sebagai contoh.

J, 21 19 18

+/@,@(>:|@j./~@i:)

Membangun kompleks dari -x-xj ke x + xj dan membutuhkan magnitudo.

Edit: Dengan >:

Sunting 2: Dengan kait dan monadik ~. Berjalan beberapa kali lebih lambat untuk beberapa alasan, tetapi masih 10 detik untuk f (1000).

J, 27 21

3 :'+/,y>:%:+/~*:i:y'

Sangat brutal: menghitung sqrt (x² + y²) pada rentang [-n, n] dan menghitung item ≤n . Masih sangat dapat diterima kali untuk 1000.

Sunting : i:ysedikit lebih pendek dari y-i.>:+:y. Terima kasih Jesse Millikan !

Ruby 1.9, 62 58 54 karakter

f=->r{1+4*eval((0..r).map{|i|"%d"%(r*r-i*i)**0.5}*?+)}

Contoh:

f[1001]
=> 3147833

t=Time.now;f[1001];Time.now-t
=> 0.003361411

Python 55 Chars

f=lambda n:1+4*sum(int((n*n-i*i)**.5)for i in range(n))

Haskell, 41 byte

f n=1+4*sum[floor$sqrt$n*n-x*x|x<-[0..n]]

Menghitung poin di kuadran x>=0, y>0, mengalikan dengan 4, menambahkan 1 untuk titik pusat.

Haskell, 44 byte

f n|w<-[-n..n]=sum[1|x<-w,y<-w,x*x+y*y<=n*n]

JavaScript (ES6), 80 byte (tidak bersaing karena ES6 terlalu baru)

n=>(a=[...Array(n+n+1)].map(_=>i--,i=n)).map(x=>a.map(y=>r+=x*x+y*y<=n*n),r=0)|r

Versi alternatif, juga 80 byte:

n=>[...Array(n+n+1)].map((_,x,a)=>a.map((_,y)=>r+=x*x+(y-=n)*y<=n*n,x-=n),r=0)|r

Versi ES7, juga 80 byte:

n=>[...Array(n+n+1)].map((_,x,a)=>a.map((_,y)=>r+=(x-n)**2+(y-n)**2<=n*n),r=0)|r

Python 2, 48 byte

f=lambda n,i=0:i>n or(n*n-i*i)**.5//1*4+f(n,i+1)

Seperti solusi fR0DDY , tetapi rekursif, dan mengembalikan float. Mengembalikan int adalah 51 byte:

f=lambda n,i=0:i>n or 4*int((n*n-i*i)**.5)+f(n,i+1)

C (gcc) , 60 byte

r,a;f(x){for(a=r=x*x;a--;)r-=hypot(a%x+1,a/x)>x;x=4*r+1;}

Cobalah online!

Loop di kuadran pertama, gandakan hasilnya dengan 4 dan tambahkan satu. Sedikit kurang golf

r,a;
f(x){
  for(a=r=x*x;a--;)
    r-=hypot(a%x+1,a/x)>x;
  x=4*r+1;
}

APL (Dyalog Extended) , 14 byte

{≢⍸⍵≥|⌾⍀⍨⍵…-⍵}

Cobalah online!

Meskipun tidak memiliki i:(kisaran inklusif dari -n ke n) yang dibangun di J, APL Extended memiliki sintaksis yang lebih pendek di area lain.

{≢⍸⍵≥|⌾⍀⍨⍵…-⍵}            Monadic function taking an argument n.
           ⍵…-⍵             n, n-1, ..., -n
      ⌾⍀                   Make a table of complex numbers
                            (equivalent to ∘.{⍺+1J×⍵} in Dyalog APL)
         ⍨                  with both real and imaginary parts from that list.
      |                       Take their magnitudes.
    ⍵≥                        1 where a magnitude are is at most n, and 0 elsewhere.
 ⍸                           Get all indices of truthy values.
≢                            Find the length of the resulting list.

Japt -x , 12 byte

òUn)ï Ëx²§U²

Cobalah online!

Penjelasan:

òUn)            #Get the range [-input ... input]
    ï           #Get each pair of numbers in that range
      Ë         #For each pair:
       x        # Get the sum...
        ²       # Of the squares
         §      # Check if that sum is less than or equal to...
          U²    # The input squared
                #Output the number of pairs that passed the check

PHP, 85 83 byte

Kode:

function f($n){for($x=$n;$x;$c+=$x,$y++)for(;$n*$n<$x*$x+$y*$y;$x--);return$c*4+1;}

Hasilnya (lihat https://3v4l.org/bC0cY untuk beberapa versi PHP):

f(1001)=3147833
time=0.000236 seconds.

Kode yang tidak dipisahkan:

/**
 * Count all the points having x > 0, y >= 0 (a quarter of the circle)
 * then multiply by 4 and add the origin.
 *
 * Walk the lattice points in zig-zag starting at ($n,0) towards (0,$n), in the
 * neighbourhood of the circle. While outside the circle, go left.
 * Go one line up and repeat until $x == 0.
 * This way it checks about 2*$n points (i.e. its complexity is linear, O(n))
 *
 * @param int $n
 * @return int
 */
function countLatticePoints2($n)
{
    $count = 0;
    // Start on the topmost right point of the circle ($n,0), go towards the topmost point (0,$n)
    // Stop when reach it (but don't count it)
    for ($y = 0, $x = $n; $x > 0; $y ++) {
        // While outside the circle, go left;
        for (; $n * $n < $x * $x + $y * $y; $x --) {
            // Nothing here
        }
        // ($x,$y) is the rightmost lattice point on row $y that is inside the circle
        // There are exactly $x lattice points on the row $y that have x > 0
        $count += $x;
    }
    // Four quarters plus the center
    return 4 * $count + 1;
}

Implementasi naif yang memeriksa $n*($n+1)poin (dan berjalan 1000 lebih lambat tetapi masih menghitung f(1001)dalam waktu kurang dari 0,5 detik) dan test suite (menggunakan data sampel yang disediakan dalam pertanyaan) dapat ditemukan di github .

Clojure / ClojureScript, 85 karakter

#(apply + 1(for[m[(inc %)]x(range 1 m)y(range m):when(<=(+(* x x)(* y y))(* % %))]4))

Brute memaksa kuadran pertama, termasuk sumbu y tetapi bukan sumbu x. Hasilkan 4 untuk setiap titik, lalu tambahkan bersama dengan 1 untuk titik asal. Berjalan di bawah 2 detik untuk input 1000.

Menyalahgunakan foruntuk mendefinisikan variabel dan menyimpan beberapa karakter. Melakukan hal yang sama untuk membuat alias untuk rangetidak menyimpan karakter apa pun (dan membuatnya berjalan lebih lambat secara signifikan), dan sepertinya Anda tidak akan menyimpan apa pun dengan membuat fungsi persegi.

Pyke, 14 byte, tidak bersaing

QFXQX-_,B)s}}h

Coba di sini!

Mathematica, 35 karakter

f[n_]:=Sum[SquaresR[2,k],{k,0,n^2}]

Diangkat dari https://oeis.org/A000328

https://reference.wolfram.com/language/ref/SquaresR.html

SquaresR[2,k]adalah jumlah cara untuk merepresentasikan k sebagai jumlah dari dua kuadrat, yang sama dengan jumlah titik kisi pada lingkaran jari-jari k ^ 2. Jumlahkan dari k = 0 hingga k = n ^ 2 untuk menemukan semua titik pada atau di dalam lingkaran jari-jari n.

Tcl, 111 byte

lassign {1001 0 -1} r R x
while {[incr x]<$r} {set R [expr {$R+floor(sqrt($r*$r-$x*$x))}]}
puts [expr {4*$R+1}]

Diskrit x loop sederhana di atas kuadran I, menghitung terbesar y menggunakan Teorema Pythagoras pada setiap langkah. Hasilnya adalah 4 kali jumlah ditambah satu (untuk titik tengah).

Ukuran program tergantung pada nilai r . Ganti {1001 0 -1}dengan "$argv 0 -1"dan Anda dapat menjalankannya dengan nilai argumen baris perintah apa pun untuk r .

Menghitung f (1001) → 3147833.0 dalam sekitar 1030 mikrodetik, prosesor AMD Sempron 130 2.6GHz 64-bit, Windows 7.

_{Jelas, semakin besar jari-jari, semakin dekat perkiraan ke PI: f (10000001) berjalan dalam waktu sekitar 30 detik menghasilkan nilai 15-digit, yaitu tentang ketepatan ganda IEEE.}

Stax , 11 byte

ä÷²M╨⌐■╝^₧░

Jalankan dan debug itu