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

[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]

Вот так надо делать файл:

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;
  m:= random(10)+1;
  n:= random(m)+1;   { так как n<=m }
  writeln(t,n,' ',m);
  for i:=1 to n do begin
    for j:=1 to m do Write(t,random(2));
    WriteLn(t);
  end;
  close(t);
end.

Тебе тут не нужно было заполнять массив, можно сразу писать в файл.

Теперь по задаче. Как я понял, тебе надо подсчитать количество связных областей единиц. По этому поводу один вопрос: диагональ не считается связью? То есть вот такая конфигурация:

1100
1100
0011
0011

- это две области или одна? Но это не принципиально, зависит только как обходить окрестность.

Если размеры сада не слишком велики, то можно использовать рекурсию. Примерно вот так:

const
  l=100;

var
  a,b: array[1..l,1..l]of integer;
  i,j,m,n,k: integer;
  f: text;
  c: char;

procedure Mark(i,j: integer);
begin
  a[i,j]:=k;
  if (i>1)and(a[i-1,j]=-1) then Mark(i-1,j);
  if (i<n)and(a[i+1,j]=-1) then Mark(i+1,j);
  if (j>1)and(a[i,j-1]=-1) then Mark(i,j-1);
  if (j<m)and(a[i,j+1]=-1) then Mark(i,j+1)
end;

begin
  Assign(f,'duom.txt');
  ReSet(f);
  ReadLn(f,n,m);
  for i:=1 to n do begin
    for j:=1 to m do begin
      Read(f,c);
      if c='1' then a[i,j]:=-1 else a[i,j]:=0;
      b[i,j]:=0
    end;
    ReadLn(f)
  end;
  Close(f);
  k:=0;
  for i:=1 to n do for j:=1 to m do if a[i,j]=-1 then begin
    Inc(k);
    Mark(i,j)
  end;
  WriteLn(k,' bushes');
  for i:=1 to n do begin
    for j:=1 to m do if a[i,j]>0 then Write(a[i,j]) else Write(' ');
    WriteLn
  end
end.

В этом решении я считаю, что связь только по горизонтали или вертикали (по диагонали не считается).

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

[maksimla]

наверное и по диагонали считается потомучто спрашивал сказали
первичные данные
2 5
11011
00100
результат
1

первичные данные
3 10
1101000111
1001000001
1111111111
результат
1

[Lapp]

наверное и по диагонали считается

Если по диагонали считается, то в процедуру Mark нужно добавить еще четыре строчки:

procedure Mark(i,j: integer);
begin
  a[i,j]:=k;
  if (i>1)and(a[i-1,j]=-1) then Mark(i-1,j);
  if (i<n)and(a[i+1,j]=-1) then Mark(i+1,j);
  if (j>1)and(a[i,j-1]=-1) then Mark(i,j-1);
  if (j<m)and(a[i,j+1]=-1) then Mark(i,j+1);
  if (i>1)and(j>1)and(a[i-1,j-1]=-1) then Mark(i-1,j-1);
  if (i>1)and(j<m)and(a[i-1,j+1]=-1) then Mark(i-1,j+1);
  if (i<n)and(j>1)and(a[i+1,j-1]=-1) then Mark(i+1,j-1);
  if (i<n)and(j<m)and(a[i+1,j+1]=-1) then Mark(i+1,j+1)
end;

- вот и все..

[maksimla]

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

идет так
a[1,1]=1;
a[2,1]=1;
a[3,1]=1;
a[3,2]=1;
a[3,3]=1;
все потом
end;
а потом строка
if (j>1)and(a[i,j-1]=-1)
потом
if (j<m)and(a[i,j+1]=-1)
потом
end;
и опять строка
if (j>1)and(a[i,j-1]=-1)
дальше запутался и какие данные уже идут может обьясните?

Добавлено через 13 мин.
На остальных n строчках написано m чисел неотделанных пробелом 0 или 1:0 показывает что в этом месте кустов роз нету , 1 - есть.

как понять что 1:0 и кустов роз нет надо будит наверное у приподователя спросить что он тут имел в виду и зачем написано знак : непонятно

может вы обьясните?

[Lapp]

Рекурсию объясню чуть позже, а сейчас вот про это:

как понять что 1:0 и кустов роз нет надо будит наверное у приподователя спросить что он тут имел в виду и зачем написано знак : непонятно
может вы обьясните?

Объясню, это несложно.
Вот оригинальная фраза:

На остальных n строчках написано m чисел неотделанных пробелом 0 или 1:0 показывает что в этом месте роз нету , 1 - есть.

В этой фразе пропущен один символ. Причем, на первый взгляд - совсем неважный. Этот символ - пробел. И он должен стоять после двоеточия (после ":"). Вот, смотри, так сразу становится понятнее:

На остальных n строчках написано m чисел неотделанных пробелом 0 или 1: 0 показывает что в этом месте роз нету , 1 - есть.

Но все же фраза построена плохо. Я бы ее построил так:

На остальных n строчках написано m чисел, неотделенных пробелом: 0 или 1. Ноль показывает что в этом месте роз нету , единица - есть.

Теперь понятнее? Правильность написания на любом языке важена, не только на Паскале . Ты только не обижайся, мы понимаем, что русский у тебя не родной язык, и стараемся вникать глубже.
Успехов тебе!

[maksimla]

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

Сообщение отредактировано: maksimla - 16.02.2009 0:37

[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 может быть очень много (в худшем случае - столько, сколько роз в кусте). На рекурсивный вызов уходит довольно много ресурсов стека. Поэтому я сказал в начале, что этот метод годится только для не очень больших размеров сада (а точнее, кустов).

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