вторник, 15 февраля 2011 г.

Часть 5. Буквометика

[Все темы по перестановкам]

Литература: Кнут. Том 4. Выпуск 2. Генерация всех картежей и перестановок. 2008

Задача: Футбол и математика

Описание решение:

Суть задачи решить ребус аналогичный такому:
                        MOTOR
                  +      FIAT 
                       ------
                        VOLVO
Где вместо букв нужно поставить цифру. При этом разные буквы должны иметь разные цифровые значения.
По условию задачи количество различных букв не превосходит 10.
Значит в общем случае нужно перебрать все размещения без повторений для n=10(10 цифр) и k = количеству различных букв в ребусе. А в худшем случае – 10! различных перестановок.
Генерация размещений без повторений имеет схожую природу с генерацией перестановок без повторений. Поэтому данная задача попала в блок к перестановкам.

Алгоритм будет иметь следующую структуру:
1) Получение строки, содержащей все различные буквы исходного ребуса в порядке слева направо, сверху вниз. Для примера это будет строка “MOTRFIAVL”.
1) Генерация текущего размещения без повторений для заданных n и k в лексикографическом порядке.
2) Т.к. длина текущего размещения равна длине строке различных букв из п.1), проинициализировать i-ую букву i-ым значением размещения.
3) Проверка корректности ребуса.
4) Если возможно, перейти на п. 1).

Реализация:
В самом решении использовалась рекурсивная схема, схожая со схемой генерации всех перестановок без повторений.
Обратите внимание на изящную реализацию считывания(ст.4):

  1. void input()
  2. {
  3.   char a[12],b[12],c[12];
  4.   scanf("%[A-Z]+%[A-Z]=%[A-Z]",&a,&b,&c);
  5.   A = string(a); B = string(b); C = string(c);
  6. }
* This source code was highlighted with Source Code Highlighter.

[Решение]

P.S: Метод ветвей и границ для данной задачи.

2 комментария:

  1. Извините. Хотел сказать что ссылка с условием требует особой секретности, которой у меня нет ))

    ОтветитьУдалить
  2. Для это необходимо зарегистрироваться на сайте contester.tsure.ru, затем залогиниться и уже после этого нажать ссылку.

    Если не получится - пишите, поможем)

    ОтветитьУдалить