Start with a random permutation of \(\{1,2,\dots,n\}\). One first-sort move finds the first entry that is smaller than the entry immediately to its left and moves that entry to the front. If \(E(n)\) denotes the expected number of moves needed to reach the increasing permutation, the task is to evaluate \(E(30)\) exactly and then print the result rounded to two decimal places.
The solution does not simulate permutations. Instead, it uses an exact recurrence for \(E(n)\), turns that recurrence into a linear-time dynamic program, and keeps every intermediate value as an exact rational number.
The C++, Python, and Java implementations all rely on the same expectation recurrence. Once that identity is available, the rest of the work is careful bookkeeping: prefix sums for speed and a common denominator for exact arithmetic.
Let \(E(0)=0\). The first-sort analysis used by the implementations gives the averaged form
$$E(n)=\frac{1}{n}\sum_{k=0}^{n-1}\left(E(k)+2^k-1\right),\qquad n\ge 1.$$
Summing the geometric correction term yields
$$\sum_{k=0}^{n-1}(2^k-1)=\left(\sum_{k=0}^{n-1}2^k\right)-n=2^n-n-1,$$
so the same recurrence can be written more compactly as
$$E(n)=\frac{\sum_{k=0}^{n-1}E(k)+(2^n-n-1)}{n}.$$
This identity is the mathematical core of the entire solution.
Define
$$P(n)=\sum_{k=0}^{n}E(k).$$
Then the recurrence becomes
$$E(n)=\frac{P(n-1)+(2^n-n-1)}{n},$$
followed by the update
$$P(n)=P(n-1)+E(n).$$
So once \(P(n-1)\) is known, the next expectation is obtained in constant time. This is why the implementations only need a single forward sweep from \(1\) to \(30\).
The recurrence also has a useful telescoping form. From
$$nE(n)=P(n-1)+2^n-n-1$$
and
$$(n-1)E(n-1)=P(n-2)+2^{n-1}-n,$$
together with \(P(n-1)=P(n-2)+E(n-1)\), we obtain
$$nE(n)-nE(n-1)=2^{n-1}-1.$$
Therefore
$$E(n)=E(n-1)+\frac{2^{n-1}-1}{n}.$$
Summing these increments from \(1\) to \(n\) gives the closed form
$$E(n)=\sum_{j=1}^{n}\frac{2^{j-1}-1}{j}.$$
This form makes the denominator structure completely transparent: every term has denominator dividing \(j\).
Let
$$D=\operatorname{lcm}(1,2,\dots,N),\qquad N=30.$$
Because the closed form is a sum of terms with denominators \(1,2,\dots,n\), every value \(E(n)\) has denominator dividing \(D\). Hence we may store
$$A(n)=D\,E(n)$$
as an integer for every \(n\le N\). Multiplying the recurrence by \(D\) gives
$$A(n)=\frac{\sum_{k=0}^{n-1}A(k)+D(2^n-n-1)}{n}.$$
The numerator here is exactly \(nD\,E(n)\), so the division by \(n\) is exact. This removes all floating-point error from the computation.
The first few values come out immediately:
$$E(1)=\frac{E(0)+(2^1-1-1)}{1}=0,$$
$$E(2)=\frac{E(0)+E(1)+(2^2-2-1)}{2}=\frac{1}{2},$$
$$E(3)=\frac{E(0)+E(1)+E(2)+(2^3-3-1)}{3}=\frac{\frac{1}{2}+4}{3}=\frac{3}{2},$$
$$E(4)=\frac{E(0)+E(1)+E(2)+E(3)+(2^4-4-1)}{4}=\frac{0+0+\frac{1}{2}+\frac{3}{2}+11}{4}=\frac{13}{4}.$$
This reproduces the checkpoint \(E(4)=13/4\). Continuing the same process gives the second checkpoint
$$E(10)=\frac{4629}{40}.$$
The implementations first build the common denominator \(D=\operatorname{lcm}(1,2,\dots,30)\) by repeated gcd/lcm updates. They then store the exact scaled expectations \(A(n)=D\,E(n)\) in an array and maintain the running prefix sum \(\sum_{k=0}^{n-1}A(k)\).
For each \(n=1,2,\dots,30\), the implementation computes the correction term \(2^n-n-1\), combines it with the scaled prefix sum, and divides by \(n\) to obtain the next exact scaled expectation. The same recurrence is used in C++, Python, and Java; only the integer machinery differs.
After the table is built, the known values \(E(4)=13/4\) and \(E(10)=4629/40\) serve as checkpoints. The final step multiplies \(E(30)\) by \(100\), performs one exact half-up rounding by comparing the remainder with \(D/2\), and prints the decimal result with exactly two digits after the decimal point.
The dynamic program performs one pass from \(1\) to \(N\), so the recurrence evaluation is \(O(N)\) arithmetic steps. Constructing the common denominator requires \(N\) gcd/lcm updates. The implementations store the table of scaled expectations, so the memory usage is \(O(N)\), although the recurrence itself only needs a running prefix sum. For the actual target \(N=30\), all of this is tiny.
Ausgangspunkt ist eine zufällige Permutation von \(\{1,2,\dots,n\}\). Ein First-Sort-Schritt sucht den ersten Eintrag, der kleiner ist als der unmittelbar links von ihm stehende Eintrag, und verschiebt genau diesen Wert an den Anfang. Mit \(E(n)\) bezeichnen wir die erwartete Anzahl solcher Schritte, bis die Permutation aufsteigend sortiert ist. Gesucht ist \(E(30)\) als exakter Wert, der erst ganz am Ende auf zwei Nachkommastellen gerundet wird.
Die Lösung simuliert keine Permutationen. Stattdessen verwendet sie eine exakte Rekurrenz für \(E(n)\), formt diese zu einer linearen Dynamik um und speichert alle Zwischenwerte als rationale Zahlen mit gemeinsamem Nenner.
Alle drei Implementierungen beruhen auf derselben Erwartungswert-Rekurrenz. Ist diese einmal hergeleitet, reduziert sich das Problem auf zwei saubere Rechenschritte: Präfixsummen für die Effizienz und einen gemeinsamen Nenner für exakte Arithmetik.
Es gilt \(E(0)=0\). Die in den Implementierungen verwendete Analyse des First-Sort-Prozesses liefert
$$E(n)=\frac{1}{n}\sum_{k=0}^{n-1}\left(E(k)+2^k-1\right),\qquad n\ge 1.$$
Für den nichtrekursiven Anteil ergibt sich
$$\sum_{k=0}^{n-1}(2^k-1)=\left(\sum_{k=0}^{n-1}2^k\right)-n=2^n-n-1,$$
und damit die kompakte Form
$$E(n)=\frac{\sum_{k=0}^{n-1}E(k)+(2^n-n-1)}{n}.$$
Diese Identität ist der mathematische Kern der gesamten Lösung.
Definiere
$$P(n)=\sum_{k=0}^{n}E(k).$$
Dann wird die Rekurrenz zu
$$E(n)=\frac{P(n-1)+(2^n-n-1)}{n},$$
gefolgt von
$$P(n)=P(n-1)+E(n).$$
Sobald also \(P(n-1)\) bekannt ist, kostet der nächste Wert nur noch konstante Zeit. Deshalb genügt in der Implementierung ein einziger Vorwärtsdurchlauf von \(1\) bis \(30\).
Die Rekurrenz lässt sich auch teleskopisch schreiben. Aus
$$nE(n)=P(n-1)+2^n-n-1$$
und
$$(n-1)E(n-1)=P(n-2)+2^{n-1}-n,$$
sowie \(P(n-1)=P(n-2)+E(n-1)\) folgt
$$nE(n)-nE(n-1)=2^{n-1}-1.$$
Also gilt
$$E(n)=E(n-1)+\frac{2^{n-1}-1}{n}.$$
Durch Aufsummieren erhält man die geschlossene Form
$$E(n)=\sum_{j=1}^{n}\frac{2^{j-1}-1}{j}.$$
Damit sieht man sofort, welche Nenner überhaupt auftreten können.
Setze
$$D=\operatorname{lcm}(1,2,\dots,N),\qquad N=30.$$
Da die geschlossene Form nur Nenner aus \(\{1,2,\dots,n\}\) enthält, teilt jeder Nenner von \(E(n)\) den Wert \(D\). Deshalb können wir
$$A(n)=D\,E(n)$$
für jedes \(n\le N\) als ganze Zahl speichern. Multipliziert man die Rekurrenz mit \(D\), erhält man
$$A(n)=\frac{\sum_{k=0}^{n-1}A(k)+D(2^n-n-1)}{n}.$$
Der Zähler ist hier exakt \(nD\,E(n)\), also ist die Division durch \(n\) ohne Rest möglich. Damit verschwinden alle Gleitkommafehler.
Die ersten Werte ergeben sich unmittelbar:
$$E(1)=\frac{E(0)+(2^1-1-1)}{1}=0,$$
$$E(2)=\frac{E(0)+E(1)+(2^2-2-1)}{2}=\frac{1}{2},$$
$$E(3)=\frac{E(0)+E(1)+E(2)+(2^3-3-1)}{3}=\frac{\frac{1}{2}+4}{3}=\frac{3}{2},$$
$$E(4)=\frac{E(0)+E(1)+E(2)+E(3)+(2^4-4-1)}{4}=\frac{0+0+\frac{1}{2}+\frac{3}{2}+11}{4}=\frac{13}{4}.$$
Damit ist der Kontrollwert \(E(4)=13/4\) reproduziert. Führt man dieselbe Rechnung weiter, erhält man außerdem
$$E(10)=\frac{4629}{40}.$$
Die Implementierungen bauen zuerst den gemeinsamen Nenner \(D=\operatorname{lcm}(1,2,\dots,30)\) über wiederholte gcd/lcm-Aktualisierungen auf. Danach speichern sie die exakten skalierten Erwartungen \(A(n)=D\,E(n)\) in einem Feld und halten zusätzlich die laufende Präfixsumme \(\sum_{k=0}^{n-1}A(k)\).
Für jedes \(n=1,2,\dots,30\) wird der Korrekturterm \(2^n-n-1\) berechnet, mit der skalierten Präfixsumme kombiniert und durch \(n\) geteilt. So entsteht der nächste exakte Erwartungswert. Inhaltlich ist das in C++, Python und Java identisch; nur die Ganzzahlarithmetik unterscheidet sich.
Nach dem Aufbau der Tabelle dienen \(E(4)=13/4\) und \(E(10)=4629/40\) als Kontrollpunkte. Zum Schluss wird \(E(30)\) mit \(100\) multipliziert, einmal exakt kaufmännisch gerundet und anschließend mit genau zwei Nachkommastellen ausgegeben.
Die Dynamik benötigt genau einen Durchlauf von \(1\) bis \(N\), also \(O(N)\) arithmetische Schritte. Der gemeinsame Nenner erfordert zusätzlich \(N\) gcd/lcm-Aktualisierungen. Da die Implementierungen die Tabelle der skalierten Erwartungen speichern, beträgt der Speicherbedarf \(O(N)\), obwohl die Rekurrenz selbst nur eine laufende Präfixsumme braucht. Für den konkreten Zielwert \(N=30\) ist der Aufwand verschwindend klein.
Başlangıçta elimizde \(\{1,2,\dots,n\}\) kümesinin rastgele bir permütasyonu vardır. First Sort hamlesi, hemen solundaki sayıdan daha küçük olan ilk elemanı bulur ve onu listenin başına taşır. Artan sıraya ulaşmak için gereken ortalama hamle sayısını \(E(n)\) ile gösterirsek, amaç \(E(30)\) değerini tam olarak hesaplayıp sonucu yalnızca en sonda iki ondalık basamağa yuvarlamaktır.
Çözüm permütasyonları tek tek canlandırmaz. Bunun yerine \(E(n)\) için tam bir rekürans kullanır, bu bağıntıyı doğrusal zamanlı bir dinamik programa dönüştürür ve bütün ara değerleri ortak paydalı kesirler olarak saklar.
C++, Python ve Java uygulamalarının üçü de aynı beklenti reküransına dayanır. Bu kimlik elde edilince geriye iki düzenli hesap kalır: hız için önek toplamlar ve tam doğruluk için ortak payda.
\(E(0)=0\) olsun. Uygulamalarda kullanılan First Sort analizi şu ortalama biçimini verir:
$$E(n)=\frac{1}{n}\sum_{k=0}^{n-1}\left(E(k)+2^k-1\right),\qquad n\ge 1.$$
Geometrik düzeltme terimi toplanınca
$$\sum_{k=0}^{n-1}(2^k-1)=\left(\sum_{k=0}^{n-1}2^k\right)-n=2^n-n-1,$$
dolayısıyla aynı bağıntı şu kısa biçime dönüşür:
$$E(n)=\frac{\sum_{k=0}^{n-1}E(k)+(2^n-n-1)}{n}.$$
Tüm çözümün matematiksel merkezi budur.
Şunu tanımlayalım:
$$P(n)=\sum_{k=0}^{n}E(k).$$
Böylece rekürans
$$E(n)=\frac{P(n-1)+(2^n-n-1)}{n}$$
olur ve ardından
$$P(n)=P(n-1)+E(n)$$
güncellemesi gelir. Yani \(P(n-1)\) biliniyorsa bir sonraki beklenti sabit zamanda hesaplanır. Bu yüzden uygulama \(1\)'den \(30\)'a kadar tek yönlü bir geçiş yapar.
Bu reküransın teleskopik bir biçimi de vardır. Şu iki eşitliği yazalım:
$$nE(n)=P(n-1)+2^n-n-1,$$
$$(n-1)E(n-1)=P(n-2)+2^{n-1}-n.$$
Bunlara \(P(n-1)=P(n-2)+E(n-1)\) bağıntısını ekleyince
$$nE(n)-nE(n-1)=2^{n-1}-1$$
elde edilir. Buradan
$$E(n)=E(n-1)+\frac{2^{n-1}-1}{n}$$
çıkar. Artımları toplayınca kapalı toplam biçimi bulunur:
$$E(n)=\sum_{j=1}^{n}\frac{2^{j-1}-1}{j}.$$
Bu yazım, paydaların neden yalnızca \(1,2,\dots,n\) içinden geldiğini açıkça gösterir.
Şöyle tanımlayalım:
$$D=\operatorname{lcm}(1,2,\dots,N),\qquad N=30.$$
Kapalı toplamda her terimin paydası en fazla \(j\) olduğundan, her \(E(n)\) kesrinin paydası \(D\)'yi böler. Bu yüzden
$$A(n)=D\,E(n)$$
değerini tamsayı olarak saklayabiliriz. Rekürans \(D\) ile çarpılınca
$$A(n)=\frac{\sum_{k=0}^{n-1}A(k)+D(2^n-n-1)}{n}$$
olur. Buradaki pay tam olarak \(nD\,E(n)\) olduğundan, \(n\)'e bölüm kalansızdır. Böylece kayan nokta hatası tamamen ortadan kalkar.
İlk birkaç değer doğrudan hesaplanabilir:
$$E(1)=\frac{E(0)+(2^1-1-1)}{1}=0,$$
$$E(2)=\frac{E(0)+E(1)+(2^2-2-1)}{2}=\frac{1}{2},$$
$$E(3)=\frac{E(0)+E(1)+E(2)+(2^3-3-1)}{3}=\frac{\frac{1}{2}+4}{3}=\frac{3}{2},$$
$$E(4)=\frac{E(0)+E(1)+E(2)+E(3)+(2^4-4-1)}{4}=\frac{0+0+\frac{1}{2}+\frac{3}{2}+11}{4}=\frac{13}{4}.$$
Böylece \(E(4)=13/4\) kontrol değeri yeniden elde edilir. Aynı süreç biraz daha sürdürüldüğünde
$$E(10)=\frac{4629}{40}$$
sonucu da çıkar.
Uygulamalar önce tekrar tekrar gcd/lcm güncelleyerek ortak paydayı \(D=\operatorname{lcm}(1,2,\dots,30)\) olarak kurar. Daha sonra tam ölçeklenmiş beklentileri \(A(n)=D\,E(n)\) bir dizide tutar ve \(\sum_{k=0}^{n-1}A(k)\) önek toplamını canlı olarak günceller.
Her \(n=1,2,\dots,30\) için düzeltme terimi \(2^n-n-1\) hesaplanır, ölçeklenmiş önek toplamla birleştirilir ve \(n\)'e bölünerek bir sonraki tam beklenti bulunur. C++, Python ve Java uygulamalarının mantığı aynıdır; değişen tek şey tamsayı aritmetiğinin dili nasıl kullandığıdır.
Tablo tamamlandıktan sonra \(E(4)=13/4\) ve \(E(10)=4629/40\) değerleri kontrol noktası olarak kullanılır. Son adımda \(E(30)\) önce \(100\) ile çarpılır, kalan değere bakılarak tek seferlik tam yuvarlama yapılır ve sonuç iki ondalık basamakla yazdırılır.
Dinamik program \(1\)'den \(N\)'e kadar yalnızca bir kez ilerlediği için rekürans değerlendirmesi \(O(N)\) aritmetik adım gerektirir. Ortak paydanın kurulması için buna ek olarak \(N\) tane gcd/lcm güncellemesi vardır. Uygulamalar ölçeklenmiş beklenti tablosunu tuttuğundan bellek kullanımı \(O(N)\)'dir; oysa reküransın kendisi yalnızca bir önek toplam ister. Gerçek hedef olan \(N=30\) için bu maliyetlerin hepsi çok küçüktür.
Partimos de una permutación aleatoria de \(\{1,2,\dots,n\}\). Un movimiento de First Sort localiza la primera entrada que es menor que la entrada inmediatamente situada a su izquierda y la mueve al frente. Si \(E(n)\) denota el número esperado de movimientos necesarios para llegar a la permutación creciente, el objetivo es evaluar \(E(30)\) exactamente y redondear solo al final a dos cifras decimales.
La solución no simula permutaciones. En su lugar usa una recurrencia exacta para \(E(n)\), la convierte en una programación dinámica lineal y mantiene todos los valores intermedios como fracciones exactas con un denominador común.
Las implementaciones en C++, Python y Java se apoyan en la misma recurrencia para la esperanza. Una vez fijada esa identidad, el resto del trabajo consiste en dos ideas simples: sumas prefijo para acelerar y un denominador común para conservar exactitud total.
Tomamos \(E(0)=0\). El análisis de First Sort utilizado por las implementaciones produce la forma promediada
$$E(n)=\frac{1}{n}\sum_{k=0}^{n-1}\left(E(k)+2^k-1\right),\qquad n\ge 1.$$
Al sumar la corrección geométrica obtenemos
$$\sum_{k=0}^{n-1}(2^k-1)=\left(\sum_{k=0}^{n-1}2^k\right)-n=2^n-n-1,$$
de modo que la misma relación queda
$$E(n)=\frac{\sum_{k=0}^{n-1}E(k)+(2^n-n-1)}{n}.$$
Esta es la identidad central de toda la solución.
Definimos
$$P(n)=\sum_{k=0}^{n}E(k).$$
Entonces la recurrencia pasa a ser
$$E(n)=\frac{P(n-1)+(2^n-n-1)}{n},$$
seguida de la actualización
$$P(n)=P(n-1)+E(n).$$
Por tanto, una vez conocido \(P(n-1)\), el siguiente valor se obtiene en tiempo constante. Esa es la razón por la que las implementaciones recorren \(n=1,2,\dots,30\) en una sola pasada.
La recurrencia admite además una forma telescópica. A partir de
$$nE(n)=P(n-1)+2^n-n-1$$
y
$$(n-1)E(n-1)=P(n-2)+2^{n-1}-n,$$
junto con \(P(n-1)=P(n-2)+E(n-1)\), se obtiene
$$nE(n)-nE(n-1)=2^{n-1}-1.$$
Así pues,
$$E(n)=E(n-1)+\frac{2^{n-1}-1}{n}.$$
Al sumar estos incrementos desde \(1\) hasta \(n\) resulta la forma cerrada
$$E(n)=\sum_{j=1}^{n}\frac{2^{j-1}-1}{j}.$$
Esta expresión deja claro por qué los denominadores posibles están contenidos en \(\{1,2,\dots,n\}\).
Sea
$$D=\operatorname{lcm}(1,2,\dots,N),\qquad N=30.$$
Como la forma cerrada es una suma de términos con denominadores \(1,2,\dots,n\), todo \(E(n)\) tiene denominador divisor de \(D\). Por eso podemos almacenar
$$A(n)=D\,E(n)$$
como entero para todo \(n\le N\). Al multiplicar la recurrencia por \(D\), queda
$$A(n)=\frac{\sum_{k=0}^{n-1}A(k)+D(2^n-n-1)}{n}.$$
El numerador es exactamente \(nD\,E(n)\), de modo que la división por \(n\) es exacta. Con ello desaparece cualquier error de punto flotante.
Los primeros valores salen enseguida:
$$E(1)=\frac{E(0)+(2^1-1-1)}{1}=0,$$
$$E(2)=\frac{E(0)+E(1)+(2^2-2-1)}{2}=\frac{1}{2},$$
$$E(3)=\frac{E(0)+E(1)+E(2)+(2^3-3-1)}{3}=\frac{\frac{1}{2}+4}{3}=\frac{3}{2},$$
$$E(4)=\frac{E(0)+E(1)+E(2)+E(3)+(2^4-4-1)}{4}=\frac{0+0+\frac{1}{2}+\frac{3}{2}+11}{4}=\frac{13}{4}.$$
Con esto se recupera el punto de control \(E(4)=13/4\). Si se continúa el mismo proceso, también se obtiene
$$E(10)=\frac{4629}{40}.$$
Las implementaciones construyen primero el denominador común \(D=\operatorname{lcm}(1,2,\dots,30)\) mediante actualizaciones sucesivas de gcd/lcm. Después guardan los valores exactos escalados \(A(n)=D\,E(n)\) en una tabla y mantienen la suma prefijo \(\sum_{k=0}^{n-1}A(k)\).
Para cada \(n=1,2,\dots,30\), la implementación calcula el término correctivo \(2^n-n-1\), lo combina con la suma prefijo escalada y divide por \(n\) para obtener la siguiente esperanza exacta. El esquema es el mismo en C++, Python y Java; solo cambia la forma concreta de manejar enteros grandes.
Una vez construida la tabla, los valores \(E(4)=13/4\) y \(E(10)=4629/40\) sirven como comprobaciones. Al final se multiplica \(E(30)\) por \(100\), se hace un único redondeo exacto comparando el resto con medio denominador y se imprime el decimal con exactamente dos cifras.
La programación dinámica realiza una sola pasada desde \(1\) hasta \(N\), así que la evaluación de la recurrencia cuesta \(O(N)\) pasos aritméticos. La construcción del denominador común añade \(N\) operaciones gcd/lcm. Como las implementaciones almacenan la tabla de expectativas escaladas, el uso de memoria es \(O(N)\), aunque matemáticamente la recurrencia solo necesita una suma prefijo en curso. Para el caso real \(N=30\), el coste es muy pequeño.
从 \(\{1,2,\dots,n\}\) 的一个随机排列出发。一次 First Sort 操作会找到第一个“比它左边紧邻元素更小”的数，并把这个数移动到最前面。记 \(E(n)\) 为把随机排列变成升序排列所需操作次数的期望值，题目的目标就是精确求出 \(E(30)\)，最后再把结果四舍五入到两位小数。
解法并不去枚举或模拟全部排列，而是直接使用一个关于 \(E(n)\) 的精确递推式。然后把这个递推式改写成线性时间的动态计算，并且始终用精确有理数而不是浮点数来保存中间结果。
C++、Python 和 Java 三份实现都建立在同一个期望递推之上。只要这个递推式确定下来，剩余工作就分成两部分：用前缀和把求和过程加速到线性时间，用一个公共分母保证全过程完全精确。
先规定 \(E(0)=0\)。实现所依据的 First Sort 分析给出下面这个平均形式：
$$E(n)=\frac{1}{n}\sum_{k=0}^{n-1}\left(E(k)+2^k-1\right),\qquad n\ge 1.$$
其中非递归部分可以直接求和：
$$\sum_{k=0}^{n-1}(2^k-1)=\left(\sum_{k=0}^{n-1}2^k\right)-n=2^n-n-1.$$
因此同一个递推式也可以改写成更紧凑的形式：
$$E(n)=\frac{\sum_{k=0}^{n-1}E(k)+(2^n-n-1)}{n}.$$
这就是整道题最核心的数学公式。
定义
$$P(n)=\sum_{k=0}^{n}E(k).$$
那么递推式就变成
$$E(n)=\frac{P(n-1)+(2^n-n-1)}{n},$$
然后再更新
$$P(n)=P(n-1)+E(n).$$
这样一来，只要知道 \(P(n-1)\)，下一个 \(E(n)\) 就能在常数时间内得到。所以程序只需从 \(1\) 到 \(30\) 做一遍顺序扫描即可。
这个递推式还可以化成非常有用的增量形式。由
$$nE(n)=P(n-1)+2^n-n-1$$
以及
$$(n-1)E(n-1)=P(n-2)+2^{n-1}-n,$$
再结合 \(P(n-1)=P(n-2)+E(n-1)\)，可以得到
$$nE(n)-nE(n-1)=2^{n-1}-1.$$
于是
$$E(n)=E(n-1)+\frac{2^{n-1}-1}{n}.$$
把这些增量从 \(1\) 一直累加到 \(n\)，便得到闭式求和：
$$E(n)=\sum_{j=1}^{n}\frac{2^{j-1}-1}{j}.$$
这个公式有一个很重要的意义：它直接说明了所有分母都只会来自 \(1,2,\dots,n\)。
令
$$D=\operatorname{lcm}(1,2,\dots,N),\qquad N=30.$$
由于闭式中的每一项分母都是某个 \(j\)，所以每个 \(E(n)\) 的分母都整除 \(D\)。因此可以把
$$A(n)=D\,E(n)$$
作为整数来保存。把递推式整体乘上 \(D\) 后，得到
$$A(n)=\frac{\sum_{k=0}^{n-1}A(k)+D(2^n-n-1)}{n}.$$
这里的分子正好就是 \(nD\,E(n)\)，所以除以 \(n\) 一定没有余数。这样做的好处是整个过程完全不需要浮点数，也就不会积累任何舍入误差。
前几个值可以直接手算出来：
$$E(1)=\frac{E(0)+(2^1-1-1)}{1}=0,$$
$$E(2)=\frac{E(0)+E(1)+(2^2-2-1)}{2}=\frac{1}{2},$$
$$E(3)=\frac{E(0)+E(1)+E(2)+(2^3-3-1)}{3}=\frac{\frac{1}{2}+4}{3}=\frac{3}{2},$$
$$E(4)=\frac{E(0)+E(1)+E(2)+E(3)+(2^4-4-1)}{4}=\frac{0+0+\frac{1}{2}+\frac{3}{2}+11}{4}=\frac{13}{4}.$$
这就重现了校验值 \(E(4)=13/4\)。继续按同样方法往后推，还会得到第二个校验值
$$E(10)=\frac{4629}{40}.$$
实现首先通过连续的 gcd/lcm 更新构造出公共分母 \(D=\operatorname{lcm}(1,2,\dots,30)\)。随后把精确缩放后的期望值 \(A(n)=D\,E(n)\) 保存在数组中，并维护运行中的前缀和 \(\sum_{k=0}^{n-1}A(k)\)。
对于每个 \(n=1,2,\dots,30\)，程序都先算出修正项 \(2^n-n-1\)，再与缩放后的前缀和组合起来，最后除以 \(n\) 得到下一个精确值。C++、Python 和 Java 的思路完全一致，区别只在于各自采用的整数类型不同。
整张表求出之后，\(E(4)=13/4\) 和 \(E(10)=4629/40\) 被用作校验点。最后一步是把 \(E(30)\) 乘以 \(100\)，通过比较余数与半个分母的大小来做一次精确四舍五入，并以固定两位小数输出结果。
动态计算只需要从 \(1\) 到 \(N\) 顺序走一遍，因此递推本身是 \(O(N)\) 次算术操作。构造公共分母额外需要 \(N\) 次 gcd/lcm 更新。由于实现保存了全部缩放后的期望值表，所以空间复杂度是 \(O(N)\)；如果只从数学递推的角度看，其实只需要一个运行中的前缀和。对于实际目标 \(N=30\)，这些开销都非常小。
Рассматривается случайная перестановка множества \(\{1,2,\dots,n\}\). Один шаг First Sort находит первый элемент, который меньше элемента непосредственно слева от него, и переносит этот элемент в начало последовательности. Если \(E(n)\) обозначает математическое ожидание числа шагов до получения возрастающей перестановки, то требуется вычислить \(E(30)\) точно и округлить результат только в самом конце до двух знаков после запятой.
Полного перебора или моделирования здесь нет. Решение использует точную рекуррентную формулу для \(E(n)\), превращает ее в линейный динамический расчет и хранит все промежуточные значения как точные рациональные числа с общим знаменателем.
Во всех трех реализациях, на C++, Python и Java, используется одна и та же формула для ожидания. После этого остаются две технические идеи: префиксные суммы для ускорения и общий знаменатель для полной точности.
Положим \(E(0)=0\). Анализ First Sort, на который опираются реализации, дает усредненную формулу
$$E(n)=\frac{1}{n}\sum_{k=0}^{n-1}\left(E(k)+2^k-1\right),\qquad n\ge 1.$$
Геометрическая поправка суммируется явно:
$$\sum_{k=0}^{n-1}(2^k-1)=\left(\sum_{k=0}^{n-1}2^k\right)-n=2^n-n-1,$$
поэтому ту же формулу можно записать короче:
$$E(n)=\frac{\sum_{k=0}^{n-1}E(k)+(2^n-n-1)}{n}.$$
Это и есть центральное математическое тождество решения.
Определим
$$P(n)=\sum_{k=0}^{n}E(k).$$
Тогда рекурсия переписывается как
$$E(n)=\frac{P(n-1)+(2^n-n-1)}{n},$$
после чего выполняется обновление
$$P(n)=P(n-1)+E(n).$$
То есть после знания \(P(n-1)\) следующий член находится за \(O(1)\). Поэтому программы просто делают один проход по \(n=1,2,\dots,30\).
У рекурсии есть полезная телескопическая форма. Из равенств
$$nE(n)=P(n-1)+2^n-n-1$$
и
$$(n-1)E(n-1)=P(n-2)+2^{n-1}-n,$$
а также из соотношения \(P(n-1)=P(n-2)+E(n-1)\), получаем
$$nE(n)-nE(n-1)=2^{n-1}-1.$$
Следовательно,
$$E(n)=E(n-1)+\frac{2^{n-1}-1}{n}.$$
Суммируя эти приращения от \(1\) до \(n\), приходим к замкнутой форме
$$E(n)=\sum_{j=1}^{n}\frac{2^{j-1}-1}{j}.$$
Эта запись сразу объясняет, почему все знаменатели берутся только из набора \(1,2,\dots,n\).
Положим
$$D=\operatorname{lcm}(1,2,\dots,N),\qquad N=30.$$
Так как замкнутая форма состоит из слагаемых со знаменателями \(1,2,\dots,n\), знаменатель любого \(E(n)\) делит \(D\). Поэтому удобно хранить
$$A(n)=D\,E(n)$$
как целое число. Если умножить рекурсию на \(D\), получится
$$A(n)=\frac{\sum_{k=0}^{n-1}A(k)+D(2^n-n-1)}{n}.$$
Числитель здесь равен \(nD\,E(n)\), так что деление на \(n\) выполняется без остатка. Благодаря этому во всем вычислении нет никаких ошибок округления.
Первые значения считаются напрямую:
$$E(1)=\frac{E(0)+(2^1-1-1)}{1}=0,$$
$$E(2)=\frac{E(0)+E(1)+(2^2-2-1)}{2}=\frac{1}{2},$$
$$E(3)=\frac{E(0)+E(1)+E(2)+(2^3-3-1)}{3}=\frac{\frac{1}{2}+4}{3}=\frac{3}{2},$$
$$E(4)=\frac{E(0)+E(1)+E(2)+E(3)+(2^4-4-1)}{4}=\frac{0+0+\frac{1}{2}+\frac{3}{2}+11}{4}=\frac{13}{4}.$$
Так восстанавливается контрольное значение \(E(4)=13/4\). Продолжая расчет тем же способом, получаем и вторую проверку:
$$E(10)=\frac{4629}{40}.$$
Сначала реализации строят общий знаменатель \(D=\operatorname{lcm}(1,2,\dots,30)\) при помощи последовательных операций gcd/lcm. Затем они хранят точные масштабированные ожидания \(A(n)=D\,E(n)\) в таблице и поддерживают текущую префиксную сумму \(\sum_{k=0}^{n-1}A(k)\).
Для каждого \(n=1,2,\dots,30\) вычисляется поправка \(2^n-n-1\), она объединяется с масштабированной префиксной суммой, после чего выполняется деление на \(n\) и получается следующий точный член. Во всех трех языках логика одинаковая; отличается только конкретный механизм целочисленной арифметики.
После построения таблицы значения \(E(4)=13/4\) и \(E(10)=4629/40\) используются как контрольные точки. Финальный этап умножает \(E(30)\) на \(100\), делает одно точное округление по остатку и печатает результат с двумя знаками после запятой.
Динамический расчет выполняет один проход от \(1\) до \(N\), то есть требует \(O(N)\) арифметических шагов. Построение общего знаменателя добавляет еще \(N\) операций gcd/lcm. Так как реализации сохраняют таблицу масштабированных ожиданий, память составляет \(O(N)\), хотя сама рекурсия в сущности требует только одну текущую префиксную сумму. Для реального значения \(N=30\) вычисление совсем невелико.
نبدأ بتبديل عشوائي للمجموعة \(\{1,2,\dots,n\}\). في خطوة واحدة من First Sort نبحث عن أول عنصر يكون أصغر من العنصر الملاصق له على اليسار، ثم ننقل ذلك العنصر إلى مقدمة القائمة. إذا رمزنا إلى العدد المتوقع للخطوات اللازمة للوصول إلى الترتيب التصاعدي بالرمز \(E(n)\)، فالمطلوب هو حساب \(E(30)\) بدقة تامة ثم تقريب النتيجة في النهاية فقط إلى منزلتين عشريتين.
الحل لا يعتمد على محاكاة جميع التبديلات. بدلا من ذلك يستعمل علاقة عودية دقيقة لـ \(E(n)\)، ثم يحولها إلى حساب ديناميكي خطي، ويحفظ كل القيم الوسيطة على هيئة كسور دقيقة ذات مقام مشترك.
تعتمد تطبيقات C++ وPython وJava كلها على العلاقة نفسها الخاصة بالقيمة المتوقعة. وبعد تثبيت هذه العلاقة، يبقى عملان واضحان: استخدام مجموعات بادئة لتسريع الحساب، واستخدام مقام مشترك للحفاظ على الدقة الكاملة.
نأخذ \(E(0)=0\). والتحليل المستخدم في التنفيذات يعطي الصيغة المتوسطة التالية:
$$E(n)=\frac{1}{n}\sum_{k=0}^{n-1}\left(E(k)+2^k-1\right),\qquad n\ge 1.$$
أما الجزء الهندسي غير العودي فيجمع إلى
$$\sum_{k=0}^{n-1}(2^k-1)=\left(\sum_{k=0}^{n-1}2^k\right)-n=2^n-n-1,$$
ومن ثم يمكن كتابة العلاقة نفسها على الصورة المضغوطة
$$E(n)=\frac{\sum_{k=0}^{n-1}E(k)+(2^n-n-1)}{n}.$$
هذه هي الهوية الرياضية الأساسية التي يقوم عليها الحل كله.
نعرف
$$P(n)=\sum_{k=0}^{n}E(k).$$
فتصبح العلاقة
$$E(n)=\frac{P(n-1)+(2^n-n-1)}{n},$$
ثم نحدثها بواسطة
$$P(n)=P(n-1)+E(n).$$
وهكذا، متى ما عرفت \(P(n-1)\)، أمكن إيجاد \(E(n)\) التالي بكلفة ثابتة. ولهذا تكتفي التنفيذات بمرور واحد من \(1\) إلى \(30\).
للعلاقة العودية صيغة تلسكوبية مفيدة أيضا. من
$$nE(n)=P(n-1)+2^n-n-1$$
و
$$(n-1)E(n-1)=P(n-2)+2^{n-1}-n,$$
ومع استخدام \(P(n-1)=P(n-2)+E(n-1)\)، نحصل على
$$nE(n)-nE(n-1)=2^{n-1}-1.$$
وبالتالي
$$E(n)=E(n-1)+\frac{2^{n-1}-1}{n}.$$
وبجمع هذه الزيادات من \(1\) حتى \(n\) نحصل على الصيغة المغلقة
$$E(n)=\sum_{j=1}^{n}\frac{2^{j-1}-1}{j}.$$
هذه الصيغة تكشف مباشرة لماذا تكون المقامات الممكنة محصورة في \(1,2,\dots,n\).
لنأخذ
$$D=\operatorname{lcm}(1,2,\dots,N),\qquad N=30.$$
وبما أن الصيغة المغلقة تتكون من حدود مقاماتها \(1,2,\dots,n\)، فإن مقام أي قيمة \(E(n)\) يقسم \(D\). لذلك يمكن تخزين
$$A(n)=D\,E(n)$$
كعدد صحيح. وبعد ضرب العلاقة العودية في \(D\) تصبح
$$A(n)=\frac{\sum_{k=0}^{n-1}A(k)+D(2^n-n-1)}{n}.$$
البسط هنا يساوي تماما \(nD\,E(n)\)، ولذلك تكون القسمة على \(n\) صحيحة بلا أي باقي. وهكذا نتجنب أخطاء الفاصلة العائمة تماما.
القيم الأولى تظهر مباشرة:
$$E(1)=\frac{E(0)+(2^1-1-1)}{1}=0,$$
$$E(2)=\frac{E(0)+E(1)+(2^2-2-1)}{2}=\frac{1}{2},$$
$$E(3)=\frac{E(0)+E(1)+E(2)+(2^3-3-1)}{3}=\frac{\frac{1}{2}+4}{3}=\frac{3}{2},$$
$$E(4)=\frac{E(0)+E(1)+E(2)+E(3)+(2^4-4-1)}{4}=\frac{0+0+\frac{1}{2}+\frac{3}{2}+11}{4}=\frac{13}{4}.$$
وبذلك نستعيد نقطة التحقق \(E(4)=13/4\). وإذا واصلنا الحساب بالطريقة نفسها نحصل أيضا على
$$E(10)=\frac{4629}{40}.$$
تبني التنفيذات أولا المقام المشترك \(D=\operatorname{lcm}(1,2,\dots,30)\) عبر تحديثات متتالية لـ gcd/lcm. ثم تخزن القيم الدقيقة المضروبة في \(D\)، أي \(A(n)=D\,E(n)\)، في جدول، وتحافظ في الوقت نفسه على مجموع البادئة \(\sum_{k=0}^{n-1}A(k)\).
لكل \(n=1,2,\dots,30\) تحسب الشيفرة حد التصحيح \(2^n-n-1\)، وتدمجه مع مجموع البادئة المضروب، ثم تقسم على \(n\) للحصول على القيمة الدقيقة التالية. الفكرة الحسابية واحدة في C++ وPython وJava، وما يختلف هو نوع الأعداد الصحيحة الذي يستخدمه كل تنفيذ.
بعد اكتمال الجدول تستعمل القيمتان \(E(4)=13/4\) و\(E(10)=4629/40\) كنقطتي تحقق. وفي النهاية تضرب \(E(30)\) في \(100\)، وتنفذ عملية تقريب دقيقة واحدة بمقارنة الباقي مع نصف المقام، ثم تطبع الناتج بمنزلتين عشريتين بالضبط.
ينفذ الحساب الديناميكي مرورا واحدا فقط من \(1\) حتى \(N\)، لذلك فإن تقييم العلاقة العودية يحتاج إلى \(O(N)\) خطوة حسابية. أما بناء المقام المشترك فيضيف \(N\) عملية gcd/lcm. وبما أن التنفيذات تحتفظ بجدول القيم المضروبة، فالاستهلاك المكاني هو \(O(N)\)، مع أن العلاقة نفسها لا تحتاج في جوهرها إلا إلى مجموع بادئة جار. وبالنسبة إلى \(N=30\) فكل ذلك صغير جدا عمليا.