Алгоритм подсчета счастливых билетов

Задача вычисления количества счастливых билетов известна давно. Ее задавали практически любому школьнику, обучающемуся программированию. В интернете можно найти множество ее решений на разных языках программирования. Все эти варианты сводятся к перебору всех существующих билетов и проверке их на «счастливость». Получается миллион вариантов.

Но данную задачу можно решить и другим способом, перебрав всего тысячу вариантов.

Напомню, что счастливыми являются билеты, сумма первых трёх цифр номера которых равна сумме последних трёх цифр номера. Например, билет с номером «546780» является счастливым, так как сумма первых трёх цифр (5+4+6) равна сумме последних трёх цифр (7+8+0). Задача состоит в определении того, сколько всего существует счастливых билетов.

Во всех примерах она решается в лоб, но что если пойти иным путем? Вначале ответим на другой вопрос. Сколько существует различных комбинаций трех цифр (троек), которые в сумме дают n? Для ответа на этот вопрос нужно перебрать все возможные тройки (тысяча вариантов).

Сумма любых троек находится между нулем (0+0+0) и 27 (9+9+9). Поэтому можно подготовить массив сумм:

{n_0, n_1, n_2, n_3, …., n_25, n_26, n_27}

где n_i – количество троек, дающих в сумме i. При этом сумма цифр равна индексу этого элемента в массиве.

Хорошо, мы подготовим такой массив, но как это связано с билетами? Рассмотрим частный случай. Всего существует n_25 троек, дающих в сумме 25. Для каждой такой тройки существует n_25 троек, при объединении с каждой из которых будет получаться счастливый номер. Поэтому существует n_25*n_25 счастливых билетов, сумма первых трёх цифр которых равна 25. Аналогично и для других сумм. Таким образом, общее количество счастливых билетов равно:

n_0*n_0 + n_1*n_1 + …. + n_26*n_26 + n_27*n_27

Ниже приводится полный исходный код приложения, реализующего данный алгоритм.

Спойлер

#include <cassert>
#include <stdio.h>

//Количество различных вариантов сумм трех цифр
#define COUNT_SUMS 28
//Суммы трех цифр
unsigned char sums[COUNT_SUMS];

/****************************/
/*Инициализирует массив сумм*/
/****************************/
void InitSums(void)
{
  unsigned char i;
  for (i = 0; i < COUNT_SUMS; i++)
    sums[i] = 0;
}

/********************************/
/*Обрабатывает трехзначное число*/
/********************************/
void PerformNumber(unsigned short number)
{
  unsigned short sum = 0;
  unsigned short val = number;
  unsigned char digit;
  //Добавляем количество сотен
  digit = (unsigned char)(val / 100);
  sum += digit;
  
  //Добавляем количество десятков
  val %= 100;
  digit = (unsigned char)(val / 10);
  sum += digit;

  //Добавляем количество единиц
  val %= 10;	
  sum += val;

  //Учитываем в массиве сумм
  assert(sum < COUNT_SUMS);

  sums[sum]++;
}

/***********************************************/
/*Вычисляет общее количество счастливых билетов*/
/***********************************************/
unsigned long GetFullCount(void)
{
  unsigned long count = 0;
  unsigned char i;

  for (i = 0; i < COUNT_SUMS; i++)
    count += sums[i] * sums[i];
  
  return count;
}

/***********************************************/
/***********Главная процедура*******************/
/***********************************************/
int main()
{
  //Инициализируем массив сумм
  InitSums();

  //Обрабатываем все трехзначные числа
  unsigned short number;
  for (number = 0; number < 1000; number++)
    PerformNumber(number);
  
  //Вычисляем количество счастливых билетов и выводим его на экран
  printf("%d\\r\\n", GetFullCount());
    
  return 0;
}

Код хорошо прокомментирован, поэтому вопросы возникнуть не должны.

Если посмотреть на массив сумм, то можно сделать два наблюдения.

1. Он симметричен:

n_13 = n_14,

n_12 = n_15,

n_11 = n_16,

n_10 = n_17,

………………

n_1 = n_26,

n_0 = n_27.

2. Больше всего существует билетов, сумма первых трёх цифр которых равна 13 и 14 (их по 75).

Массив сумм из 28 элементов подготавливается за один проход перебора троек. Поэтому для подсчета количества счастливых билетов достаточно перебрать 1000 вариантов.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *