Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
yoink
0 / 0 / 0
Регистрация: 04.11.2009
Сообщений: 4
#1

Поиск прямоугольников. - C++

04.11.2009, 13:58. Просмотров 1129. Ответов 5
Метки нет (Все метки)

Есть такая задача: дан массив 100х100 состоящий из нулей и единиц. Из единиц построены прямоугольники, так, что они не могут совпадать и пересекаться (между прямоугольниками всегда нули). Надо написать программу, которая считает эти прямоугольники.
Основное задание я сделал, но вот у меня такие проблемы: массив нужно задавать произвольно, то есть чтобы он создавал эти прямоугольники в произвольных местах и с заданным условием, чтобы они не пересекались. Помогите, пожалуйста, такое реализовать на C.
Над самим алгоритмом думал и пришел к такому заключению: задаем произвольные координаты двух точек, проверяем, нет ли рядом единиц, если есть смещаемся от них, и по двум этим точкам строим прямоугольник. Но все равно не понимаю, как это реализовать.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.11.2009, 13:58     Поиск прямоугольников.
Посмотрите здесь:

C++ Площади прямоугольников
C++ Пересечение прямоугольников
C++ класс прямоугольников
Пересечение прямоугольников на плоскости C++
C++ С++ Метод прямоугольников
Размещение прямоугольников C++
C++ вложенность прямоугольников
метод прямоугольников C++
Даны стороны трех прямоугольников Найти периметры и площади этих прямоугольников C++
Объединение прямоугольников (количество объединенных прямоугольников минимально) C++
Площадь пересечения прямоугольников C++
Метод прямоугольников C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
04.11.2009, 22:36     Поиск прямоугольников. #2
Найти прямоугольники.
Достаточно посчитать левые верхние углы. Сколько углов - столько и прямоугольников.

Построить прямоугольники.
N - число попыток.
Сначала поле 100 x 100 не заполняем, а просто получим координаты всех.

Строим случайную пару (X,Y) - координаты левого верхнего угла.
Потом строим случайную пару (W,H) - ширина и высота.
Проверяем что построенный прямоугольник не пересекается с другими уже построенными.
И не лежит рядом !
Если все нормально - записываем координаты.
Если не нормально - отбрасываем.

Повторяем процедуру N раз.

Потом по заданным координатам заполняем поле 100x100.

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

Тест труднее сделать, чем алгоритм подсчета
yoink
0 / 0 / 0
Регистрация: 04.11.2009
Сообщений: 4
05.11.2009, 00:22  [ТС]     Поиск прямоугольников. #3
Я конечно понимаю, что код и метод индусские (зато все свое) Но помогите найти ошибку. Пишет, что "zadacha3 вызвал ошибку при использовании стека в модуле zadaxha3.exe"
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <math.h>;
#include <stdio.h>;
#include <conio.h>;
#include <stdlib.h>;
void main ()
{int mas[100][100],i,j,t,k,b = 0,n,kol,proverka=0;
float tI,tJ,tW,tH;
randomize();
printf ("\n Vvedite koli4estvo", kol);
scanf ("%d",&kol);
for (i=0; i<=kol;i++)
   {tI = double(rand()%100);
    tJ = double(rand()%100);
    tH = double(rand()%100);
    tW = double(rand()%100);
    proverka = 0;
    for (j=(tI-1);j<(tI+tW+2);j++)
      {for (k=(tJ-1);t<(tJ+tH+2);t++)
    {if (mas[j][t] == 1)
         proverka = 1;}
       }
    if (proverka != 0)
     break;
    for (j=tI;j<(tI+tW);j++)
      {for (k=tJ;t<(tJ+tH);t++)
     mas[j][t] = 1;}
    }
   for (i=0;i<100;i++)
    {for (j=0; j<100; j++)
         {if (mas[i][j] == 1)
         {for (t=0;t<100;t++)
              {for (n = i;n<100; n++)
                if (mas[n][j+t] == 1)
                mas[n][j+t] = 0;
                if (mas[n][j+t] == 0)
                break;
              }
               if (mas[i][j+t+1] == 0)
               {b = b + 1;
                break;}
         }
         }
    }
    printf ("%d",b);
}
easybudda
Эксперт С++
9456 / 5469 / 927
Регистрация: 25.07.2009
Сообщений: 10,495
05.11.2009, 00:46     Поиск прямоугольников. #4
Цитата Сообщение от yoink Посмотреть сообщение
printf ("\n Vvedite koli4estvo", kol);
переменную kol отсюда уберите
printf ("\n Vvedite koli4estvo ");
и будет Вам счастье
yoink
0 / 0 / 0
Регистрация: 04.11.2009
Сообщений: 4
05.11.2009, 00:54  [ТС]     Поиск прямоугольников. #5
ой, точно ))
стыдно даже
но все равно ошибка в 35й строчке.
yoink
0 / 0 / 0
Регистрация: 04.11.2009
Сообщений: 4
08.11.2009, 16:35  [ТС]     Поиск прямоугольников. #6
В общем) Сегодня решил добить эту задачу. Решил сделать так: пусть вообще произвольное количество прямоугольников будет. И для того, чтобы нагляднее решить задачу, пускай будет массив 10 на 10 и будет выводиться, чтобы легче посчитать было. Вопрос: ошибка явно в алгоритме. Помогите пожалуйста.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <math.h>;
#include <stdio.h>;
#include <conio.h>;
#include <stdlib.h>;
void main ()
{int mas[11][11],i,j,t,k,b = 0,n,kol,l;
randomize();
for (i=0;i<10;i++) {
 for (j=0;j<10;j++) {
  mas[i][j] = 1;
 }
}
for (i=10;i<=10;i++)
  for (j=0;j<11;j++)
   mas[i][j] = 0;
for (j=10;j<=10;j++)
  for (i=0;i<11;i++)
    mas[i][j] = 0;
kol = random(10);
i=0;
 do
    {l = random(10);
    for (j=l;j<=l;j++)
      for (n=0;n<10;n++)
    mas[j][n] = 0;
    for (n=l;n<=l;n++)
      for (j=0;j<10;j++)
    mas[j][n] = 0;
     i++;
    }
    while (i<=kol);
for (i=0;i<11;i++)
  {for (j=0;j<11;j++)
     {printf (" %d ",mas[i][j]);}
      printf ("\n");}
   for (i=0;i<10;i++)
    {for (j=0; j<10; j++)
         {if (mas[i][j] == 1)
         {for (t=0;t<10;t++)
              {for (n = i;n<10; n++)
                if (mas[n][j+t] == 1)
                mas[n][j+t] = 0;
                if (mas[n][j+t] == 0)
                break;
              }
               if (mas[i][j+t+1] == 0)
                           {b = b + 1;
                break;}
         }
         }
    }
    printf ("\n %d",b);
}
Yandex
Объявления
08.11.2009, 16:35     Поиск прямоугольников.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru