On turn \(k\), the random point is chosen uniformly as
$$P=(1+ka,\ 1+kb),\qquad a,b\in[0,1],$$
so \(P\) is uniform in the square
$$Q_k=[1,k+1]\times[1,k+1].$$
The score is \(k\) exactly when the distance from the origin rounds to \(k\), i.e.
$$k-\frac12 \le \|P\| < k+\frac12.$$
The program computes the expected total score up to \(k=100000\). The final numeric answer is intentionally omitted here.
1) Expected score on one turn is an area. Since \(P\) is uniform in a square of area \(k^2\), the probability of scoring \(k\) equals
$$\frac{\operatorname{area}\bigl(Q_k\cap \mathcal A_k\bigr)}{k^2},$$
where \(\mathcal A_k\) is the annulus
$$\mathcal A_k=\left\{(x,y):k-\frac12\le \sqrt{x^2+y^2}<k+\frac12\right\}.$$
Therefore the expected contribution of turn \(k\) is
$$k\cdot \frac{\operatorname{area}(Q_k\cap \mathcal A_k)}{k^2} =\frac{\operatorname{area}(Q_k\cap \mathcal A_k)}{k}.$$
2) Why the upper edges of the square do not matter. Every point in the outer disk
$$x^2+y^2\le \left(k+\frac12\right)^2$$
has \(x\le k+\frac12\) and \(y\le k+\frac12\), which is strictly inside the square bounds \(x,y\le k+1\). So the only relevant constraints from \(Q_k\) are
$$x\ge 1,\qquad y\ge 1.$$
This is the key simplification behind the whole solution.
3) Introduce a cumulative area primitive. Define
$$A(r)=\operatorname{area}\left\{(x,y):x\ge 1,\ y\ge 1,\ x^2+y^2\le r^2\right\}.$$
Then the annulus area needed on turn \(k\) is just the difference
$$\Delta_k=A\left(k+\frac12\right)-A\left(k-\frac12\right).$$
So the full expectation becomes
$$E_K=\sum_{k=1}^{K}\frac{\Delta_k}{k} =\sum_{k=1}^{K}\frac{A(k+1/2)-A(k-1/2)}{k}.$$
This is exactly the summation implemented by the code.
4) Why \(A(r)=0\) for \(r\le \sqrt2\). The region \(x\ge 1,\ y\ge 1\) begins at the corner \((1,1)\), whose distance from the origin is
$$\sqrt{1^2+1^2}=\sqrt2.$$
If \(r\le \sqrt2\), the disk of radius \(r\) does not reach that corner, so there is no area at all inside the target region. Hence
$$A(r)=0\qquad (r\le \sqrt2).$$
5) Integral formula for \(A(r)\). For \(r>\sqrt2\), the circle \(x^2+y^2=r^2\) meets the line \(y=1\) at
$$x=t=\sqrt{r^2-1}.$$
Thus the desired area is the region between the arc
$$y=\sqrt{r^2-x^2}$$
and the line \(y=1\), for \(x\in[1,t]\). Therefore
$$A(r)=\int_1^t \left(\sqrt{r^2-x^2}-1\right)\,dx.$$
6) Evaluate the integral in closed form. We use
$$\int \sqrt{r^2-x^2}\,dx =\frac12\left(x\sqrt{r^2-x^2}+r^2\arcsin\frac{x}{r}\right).$$
Hence
$$ A(r)= \left[ \frac12\left(x\sqrt{r^2-x^2}+r^2\arcsin\frac{x}{r}\right)-x \right]_{x=1}^{x=t}. $$
At the upper limit, \(t=\sqrt{r^2-1}\) and \(\sqrt{r^2-t^2}=1\). Also
$$\arcsin\frac{t}{r}=\frac{\pi}{2}-\arcsin\frac1r.$$
Substituting and simplifying gives
$$A(r)=r^2\left(\frac{\pi}{4}-\arcsin\frac1r\right)-\sqrt{r^2-1}+1.$$
This is the exact formula used by area_inside_square_and_circle.
Example 1: the first turn. For \(k=1\), the inner radius is \(1/2\), so \(A(1/2)=0\). The outer radius is \(3/2\), hence
$$\Delta_1=A\left(\frac32\right)\approx 0.0072246524.$$
Since the turn score is weighted by \(1/k=1\), the expected contribution of turn 1 is the same tiny area. Geometrically, this is just the small lens near the corner \((1,1)\).
Example 2: checkpoint value. The source file checks that
$$E_{10}\approx 10.20914,$$
rounded to five digits after the decimal point. That is the numerical sanity check for the whole derivation.
The solver does not simulate random throws. Instead, for each \(k\), it evaluates the exact outer area
$$A\left(k+\frac12\right),$$
subtracts the exact inner area
$$A\left(k-\frac12\right),$$
and divides by \(k\), which is precisely the expected contribution of the \(k\)-th turn. Summing these deterministic terms gives the exact expectation up to floating-point rounding.
Each \(k\) requires only a constant number of elementary operations: one square root, one arcsine, and a few additions and multiplications. Therefore
$$\text{time}=O(K),\qquad \text{memory}=O(1).$$
The implementation uses long double and prints the final value to five decimal places.
Im \(k\)-ten Zug wird der Punkt
$$P=(1+ka,\ 1+kb),\qquad a,b\in[0,1]$$
gleichverteilt im Quadrat
$$Q_k=[1,k+1]\times[1,k+1]$$
gewählt. Der Score ist genau \(k\), wenn der Abstand vom Ursprung auf \(k\) gerundet wird, also
$$k-\frac12 \le \|P\| < k+\frac12.$$
Das Programm berechnet den Erwartungswert der Gesamtsumme bis \(k=100000\). Der endgültige Zahlenwert wird hier absichtlich nicht genannt.
1) Erwartungswert eines Zuges als Fläche. Da \(P\) gleichverteilt auf einer Fläche \(k^2\) liegt, ist die Trefferwahrscheinlichkeit
$$\frac{\operatorname{area}(Q_k\cap \mathcal A_k)}{k^2},$$
wobei \(\mathcal A_k\) der Ring
$$\mathcal A_k=\left\{(x,y):k-\frac12\le \sqrt{x^2+y^2}<k+\frac12\right\}$$
ist. Also beträgt der Erwartungsbeitrag des Zuges
$$\frac{\operatorname{area}(Q_k\cap \mathcal A_k)}{k}.$$
2) Warum die oberen Quadratgrenzen irrelevant sind. Im äußeren Kreis mit Radius \(k+\tfrac12\) gilt stets
$$x\le k+\frac12<k+1,\qquad y\le k+\frac12<k+1.$$
Darum spielen die Randbedingungen \(x\le k+1\), \(y\le k+1\) gar keine Rolle. Übrig bleiben nur
$$x\ge 1,\qquad y\ge 1.$$
3) Eine kumulative Flächenfunktion. Definiere
$$A(r)=\operatorname{area}\{(x,y):x\ge 1,\ y\ge 1,\ x^2+y^2\le r^2\}.$$
Dann ist die benötigte Ringfläche
$$\Delta_k=A\left(k+\frac12\right)-A\left(k-\frac12\right),$$
und damit
$$E_K=\sum_{k=1}^{K}\frac{\Delta_k}{k} =\sum_{k=1}^{K}\frac{A(k+1/2)-A(k-1/2)}{k}.$$
4) Warum \(A(r)=0\) für \(r\le \sqrt2\). Der erste Punkt des Bereichs \(x\ge 1,\ y\ge 1\) ist die Ecke \((1,1)\) mit Abstand
$$\sqrt{1^2+1^2}=\sqrt2.$$
Erreicht der Kreis diesen Punkt nicht, gibt es keine Fläche. Also
$$A(r)=0\qquad (r\le \sqrt2).$$
5) Integralformel für \(A(r)\). Für \(r>\sqrt2\) schneidet der Kreis \(x^2+y^2=r^2\) die Gerade \(y=1\) bei
$$x=t=\sqrt{r^2-1}.$$
Die gesuchte Fläche liegt zwischen dem Kreisbogen
$$y=\sqrt{r^2-x^2}$$
und der Geraden \(y=1\), für \(x\in[1,t]\). Daher
$$A(r)=\int_1^t\left(\sqrt{r^2-x^2}-1\right)\,dx.$$
6) Geschlossene Form. Mit
$$\int \sqrt{r^2-x^2}\,dx =\frac12\left(x\sqrt{r^2-x^2}+r^2\arcsin\frac{x}{r}\right)$$
folgt
$$ A(r)= \left[ \frac12\left(x\sqrt{r^2-x^2}+r^2\arcsin\frac{x}{r}\right)-x \right]_{1}^{t}. $$
Mit \(t=\sqrt{r^2-1}\), \(\sqrt{r^2-t^2}=1\) und
$$\arcsin\frac{t}{r}=\frac{\pi}{2}-\arcsin\frac1r$$
vereinfacht sich das zu
$$A(r)=r^2\left(\frac{\pi}{4}-\arcsin\frac1r\right)-\sqrt{r^2-1}+1.$$
Beispiel 1: \(k=1\). Dann ist \(A(1/2)=0\) und
$$\Delta_1=A\left(\frac32\right)\approx 0.0072246524.$$
Das ist ein sehr kleiner Linsenbereich nahe der Ecke \((1,1)\).
Beispiel 2: Checkpoint. Der Quelltext prüft
$$E_{10}\approx 10.20914$$
auf fünf Nachkommastellen.
Der Solver simuliert keine Zufallswürfe. Für jedes \(k\) berechnet er exakt die äußere Fläche \(A(k+\tfrac12)\), zieht die innere Fläche \(A(k-\tfrac12)\) ab und teilt durch \(k\). Genau das ist der Erwartungsbeitrag des \(k\)-ten Zuges. Die Summe über alle \(k\) liefert daher den gesuchten Erwartungswert.
Pro \(k\) fallen nur konstant viele elementare Operationen an: eine Wurzel, ein \(\arcsin\) und einige arithmetische Verknüpfungen. Also gilt
$$\text{Zeit}=O(K),\qquad \text{Speicher}=O(1).$$
Die Implementierung nutzt long double und gibt das Ergebnis mit fünf Nachkommastellen aus.
\(k\). turda rastgele nokta
$$P=(1+ka,\ 1+kb),\qquad a,b\in[0,1]$$
şeklinde seçilir. Bu, \(P\)'nin
$$Q_k=[1,k+1]\times[1,k+1]$$
karesi üzerinde düzgün dağıldığı anlamına gelir. Skorun \(k\) olması için orijine uzaklığın \(k\)'ye yuvarlanması gerekir; yani
$$k-\frac12 \le \|P\| < k+\frac12.$$
Program \(k=1\)'den \(100000\)'e kadar toplam beklenen skoru hesaplar. Son sayısal cevap burada özellikle verilmez.
1) Tek turun beklentisi bir alan hesabıdır. \(P\), alanı \(k^2\) olan kare üzerinde uniform olduğundan, \(k\) puan alma olasılığı
$$\frac{\operatorname{area}(Q_k\cap \mathcal A_k)}{k^2}$$
olur. Burada halka bölgesi
$$\mathcal A_k=\left\{(x,y):k-\frac12\le \sqrt{x^2+y^2}<k+\frac12\right\}$$
şeklindedir. Dolayısıyla \(k\). turun beklenen katkısı
$$k\cdot \frac{\operatorname{area}(Q_k\cap \mathcal A_k)}{k^2} =\frac{\operatorname{area}(Q_k\cap \mathcal A_k)}{k}$$
olur.
2) Karenin üst sınırları neden hiç rol oynamaz? Dış çember yarıçapı \(k+\tfrac12\) olduğundan, bu diskin içindeki her nokta için
$$x\le k+\frac12<k+1,\qquad y\le k+\frac12<k+1$$
vardır. Yani \(x\le k+1\) ve \(y\le k+1\) kısıtları zaten otomatik sağlanır. Geriye sadece
$$x\ge 1,\qquad y\ge 1$$
koşulları kalır. Çözümün asıl sadeleşmesi budur.
3) Birikimli alan fonksiyonu tanımla. Şimdi
$$A(r)=\operatorname{area}\{(x,y):x\ge 1,\ y\ge 1,\ x^2+y^2\le r^2\}$$
tanımını yapalım. O zaman \(k\). turdaki halka kesişim alanı
$$\Delta_k=A\left(k+\frac12\right)-A\left(k-\frac12\right)$$
olur ve toplam beklenti
$$E_K=\sum_{k=1}^{K}\frac{\Delta_k}{k} =\sum_{k=1}^{K}\frac{A(k+1/2)-A(k-1/2)}{k}$$
şekline iner. Kod tam olarak bu toplamı hesaplar.
4) Neden \(A(r)=0\) için eşik \(\sqrt2\)? Bölgenin ilk noktası \((1,1)\) köşesidir ve orijine uzaklığı
$$\sqrt{1^2+1^2}=\sqrt2$$
olur. Eğer \(r\le \sqrt2\) ise disk bu köşeye bile ulaşamaz; dolayısıyla alan sıfırdır:
$$A(r)=0\qquad (r\le \sqrt2).$$
5) \(A(r)\) için integral. \(r>\sqrt2\) olduğunda çember \(x^2+y^2=r^2\), \(y=1\) doğrusunu
$$x=t=\sqrt{r^2-1}$$
noktasında keser. Aranan alan,
$$y=\sqrt{r^2-x^2}$$
yayı ile \(y=1\) doğrusu arasındaki bölgedir. Bu yüzden
$$A(r)=\int_1^t\left(\sqrt{r^2-x^2}-1\right)\,dx$$
yazılır.
6) Kapalı formu çıkar. Kullanılan temel integral
$$\int \sqrt{r^2-x^2}\,dx =\frac12\left(x\sqrt{r^2-x^2}+r^2\arcsin\frac{x}{r}\right)$$
olduğundan
$$ A(r)= \left[ \frac12\left(x\sqrt{r^2-x^2}+r^2\arcsin\frac{x}{r}\right)-x \right]_{1}^{t} $$
elde edilir. Üst sınırda \(t=\sqrt{r^2-1}\), \(\sqrt{r^2-t^2}=1\) ve
$$\arcsin\frac{t}{r}=\frac{\pi}{2}-\arcsin\frac1r$$
olduğu için sadeleştirme sonunda
$$A(r)=r^2\left(\frac{\pi}{4}-\arcsin\frac1r\right)-\sqrt{r^2-1}+1$$
çıkar. Kodun area_inside_square_and_circle fonksiyonu doğrudan bunu uygular.
Örnek 1: ilk tur. \(k=1\) için iç yarıçap \(1/2\) olduğundan \(A(1/2)=0\). Dış yarıçap \(3/2\) için
$$\Delta_1=A\left(\frac32\right)\approx 0.0072246524$$
bulunur. Bu, \((1,1)\) köşesi yakınındaki çok küçük lens bölgesidir.
Örnek 2: checkpoint. Kaynak dosya
$$E_{10}\approx 10.20914$$
değerini beş ondalık basamağa yuvarlayarak doğrular.
Çözüm rastgele deneme yapmaz. Her \(k\) için tam dış alan \(A(k+\tfrac12)\) hesaplanır, tam iç alan \(A(k-\tfrac12)\) çıkarılır ve sonuç \(k\)'ya bölünür. Bu, \(k\). turun beklenen katkısının birebir kendisidir. Dolayısıyla tüm \(k\)'lar üzerindeki toplam tam beklentiyi verir.
Her \(k\) için yalnızca sabit sayıda temel işlem vardır: bir karekök, bir \(\arcsin\) ve birkaç aritmetik işlem. Bu nedenle
$$\text{süre}=O(K),\qquad \text{bellek}=O(1).$$
Implementasyon long double kullanır ve sonucu beş ondalık basamakla yazar.
En el turno \(k\), el punto aleatorio es
$$P=(1+ka,\ 1+kb),\qquad a,b\in[0,1],$$
así que \(P\) es uniforme en el cuadrado
$$Q_k=[1,k+1]\times[1,k+1].$$
La puntuación es \(k\) exactamente cuando la distancia al origen se redondea a \(k\), es decir, cuando
$$k-\frac12 \le \|P\| < k+\frac12.$$
El programa calcula la esperanza del total hasta \(k=100000\). El valor numérico final se omite aquí a propósito.
1) La esperanza de un turno es un área. Como \(P\) es uniforme en un cuadrado de área \(k^2\), la probabilidad de anotar \(k\) es
$$\frac{\operatorname{area}(Q_k\cap \mathcal A_k)}{k^2},$$
donde
$$\mathcal A_k=\left\{(x,y):k-\frac12\le \sqrt{x^2+y^2}<k+\frac12\right\}$$
es el anillo correspondiente. Por tanto, la contribución esperada del turno \(k\) es
$$\frac{\operatorname{area}(Q_k\cap \mathcal A_k)}{k}.$$
2) Por qué los bordes superiores del cuadrado no importan. Dentro del disco exterior de radio \(k+\tfrac12\) siempre se cumple
$$x\le k+\frac12<k+1,\qquad y\le k+\frac12<k+1.$$
Así que las restricciones superiores del cuadrado ya están satisfechas automáticamente. Solo quedan
$$x\ge 1,\qquad y\ge 1.$$
3) Definir una función acumulada de área. Sea
$$A(r)=\operatorname{area}\{(x,y):x\ge 1,\ y\ge 1,\ x^2+y^2\le r^2\}.$$
Entonces el área útil del anillo del turno \(k\) es
$$\Delta_k=A\left(k+\frac12\right)-A\left(k-\frac12\right),$$
y la esperanza total es
$$E_K=\sum_{k=1}^{K}\frac{\Delta_k}{k} =\sum_{k=1}^{K}\frac{A(k+1/2)-A(k-1/2)}{k}.$$
4) Por qué \(A(r)=0\) si \(r\le \sqrt2\). La primera esquina de la región \(x\ge 1,\ y\ge 1\) es \((1,1)\), cuya distancia al origen es
$$\sqrt{1^2+1^2}=\sqrt2.$$
Si el disco no llega a esa esquina, no hay área alguna. Por tanto,
$$A(r)=0\qquad (r\le \sqrt2).$$
5) Fórmula integral para \(A(r)\). Si \(r>\sqrt2\), el círculo \(x^2+y^2=r^2\) corta la recta \(y=1\) en
$$x=t=\sqrt{r^2-1}.$$
El área deseada es la región entre el arco
$$y=\sqrt{r^2-x^2}$$
y la recta \(y=1\), para \(x\in[1,t]\). Luego
$$A(r)=\int_1^t\left(\sqrt{r^2-x^2}-1\right)\,dx.$$
6) Forma cerrada. Usando
$$\int \sqrt{r^2-x^2}\,dx =\frac12\left(x\sqrt{r^2-x^2}+r^2\arcsin\frac{x}{r}\right),$$
obtenemos
$$ A(r)= \left[ \frac12\left(x\sqrt{r^2-x^2}+r^2\arcsin\frac{x}{r}\right)-x \right]_{1}^{t}. $$
Con \(t=\sqrt{r^2-1}\), \(\sqrt{r^2-t^2}=1\) y
$$\arcsin\frac{t}{r}=\frac{\pi}{2}-\arcsin\frac1r,$$
la expresión se simplifica a
$$A(r)=r^2\left(\frac{\pi}{4}-\arcsin\frac1r\right)-\sqrt{r^2-1}+1.$$
Ejemplo 1: \(k=1\). Aquí \(A(1/2)=0\) y
$$\Delta_1=A\left(\frac32\right)\approx 0.0072246524.$$
Geométricamente es una pequeña lente cerca de la esquina \((1,1)\).
Ejemplo 2: checkpoint. El archivo fuente verifica que
$$E_{10}\approx 10.20914$$
redondeado a cinco decimales.
La solución no simula lanzamientos aleatorios. Para cada \(k\), calcula exactamente el área exterior \(A(k+\tfrac12)\), resta el área interior \(A(k-\tfrac12)\) y divide por \(k\). Esa cantidad es exactamente la contribución esperada del turno \(k\). La suma de todos esos términos produce la esperanza total.
Cada \(k\) requiere solo un número constante de operaciones elementales: una raíz, un \(\arcsin\) y unas pocas sumas y productos. Por ello,
$$\text{tiempo}=O(K),\qquad \text{memoria}=O(1).$$
La implementación usa long double y muestra el resultado con cinco cifras decimales.
第 \(k\) 轮时，随机点取为
$$P=(1+ka,\ 1+kb),\qquad a,b\in[0,1],$$
因此 \(P\) 在正方形
$$Q_k=[1,k+1]\times[1,k+1]$$
上均匀分布。若点到原点的距离被四舍五入为 \(k\)，也就是
$$k-\frac12 \le \|P\| < k+\frac12,$$
则本轮得分为 \(k\)。程序计算一直到 \(k=100000\) 的总期望得分。最终数值答案这里不写出。
1) 单轮期望就是一个面积。 因为 \(P\) 在面积为 \(k^2\) 的正方形上均匀分布，所以本轮得 \(k\) 分的概率为
$$\frac{\operatorname{area}(Q_k\cap \mathcal A_k)}{k^2},$$
其中
$$\mathcal A_k=\left\{(x,y):k-\frac12\le \sqrt{x^2+y^2}<k+\frac12\right\}$$
是对应的圆环区域。因此第 \(k\) 轮的期望贡献为
$$\frac{\operatorname{area}(Q_k\cap \mathcal A_k)}{k}.$$
2) 为什么正方形的上边界完全不起作用。 在外圆盘
$$x^2+y^2\le \left(k+\frac12\right)^2$$
内，必然有
$$x\le k+\frac12<k+1,\qquad y\le k+\frac12<k+1.$$
所以正方形上边和右边的限制自动满足。真正留下来的只有
$$x\ge 1,\qquad y\ge 1.$$
3) 定义累计面积函数。 设
$$A(r)=\operatorname{area}\{(x,y):x\ge 1,\ y\ge 1,\ x^2+y^2\le r^2\}.$$
那么第 \(k\) 轮所需的圆环面积就是
$$\Delta_k=A\left(k+\frac12\right)-A\left(k-\frac12\right),$$
总期望变为
$$E_K=\sum_{k=1}^{K}\frac{\Delta_k}{k} =\sum_{k=1}^{K}\frac{A(k+1/2)-A(k-1/2)}{k}.$$
4) 为什么当 \(r\le \sqrt2\) 时 \(A(r)=0\)。 区域 \(x\ge 1,\ y\ge 1\) 的最靠近原点的点是角点 \((1,1)\)，其距离为
$$\sqrt{1^2+1^2}=\sqrt2.$$
如果半径不超过这个值，圆盘根本碰不到该区域，因此
$$A(r)=0\qquad (r\le \sqrt2).$$
5) \(A(r)\) 的积分表达式。 当 \(r>\sqrt2\) 时，圆 \(x^2+y^2=r^2\) 与直线 \(y=1\) 的交点横坐标为
$$x=t=\sqrt{r^2-1}.$$
于是目标面积就是圆弧
$$y=\sqrt{r^2-x^2}$$
与直线 \(y=1\) 之间、\(x\in[1,t]\) 的区域，所以
$$A(r)=\int_1^t\left(\sqrt{r^2-x^2}-1\right)\,dx.$$
6) 闭式求值。 利用
$$\int \sqrt{r^2-x^2}\,dx =\frac12\left(x\sqrt{r^2-x^2}+r^2\arcsin\frac{x}{r}\right),$$
得到
$$ A(r)= \left[ \frac12\left(x\sqrt{r^2-x^2}+r^2\arcsin\frac{x}{r}\right)-x \right]_{1}^{t}. $$
再用 \(t=\sqrt{r^2-1}\)、\(\sqrt{r^2-t^2}=1\) 以及
$$\arcsin\frac{t}{r}=\frac{\pi}{2}-\arcsin\frac1r$$
可化简为
$$A(r)=r^2\left(\frac{\pi}{4}-\arcsin\frac1r\right)-\sqrt{r^2-1}+1.$$
示例 1: \(k=1\). 此时 \(A(1/2)=0\)，并且
$$\Delta_1=A\left(\frac32\right)\approx 0.0072246524.$$
这在几何上就是角点 \((1,1)\) 附近的一小块透镜区域。
示例 2: checkpoint. 源码验证了
$$E_{10}\approx 10.20914$$
保留五位小数时成立。
程序没有做 Monte Carlo 模拟。它对每个 \(k\) 精确计算外半径面积 \(A(k+\tfrac12)\)，减去内半径面积 \(A(k-\tfrac12)\)，再除以 \(k\)。这正好就是第 \(k\) 轮的期望得分贡献。把所有轮次求和，就得到总期望。
每个 \(k\) 只需要常数次基本运算：一次开方、一次反正弦以及少量加减乘法。因此
$$\text{时间}=O(K),\qquad \text{空间}=O(1).$$
实现使用 long double，并将结果输出到小数点后五位。
На ходе \(k\) случайная точка выбирается как
$$P=(1+ka,\ 1+kb),\qquad a,b\in[0,1],$$
то есть равномерно в квадрате
$$Q_k=[1,k+1]\times[1,k+1].$$
Очки равны \(k\) тогда и только тогда, когда расстояние до начала координат округляется до \(k\), то есть
$$k-\frac12 \le \|P\| < k+\frac12.$$
Программа вычисляет математическое ожидание суммарного результата до \(k=100000\). Финальное числовое значение здесь намеренно не приводится.
1) Ожидание одного хода - это площадь. Так как \(P\) равномерна на квадрате площади \(k^2\), вероятность получить \(k\) очков равна
$$\frac{\operatorname{area}(Q_k\cap \mathcal A_k)}{k^2},$$
где
$$\mathcal A_k=\left\{(x,y):k-\frac12\le \sqrt{x^2+y^2}<k+\frac12\right\}$$
есть нужное кольцо. Следовательно, ожидаемый вклад \(k\)-го хода равен
$$\frac{\operatorname{area}(Q_k\cap \mathcal A_k)}{k}.$$
2) Почему верхние границы квадрата не важны. Для любой точки во внешнем диске радиуса \(k+\tfrac12\) выполнено
$$x\le k+\frac12<k+1,\qquad y\le k+\frac12<k+1.$$
Значит, ограничения \(x\le k+1\), \(y\le k+1\) выполняются автоматически. Остаются только условия
$$x\ge 1,\qquad y\ge 1.$$
3) Накопленная функция площади. Введем
$$A(r)=\operatorname{area}\{(x,y):x\ge 1,\ y\ge 1,\ x^2+y^2\le r^2\}.$$
Тогда нужная площадь кольца на ходе \(k\) равна
$$\Delta_k=A\left(k+\frac12\right)-A\left(k-\frac12\right),$$
а полное ожидание имеет вид
$$E_K=\sum_{k=1}^{K}\frac{\Delta_k}{k} =\sum_{k=1}^{K}\frac{A(k+1/2)-A(k-1/2)}{k}.$$
4) Почему \(A(r)=0\) при \(r\le \sqrt2\). Ближайшая к началу координат точка области \(x\ge 1,\ y\ge 1\) - это угол \((1,1)\), расстояние до которого равно
$$\sqrt{1^2+1^2}=\sqrt2.$$
Если радиус меньше либо равен этому значению, диск вообще не заходит в нужную область. Поэтому
$$A(r)=0\qquad (r\le \sqrt2).$$
5) Интегральная формула для \(A(r)\). Если \(r>\sqrt2\), то окружность \(x^2+y^2=r^2\) пересекает прямую \(y=1\) при
$$x=t=\sqrt{r^2-1}.$$
Искомая площадь лежит между дугой
$$y=\sqrt{r^2-x^2}$$
и прямой \(y=1\) на промежутке \(x\in[1,t]\). Следовательно,
$$A(r)=\int_1^t\left(\sqrt{r^2-x^2}-1\right)\,dx.$$
6) Замкнутая формула. Используем
$$\int \sqrt{r^2-x^2}\,dx =\frac12\left(x\sqrt{r^2-x^2}+r^2\arcsin\frac{x}{r}\right).$$
Тогда
$$ A(r)= \left[ \frac12\left(x\sqrt{r^2-x^2}+r^2\arcsin\frac{x}{r}\right)-x \right]_{1}^{t}. $$
Подставляя \(t=\sqrt{r^2-1}\), \(\sqrt{r^2-t^2}=1\) и
$$\arcsin\frac{t}{r}=\frac{\pi}{2}-\arcsin\frac1r,$$
получаем
$$A(r)=r^2\left(\frac{\pi}{4}-\arcsin\frac1r\right)-\sqrt{r^2-1}+1.$$
Пример 1: \(k=1\). Здесь \(A(1/2)=0\), а
$$\Delta_1=A\left(\frac32\right)\approx 0.0072246524.$$
Геометрически это очень маленькая линза около угла \((1,1)\).
Пример 2: checkpoint. Исходный файл проверяет, что
$$E_{10}\approx 10.20914$$
после округления до пяти знаков после запятой.
Решение не делает случайное моделирование. Для каждого \(k\) оно точно вычисляет внешнюю площадь \(A(k+\tfrac12)\), вычитает внутреннюю площадь \(A(k-\tfrac12)\) и делит результат на \(k\). Это в точности и есть ожидаемый вклад \(k\)-го хода. Сумма по всем \(k\) дает искомое математическое ожидание.
Для каждого \(k\) требуется лишь константное число элементарных операций: корень, \(\arcsin\) и несколько арифметических действий. Поэтому
$$\text{время}=O(K),\qquad \text{память}=O(1).$$
Реализация использует long double и выводит результат с пятью знаками после запятой.
في الدور رقم \(k\)، يتم اختيار النقطة العشوائية
$$P=(1+ka,\ 1+kb),\qquad a,b\in[0,1],$$
وبالتالي تكون موزعة بانتظام داخل المربع
$$Q_k=[1,k+1]\times[1,k+1].$$
تكون النقاط المسجلة مساوية لـ \(k\) بالضبط عندما تُقرب المسافة إلى الأصل إلى \(k\)، أي عندما
$$k-\frac12 \le \|P\| < k+\frac12.$$
البرنامج يحسب القيمة المتوقعة للمجموع الكلي حتى \(k=100000\). أما القيمة العددية النهائية فلا نعرضها هنا عمدًا.
1) توقع الدور الواحد هو مساحة. بما أن \(P\) موزعة بانتظام على مربع مساحته \(k^2\)، فإن احتمال تسجيل \(k\) يساوي
$$\frac{\operatorname{area}(Q_k\cap \mathcal A_k)}{k^2},$$
حيث
$$\mathcal A_k=\left\{(x,y):k-\frac12\le \sqrt{x^2+y^2}<k+\frac12\right\}$$
هي الحلقة الشعاعية المناسبة. لذلك فإن المساهمة المتوقعة للدور \(k\) هي
$$\frac{\operatorname{area}(Q_k\cap \mathcal A_k)}{k}.$$
2) لماذا لا تؤثر الحدود العليا للمربع. داخل القرص الخارجي ذي نصف القطر \(k+\tfrac12\) لدينا دائمًا
$$x\le k+\frac12<k+1,\qquad y\le k+\frac12<k+1.$$
إذًا القيود \(x\le k+1\) و\(y\le k+1\) محققة تلقائيًا. لذلك لا يبقى من شروط المربع إلا
$$x\ge 1,\qquad y\ge 1.$$
3) تعريف دالة مساحة تراكمية. نعرّف
$$A(r)=\operatorname{area}\{(x,y):x\ge 1,\ y\ge 1,\ x^2+y^2\le r^2\}.$$
عندئذ تصبح مساحة الحلقة المطلوبة في الدور \(k\) مساوية لـ
$$\Delta_k=A\left(k+\frac12\right)-A\left(k-\frac12\right),$$
ومن ثم يكون التوقع الكلي
$$E_K=\sum_{k=1}^{K}\frac{\Delta_k}{k} =\sum_{k=1}^{K}\frac{A(k+1/2)-A(k-1/2)}{k}.$$
4) لماذا \(A(r)=0\) عندما \(r\le \sqrt2\). أقرب نقطة في المنطقة \(x\ge 1,\ y\ge 1\) إلى الأصل هي الزاوية \((1,1)\)، ومسافتها
$$\sqrt{1^2+1^2}=\sqrt2.$$
إذا لم يصل القرص إلى هذه الزاوية، فلا توجد أي مساحة داخل المنطقة المستهدفة. ولذلك
$$A(r)=0\qquad (r\le \sqrt2).$$
5) صيغة تكاملية لـ \(A(r)\). عندما \(r>\sqrt2\)، تقطع الدائرة \(x^2+y^2=r^2\) المستقيم \(y=1\) عند
$$x=t=\sqrt{r^2-1}.$$
وعليه فإن المساحة المطلوبة هي المنطقة بين القوس
$$y=\sqrt{r^2-x^2}$$
والمستقيم \(y=1\)، على المجال \(x\in[1,t]\). لذلك
$$A(r)=\int_1^t\left(\sqrt{r^2-x^2}-1\right)\,dx.$$
6) استخراج الصيغة المغلقة. نستخدم
$$\int \sqrt{r^2-x^2}\,dx =\frac12\left(x\sqrt{r^2-x^2}+r^2\arcsin\frac{x}{r}\right).$$
ومن ثم
$$ A(r)= \left[ \frac12\left(x\sqrt{r^2-x^2}+r^2\arcsin\frac{x}{r}\right)-x \right]_{1}^{t}. $$
وباستخدام \(t=\sqrt{r^2-1}\)، و\(\sqrt{r^2-t^2}=1\)، و
$$\arcsin\frac{t}{r}=\frac{\pi}{2}-\arcsin\frac1r,$$
نصل إلى
$$A(r)=r^2\left(\frac{\pi}{4}-\arcsin\frac1r\right)-\sqrt{r^2-1}+1.$$
مثال 1: \(k=1\). لدينا \(A(1/2)=0\)، ومن ثم
$$\Delta_1=A\left(\frac32\right)\approx 0.0072246524.$$
هندسيًا هذه مجرد عدسة صغيرة جدًا قرب الزاوية \((1,1)\).
مثال 2: نقطة تحقق. يتحقق الملف من أن
$$E_{10}\approx 10.20914$$
بعد التقريب إلى خمس منازل عشرية.
الحل لا يعتمد على المحاكاة العشوائية. لكل \(k\)، يحسب المساحة الخارجية الدقيقة \(A(k+\tfrac12)\)، ويطرح منها المساحة الداخلية الدقيقة \(A(k-\tfrac12)\)، ثم يقسم الناتج على \(k\). وهذا هو بالضبط التوقع الخاص بالدور \(k\). بجمع هذه الحدود نحصل على القيمة المتوقعة الكلية.
لكل قيمة \(k\) توجد فقط عمليات أساسية بعدد ثابت: جذر تربيعي، و\(\arcsin\)، وبعض العمليات الحسابية. لذلك
$$\text{الزمن}=O(K),\qquad \text{الذاكرة}=O(1).$$
التنفيذ يستخدم long double ويطبع النتيجة بخمس خانات بعد الفاصلة.