Рассматриваются n лучей,проведённых в плоскости из точки О.Углы между соседними лучами равны 2pi/n.На лучах выбраны точки A1,А2..An и из этих точек как из центров проведены окружности,проходящие через точку O.Необходимо вычислить площадь фигуры,образованную всеми окружностями. В этом как раз вся и проблема. Все идеи свои я исчерпал.Если у вас есть свои размышления,прошу напишите их.
Вот рисунок:
М
Сообщения объеденены ... а на следюющий раз знай, что есть кнопака "правка" klem4
klem4
11.11.2005 2:42
Цитата
.Необходимо вычислить площадь фигуры,образованную всеми окружностями.
А можешь показать где такое есть на твоем рисунке ? Я например не вижу пересечения левой окружности и правой или верхней с нижней ... да и вообще помойму данных маловато для решения...
volvo
11.11.2005 2:45
To: klem4 А кто тебе сказал "площадь, образованную пересечением всех окружностей"? Найти нужно:
Цитата
площадь фигуры, образованную всеми окружностями.
, а это не одно и то же. Нужна площадь самой фигуры, образованной окружностями...
klem4
11.11.2005 2:49
Так точно, теперь вижу ... прошу прощения за невнимателность.
Vardes
11.11.2005 3:51
Ну вот в принципе площадь чего надо найти:
volvo
11.11.2005 21:56
По-моему, классическая задача для метода Монте-Карло...
Vardes
12.11.2005 1:04
А можно как-то этот метод Монте-Карло пояснить?
volvo
12.11.2005 1:18
Можно... Допустим, у тебя есть прямоугольник, в который полностью помещается твоя фигура, и ты точно знаешь его площадь. Тогда ты генерируешь большое количество случайных точек (чем больше точек - тем точнее результат), точно находящихся внутри прямоугольника, и проверяешь, сколько из них попадают в твою фигуру (зная координаты центров всех окружностей и их радиусы, несложно вычислить, попадает ли заданная точка в фигуру)...
Естественно, что чем больше точек попадут внутрь твоей фигуры, тем ее площадь больше А саму площадь вычисляешь так:
Цитата
S фигуры = S прямоугольника * ({Число попаданий} / {Общее число сгенерированных точек})
(бери число испытаний в районе 500 тыс - 1 млн, и в течении 5-7 секунд получай ответ...)
Vardes
12.11.2005 2:23
Тогда у меня возникают такие вопросы,как же мне задать мой прямоугольник,ведь количество лучей у меня не ограничено,и может доходить до 10,15 и т.д. И ещё,бывет так,что окружности накладывается др. на др.,следовательно точка попадёт и в ту и в др. окружность.
volvo
12.11.2005 2:42
Цитата
как же мне задать мой прямоугольник, ведь количество лучей у меня не ограничено, и может доходить до 10,15 и т.д.
это совершенно безразлично... В любом случае ты ВСЕГДА можешь вычислить самую верхнюю/нижнюю и левую/правую точки фигуры... По ним и строй прямоугольник...
Цитата
И ещё,бывет так,что окружности накладывается др. на др.,следовательно точка попадёт и в ту и в др. окружность.
Нет. Как только точка попала в какую-то окружность, вся дальнейшая работа с этой точкой прекращается, ведь она УЖЕ внутри фигуры, и ты переходишь к следующей точке...
Вот тебе пример (по твоему же рисунку), как выбрать прямоугольник...
Vardes
12.11.2005 4:20
Тогда получается,что мне надо вводить оси координат,если речь уже заходит о координатах,а как я могу их воодить,если все точки имеют положительное значение.
volvo
12.11.2005 4:52
To: Vardes Ну вот скажи мне, что именно тебе не понятно? Какие точки имеют положительное значение? Ты что, не умеешь генерировать отрицательные случайные числа? Кто тебе запрещает их генерировать?
Это первое. А второе, я не говорю о глобальных координатах. Ты вполне можешь принять свою систему координат, в которой точка пересечения осей будет не (0, 0) а, скажем, (100, 100)... Это ничего не меняет. Если ВЕСЬ график начерчен в одной системе координат, результат будет правильным...
Кстати, программа, вычисляющая площадь твоей фигуры (вместе с графическим представлением) занимает меньше 150 строк...
Vardes
12.11.2005 22:29
Ну вот введу я систему координат,мне необходимо чтобы все лучи выходили из одной точки(это ладно),но и углы между лучами должны быть равными.И ещё,мой препод будет вводить только радиусы этих окружностей(2,3,4 и т.д) и всё,а не координаты центров окружностей. И генерировать числа я пока тоже не умею,т.к. опыта у меня немного.Ещё пробовал решать эту задачу через центральный угол,найдя его можно пощитать площадь кругового сектора.Рассчитав площадди всех секторов,можно найти площадь и всей фигуры.Вот. Но тут есть загвоздка,дело в том,что если окружностей много,то происходит большое количество наложений,чуть ли одна не вписывается в др.,поэтому условия все предусмотреть очень сложно.
volvo
12.11.2005 22:40
To: Vardes Полярную систему координат еще никто не отменял Там как раз очень просто реализовать то, что ВСЕ лучи выходят их одной точки (r = 0), и углы между лучами равны: (Phi изменяется с шагом 360 div n, где n - количество лучей)...
Для того, чтобы узнать координаты центра окружности в полярной СК достаточно на соответствующем луче поставить точку, для которой удаление от центра координат r = {нужный тебе радиус}...
А уже потом, когда у тебя есть все координаты в полярной CK, переводишь их в декартову и делаешь то, что я тебе написал в посте №8.
Кстати, для генерации случайного числа X в интервале -100 .. 100 достаточно сделать
X := Random(201) - 100;
Vardes
13.11.2005 0:12
Значит я так понимаю,что радиусы окружности и лучи можно задать таким образом.Где L-это полярная ось,P-центр окружности,и углы. Вот рисунок:
Vardes
13.11.2005 0:16
А декартовы координаты тогда можно будет выразить так:x=p*cos угла 360/n; y=p*sin угла 360/n.
volvo
13.11.2005 0:22
Правильно понимаешь... Еще какие-то затруднения?
Vardes
13.11.2005 0:53
Да,необходимо определить принадлежит ли точка к плоскости какой-то из наших окружностей,чтобы её нам запомнить и разделить потом на общее количество таких точек. Ещё хотел по-больше узнать о генерации случайного числа x и y:нам надо брать те границы чисел,которыми у нас ограничен прямоугольник.НАпример он у нас ограничен следущими координатами 4 точек6,0);(-5,0);(0,4);(0,-7),как тогда нам сгенерировать числа по x и y.
Vardes
13.11.2005 1:13
Цитата
Да,необходимо определить принадлежит ли точка к плоскости какой-то из наших окружностей,чтобы её нам запомнить и разделить потом на общее количество таких точек.
Есть такая идея проверять ту или иную точку,образует ли она радиус вписанной окружности в нашу(конечно же,центр у них должен быть одинаковым)если образует,то мы её запоминаем.
volvo
13.11.2005 1:26
To: Vardes Ты что, издеваешься? Геометрию учил? У тебя есть координаты центра каждой окружности, так? Их радиусы тоже есть, так? Допустим, сгенерировал точку с координатами (point_x, point_y). Дальше - вот так:
i := 1; found := false;
while (i <= n) andnot found dobeginif sqrt(sqr(x[i] - point_x) + sqr(y[i] - point_y)) < radius[i] then found := true;
inc(i)
end;
{
если found = true, точка (point_x, point_y) находится
внутри хотя бы одной окружности, иначе - не попадает ни в одну
}
вот и все...
Vardes
13.11.2005 1:42
Блин,точно... Просто у меня уже голова кипит от этой задачи,но цель уже поставлена,поэтому и пытаюсь всякими извращёнными способами достигнуть её.НУ всё же остаётся поставленный вопрос про генерирование точки в посте №18.
volvo
13.11.2005 2:23
Значит, у тебя прямоугольник ограничен -5 <= x <= 6 и -7 <= y <= 4?
Общий случай: чтобы сгенерировать случайное число в интервале [a .. b]: X := random(b - a + 1) + a;
Vardes
13.11.2005 16:46
Вот реализация части програмного кода,до нахождения max и min значения x и y.
Код
const pi=3.14159; var n,i:integer; miny,maxy,minx,maxx,r,x,y:real; mas:array[1..50] of real; begin Writeln('‚Введите кол-во окружнростей-'); readln(n); Writeln('‚Введите радиус окружностей-'); minx:=0;maxx:=0; miny:=0;maxy:=0; for i:=1 to n do readln(mas[i]); for i:=1 to n do begin
x:=mas[i]*(cos(2*pi/n*(i-1)));{нахождение декартовых координат} y:=mas[i]*(sin(2*pi/n*(i-1))); writeln(x:2:2,' ',y:2:2); {нахождение min и max значения x и y}
if x-mas[i]<=minx then minx:=x-mas[i]; if x+mas[i]>=maxx then maxx:=x+mas[i]; if y-mas[i]<=miny then miny:=y-mas[i]; if y+mas[i]>=maxy then maxy:=y+mas[i]; end; writeln(minx:2:2,' ',maxx:2:2,' ',miny:2:2,' ',maxy:2:2) end.
volvo
13.11.2005 16:52
To: Vardes Ну, и что нам делать с этим кодом? Если уж выкладываешь, то или выкладывай полный код (когда закончишь), или задавай вопросы (если что-то не получается...)
Vardes
13.11.2005 18:16
Правилен ли будет код для генерации случайных точек и их проверки(ссылаясь на код выше),так как у меня идёт зацикливание.
Код
var found:boolean; point_x,point_y:integer; begin randomize; point_x:=random(round((maxx-minx+1)+minx)); point_y:=random(round((maxy-miny+1)+miny)); Sum:=0; For i:=1 to n do While not found do begin If Sqrt(sqr(point_x-x)+sqr(point_y-y))<=mas[i] then found:=true; Inc(Sum); end;
Всё исправил,но всё равно идёт зацикливание. не пойму в чём дело.
Код
const pi=3.14159; var found:boolean; sum,n,i:integer; point_x,point_y,miny,maxy,minx,maxx,r,x,y:real; mas:array[1..50] of real; begin Writeln('‚Введите кол-во окружнростей-'); readln(n); Writeln('‚Введите радиус окружностей-'); minx:=0;maxx:=0; miny:=0;maxy:=0; for i:=1 to n do readln(mas[i]); for i:=1 to n do begin
x:=mas[i]*(cos(2*pi/n*(i-1)));{нахождение декартовых координат} y:=mas[i]*(sin(2*pi/n*(i-1))); writeln(x:2:2,' ',y:2:2); {нахождение min и max значения x и y}
if x-mas[i]<=minx then minx:=x-mas[i]; if x+mas[i]>=maxx then maxx:=x+mas[i]; if y-mas[i]<=miny then miny:=y-mas[i]; if y+mas[i]>=maxy then maxy:=y+mas[i]; end; writeln(minx:2:2,' ',maxx:2:2,' ',miny:2:2,' ',maxy:2:2) begin randomize; point_x:=random(round(maxx-minx+1))+minx; point_y:=random(round(maxy-miny+1))+miny; Sum:=0; For i:=1 to n do While not found do begin If Sqrt(sqr(point_x-x)+sqr(point_y-y))<=mas[i] then found:=true; Inc(Sum); end; writeln(sum); end.
volvo
13.11.2005 20:10
Данные, которые вводишь, приведи... И объясни, что значит "зацикливание"...
Ну, я же тебе не так говорил делать !!! Внимательно читай пост №20. Условие под последним While может и не закончиться. Вот так перепиши его (нужно же ограничивать перебор числом окружностей):
While (i <= n) and (not found) dobegin
Кстати, а с каким именно X и Y ты производишь операции? Ты их сохранил куда-то (в массив), когда преобразовал из полярной СК? Я у тебя в коде этого не увидел... Более того, у тебя даже массива для этого не описано...
Vardes
13.11.2005 20:27
Провожу такой ввод данных: n- кол-во окружностей и ввожу радиус окружности,переводя его в массив mas[1..n].Вот и все данные. Проблема в том,что постоянно работает цикл while как взял i=1,так постоянно и гоняет себя не переходя на др. значения i.Переделал и всё равно гоняет.
volvo
13.11.2005 20:38
Я тебе уже написал почему... Вот НЕзацикливающийся вариант. Я не проверял все формулы, если там все правильно, то тебе осталось только зациклить генерацию точки, сделать это несколько сот тысяч раз (не меньше 200000-250000, лучше - несколько миллионов), посчитать количество попаданий, и вычислить площадь (как - см. пост №8)...
Vardes
13.11.2005 21:17
значит генерация происходит по одной точке,если я правильно понимаю.Как же тогда можно генерировать несколько тысяч раз,если у нас промежуток по x[-4:5],а по у [-3;9].Принцип не могу понять.
volvo
13.11.2005 21:20
var amount: longint;
...
for amount := 1to200000dobegin
randomize;
point_x:=random(round(maxx-minx+1))+minx;
point_y:=random(round(maxy-miny+1))+miny;
i := 1; found := False;
While (i <= n) andnot found dobeginIf Sqrt(sqr(point_x-x[i])+sqr(point_y-y[i]))<=mas[i] then found:=true
else inc(i);
end;
write(point_x:3:3, ', ', point_y:3:3);
if found then writeln(' is inside circle #', i)
else writeln(' is outside');
end;
у тебя сгенерируется 200000 точек и каждая проверится на попадание в фигуру. Только надо организовать подсчет (вместо Writeln)
Vardes
13.11.2005 21:45
так это всё понятно,я про принцип спрашивал,откуда берётся такое большое кол-во точек,если у нас промежуток маленький.
volvo
13.11.2005 21:58
To: Vardes А тебе все равно, какой у тебя промежуток. Если у тебя прямоугольник (граничные точки) размером 5*5, а сама фигура - размером 3*3, я что, не могу сгенерировать 5 миллионов точек, КАЖДАЯ из которых будет находиться в прямоугольнике? И проверить, сколько попадет в фигуру? Пускай из них будет по полмиллиона точек повторяться, это НЕ твоя проблема. Это и есть Monte-Carlo (Метод Рулетки)
Vardes
13.11.2005 22:12
Ну ведь каждая сгенерированная точка имеет свои координаты,для вещественного типа их можно сколько угодно сгенерировать,а если у нас генерирование идёт целых чисел, да и промежуток небольшой,то как тогда поступать.
Теперь более ясно? Можно увеличить множитель до 1000, только не перестарайся, макс. число допустимое как параметр для Random должно быть 65535 ...
Altair
13.11.2005 22:29
Vardes, итоговую программу, выложи пожалуйста здесь. Спасибо. (думаю как метериал для FAQ использовать )
Vardes
13.11.2005 22:54
А почему тогда одно и то же значение он по 100 раз просматривает. И ещё вопрос,идёт генерация точек,анализируется например 2 пересекаемые окружности,тогда точки попавшие в область пересечения окружностей будут суммироваться относительно первой и второй,или только относительно одной из них(в которую они попадут первыми).Что предусматривает метод Монте-Карло?
volvo
13.11.2005 22:58
To: Vardes Ты ответы мои ВНИМАТЕЛЬНО читал? Я кому это все пишу?
Цитата(Пост №10)
Как только точка попала в какую-то окружность, вся дальнейшая работа с этой точкой прекращается, ведь она УЖЕ внутри фигуры, и ты переходишь к следующей точке...
Цитата
А почему тогда одно и то же значение он по 100 раз просматривает.
Это ты к чему? КАКОЕ значение "он" (кстати, кто это ОН?) просматривает по 100 раз. Можно более четко выражать свои мысли?
Vardes
13.11.2005 23:06
Код
write(point_x:3:3, ', ', point_y:3:3);
Если приостановить процесс,то увидишь,что значения сгенерированных точек повторяются.Это как объяснить?
volvo
13.11.2005 23:34
Ну, во-первых, они СЛУЧАЙНЫЕ, то есть могут и повторяться. А во вторых - посмотри лог работы программы, генерирующей 1000 точек (так, как я показал в посте №36). Что-то я не вижу тут явных повторений
Vardes
14.11.2005 0:17
Вот программа,но почему-то слишком долго она генерирует точки,и большая очень погрешность(если взять только одну окружность).
volvo
14.11.2005 0:58
To: Vardes Я устал уже писать одно и то же. Ты не хочешь замечать того, что я делаю? Это нужно не мне, а тебе прежде всего !!! Какой точности ты хочешь добиться, если у тебя точки генерируются с точностью до целых? Сколько раз я должен писАть, КАК генерировать точки с точностью до сотых? Больше не буду повторять. Да и 50000 точек маловато. У меня после небольшого исправления твоей программы полмиллиона точек отработало за 4 секунды и дало для одной окружности радиусом 6 результат 113.091 Это первое.
А второе - ты сначала отладь сам алгоритм, а уж увеличением быстродействия займешься потом. А его можно ОЧЕНЬ сильно ускорить: 1) выносишь из цикла то, что можно вынести (в цикле постояноо вычисляется одно и то же) 2) тип с Real меняешь на Double - быстродействие РЕЗКО увеличивается (причины - смотри в FAQ-е)
Vardes
14.11.2005 1:15
Ну у меня совсем небольшой опыт по программированию,чтобы легко отрабатывать алгоритм. А говорить о том,что я невнимательно читаю ваши посты не надо,как генерировать точки с точностью до сотых,я понял.До этого проблема у меня была в том,что если генерировать около 200 тыс. точек,то приходиться ждать около 20 сек.,и результат ещё отрицательный получается.
volvo
14.11.2005 2:31
Цитата
и результат ещё отрицательный получается.
А чтобы не было отрицательного результата, объяви переменную Sum не как Integer, а как LongInt... В Integer нельзя хранить числа больше 32767, и у тебя просто происходит переполнение, число "уходит" в минус... LongInt может хранить числа больше 2 миллиардов...
Vardes
14.11.2005 3:24
Ошибку в своём алгоритме я так найти и не могу,а то,что в нём есть ошибка-это точно,делал генерацию в полмиллиона,получил совсем др. значение площади окружности радиуса 6.
volvo
14.11.2005 15:42
Смотри, есть такое предложение: если у тебя не выходит с методом Монте-Карло, сделай почти Монте-Карло Просто перебирай с маленьким шагом все точки, лежащие внутри прямоугольника, и проверяй, какие из них попадают внутрь фигуры:
{
добавляешь эти описания:
}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 dobegin
point_y := miny;
while point_y <= maxy dobegin
i := 1; found := False;
While (i <= n) andnot found dobeginIf 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+1else 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.
Это уже будет работать быстрее алгоритма со случайными числами, т.к. "тяжелая" операция генерации чисел просто отсутствует, и заменена на гораздо более простую - перебор в цикле.
Но и это еще не предел... Как я уже писал выше, оптимизируем программу. 1) заменяем Real на Double 2) вместо того, чтобы в цикле выполнять Sqrt, можно ДО цикла возвести все mas[i] в квадрат, и потом сравнивать квадраты 3) целочисленные X := X + 1 заменяем на Inc(X). Вот что имеем:
sum:=0; none := 0;
tm_s:= MemL[$0040:$006c]; { контроль времени }for i := 1to n do
mas[i] := sqr(mas[i]);
point_x := minx;
while point_x <= maxx dobegin
point_y := miny;
while point_y <= maxy dobegin
i := 1; found := False;
While (i <= n) andnot found dobeginIf (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;
постепеннот доходим до max и на этом у нас циклы заканчиваются. А старый метод Монте-Карло уже никак нельзя изменить?
volvo
14.11.2005 17:55
Послушай, Vardes... Тебе не нравится, что Метод Монте-Карло (МК) работает МЕДЛЕННО, как я тебе его ускорю? А он ведь именно со случайными данными работает, так что придется Random использовать. Кроме того, ты не знаешь, сколько точек перебирается в моей последней программе? Я тебе скажу, больше 35 миллионов (для окружности радиусом 6), попробуй это число поставить в программку по методу MK, сколько часов ты будешь ждать? А если тебе нужно еще точнее, то замени Divider на 1000, и получишь более 140 миллионов точек... Будешь сравнивать время выполнения?
Так что ты для себя реши, тебе нужен ИМЕННО метод Монте-Карло, или БЫСТРОЕ решение. А смешивать их не надо, не получится...
Vardes
14.11.2005 18:32
Нет,что ВЫ,мне нравятся оба метода,второй даже больше,т.к я его хорошо понял. И ещё я хотел сказать,что после общения с вами я узнал столько много нового,что просто вам очень сильно благодарен, т.к сам по себе я ещё чайник в программировании.
*Наверно рекорд у вас поставил по кол-ву сообщений*
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.