Нужно составить алгоритм
 

Есть кроссворд. Любой. На пример как на картинке.

И есть набор чисел, которых в несколько раз больше, чем поместится в кроссворд. На пример:
92365
13846
4356
128
95
1250
3916735
3594
190346
5843
9571
126534
59
21
39468
593823
96986
9348
594756
33466

Нужно составить алгоритм, который заполняет кроссворд числами из списка. Условие: чтобы сумма цифр из всех квадратов в кроссворде получилась максимальная.
Конкретно я немогу понять через что представлять сам кроссворд (массив? дерево?). И как проверять какие места свободны, какие частично заняты.

И ещё:

Квадрат разбит на девять частей. В каждой части вписана буква:

T __ S __ E

K __ I __ H

U __ R __ A

Нужен алгоритм, выписывающий все возможные комбинации (слова) из этих букв. Условие: минимум четыре буквы, в каждой комбинации должна быть буква I (середина квадрата), каждая буква может присутствовать только один раз.

Под конец рабочего дня уже соображать трудно - но рискну предложить решение по первой части задачи - так как ни каких дополнительных условий не указанно то максимальная сумма кросворда - это сумма всех чисел - минус сумма чисел не вошедших в кроссворд. ;) Хотя в моем понимании - кроссворд - это всеже слова.
И не очень понятно, что имеется ввиду под представлением. Если имеется ввиду хранение результатов - то каждая ячейка описывается положением по горизонтали и по вертикали - то есть, как вариант, для ее хранения можно создать структуру, членами которой является позиция по Х У и собственно значение ячейки. А хранить ее можно или в двумерном массиве - самое простое, но не самое эффективное, или использовать два контейнера с уникальным значением ключа. В качестве ключа использовать соответственно в одном случае Х в другом У.
Я бы сделал это так -
меп ищет по ключу достаточно быстро - решение проблемы, заполнена ли ячейка - поиск по Х или У и т.д. Вобще-то структуру создавать не обязательно - просто так уневерсальней, то есть универсальней я хотел сказать. Все начал заговариваться - пора рулить до хаты. :biggrin:

Ты неправильно понял. Я написал Нужно составить алгоритм, который заполняет кроссворд числами из списка. Условие: чтобы сумма цифр из всех квадратов в кроссворде получилась максимальная.

То есть вписали число 3465, считаем: 3+4+6+5. В кроссворд надо добавлять как слова: если число из трёх цифр, то оно займёт три квадрата. Потом считать сумму всех квадратов. Получившийся алгоритм для заполнения должен работать со словами тоже (может быть при минимальном изменении).
Меня больше всего интересует как сделать перересечение линий в кроссворде. Если в одной линии я вписал 2 7 9 4 2 5, предположим цифра 4 попала на пересечение. Тогда нужно както вычислить, что по другой линии одна цифра уже есть. Соответственно туда надо искать число соответствующее условию.

Опять же я бы использовал для этих целей преобразование числа в строку - длина строки=количество клеток. Тогда ты легко можешь работать как со строками так и с цифрами. Единственное - возникнут накладные расходы на преобразование цифры в строку и обратно - но не настолько уж большие. Используя предложеную связку контейнеров ты можешь легко определить наличие или отсутствие букв в строке пересечения - все что для этого тебе необходимо - написать шаблон функции поиска которая возвращает количество элементов имеющих У (или Х смотря какое пересечение) одинаковый с искомой позицией (блин как завернул) и валюе которых не пусто или в противном случае ноль. Но при этом важно не забыть проверять на наличие разрывов между ячейками. Кстати, я немного не сообразил вчера, для связки нужно использовать не 3 а 2 контейнера - в одной хранится уникальный идентификатор ячейки и итератор на элемент второго контейнера. А во втором хранится структура, полями которой являются - ид, Х,У, признак первой или последней ячейки и значение. Так же здесь может хранится идентификатор следующей и предыдущей ячейки по вертикали, горизонтали и верхней нижней. Можно использовать и просто массив - но у контейнера есть преимущество - стандартная библиотека функций. Можно использовать и один контейнер - но это решение мне нравится меньше.
То есть в первом приближении алгоритм выглядит так:
1. Шаг первый - инициализируешь сетку кроссворда - т.е. заполняешь массивы структурами с установленным значением Х и У и присваеваешь им уникальный идентификатор.
2. Получаешь длину строки которую необходимо заполнить.
3. Находишь число совпадающее с длиной строки.
4. Раскладываешь его на составляющие и получаешь сумму.
5. Проверяешь на соответствие условиям.
6. Помещаешь в ячейки.
7.Повторяешь со 2 до тех пор пока не дойдешь до последней ячейки.
:)

хм... интересная задачка. А ты можешь предложить быстрый алгоритм который будет просто законно заполнять кроссворд?

