Average loop length: Difference between revisions
Content added Content deleted
Alextretyak (talk | contribs) (Added 11l) |
No edit summary |
||
Line 314: | Line 314: | ||
19 5.1479 5.1522 -0.084% |
19 5.1479 5.1522 -0.084% |
||
20 5.2957 5.2936 0.040% |
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> |
</pre> |
||