Домашнее задание по информатике №7
Оглавление
Задача «Игра в города». 2
Задача «Черепашка». 3
Задача «Площади островов». 4
Задача «Игра в города»
Всем известны правила игры "в города": первый игрок называет произвольный город, следующий - город, название которого начинается на ту же букву, на которую заканчивается название предыдущего города, и т. д. Аналогичным образом можно играть не в названия городов, а, например, в названия животных. Задан список допустимых для описанной игры слов, слова в нём могут повторяться. Напишите программу, определяющую, в каком порядке в процессе игры должны быть названы слова из списка, чтобы каждое слово было использовано, ровно столько раз, сколько оно в нём встречается.
Решение. Используется очень простая идея. Это перебор 0 и 1 в n-значном числе. Т. е. если мы натыкаемся на 0, то данное слово мы не берём в последовательность, если 1, то берём. Получив некую последовательность проверяем на то, что есть ли такие слова, которые начинаются на ту букву, на которую некоторые заканчиваются. Затем ты записываем в двумерный массив в первый столбец количество слов, а затем в остальные столбцы последовательность слов. Потом просто находим строчку с максимальным значением слов и выдаём эту последовательность.
while (true) do begin
inc(p[1]);
for i:=1 to n do
if p[i]>1 then begin
inc(p[i+1]);
p[i]:=0;
end;
-
if p[n+1]=1 then break;
end; - пример перебора нулей и единиц.
Вместо - вставьте текст программы.
Задача «Черепашка»
Моя любимая задачка. В двумерном массиве NxN в [1,1] расположена черепаха. Она мечтает попасть в клетку [N, N]. Всё поле заполнено числами - это количество еды в данной клетке. И вот черепашке мало того, что нужно перейти в конечную клетку, но ей ещё нужно и собрать максимальное количество еды. Причём черепашка может двигаться на одну клетку по горизонтали вправо или на одну клетку по вертикали вниз.
Пример входного файла:
4
0 23 43 55
33 23 21 3
33 12 33 1
100 0 0 200
Решение. Нам повезло, что наша черепаха двигается только в два направления. Т. е. нам достаточно перебрать только 0 и 1. Если 0, то вниз. Если 1, то вправо. Далее, а сколько мы чисел будем перебирать? 2n-2. И всё. Кстати, к этой задаче есть полное решение. После того как мы получим массив с нулями и единицами. Строем траекторию движения черепашки и считаем, сколько еды она собрала. Сравниваем с максимальным. И всё. В данном примере максимум эта обжора съест 366 кг. еды.
Задача «Площади островов»
Карта моря задана матрицей размера N*M, состоящей из квадратиков, в которых записаны 0 или 1, 0 – это вода,1 – суша. Два квадратика с единицами принадлежат одному острову, если они имеют общую сторону. Найти количество островов и площадь каждого острова. Площади островов вывести в порядке неубывания (возрастания).
Входные данные:
в первой строке два целых числа N и M (1<=N, M<=100) – размеры матрицы. В последующих N строках карта моря. В каждой строке M нулей и единиц, не разделённых пробелом.
Выходные данные:
в первой строке одно целое число – количество островов. Во второй строке площади островов, выведенные в порядке неубывания (возрастания).
Пример:
Input. txt | Output. txt |
3 4 | 2 |
0110 | 2 4 |
0000 | |
1111 |
Алгоритм решения этой задачи следующий. Просматривая двумерный массив построчно, найти единицу, принадлежащую острову. Рекурсивно или двумя очередями найти площадь острова, при этом потопив его. Повторять процесс поиска до тех пор пока есть острова. Найденные площади островов запоминаем в одномерном массиве. Когда все острова будут потоплены, сортируем массив площадей по неубыванию и выводим результат.
