Острова Опции

[Lapp]

LAPP - говорил, что поможешь реализовать блок-схему процедуры SCHET, а сам пропал куда-то.

А разве ты уже выложил последний рабочий вариант программы?..
Я слежу и каждый день проверяю..

Добавлено через 1 мин.
Кроме того, помочь - не значит сделать за тебя.
Ты выложи, что сделал (как ты это сделал со старым вариантом), я посмотрю и подправлю.. Ок?

[@^WARlock^@]

Последний рабочий вариант программы:
 OSTROVA.rar ( 9.27 килобайт ) Кол-во скачиваний: 309


Подскажи, по какому принципу работает твоя прога(моя процедура) подсчета островов. Может тогда и придумаю, как нарисовать блок-схему.

[Lapp]

Подскажи, по какому принципу работает твоя прога(моя процедура) подсчета островов

Сейчас попробую вспомнить..
Я просто введу комментарии в тот агоритм в первом посте.

[Lapp]

1. Обнуляем счетчик островов N.
Ну, это понятно.

2. Проходим по всему массиву до встречи первой -1.
Тоже понятно - идем до встречи с нехоженой землей. В самом начале в нашем массиве есть только 0 (вода) и -1 (земля). Затем земля перемаркировывается номером острова. Но -1 всегда означает землю, на которой мы еще не были (где не ступала нога человека ).

3. Если ни одной -1 не было найдено - выходим.
И это понятно - неизведанные земли кончились. Выход из процедуры.

4. Увеличиваем N на 1.
Если нашли -1 - значит, нашли новый остров. Увеличиваем счетчик островов.

5. Меняем значение найденной клетки на N.
Столбим землю. Вместо -1 записываем номер острова

6. Сбрасываем флаг.
Флаг будет установлен, если мы найдем новые клетки этого же острова (то есть -1 соседние к N). Он нужен нам, чтобы понять, когда закончится процесс перемаркировки текущего (N-го) острова.

7. Проходим циклом по всему массиву. Если текущий элемент равен -1, а один из его четырех соседей равен N, то меняем его на N и устанавливаем флаг.
Цикл по всему массиву - это двойной цикл по координатам, как обычно (по строчкам, сверху вниз). Перемаркировка текущего острова производится не за один цикл. Это я поясню потом на примере

8. Если флаг установлен - переходим к п.6
Установленный флаг означает, что соседние клетки были найдены. А это значит, что могут быть и соседние к новым найденным. Значит, надо пройти еще раз..

9. Если флаг сброшен - переходим к п.2
Сброшенный флаг значит, что за последний проход не было найдено новых соседних клеток к текущему острову. Значит, мы нашли все. Можно переходить к поиску нового острова.

Вот пример.
Представь себе остров, закрученный наподобие спирали (# означает -1, а ~ - воду, то есть 0 ):

Код

~~~~~~~~~~~~
~##########~
~#~~~~~~~~#~
~#~######~#~
~#~#~~~~#~#~
~#~#~~#~#~#~
~#~####~#~#~
~#~~~~~~#~#~
~########~#~
~~~~~~~~~~~~

Когда мы его только нашли, ситуация такая:

~~~~~~~~~~~~
~1#########~
~#~~~~~~~~#~
~#~######~#~
~#~#~~~~#~#~
~#~#~~#~#~#~
~#~####~#~#~
~#~~~~~~#~#~
~########~#~
~~~~~~~~~~~~

После первого прохода мы получим:

~~~~~~~~~~~~
~1111111111~
~1~~~~~~~~1~
~1~######~1~
~1~#~~~~#~1~
~1~#~~#~#~1~
~1~####~#~1~
~1~~~~~~#~1~
~11111111~1~
~~~~~~~~~~~~

Перемаркированы только те клетки, которые правее-ниже от пройденных.

После 2-го:

~~~~~~~~~~~~
~1111111111~
~1~~~~~~~~1~
~1~######~1~
~1~#~~~~#~1~
~1~#~~#~#~1~
~1~####~#~1~
~1~~~~~~1~1~
~11111111~1~
~~~~~~~~~~~~

После 3-го:

~~~~~~~~~~~~
~1111111111~
~1~~~~~~~~1~
~1~######~1~
~1~#~~~~#~1~
~1~#~~#~#~1~
~1~####~1~1~
~1~~~~~~1~1~
~11111111~1~
~~~~~~~~~~~~

Медленно продвигаемся наверх, по клетке за проход по всей матрице..
....
После 9-го:

~~~~~~~~~~~~
~1111111111~
~1~~~~~~~~1~
~1~##1111~1~
~1~#~~~~1~1~
~1~#~~#~1~1~
~1~####~1~1~
~1~~~~~~1~1~
~11111111~1~
~~~~~~~~~~~~

.....


После 11-го остается только одна клетка:

~~~~~~~~~~~~
~1111111111~
~1~~~~~~~~1~
~1~111111~1~
~1~1~~~~1~1~
~1~1~~#~1~1~
~1~1111~1~1~
~1~~~~~~1~1~
~11111111~1~
~~~~~~~~~~~~

После 12-го все клетки закрашены, но флаг все же установлен.
На 13-м проходе флаг установлен не будет: больше нет -1, соседних к 1.

Вот так. Алгоритм небыстрый, но работает корректно, не собъется ни на какой самой запутанной комбинации.

Ну что, сможешь составить блок-схему?

[@^WARlock^@]

У меня вот, что получилось:
 Процедура_SCHET.rar ( 5.05 килобайт ) Кол-во скачиваний: 340

[Lapp]

У меня вот, что получилось:

Пока что сыровато, я не стал вникать. Так в принципе направление верное.
В конце есть явная ошибка: выхода в конце нет и быть не может! Выход только в п.4.
И почему ты называешь выход "выводом"?..

[@^WARlock^@]

Пока что сыровато

Я в блок-схемах не силен. Может тогда предложишь свой вариант.

[@^WARlock^@]

И почему ты называешь выход "выводом"?

Как я понял, это выход в твоей проге, а в моей это вывод кол-ва островов, поэтому и "вывод".

Не много откорректировал блок-схему:
 Процедура_SCHET.rar ( 5.09 килобайт ) Кол-во скачиваний: 330


Сообщение отредактировано: @^WARlock^@ - 3.05.2007 5:22

[Lapp]

Я в блок-схемах не силен. Может тогда предложишь свой вариант.

Я вообще им не обучался..

Вот мой вариант:

В принципе, "поиск -1" тоже можно расписать. Но это уж ты сам, если захочешь..

[@^WARlock^@]

Решил перед сдачей проги окончательно её протестировать, и вот те здравствуйте,
каккой-то глюк:

1)Ввожу острова, их кол-во выводится правильно, в данном случае (14).

X~~XX~X~~~
~X~~~X~X~~
X~X~X~X~~~
~X~X~~~~~~
X~X~~~~~~~
~~~~~~~~~~

2)Снова ввожу острова, кол-во выводится либо правильно, либо почти.
3)Ввожу ту же комбнацию, что и в 1-ом случае, совершенно друго результат. 

Может ли это связано с тем, что отчистку поля я осуществляю путем отчистки экрана, а не массива
или куда там производится запись результатаов.

Подскажите, как от него(глюка) избавиться.