Дочка принесла из школы задачу:
Попросила помочь решить. Под катом мое решение:
using System;
namespace Task1 {
class Program {
static void Main(string[] args) {
var n = Int32.Parse(args[0]);
var count = Digit(true, 1, n - 1)
+ Digit(false, 1, n - 1);
Console.WriteLine("Numbers count: {0}", count);
}
static int Digit(bool current, int count, int rest) {
if (count == 3) return 0;
if (rest > 0) {
return Digit(current, count + 1, rest - 1)
+ Digit(!current, 1, rest - 1);
} else
return 1;
}
}
}
Простой рекурсивный перебор.
В ограничения укладываюсь, но кажется мне что эту задачу можно решить математически.
Я прав?
Коментарі
где F(n) - n-ое число фибоначчи
заметим, что все числа с окончаниями 95 и 59 мы уже получили. (действительно, если в n-1 значное число X мжно дописать скажем 5, то получим валидное n-1 значное число Y, к которому мы уже приписали 9. по-этому X + 59 == Y + 9)
получаем f(n) = f(n-1) + f(n-2),
что соответствует F(n)×2 в нашем случае.
Введем f(d)(k) - количество чисел длины k, которые заканчиваются цифрой d и удовлетворяют условию задачи.
Число, которые заканчивается на 5, может заканчиваться одной "5"-кой или двумя, а перед ними идет обязательно "9"-ка. Это выражается формулой:
f(5)(k) = f(9)(k-1) + f(9)(k-2)
f(5)(1) = 1, f(5)(2) = 2.
Аналогично для девяток.
Конечный ответ равен f(5)(n) + f(9)(n)
Но из формулы видно, что вычисление f никак не зависит от первого индекса, поэтому его просто можно выкинуть (кстати, в твоей программке параметр `current` функции `Digit` тоже можно выкинуть аналогичным образом).
После этого и получаем f(k) = f(k-1) + f(k-2). С учетом начальных условий f(n) = F(n+1) (числа Фибоначчи смещены на 1 индекс).
И соответственно конечный ответ F(n+1) * 2.