Kot (Sorrryyyy!) предложил по крайней мере O(n*n)

Male - это кто? ;) У меня вроде ник есть...
Конечно, приведеныый алгоритм может быть оптимизирован, но по сути он все же сводится к О(n*n).
Возможно повышение эффективности и свдение задачи к алгоритму поиска в бинарном дереве (блин хочется :beer: и котелок уже не варит) но в таком случае необходима оптимизация словаря, введение частот и возможно создание объектов типа строк - как совокупность ячеек. Это позволит получить гораздо более быстрый алгоритм и избежать перелопачивания массивов. Но эту мысль я еще не додумал по причине вышеуказанной.
;)

проблема в том что кроме перебора (оптимизированного по частотам и т.д.), т.е. greedy никаких идей нету. К тому же ето не обеспечивает ОПТИМАЛьНОГО заполнения. Можно подумать о каких нибудь генетических алгоритмах... но как найти оптималный ответ???

Оптимизированный по частотам - это уже не перебор. Если провести оптимизацию словарей хотя бы по двум критериям - размер слова и, в случае цифрового кросворда, сумма - это уже бинарное дерево. То есть скорость выборки словаря может быть оптимизирована и сведена к поиску в бинарном дереве, что эффективней перебора. Соответственно сетка кросворда так же может быть оптимизирована, только критерий оптимизации должен совпадать с критериями словаря.

То, что числа надо в строки переделать - это понятно. Идея с контейнерами интересная. А как со второй задачей? Предложения будут?

Если нет ограничений на позицию I в слове - то задачу я бы предложил алгоритм - разделить гласные и согласные, выделить букву I отдельно - выделить сочетания в которых буквы из первого массива находятся в первой, второй позиции и четвертой, I в третьей. В получившихся сочетаниях последовательно заменить первую позицию буквами из второго массива, потом вторую.
Поместить в массив - заканчивается на согласную.
Выделить сочетания в которых буквы из первого массива находятся в первой, третьей позиции и четвертой, I во второй.
В получившихся сочетаниях последовательно заменить третью позицию буквами из второго массива, потом четвертую.
Поместить - заканчиваются на гласную.
Полученные сочетания из заканчивается на первом этапе добавить пятой из массива гласных сравнив с первой и второй позицией.
И так до конца.
То есть предполагается что сочетаний типа TSHKIUAE быть не должно.

А надо все сочетания. и такие:

тоже...

Так вторая задача ето действительно просто перебор: все слова по 4 буквы, по 5 букв, и до 9 букв. Кстати по моим посчетам ето 876624 слов

А на первую оптимального решения не видно...

Тю ну ради бога - это тогда просто перебор с контролем неповторяемости и обязательным присутствием I. При чем, если нет ограничения на осмысленность то задачу вообще можно упростить - выделить массив букв из восьми элементов, букву I и массив для хранения слов.

Только я чтото недогоняю как алгоритм для такого перебора составить?
Набросайте, если не влом...

В алгоритме ничего сложного нет. У тебя есть символ который обязательно должен присутствовать - значит начинаешь с того, что устанавливаешь его в первую позицию - после начинаешь перебор. В массиве каждая буква у тебя встречается один раз - это нужно использовать - то есть каждую позицию массива помещаешь один раз в в свободную позицию слова - для 4-х буквенного слова это будет примерно так:
- скопировать первые три элемента в слово
-записать
- скопировать следующие три элемента
-пункт 2
-скопировать первый второй и четвертый
-пункт два
-скопировать первый второй и пятый
-пункт два
-скопировать первый второй и шестой
...
-скопировать первый третий и четвертый
и так далее.
Потом первый элемент массива копируется во вторую позицию второй в первую. Выполняешь последовательно теже шаги.
Затем третий элемент копируется в первую. Опять прогоняешь
Когда все элементы массива пройдут первую позицию смещаешь второй на место третьего и опять итерация. То есть выполняешь все шаги до тех пор, пока первый элемент массива не вернется в начало.
То же самое используешь для 5 и более буквенных. Но здесь возможны два варианта - с одной строны у тебя уже есть 4-х буквенные слова - можно использовать их - но тогда на этом этапе должна быть добавлена функция проверки на наличие буквы - мне кажется это может усложнить работу с алгоритмом. И по этому, я бы использовал тот же принцип что и для 4-х буквенных но соответственно копировал просто большее колво элементов.

Могу добавить, что имеет смысл не забывать о нумерации с нуля. Это упростит работу с постоянным символом - его позиция в массиве - это количество символов перед ним. Что позволяет избежать кучи if() else - я имею ввиду, что нет нужды проверять в какой позиции находится постоянная буква - нужно просто использовать позицию ее цикла итерации - например если в текущей итерации буква I находится в первой позиции - ее номер 0 - если в во второй и больше - позиция каждой вычисляется следующим образом - для букв перед - (индекс буквы+1)-(индекс постоянной буквы в массиве - количество букв перед) -1. Для букв после (индекс буквы+1)-(индекс постоянной буквы в массиве - количество букв перед).
:) Фу еле написал. Но на самом деле это позволяет неплохо оптимизировать алгоритм и ускорить его работу.

Спасибо! :cool:

Маленькое предположение - а не получится разложить или развернуть квадрат в дерево с корнем в I, а потом просто различные обходы делать??? ИМХО если получится, то тогда можно опять же стандартными контейнерами решить, что в разы быстрее тривиального перебора...
Не утверждаю что так получится, но вдруг :):)

Брутфорсе он и есть брутфорсе :) То что ты предлагаешь - это называется атака по словарю. То есть, предполагается, что у нас уже есть массивы всех возможных сочетаний и мы просто подставляем их в нужное место. А задача вроде как обратная - есть набор символов - и необходимо создать словарь. Или может я просто неверно понял твою идею?

быстрее тривиального перебора не может быть быстрее по определению - все равно все решения надо найти

Вот снова понадобилось. Теперь уже больше математичекое решение нужно.


FlatLand pianos are rectangles of various sizes. FlatLand building codes require all turns in corridors to be right angle turns and prohibit ``T'' intersections. You can assume that each portion of a corridor is long enough so that other corners or doors into rooms don't have any effect on getting around a turn. You can also assume that the piano is narrower than the width of any corridor. "

"Note that the piano actually has to turn in the corner, since it can only be pushed or pulled on one of its shorter sides (there are no square pianos). Your team's job is to write a program for a palmtop computer that will determine if a given piano will fit around a corner in a corridor. "


То есть имеем два коридора под прямым углом в виде буквы "Т" и пианино. Дана длинна пианино, ширина пианино, ширина первого коридора, ширина второго коридора. Как вычислить пролезет ли там пианино?
:cool:

Попробуем решить. Только решение боюсь, будет длинным, поэтому я разобъю несколько этапов, каждый опишу подробно.

Этап 0: Подготовительный этап. Вводятся условные обозначения, система координат, начальные условия, базис, по которому можно однозначно восстановить положение пианино в данной с.к., формулы вычисления координат границ пианино.
Этап 1: Движение точки А вдоль прямой x=0.
Этап 2: Движение стороны АВ пианино, упираясь в точку P. Вычисление закона движения точки А.
Этап 3: По закону движения точки А можно восстановить закон движения стороны BC.
Этап 4: Проверка, пересекает ли прямая ВС точку Q? Если не пересекает, то пианино сможет совершить заданный маневр.


Начальное и конечное положение - см. рисунок.

Так как я не владею английским языком, скажите, верно ли я понял условие задачи?

Пусть координаты пианино зависят от времени, поэтому:

A(t): (X_a(t), Y_a(t))
B(t): (X_b(t), Y_b(t))
C(t): (X_c(t), Y_c(t))
D(t): (X_d(t), Y_d(t))

Положение пианино можно однозначно задать координатами точки А и ориентацией пианино (направлением вектора АВ).
Но можно ввести дополнительное ограничение: Пусть точка D будет всегда прижата к нижней стене (в введенной системе координат - это означает, что y_d(t)=0 для любого t). Поэтому можно ограничится только координатами точки А и с соблюдением того, чтобы наше условие всегда выполнялось.

Другие точки пианино будут выражаться так:

cos(phi)=Y_a(t)/|AD|
sin(phi)=(X_d(t)-X_a(t))/|AD|
cos(phi)^2+sin(phi)^2=1
=>
(X_d(t)-X_a(t))/|AD|=sqrt(1-(Y_a(t)/|AD|)^2)
X_d(t)=X_a(t)+sqrt(y^2-Y_a(t)^2)
Y_d(t)=0

Координаты точек B и C нам не понадобятся. (но нам понадобятся уравнения прямых, проходящих через эти точки - они будут выведены позже.)

Я сам немного не точно понял. Наоборот: коридор не может быть типа "Т". То есть, это не два коридора, а один поворачивающий на 90 градусов. Он делится на два по ширине. До и после поворота ширина коридора отличается. Каждый коридор шире чем пианино.
Нужно не вычислять движение, а найти ответ: пролезет или нет.

Я пока дошёл до простого перебора. Ставить отрезок в угол и начинать наклонять получая разные треугольники. отрезок = длине пианино. При каждом наклоне проверять расстояние между другим углом (вокруг которого двигаюсь) и отрезком. Если расстояние больше ширины пианино, зназит ещё не застряли. :)

А вот без перебора наверно никак....

Собственно законы движения на этом этапе выводить совсем необязательно. Достаточно рассмотреть конечное положение этого этапа.

Для точки А: X_a=0, Y_a=и
Для точки D: X_d=sqrt(y^2-Y_a^2), Y_d=0

Для следующего этапа нам потребуется точка B и зависимость ее от точки А.

Уравнение прямой через A и B:
(y-Y_a)/(Y_b-Y_a)=(x-x_a)/(x_b-x_a) (1)
y-Y_a=(x-X_a)(((Y_b-Y_a)/(x_b-x_a))
Поскольку АВ перпендикулярно АD, то
(Y_b-Y_a)/(x_b-x_a)=(X_d-X_a)/(Y_d-Y_a)

Подставляем в (1) - получили уравние прямой, выраженное через координаты точки А.

Можно переходить к этапу 2. Этап самый труоемкий, решение будет дописано позже.
(14:59)

:) О! Задача упрощается! Теперь этап 2 совсем не нужен - а он самый трудный в расчетах был. Перебор - это конечно хорошо - но долго(понятие конечно относительное). Задача ведь олимпиадная - скорость тоже важна! Можно ведь вывести формулу - а потом просто подсчитать, и все.
Скоро выдам исправленную версию.


Исправленная версия

Итак, если если вы читали, что написано ранее, то это вам покажется сущим пустяком! :)

Упрощения в связи с новым условием:
X_a(t)=0 - для любого t

Точка A: (0, Y_a)
Точка D: (x_d, 0)

x_d=sqrt(y^2-Y_a^2)

Отсюда в качестве переменной достаточно взять Y_a и Еще нам понадобится Y_с. Ее можно вычислить так:
Y_c^2+(X_d-X_с)^2= BD^2=x^2+y^2 (1)
Из другого треугольника:
(x+y)^2=(X_d+X_c)^2+Y_c^2

Из этих уравнений можно получить, что X_c=xy/2*x_d
Подставляя X_с в любое уравнение, можно получить Y_с.

Уравнение прямой, проходящее через A и D:
(y-Y_a)/(Y_d-Y_a)=(x-x_a)/(x_d-x_a)
(y-Y_a)/(-Y_a)=(x)/(x_d)
y=((-Y_a)/(x_d))(x)+Y_a (2)

Уравнение прямой через В и С:
эта прямая параллельна прямой АD => выразим через (2) и (Y_c)
y2=((-Y_a)/(x_d))(x)+Y_a + 2(Y_c - y_a) (3)

Вот почти и все. у2(a - ширина коридора) - это есть расстояние от нижней стенки до стороны ВС на уровне точки Q (угла стенки). Осталось исследовать эту функцию на max. (пределы исследования: Y_a=y до Y_a=0 - конец маневра)
В программе полученный результат сравнивается с другой шириной коридора) - и программа выдает нужный ответ... Исследование функции на экстремумы проходили в школе, я надеюсь?

PS1: Проверьте вычисления, может где-то ошибка закралась...
PS2: Записывать окончательную формулу в приведенном виде не стал - в режиме текстовой строки прочитать ее довольно трудно. Но здесь просто надо поставить одни формулы в другую и получить искомую формулу...

Что-то я ничего не понял. Что значит Y_a=и?
Почему для точки D: X_d=sqrt(y^2-Y_a^2)? y здесь какаято длинна, Y_a - координата? А для уравнения треугольника должно быть две длины. И вообще, X_d должно быть тоже координата? Совсем ничего не понимаю...

И в каком месте можно определить, что пианино всё-таки не пролезло? Както это всё слишком запутано....

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

Начало процесса поворота: t=0
Конец процесса поворота: t=Pi/2

Уравнение прямой CD, выраженное через угол t
y= -x tg(t) – p sin(t) - q/ cos(t)

Запустив цикл по t от 0 до 90° с шагом, например, в 1°, получим семейство уравнений прямой СD при протискивании пианино в углу. В кажом шаге цикла проверим условие пианинного проползания:
y(-a) > -b - если через перебор.

А можно исследовать y(-a) на экстремумы (t=0 до t=90°). Правда это не такая уж и легкая задача будет. Здесь нужно использовать матпакеты и получить приближенное значение(точного решения задача не имеет) и работать уже с ним.

Вообщем, перебором все-таки гораздо проще выйдет.
(копирайт Дин Гиор)
Примечание: вывод формулы:
Коэффициент наклона прямой: k=y_b/(-x_a)=-(p*sin(t))/(p*cos(t))=-tan(t);
Координаты точки D: (-p*cos(t)-q*sin(t),-q*cos(t);
Уравнение прямой: y=y_D+k(x-x_D)
или: y=-q*cos(t)-tan(t)(x+p*cos(t)+q*sin(t))
или: y= -x tg(t) – p sin(t) - q/ cos(t)

Ну, тогда понятно. Я примерно также думал.
Спасибо! :)

Читай также вот эту тему:
_http://arbuz.uz/forum/index.php?showtopic=1009&st=0
Там подкинули еще одну свежую идейку.