Anonymous user
Average loop length: Difference between revisions
no edit summary
Alextretyak (talk | contribs) (Added 11l) |
No edit summary |
||
Line 314:
19 5.1479 5.1522 -0.084%
20 5.2957 5.2936 0.040%
</pre>
=={{header|C sharp|C#}}==
{{trans|Java}}
<lang csharp>public class AverageLoopLength {
private static int N = 100000;
private static double analytical(int n) {
double[] factorial = new double[n + 1];
double[] powers = new double[n + 1];
powers[0] = 1.0;
factorial[0] = 1.0;
for (int i = 1; i <= n; i++) {
factorial[i] = factorial[i - 1] * i;
powers[i] = powers[i - 1] * n;
}
double sum = 0;
for (int i = 1; i <= n; i++) {
sum += factorial[n] / factorial[n - i] / powers[i];
}
return sum;
}
private static double average(int n) {
Random rnd = new Random();
double sum = 0.0;
for (int a = 0; a < N; a++) {
int[] random = new int[n];
for (int i = 0; i < n; i++) {
random[i] = rnd.Next(n);
}
var seen = new HashSet<double>(n);
int current = 0;
int length = 0;
while (seen.Add(current)) {
length++;
current = random[current];
}
sum += length;
}
return sum / N;
}
public static void Main(string[] args) {
Console.WriteLine(" N average analytical (error)");
Console.WriteLine("=== ========= ============ =========");
for (int i = 1; i <= 20; i++) {
var average = AverageLoopLength.average(i);
var analytical = AverageLoopLength.analytical(i);
Console.WriteLine("{0,3} {1,10:N4} {2,13:N4} {3,8:N2}%", i, average, analytical, (analytical - average) / analytical * 100);
}
}
}
</lang>
{{out}}
<pre>
N average analytical (error)
=== ========= ============ =========
1 1.0000 1.0000 0.00%
2 1.4999 1.5000 0.01%
3 1.8860 1.8889 0.15%
4 2.2235 2.2188 -0.22%
5 2.5115 2.5104 -0.04%
6 2.7793 2.7747 -0.17%
7 3.0149 3.0181 0.11%
8 3.2457 3.2450 -0.02%
9 3.4559 3.4583 0.07%
10 3.6558 3.6602 0.12%
11 3.8428 3.8524 0.25%
12 4.0270 4.0361 0.22%
13 4.2111 4.2123 0.03%
14 4.3766 4.3820 0.12%
15 4.5535 4.5458 -0.17%
16 4.6989 4.7043 0.11%
17 4.8590 4.8579 -0.02%
18 4.9972 5.0071 0.20%
19 5.1542 5.1522 -0.04%
20 5.3024 5.2936 -0.17%
</pre>
| |||