Посчитать количество красивых чисел
На просторах интернета нашел интересную задачу:
Нужно посчитать кол-во красивых (сумма первых шести чисел равна сумме шести последних цифр) 13-значных чисел в 13-значной системе счисления, например: число 0055237050A00 - красивое, так как 0+0+5+5+2+3 = 0+5+0+A+0+0, а число 1234AB988BABA - некрасивое, так как 1+2+3+4+A+B != 8+8+B+A+B+A
Я решил написать класс для этого, который будет хранить число в преобразованном в массив виде:
struct Number
{
explicit Number(size_t number);
Number& operator ++ ();
Number& operator ++ (int);
bool is_beautiful() const;
private:
std::array<uint8_t, 13> m_digits;
};
И потом в цикле проверять все числа в интервале:
Number number{ 0u };
size_t count_numbers = 0u;
for (size_t i = 0u; i < std::pow(13,13); ++i) {
count_numbers |= (number++).is_beautiful();
}
Но хотел спросить насколько это оптимальное решение, может быть можно как-то обойтись без массива с использованием арифметики? Если да, то как тогда это можно реализовать?
Ответы (4 шт):
Ну проверять все числа в большом интервале - не наш метод...
Подумайте вот о чём: количество сумм 6 цифр невелико - всего 79 - от 0 до 78. Если мы знаем, что слева сумма k может быть в F(k) вариантах, то справа то же самое, и существует F(k)*F(k) красивых чисел с такой суммой. Выполнив суммирование для всех k в указанном диапазоне, получим общее количество красивых чисел (если умножим полученную сумму на 13 для учёта центральной цифры, которая может быть любой)
N = 13 * (F(0)*F(0)+F(1)*F(1)+...F(78)*F(78))
F(k) можно найти математически, но в простом случае достаточно перебрать все 4.8 миллиона чисел из 6 знаков, для каждого считать сумму цифр, и увеличивать соответствующий счётчик в массиве из 79 целых чисел.
По сути у вас задача о количестве счастливых билетов длиной 12 в 13-ричной системе счисления, умноженное на 13 (средняя цифра).
Функция для числа билетов произвольной длины в произвольной системе счисления выглядит так:
unsigned long long happy(unsigned int n, unsigned int base)
{
if (n%2 || n < 2 || base < 2) throw runtime_error("Wrong data");
auto N = [](unsigned int n, unsigned int k,
unsigned int base, auto&&N)
{
if (n == 1) return (unsigned long long)(k < base);
unsigned long long s = 0;
for(unsigned int l = 0; l < base; ++l) s += N(n-1,k-l,base,N);
return s;
};
unsigned long long s = 0;
for(unsigned int k = 0; k <= (base-1)*n/2; ++k)
{
auto m = N(n/2,k,base,N);
s += m*m;
}
return s;
}
Теперь, чтоб посчитать все счастливые билеты в задании, надо написать
cout << 13*happy(12,13) << endl;
P.S. Алгоритм для написания функции взят из набора очень интересных статей по адресу: http://www.ega-math.narod.ru/Quant/Tickets.htm
P.P.S. Результат посчитан тут, и он равен 9203637295151.
Сделали на c#
Количество сумм 6 цифр не 79, а 72.
Не забываем умножить еще на 13, так как по середине есть еще одно число.
Результат равен 9203637295151
public static void Main(string[] args)
{
char[] numbers = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C' };
//char[] numbers = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };
var maxSum = Sum("CCCCCC");
//var maxSum = Sum("9999");
//индекс массива - сумма чисел, значение ячейки - количество комбинаций
long[] maxSums = new long[maxSum + 1];
var count = numbers.Count();
for (int a = 0; a < count; a++)
{
for (int b = 0; b < count; b++)
{
for (int c = 0; c < count; c++)
{
for (int d = 0; d < count; d++)
{
for (int e = 0; e < count; e++)
{
for (int f = 0; f < count; f++)
{
var index = a + b + c + d + e + f;
++maxSums[index];
}
}
}
}
}
}
long result = 0;
var x = Sum("CCCCCC");
//var x = Sum("9999");
for (int i = 0; i < maxSums.Count(); ++i)
{
result += maxSums[i] * maxSums[i];
}
Console.WriteLine($"Actual result:\n{result}");
//Умножаем еще на 1, потому что посередине есть цифра, которая не учитывается при подсчёте комбинаций
Console.WriteLine($"Actual result * 13:\n{result * 13}");
//для 13 значных 13-теричных счастливых билетиков получаем 46767020079 счастливых билетиков
}
public static int Sum(string str)
{
int x = 0;
foreach (char c in str)
{
x += ConvertToInt13(c.ToString());
}
return x;
}
public static int ConvertToInt13(string str)
{
if (str == "A")
{
return 10;
}
if (str == "B")
{
return 11;
}
if (str == "C")
{
return 12;
}
return int.Parse(str);
}
Репо выложили здесь - https://github.com/mathewsun/HappyTickets13
Решал задачку на C# и уже после решения нашел это обсуждение. Хотел сначала выразить аналитически, но увы... Как следствие пошел по пути динамического программирования))) Сначала через рекурсию, но переписал на нерекурсивный вариант.
long GetLuckyTicketCount(int digitsCount, int numeralSystem)
{
int maxDigitValue = numeralSystem - 1;
// инициализируем матрицу для частичных решений
var partialSolutions = new long[digitsCount][];
partialSolutions[0] = new long[numeralSystem];
for (int k = 0; k <= maxDigitValue; ++k)
{
partialSolutions[0][k] = 1;
}
for (int n = 1; n < digitsCount; ++n)
{
int maxSum = (n + 1) * maxDigitValue;
partialSolutions[n] = new long[maxSum + 1];
for (int k = maxSum; k >= 0; --k)
{
int statIndex = Math.Max(0, k - n * maxDigitValue);
for (int i = statIndex; i < numeralSystem && i <= k; ++i)
{
partialSolutions[n][k] += partialSolutions[n - 1][k - i];
}
}
}
long result = 0;
for (int k = 0; k <= maxDigitValue * digitsCount; ++k)
{
result += partialSolutions[digitsCount - 1][k] * partialSolutions[digitsCount - 1][k];
}
return result;
}
https://github.com/Vovanda/BeautifulNumbers/blob/master/Service/BeautifulNumbersService.cs
P.S Однако я удивлен, что никто не решил сохранять промежуточные вычисления