Форум программистов
 
Регистрация на форуме тут, о проблемах пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail, а тут можно восстановить пароль

Купить рекламу на форуме 15-35 тыс рублей в месяц

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail


Оплата за обучение в Kata Academy только после твоего трудоустройства в IT, начни карьеру Middle Java-разработчика


Ответ
 
Опции темы Поиск в этой теме
Старый 26.05.2012, 17:27   #1
sasha1988
 
Регистрация: 26.05.2012
Сообщений: 6
По умолчанию Помоготе,пожайлуста, составить блок-схемы по описанию схемы.

Это алгоритм нахождения одного кратчайшего покрытия.

структура данных
m – количество строк таблицы покрытия;
n – количество столбцов таблицы покрытия;
i, j – переменные цикла по строкам и столбцам соответственно;
Sprev – предыдущая сумма столбца либо строки;
Scurr – текущая сумма столбца либо строки.
Таблица покрытия – это двумерная матрица. Ее целесообразно представить в виде двумерного массива A (m, n).
P – одномерный массив для хранения номеров строк, покрывающих матрицу


3.4 Описание схемы алгоритма


Сначала вводятся исходные данные: размерность таблицы m и n и сама таблица покрытия (блок 1). Далее происходит поиск пустого столбца (блок 2): это целесообразно, поскольку, если хотя бы один столбец не покрыт, то и не существует покрытия данной таблицы, и, следовательно, конец алгоритма. Далее, если не найдено пустого столбца (проверка в блоке 3), – поиск ядерных строк (блок 4), после – столбцов, покрытых ими (блок 5). После этого вычеркиваются все столбцы и строки, найденные в блоках 4,5 (блок 6).Вычеркиваются антиядерные строки (блок 7). Вычеркиваются поглощающие столбцы (блок 8). Вычеркиваются поглощаемые строки (блок 9). Если в результате выполнения блоков 6–9 текущая таблица покрытий изменилась, то выполняется блок 4; иначе следует вывод найденного кратчайшего покрытия в виде номеров строк, покрывающих таблицу. Затем конец алгоритма.

3.5 Подпрограммы основного алгоритма

Функция MOJNO_LI(A) ведет поиск пустых столбцов, то есть не покрываемых ни одной строкой. Приложения. Организуется цикл по всем столбцам (блоки 1–6). В каждом столбце идет счет нулей (счетчик i инициализируется в каждом проходе – блок 2; счет ведется в блоке 5), то есть если встречается хотя бы одна единица (проверка в блоке 3), то происходит переход в следующий столбец. Алгоритм работает до тех пор, пока не будет достигнут конец таблицы (то есть конец цикла по j, блок 6) либо пока не будет сосчитано m нулей в одном столбце (проверка условия в блоке 4), то есть i=m. Функция возвращает 0, если найдено m нулей, и 1, если достигнут конец таблицы.
Функция YAD-STROKA(A) ведет поиск ядерных строк. В блоке 1 S инициализируется значением 0. Далее организуется цикл по всем столбцам (блок 2). Обнуляем текущую сумму (блок 4) и считаем сумму в j-м столбце (цикл в блоках 5–7 и собственно суммирование элементов в блоке 6). Далее сравниваем полученную сумму S с 1 (блок 8). Если текущая сумма равна 1, запоминаем её и номеру этого столбца присваиваем 0 (блок 9), иначе переходим к следующему столбцу. Таким образом, по окончании цикла по j в переменной yad stroka(A) будет храниться массив ядерных строк.
Функция ANTI_STROK(A) ведет поиск антиядерных строк. Переменной S2 присваивается значение 0. Организовывается цикл по строкам. Ищется сумма каждой строки и если она равна 0, то строка вычеркивается. Если нет, то переходим к следующей строке.
Процедура VICHEK(A) реализует вычеркивание столбцов, покрытых ядерными строками. Аналогично данная процедура работает и для самих ядерных строк, и для антиядерных строк, поглощающих столбцов, поглощаемых строк. Чтобы данный столбец (строку) «вычеркнуть», необходимо поставить 1 на его (ее) пересечении с нулевой строкой (столбцом).
Процедура VIVOD(P) реализует вывод полученного множества строк из массива P. Для этого организуется цикл по элементам массива Р (блоки 1–4), в котором проверяется отмечен ли номер строки i единицей (блок 2). Если да, то выводится номер строки i (блок 3).

Последний раз редактировалось sasha1988; 26.05.2012 в 20:23.
sasha1988 вне форума Ответить с цитированием
Ответ
Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Составить болк-схемы. Света=) Помощь студентам 7 05.04.2013 22:40
Составить блок-схемы алгоритма doug1as Помощь студентам 2 07.04.2012 19:36
Составить блок-схемы kazarcev Помощь студентам 2 22.12.2010 21:24
Нужно составить 2 блок-схемы bwitcher Помощь студентам 5 23.09.2010 19:52
составить блок-схемы Vints Помощь студентам 4 06.02.2010 21:45

Реклама для незарегистрированных, регистрация на форуме