Some study notes: апреля 2015

Задача
Чтобы твой трек попал в ротацию на online радио для айтишников, реши следующую задачу: Билет на твой первый концерт в Лужниках содержит 6 цифр от 0 до 5. Сколько среди всех билетов «счастливых», т.е. таких, для которых сумма первых 3 цифр равна сумме последних 3 цифр?

Предисловие
Мы можем взять готовую формулу формулу из бесконечных статей на эту тему... Или попробовать разобраться.

Наш номер билета можно представить как AB, где А сумма первой половины билета, В - сумма второй половины билета. А и В входят в множество Х. Счастливыми будут билеты AA, где А = В.

Минимальная сумма у размещения: "000" = 0, максимальная у "555" = 15, т.е. всего Х = 16 различных сумм. Каждую сумму можно собрать из заданных чисел различными способами, назовем эти способы функцией S(x). Тогда наш счастливый билет для суммы х можно представить как:

AB => AA => S(x) S(x)

Т.е. счастливых билетов для каждой суммы это количество перестановок функции S(x) по двум позициям = S(x)^2

Осталось найти сколькими же способами можно собрать каждую сумму и просуммировать это безобразие.

Тут есть два способа: перебором и математикой. Я, пожалуй, воспользуюсь формулой из вот этой статьи , с учетом того что у нас n = 3 позиции и цифры от 0 до 5

	5
N₃(x) =	∑	N₂(x – l),
	l=0

при этом N₁(x) = 1 (x от 0 до 5) или 0 (x > 5)

Если l > x, слагаемое возвращает 0.

Решение.

Что еще описать в решении я, честно говоря не знаю. Нам осталось только закодить формулу.
Я завела массив цифр в билете и количество позиций в половине билета как константы.
Массив цифр, откровенно говоря, никак не контролирует что в нем нет пропусков... а в противном случае, если я правильно все понимаю, алгоритм будет не корректен. Но предположим, что если бы у нас был метод ввода этих цифр, он бы контролировал заполнение массива корректными данными.

public partial class MainWindow : Window
{
List<int> ValidNumbers = new List<int>() { 0, 1, 2, 3, 4, 5 };
int Positions = 3;

public MainWindow()
{
InitializeComponent();
}

private void EncryptBtn_Click(object sender, RoutedEventArgs e)
{
int result = 0;

int min_sum = ValidNumbers.Min() * Positions;
int max_sum = ValidNumbers.Max() * Positions;
for (int x = min_sum; x < max_sum + 1; x++)
{
result = result + Convert.ToInt32(Math.Pow(GetNByX(x, Positions), 2));
}
this.ResultTB.Text = result.ToString();
}

private int GetNByX(int x, int division)
{
if ((division == 1) && (!ValidNumbers.Contains(x)))
return 0;
else if ((division == 1) && (ValidNumbers.Contains(x)))
return 1;
else
{
int result = 0;
for (int l = 0; l < ValidNumbers.Max() + 1; l++)
{
if (l <= x)
result = result + GetNByX(x - l, division - 1);
}
return result;
}
}
}

Примечание:
Использовано: