Метод решения

Рыбинск 2010

Содержание

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

2. Метод решения. 4

3. Организация данных. 6

4. Описание процедур и функций. 7

5. Разработка алгоритма. 8

5.1 Общий алгоритм. 8

5.2 Частные алгоритмы.. 8

5.2 Частные алгоритмы.. 9

5.2.1 Алгоритм проверки возможности составления кроссворда. 9

5.2.3 Алгоритм поиска слов в шаблоне. 11

6. Тестирование. 13

6.1 Методика тестирования. 13

6.2 Результаты тестирования. 15

7. Руководство пользователя. 17

Литература. 18

Приложение. Текст программы.. 19

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

Пусть заданы конечное множество слов и таблица N*N, в некоторые клетки которой записан символ #.

Составить кроссворд, размещая буквы слов в свободные клетки заданной таблицы-шаблона.

Если по заданным таблице и множеству слов составить кроссворд невозможно, вывести соответствующее сообщение.

Метод решения

Задачу о составлении кроссворда можно разбить на три блока:

1. блок ввода

2. блок поиска решения

3. блок вывода

Ввод данных можно организовать двумя способами:

1) из файла;

Для этого необходимо

· определить структуру входного файла:

1 строка – размер матрицы – шаблона (N) (целое число);

2 строка – 1-ая строка матрицы из ‘_’ и ‘#’ (без пробелов и знаков препинания);

3 строка - 2-ая строка матрицы из ‘_’ и ‘#’;

....................................................................

N+1 строка – N-я строка матрицы из ‘_’ и ’#’;

N+2 строка – первое слово из множества слов;

N+3 строка – второе слово и т.д.

· организовать ввод имени файла:

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

· читать данные из файла.

2) в режиме диалога (ввод с клавиатуры).

Для организации ввода данных с клавиатуры необходимо:

· ввести размер матрицы;

· ввести матрицу;

· ввести количество слов;

· ввести слова.

Для проверки возможности составления кроссворда по заданному шаблону и набору слов необходимо выполнить инициализацию ряда переменных: массив, в который будет записан вариант кроссворда, и массив слов шаблона кроссворда. В каждую ячейку массива варианта кроссворда записывается символ слова и номер слова, из которого взят символ, если ячейка располагается на пересечении двух слов, то номер слова соответствует первому вписанному в эту ячейку символу слова. При инициализации все ячейки заполняются символами ‘#’ и номерами 0. Массив слов шаблона кроссворда представляет собой одномерный массив, в каждую ячейка которого записывается номер слова по вертикали, номер слова по горизонтали, глина слова, ориентация слова (слово расположено по вертикали или по горизонтали). При инициализации данного массива просматривается шаблон кроссворда: по строкам (ищутся все слова, расположенные по горизонтали) и по столбцам (ищутся все слова, расположенные по вертикали).

После этапа инициализации выполняется этап проверки возможности составления кроссворда.

1 Проверить, хватит ли слов для заполнения кроссворда: Для этого необходимо подсчитать количество слов в кроссворде и количество слов из заданного множества с учетом их длины. Если количество заданных слов некоторой длины меньше, чем количество слов в кроссворде этой длины, то кроссворд составить невозможно.

2 Если проверка по п.1 завершилась удачно, необходимо попытаться вписать слова в нулевые ячейки матрицы. Для этого необходимо определить первое незаполненное слово в кроссворде: просматриваем массив слов шаблона кроссворда от 1 до количества слов в шаблоне; найти в множестве слов незанятое слово подходящей длины и попытаться вписать в шаблон. Слово возможно вписать в шаблон, если оно не содержит пересечений с другими словами или если пересечения с внесенными словами не приводят к ошибке, то есть символы слов на пересечении совпадают. Если слово невозможно вписать в шаблон, то ищем следующее подходящее по длине слово. Если слов данной длины больше нет, то возвращаемся на слово назад, то есть, заменяем последнее вписанное слово в шаблоне нулями, помечаем это слово как свободное, ищем другое слово заданной длины.

3 Если перебраны все варианты, а кроссворд остался незаполненным, то составить кроссворд из такого набора слов и такого шаблона кроссворда невозможно.

Вывод результата предполагает либо вывод одного варианта заполнения кроссворда, либо сообщение о том, что кроссворд составить невозможно.

Дата добавления: 2015-12-08