Главная

В матрице из букв найти слово

Пнд, 11/03/2014 - 09:05 — tech
Задача: 

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

Описание переменных: 

str - матрица из символов;
w - заданное слово;
wcol - строка из букв столбцов.

Алгоритм решения задачи: 

Чтобы не заполнять матрицу вручную, заполним ее случайными буквами английского алфавита. Далее запросим у пользователя искомое слово.

Функция pos() языка программирования Pascal ищет вхождение подстроки (первый параметр функции) в строку (второй параметр). Если подстрока найдена, то возвращается номер ее первой буквы в строке. Если не найдена, то возвращается 0.

В языке Pascal если матрица состоит из типа данных char, то к строкам матрицы можно обращаться как к строкам, а не массивам. То есть можно извлечь строку матрицы целиком, опуская второй индекс (номер столбца). Таким образом при поиске вхождения заданного слова в строку достаточно перебрать матрицу построчно, каждую строку проверить на вхождение слова (подстроки) с помощью функции pos(). Если pos() возвращает значение больше 0, значит слово входит в строку. Это слово будет начинаться в строке, чей номер определяется итерацией цикла, и в столбце, чей номер определяется значением, которое вернула функция pos().

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

Программа на языке Паскаль:  

const N = 10;
var
    str: array[1..N,1..N] of char;
    i,j,k: byte;
    w, wcol: string[N];
 
begin
    randomize;
    for i:=1 to N do begin
        for j:=1 to N do begin
            str[i,j] := chr(random(26) + 97);
            write(str[i,j],' ');
        end;
        writeln;
    end;
    write('Введите слово: ');
    readln(w);
    // проверяем по строкам
    for i:=1 to N do begin
        j := pos(w,str[i]);
        if j > 0 then 
            writeln('Слово начинается в строке ', i, ' в столбце ', j, ' (горизонтально)');
    end;
    // проверяем по столбцам
    for j:=1 to N do begin
        // собираем строку из букв столбца
        wcol := '';
        for i:=1 to N do 
            wcol := wcol + str[i,j];
        // проверяем нет ли в ней слова
        k := pos(w,wcol);
        if k > 0 then
            writeln('Слово начинается в строке ', k, ' в столбце ', j, ' (вертикально)');
    end;
end.

Пример работы программы:

t r j c s m x i c j 
p c u k r e q k q s 
k k v i a l t q d l 
z b m o e e n o b a 
u d b p w u x w p p 
y n y x p f f m j d 
t z h q j f z b a d 
d r p l x e h i q c 
o m z g c o e t f a 
x y d w d e p j p m 
Введите слово: moe
Слово начинается в строке 4 в столбце 3 (горизонтально)
  • Добавить комментарий