Блок задач

4. Структуры данных

Темы
Сложность 3

Задача «Анаграммы»

Анаграмма — литературный приём, состоящий в перестановке букв или звуков определённого слова (или словосочетания), что в результате даёт другое слово или словосочетание.

Необходимо написать программу, которая расшифровывает заданную анаграмму, пользуясь словарём.

Входные данные

  1. Текстовый файл, содержащий одно предложение. Каждое слово в нем является анаграммой. Само предложение также является анаграммой (то есть в нем переставлены слова). Пример:
ym hree lsvei fendri
  1. Текстовый файл-словарь, содержащий в себе слова и связанные с ними веса, отражающие вероятность нахождения слов в тексте. Вероятность употребления слова с бóльшим весом больше, чем с меньшим. Пример:
my, 10
bye, 10
friend, 10
here, 10
elvis, 4
lives, 10

Файлы могут содержать пустые строки. Их необходимо игнорировать.

Постановка задачи

1) Расшифровать каждое слово. Основываясь на весах слов, выбрать наиболее вероятный вариант.

2) Распечатать все возможные предложения (все перестановки), используя только!! наиболее вероятные варианты слов.

Примечания
  1. Если в словаре нет подходящего для анаграммы слова — выдать ошибку.
  2. Если для одной анаграммы слова есть несколько вариантов в словаре — выбрать с большим весом. Если веса равны, выбрать любой.
  3. Передачу имен файлов реализовать через аргументы командной строки.

Пример вывода

(использует файл из примера выше)

friend here my lives
friend lives here my
friend lives my here
friend my here lives
friend my lives here
here friend lives my
here friend my lives
here lives friend my
here lives my friend
here my friend lives
here my lives friend
lives friend here my
lives friend my here
lives here friend my
lives here my friend
lives my friend here
lives my here friend
my friend here lives
my friend lives here
my here friend lives
my here lives friend
my lives friend here
my lives here friend

Входные данные для тестирования

Словарь:

time, 10
person, 10
year, 10
way, 10
day, 10
thing, 10
man, 10
world, 10
life, 10
hand, 10
part, 10
child, 10
eye, 10
woman, 10
place, 10
work, 10
week, 10
case, 10
point, 10
government, 10
company, 10
number, 10
group, 10
problem, 10
fact, 10
Verbs, 10
be, 10
have, 10
do, 10
say, 10
get, 10
make, 10
go, 10
know, 10
take, 10
see, 10
come, 10
think, 10
look, 10
want, 10
give, 10
use, 10
find, 10
tell, 10
ask, 10
work, 10
seem, 10
feel, 10
try, 10
leave, 10
call, 10
good, 10
new, 10
first, 10
last, 10
long, 10
great, 10
little, 10
own, 10
other, 10
old, 10
right, 10
big, 10
high, 10
different, 10
small, 10
large, 10
next, 10
early, 10
young, 10
important, 10
few, 10
public, 10
bad, 10
same, 10
able, 10
to, 10
of, 10
in, 10
for, 10
on, 10
with, 10
at, 10
by, 10
from, 10
up, 10
about, 10
into, 10
over, 10
after, 10
beneath, 10
under, 10
above, 10
Others, 10
the, 10
and, 10
a, 10
that, 10
I, 10
it, 10
not, 10
he, 10
as, 10
you, 10
this, 10
but, 10
his, 10
they, 10
her, 10
she, 10
or, 10
an, 10
will, 10
my, 10
one, 10
all, 10
would, 10
there, 10
their, 10
alert, 5 
alter, 6
later, 10
arts, 5
rats, 6
star, 10
tars, 1
dare, 7
dear, 8
read, 10
book, 10
can, 10
drawer, 5
redraw, 10
reward, 7
warder, 3
warred, 2
please, 10
bye, 10
friend, 10
here, 10
elvis, 4
lives, 10

Файл анаграмм для расшифровки:

dera liwl hatt ralet kobo I
tras nca ese ouy shti 
wedrar ti saeelp
ym hree lsvei fendri

Тестирование

Для всех разработанных модулей должны быть созданы наборы unit тестов. Функции ввода/вывода нужно тестировать с помощью std::stringstream.