当考察整个小方格是否位于圆内/外或者被圆穿越时，有没有人担心两个对顶格所公共的对顶格点刚好在圆上，使得两格刚好一内一外？
或者像@lsr314 那样仅仅考察格子的中心时，有没有考虑过一个格子的中心刚好在圆上？
一个简单而有趣的事实是：无论分辨率多大，不可能有一个格子，它的中心或者一个顶点刚好在圆上。
其实这里面有大量的重复计算。 当确定了某个正方形已经是 整体的在圆内，或者圆外时，下一次迭代的时，由此产生的8个小正方形跟圆的关系 没必要重复判断 。我们只需进行简单的计数就行。 这样程序只进行 圆上的方格个数的统计。这样能大大的降低空间复杂度和时间复杂度。
wayne 发表于 2017-9-26 21:07
其实这里面有大量的重复计算。 当确定了某个正方形已经是 整体的在圆内，或者圆外时，下一次迭代的时，由此 ...
按次思路写了一个很笨的代码，迭代10次，得到:
下面的第一个三元组分别代表圆外，圆上，圆内的格子的个数。
{{0,8,0},8,{0,1.0000000,0}}
{{4,28,32},64,{0.062500000,0.43750000,0.50000000}}
{{104,76,332},512,{0.20312500,0.14843750,0.64843750}}
{{984,204,2908},4096,{0.24023438,0.049804688,0.70996094}}
{{8288,580,23900},32768,{0.25292969,0.017700195,0.72937012}}
{{67744,1556,192844},262144,{0.25842285,0.0059356689,0.73564148}}
{{545904,4180,1547068},2097152,{0.26030731,0.0019931793,0.73769951}}
{{4377944,11204,12388068},16777216,{0.26094580,0.00066781044,0.73838639}}
{{35052688,29724,99135316},134217728,{0.26116288,0.00022146106,0.73861566}}
{{280499768,79276,793162780},1073741824,{0.26123577,0.000073831528,0.73869040}}
{{2244206376,212076,6345516140},8589934592,{0.26126001,0.000024688896,0.73871530}}
{{17954209288,565692,50764701756},68719476736,{0.26126813,8.2319020*10^-6,0.73872364}}
wayne 发表于 2017-9-26 22:01
按次思路写了一个很笨的代码，迭代10次，得到:
下面的第一个三元组分别代表圆外，圆上，圆内的格子的 ...
迭代$18$次，可得：{0,8,0},8,{0.0000000000000000,1.0000000000000000,0.0000000000000000}
{4,28,32},64,{0.0625000000000000,0.4375000000000000,0.5000000000000000}
{104,76,332},512,{0.2031250000000000,0.1484375000000000,0.6484375000000000}
{984,204,2908},4096,{0.2402343750000000,0.0498046875000000,0.7099609375000000}
{8288,580,23900},32768,{0.2529296875000000,0.0177001953125000,0.7293701171875000}
{67744,1556,192844},262144,{0.2584228515625000,0.0059356689453125,0.7356414794921875}
{545904,4180,1547068},2097152,{0.2603073120117188,0.0019931793212891,0.7376995086669922}
{4377944,11204,12388068},16777216,{0.2609457969665527,0.0006678104400635,0.7383863925933838}
{35052688,29724,99135316},134217728,{0.2611628770828247,0.0002214610576630,0.7386156618595123}
{280499768,79276,793162780},1073741824,{0.2612357661128044,0.0000738315284252,0.7386904023587704}
{2244206376,212076,6345516140},8589934592,{0.2612600075080991,0.0000246888957918,0.7387153035961092}
{17954209288,565692,50764701756},68719476736,{0.2612681315513328,0.0000082319020294,0.7387236365466379}
{143635171632,1509332,406119132924},549755813888,{0.2612708551750984,0.0000027454589144,0.7387263993659872}
{1149085383304,4026028,3248957101772},4398046511104,{0.2612717669999256,0.0000009154127838,0.7387273175872906}
{9192693786392,10740796,25991667561644},35184372088832,{0.2612720716795138,0.0000003052717830,0.7387276230487032}
{73541578891856,28646804,207933369171996},281474976710656,{0.2612721732896830,0.0000001017738924,0.7387277249364246}
{588332707461496,76396620,1663467029827132},2251799813685248,{0.2612722071855238,0.0000000339269146,0.7387277588875616}
{4706661863240488,203728972,13307736442512524},18014398509481984,{0.2612722184847365,0.0000000113092298,0.7387277702060338}
KeyTo9_Fans 发表于 2017-9-26 22:21
迭代$18$次，可得：
:'(， 刚补上了 2个结果，结果 fans一下子给出了 18个，不好玩
hujunhua 发表于 2017-9-26 21:00
当考察整个小方格是否位于圆内/外或者被圆穿越时，有没有人担心两个对顶格所公共的对顶格点刚好在圆上，使 ...
是因为1/2 无法被表达成三进制里的有理数吧。
===
额，这种表达 好像有点问题，从迭代过程看， 正方形的顶点应该 都是从 三进制里的有理数。
设上述圆内、圆上的非白格数分别为 a(n)，b(n),记@KeyTo9Fans要的面积为A，则\[
A=\lim_{n\to\infty}\frac{a(n)}{8^n}，0=\lim_{n\to\infty}\frac{b(n)}{8^n}
\Longrightarrow A=\lim_{n\to\infty}\frac{a(n)+\lambda b(n)}{8^n}
\]`\lambda`为 0~1 的一个常系数。如果取\(\lambda_1\)序列递增而\(\lambda_2\)序列递减，这就得到了一个上界和下界。
显然取 0 和 1 可以得到一个上、下界，不过这未免也太懒了。貌似可取\(\lambda_1=1/2\)，能再大一点么?。
取\(\lambda=1/2\)的“面积”序列
{{0, 8, 0}, 0.50000000000000000000},
{{4, 28, 32},0.71875000000000000000},
{{104, 76, 332},0.72265625000000000000},
{{984, 204, 2908},0.73486328125000000000},
{{8288, 580, 23900},0.73822021484375000000},
{{67744, 1556, 192844},0.73860931396484375000},
{{545904, 4180, 1547068},0.73869609832763671875},
{{4377944, 11204, 12388068},0.73872029781341552734},
{{35052688, 29724, 99135316},0.73872639238834381104},
{{280499768, 79276, 793162780},0.73872731812298297882},
{{2244206376, 212076, 6345516140}, 0.73872764804400503635},
{{17954209288, 565692, 50764701756},0.73872775249765254557},
{{143635171632, 1509332, 406119132924},0.73872777209544437937},
{{1149085383304, 4026028, 3248957101772},0.73872777529368249816},
{{9192693786392, 10740796, 25991667561644},0.73872777568459468966},
{{73541578891856, 28646804, 207933369171996}, 0.73872777582337079139},
{{588332707461496, 76396620, 1663467029827132}, 0.73872777585101889741},
{{4706661863240488, 203728972, 13307736442512524}, 0.73872777586064863886}
此图还存在一个y=x的对称性。于是，只需计算1/8的面积就行了。迭代至19次， 计算了大约半个小时，占用内存超过6G，这个内存占用主要来自于保存1/8的圆上的格子坐标。终于突破了Fans的记录，第19次，20次，……的迭代结果为：
19: {37653295449008288,543283204,106461892083564380},{0.26127222225314139514,3.7697845123307871518*10^-9,0.73872777397707409253}
20: {301226365040331144,1448779164,851695138117736668},{0.26127222350931090383,1.2566156136484263328*10^-9,0.73872777523407348252}
21: {2409810924185402784,3863345612,6813561108806027412},{0.26127222392811149179,4.1886477055927406887*10^-10,0.73872777565302373765}
22: {19278487403784147304,10302538780,54508488880751520380},{0.26127222406771505802,1.3962543659240198024*10^-10,0.73872777579265950539}
23: {154227899257743649824,27473690092,436067911073488311796}
24: {1233823194135208730288,73263231116,3488543288661173252292}
25: {9870585553277031899992,195369181668,27908346309484760627908}
26: {78964684426737227956608,520985280228,223266770476399080439708}
27: {631717475415287101141792,1389296277316,1786134163812581951993244}
28: {5053739803326001562892000,3704793953044,14289073310504360438453772}
29: {40429918426617891895941808,9879454623900,114312586484044763011824820}
30: {323439347412969480294205216,26345219429236,914500691872384449385489772}
面积比例： $0.73872777586246736918$
算出第20次迭代的结果，果断终止程序的运行，因为此时虽然只是过去了一个小时12分钟，我有的是时间等待，但是内存已经占用了18G 了。:L
修改Fans的代码，运行1分34秒完成22次迭代，10分22秒完成24次迭代，1小时16分完成26次迭代，8小时27分完成28次迭代，2天12小时27分完成30次迭代，预计在2017年10月23日完成32次迭代。:D
我们可以查看圆弧和一个3*3网格相交的一般情况得出的函数。一个确定圆弧需要三个参数，圆心坐标和半径x,y,r.
我们把3*3正方形网格中间部分挖掉，然后看余下部分的圆弧下方部分占总面积比例为f0(x,y,r)
然后我们定义f_{n+1}(x,y,r)为8个小正方形各自看成一个大正方形计算对应fn值后的平均值。
那么n趋向无穷时结果就是我们所要的极限函数