Лабораторный практикум по информатике



бет76/83
Дата06.01.2022
өлшемі1,1 Mb.
#15674
түріПрактикум
1   ...   72   73   74   75   76   77   78   79   ...   83
Задача 8. Дан двумерный массив, заполненный нулями и единицами.

Найти прямоугольник наибольшей площади, заполненный единицами.

Площадь прямоугольников изменяется от максимальной (весь мас- сив) до минимальной (прямоугольник, состоящий из одной 1). Каждый прямоугольник конкретной площади может быть построен множеством способов. Для площади S допустимый прямоугольник – это такой, про- изведение сторон которого равно S. Мы должны для каждого значения площади перебрать все допустимые способы построения прямоугольни- ков. Каждый прямоугольник конкретной площади и формы может рас- полагаться в массиве различным образом. Точнее сказать, его левая верхняя вершина может находиться в разных точках массива. Следова- тельно, для прямоугольника определенной площади и формы мы долж- ны перебрать все возможные расположения.

Может показаться, что программа для большого массива будет ра- ботать слишком долго, но есть серьезные возможности для ее ускоре- ния. А именно:



  1. Если площадь перебирать от максимальной к минимальной, то пер- вый найденный прямоугольник и будет искомым.

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

Учет этих утверждений ведет к очень серьезному ускорению про- граммы.


Достарыңызбен бөлісу:
1   ...   72   73   74   75   76   77   78   79   ...   83




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет