подсчитать кусты роз, незнаю с чего начать Опции

[maksimla]

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

напишите а)идею решения задачи
б) написать программу сколько теперь маленких кустов.

Первичные данные записаны в файле duom.txt. На первой строчке написаны два натуральных числа отделенные пробелом числа n m (1<=n<=m<=100) На остальных n строчках написано m чисел неотделанных пробелом 0 или 1:0 показывает что в этом месте роз нету , 1 - есть.

результат записываем в файл rez.txt
первичные данные и результат пример
данные
3 12
110110110111
100010010111
111011010011
результат
4
обьяснение

11 11 11 111
1   1  1 111
111 11 1  11

видно что есть 4 куста роз

вместе с этой программой напишите генератор случайных чисел для этой программы

я так незнаю с чего начать и что делать чтобы программу эту выполнил только думаю сперва все в двойной массив записать а как дальше незнаю помогите


вот написал генератор но неправильно записывает цифры в файл почему? исправьте пожалуйста

program Bevarde1;
var  v: array [1..100,1..100] of byte;
i,j,n,m:integer;
 t:text;
begin
   assign (t, 'duom.TXT');
 rewrite (t);
  randomize;
  n:= random(10)+1;
  m:= random(10)+1;
  writeln(t,n,' ',m);
   for i:=1 to n do
    for j:=1 to m do
    v[j,i]:=random(2);
    
    for i:=1 to n do
    begin
    writeln ;
    for j:=1 to m do
    write(t,v[j,i]);
    writeln
    end;
  close(t);
end.

Сообщение отредактировано: Lapp - 15.02.2009 16:54

[Lapp]

Теперь про рекурсию..
Если будет не очень понятно - перейди к примеру в конце сообщения.

можете обеснить как у вас эта рекурсия работает как она дальше идет
я и неразобрал подсчитал только это что сперва происходит

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

1. Изначально предполагается, что 1 означет розу, а 0 - ее отсутствие. Но я собираюсь метить связные группы (кусты) их номером (в каждую точку, где роза, буду помещать номер этой группы). Но нумерацию лучше начинать с 1, а это конфликтует с признаком наличия розы. Чтобы их не путать, я сменил признак наличия розы с 1 на -1 (не в файле, конечно, а в массиве).

2. Переменная k - счетчик групп (кустов). Сначала он равен 0. Потом я прохожу в двойном цикле по всему массиву. Как только наткнулся на -1 (роза), я увеличиваю k на 1 и захожу в Mark.

3. В процедуре Mark я мечу эту позицию номером группы (k). Затем я проверяю все соседние точки (слева, справа, сверху, снизу и еще четыре по диагоналям, если нужно). Для этого я снова захожу в Mark уже для этих (соседних) точек - но только если в этой точке роза (то есть -1). Зайдя в нее, я снова мечу и снова проверяю соседние точки - теперь уже от нее. И так повторяется до тех пор, пока не кончатся соседние точки, помеченные -1 (роза). В этом случае рекурсивный вызов в Mark уже не проичходит (ни одно из условий не выполняется), и мы выходим из нее, а потом из экземпляра Марк, который ее вызвал, и так далее. В результате, к моменту выхода из первоначально вызванного экземпляра Mark (который вызван из главного двойного цикла) вся текущая группа будет помечена своим номером.

4. Тогда мы продолжим цикл до следующей розы (-1), которая будет означать встречу нового куста (потому что все розы уже пройденных кустов уже помечены номерами кустов, а не -1). Тогда процесс отмечания куста повторяется, но уже с новым номером.

Примечание:
Вложенных (рекурсивных) вызовов Mark может быть очень много (в худшем случае - столько, сколько роз в кусте). На рекурсивный вызов уходит довольно много ресурсов стека. Поэтому я сказал в начале, что этот метод годится только для не очень больших размеров сада (а точнее, кустов).

Вот, если хочешь, наглядный пример.
Допустим, есть дачный поселок, состоящий из квадратых участков (домов). В некоторых домах живут, а некоторые пустуют (еще не приехали из города). Предположим, что надо всех оповестить, что завтра будет собрание всех жителей, кто есть здесь сейчас. Староста поселка подходит к какому-нибудь дому и говорит хозяину: "Завтра будет собрание всех присутствующих; скажи об этом всем своим соседям и попроси их сделать то же самое". Хозяин честно идет к каждому своему соседу и передает эту фразу. Каждый сосед, тоже делает это. Вот это и есть рекурсия.
Будут ли таким образом оповещены ВСЕ присутствующие жители поселка? Возможно, что и нет. Почему? Потому что может случиться так, что есть прослойка нежилых домов, через которую информация не проникнет. То есть в результате будут оповещены только все жители этой группы (куста) домов - но они будут оповещены ВСЕ. Вот это и есть процесс пометки одного куста. Но это не есть полная модель твоей задачи.