Площадь фигуры,образованная окружностями. Опции

[volvo]

Ну, во-первых, они СЛУЧАЙНЫЕ, то есть могут и повторяться. А во вторых - посмотри лог работы программы, генерирующей 1000 точек (так, как я показал в посте №36). Что-то я не вижу тут явных повторений

[Vardes]

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

Сообщение отредактировано: Vardes - 14.11.2005 0:25

[volvo]

To: Vardes
Я устал уже писать одно и то же. Ты не хочешь замечать того, что я делаю? Это нужно не мне, а тебе прежде всего !!! Какой точности ты хочешь добиться, если у тебя точки генерируются с точностью до целых? Сколько раз я должен писАть, КАК генерировать точки с точностью до сотых? Больше не буду повторять. Да и 50000 точек маловато. У меня после небольшого исправления твоей программы полмиллиона точек отработало за 4 секунды и дало для одной окружности радиусом 6 результат 113.091
Это первое.

А второе - ты сначала отладь сам алгоритм, а уж увеличением быстродействия займешься потом. А его можно ОЧЕНЬ сильно ускорить:
1) выносишь из цикла то, что можно вынести (в цикле постояноо вычисляется одно и то же)
2) тип с Real меняешь на Double - быстродействие РЕЗКО увеличивается (причины - смотри в FAQ-е)

[Vardes]

Ну у меня совсем небольшой опыт по программированию,чтобы легко отрабатывать алгоритм.
А говорить о том,что я невнимательно читаю ваши посты не надо,как генерировать точки с точностью до сотых,я понял.До этого проблема у меня была в том,что если генерировать около 200 тыс. точек,то приходиться ждать около 20 сек.,и результат ещё отрицательный получается.

[volvo]

и результат ещё отрицательный получается.

А чтобы не было отрицательного результата, объяви переменную Sum не как Integer, а как LongInt... В Integer нельзя хранить числа больше 32767, и у тебя просто происходит переполнение, число "уходит" в минус... LongInt может хранить числа больше 2 миллиардов...

[Vardes]

Ошибку в своём алгоритме я так найти и не могу,а то,что в нём есть ошибка-это точно,делал генерацию в полмиллиона,получил совсем др. значение площади окружности радиуса 6.

[volvo]

Смотри, есть такое предложение: если у тебя не выходит с методом Монте-Карло, сделай почти Монте-Карло Просто перебирай с маленьким шагом все точки, лежащие внутри прямоугольника, и проверяй, какие из них попадают внутрь фигуры:

{
  добавляешь эти описания:
}
const
  divider = 500;
  delta = 1/ divider;
var
  sum, none: longint;
  {
    ... и все остальные
  }

begin
{
  Здесь - все, что касается нахождения minx, miny, maxx, maxy,
  как и было раньше... А вот дальше:
}
  sum:=0; none := 0;
  tm_s:= MemL[$0040:$006c]; { контроль времени - начали отсчет }

  point_x := minx;
  while point_x <= maxx do begin

    point_y := miny;
    while point_y <= maxy do begin

      i := 1; found := False;
      While (i <= n) and not found do begin
        If Sqrt(sqr(point_x-x[i])+sqr(point_y-y[i]))<=mas[i] then found:=true
        else inc(i);
      end;
      if found then sum:=sum+1 else none := none+1;

      point_y := point_y + delta;
    end;

    point_x := point_x + delta;
  end;

  tm_f:= MemL[$0040:$006c]; { отсчет окончен }
  tm_f:=tm_f - tm_s; { замеряем время }

  writeln('time: ', tm_f);
  writeln('Внутри: ', sum, ' снаружи: ', none);
  S2:=S1*(sum/(sum+none));
  writeln('Площадь фигуры = ',S2:2:2);
end.

Программа полностью:  __VARD_1.PAS ( 1.61 килобайт ) Кол-во скачиваний: 562


Это уже будет работать быстрее алгоритма со случайными числами, т.к. "тяжелая" операция генерации чисел просто отсутствует, и заменена на гораздо более простую - перебор в цикле.

Но и это еще не предел... Как я уже писал выше, оптимизируем программу.
1) заменяем Real на Double
2) вместо того, чтобы в цикле выполнять Sqrt, можно ДО цикла возвести все mas[i] в квадрат, и потом сравнивать квадраты
3) целочисленные X := X + 1 заменяем на Inc(X). Вот что имеем:

  sum:=0; none := 0;
  tm_s:= MemL[$0040:$006c]; { контроль времени }

  for i := 1 to n do
    mas[i] := sqr(mas[i]);

  point_x := minx;
  while point_x <= maxx do begin

    point_y := miny;
    while point_y <= maxy do begin

      i := 1; found := False;
      While (i <= n) and not found do begin
        If (sqr(point_x-x[i])+sqr(point_y-y[i])) <= mas[i] then found:=true
        else inc(i);
      end;
      if found then inc(sum) else inc(none);

      point_y := point_y + delta;
    end;

    point_x := point_x + delta;
  end;

  tm_f:= MemL[$0040:$006c];
  tm_f:=tm_f - tm_s;

Программа полностью:  __VARD_2.PAS ( 1.66 килобайт ) Кол-во скачиваний: 590


Вторая программа выполняется быстрее первой почти в 25 раз !!!

[Vardes]

Значит если я понимаю правильно,то мы сгенерированным точкам присваиваем min значения,а потом используя

Код

     
point_y := point_y + delta;
point_x := point_x + delta

постепеннот доходим до max и на этом у нас циклы заканчиваются.
А старый метод Монте-Карло уже никак нельзя изменить?

[volvo]

Послушай, Vardes...
Тебе не нравится, что Метод Монте-Карло (МК) работает МЕДЛЕННО, как я тебе его ускорю? А он ведь именно со случайными данными работает, так что придется Random использовать. Кроме того, ты не знаешь, сколько точек перебирается в моей последней программе? Я тебе скажу, больше 35 миллионов (для окружности радиусом 6), попробуй это число поставить в программку по методу MK, сколько часов ты будешь ждать? А если тебе нужно еще точнее, то замени Divider на 1000, и получишь более 140 миллионов точек... Будешь сравнивать время выполнения?

Так что ты для себя реши, тебе нужен ИМЕННО метод Монте-Карло, или БЫСТРОЕ решение. А смешивать их не надо, не получится...

[Vardes]

Нет,что ВЫ,мне нравятся оба метода,второй даже больше,т.к я его хорошо понял.
И ещё я хотел сказать,что после общения с вами я узнал столько много нового,что просто вам очень сильно благодарен, т.к сам по себе я ещё чайник в программировании.

*Наверно рекорд у вас поставил по кол-ву сообщений*