64 lines
2.4 KiB
C#
64 lines
2.4 KiB
C#
using System;
|
|
using System.Collections.Generic;
|
|
|
|
namespace HofstadterQSequence
|
|
{
|
|
class Program
|
|
{
|
|
// Initialize the dictionary with the first two indices filled.
|
|
private static readonly Dictionary<int, int> QList = new Dictionary<int, int>
|
|
{
|
|
{1, 1},
|
|
{2, 1}
|
|
};
|
|
|
|
private static void Main()
|
|
{
|
|
int lessThanLast = 0;
|
|
/* Initialize our variable that holds the number of times
|
|
* a member of the sequence was less than its preceding term. */
|
|
|
|
for (int n = 1; n <= 100000; n++)
|
|
{
|
|
int q = Q(n); // Get Q(n).
|
|
|
|
if (n > 1 && QList[n - 1] > q) // If Q(n) is less than Q(n - 1),
|
|
lessThanLast++; // then add to the counter.
|
|
|
|
if (n > 10 && n != 1000) continue; /* If n is greater than 10 and not 1000,
|
|
* the rest of the code in the loop does not apply,
|
|
* and it will be skipped. */
|
|
|
|
if (!Confirm(n, q)) // Confirm Q(n) is correct.
|
|
throw new Exception(string.Format("Invalid result: Q({0}) != {1}", n, q));
|
|
|
|
Console.WriteLine("Q({0}) = {1}", n, q); // Write Q(n) to the console.
|
|
}
|
|
|
|
Console.WriteLine("Number of times a member of the sequence was less than its preceding term: {0}.",
|
|
lessThanLast);
|
|
}
|
|
|
|
private static bool Confirm(int n, int value)
|
|
{
|
|
if (n <= 10)
|
|
return new[] {1, 1, 2, 3, 3, 4, 5, 5, 6, 6}[n - 1] == value;
|
|
if (n == 1000)
|
|
return 502 == value;
|
|
throw new ArgumentException("Invalid index.", "n");
|
|
}
|
|
|
|
private static int Q(int n)
|
|
{
|
|
int q;
|
|
|
|
if (!QList.TryGetValue(n, out q)) // Try to get Q(n) from the dictionary.
|
|
{
|
|
q = Q(n - Q(n - 1)) + Q(n - Q(n - 2)); // If it's not available, then calculate it.
|
|
QList.Add(n, q); // Add it to the dictionary.
|
|
}
|
|
|
|
return q;
|
|
}
|
|
}
|
|
}
|