Пятничные задачки. Разомнем извилины.

← →
Думкин © (2005-09-16 13:34) [40]

> default © (16.09.05 13:28) [37]

Раз 0 обидели - корректность в вере не нуждается. Если конечно, не было ничьих.

← →
default © (2005-09-16 13:34) [41]

Думкин © (16.09.05 13:30) [39]
0+1+2=3:)13 тестов это улёт:)

← →
SergP. (2005-09-16 13:41) [42]

7. 40500000001

Сумма цифр от 1 до 9 равна 45
В каждом разряде каждая цифра встречается 100 000 000 раз
Всего разрядов 9

Итого 40500000000 и добавим 1 (это потому что конечное число 1 000 000 000) мы не учли....

Получим 40500000001

← →
SergP. (2005-09-16 13:47) [43]

← →
default © (2005-09-16 13:50) [44]

11. первое что приходит в голову, описать прямоугольник вокруг нужной фигуры, и генерировать точки для прямоугольника, если точка не попала в фигуру, то производим генерацию точки ещё раз и тд пока она не попадёт в фигуру

← →
palva © (2005-09-16 13:53) [45]

MBo © (16.09.05 12:36) [24]
> т.е. 6 путей вместо 8 в данной.
8. Что-то у меня для трехмерного случая тоже получается возврат с вероятностью единица. Странно, путей больше и, казалось, вероятность возврата должна быть меньше.

← →
SergP. (2005-09-16 13:55) [46]

> 2. В квадрат со стороной 1 вписан круг. В оставшееся место
> в левом верхнем уголке
> вписан еще один кружок. В оставшееся слева-вверху место
> - следующий и так далее до
> бесконечности. Какова суммарная площадь и периметр кругов?
>

Радиус первой окружности R1=0.5

радиус следующей R(n)=R(n-1)*(sqrt(2)-1)/(sqrt(2)+1)

Получаем геометрическую (сходящуюся) прогрессию где первый член равен Pi/4 а коэффициент равен (sqrt(2)-1)^4

Я точно не помню формулу суммы.... Так что

← →
MBo © (2005-09-16 13:57) [47]

>SergP. (16.09.05 13:41) [42]
>7. 40500000001
Все верно.

Еще один путь - образуем пары
0, 999999999 // 0 не повлияет на результат
1, 999999998
...
500 миллионов пар по 81 + единица из миллиарда.

← →
Jeer © (2005-09-16 14:02) [48]

КаПиБаРа © (16.09.05 11:28) [17]
MBo © (16.09.05 13:05) [28]
Antonn © (16.09.05 12:53) [25]

На Jeer © (16.09.05 11:13) [16]

S = 0.5*H/(R+H) = 0.5*360/(6371+360) = 0.0267.. (2.67..%)

:)))

← →
default © (2005-09-16 14:05) [49]

10. C

← →
Igorek © (2005-09-16 14:07) [50]

> 11. Нетрудно написать процедуру для генерации равномерно
> распределенных
> в прямоугольнике случайных точек.
> А вот как сделать то же самое для круга, треугольника и
> произвольного выпуклого
> четырехугольника?

Один из вариантов:
1 охватываем фигуру прямоугольником по габаритам
2 генерим точку
3 если она не в фигуре то 2

← →
MBo © (2005-09-16 14:12) [51]

>default © (16.09.05 13:50) [44]
11. первое что приходит в голову, описать прямоугольник вокруг нужной фигуры, и генерировать точки для прямоугольника, если точка не попала в фигуру, то производим генерацию точки ещё раз и тд пока она не попадёт в фигуру

Да, так можно. Этот путь в общем-то подходит для круга - пропадает всего 1-Pi/4, т.е примерно четверть случайных чисел, да и проверка на вхождения укладывается в пяток операций.
Но вот для треугольника и четырехугольника и промахов больше, и проверка существенно сложнее.

С точки зрения создания интересного алгоритма лучше считать, что генерация случайного числа - затратная операция. Для каждой точки нам дается пара случайных чисел, и потратить их надо по делу ;)

>palva © (16.09.05 13:53) [45]
>8. Что-то у меня для трехмерного случая тоже получается возврат с вероятностью единица. Странно, путей больше и, казалось, вероятность возврата должна быть меньше.
Да, вероятность возврата меньше будет. Насколько я помню, там получается сумма ряда с членами 1/n^3/2, т.е. сходящаяся

← →
MBo © (2005-09-16 14:20) [52]

>Jeer © (16.09.05 14:02) [48]
>На Jeer © (16.09.05 11:13) [16]
>S = 0.5*H/(R+H) = 0.5*360/(6371+360) = 0.0267.. (2.67..%)

Пардон, не воспринял, поскольку у меня было в разностной форме (1-R/(R+h))
;))

← →
MBo © (2005-09-16 14:25) [53]

default © (16.09.05 14:05) [49]
10. C

Верно.

>Igorek © (16.09.05 14:07) [50]
см. [51]

Проще всего сделать для круга, тут никаких хитростей нет.
А для треугольника нужно маленько подумать.

← →
default © (2005-09-16 14:50) [54]

MBo © (16.09.05 14:25) [53]
можно взять любую точку треугольника за начала косоугольной системы координат, генерируем случайно одну координату точки на каком-то прилежащем к началу координат отрезке прямой, следущую координтату генерируем в пределах обусловленных первой координатой и отрезком прямой не прилежащем к началу координат

← →
MBo © (2005-09-16 15:02) [55]

Вот тестовая система с некоей намеренно неправильной функцией генерации.
Как ее исправить в соответствии с твоим методом?

function RandPointT(const P:array of TPoint):TPoint; var a,b,c:Double; begin a:=Random; b:=Random; Result.X:=Round((P[0].X*a+P[1].X*(1-a)+P[0].X*b+P[2].X*(1-b))); Result.Y:=Round((P[0].Y*a+P[1].Y*(1-a)+P[0].Y*b+P[2].Y*(1-b))); end; procedure TForm1.Button2Click(Sender: TObject); var P:array[0..2] of TPoint; i:Integer; RP:TPoint; begin Randomize; P[0]:=Point(0,0); P[1]:=Point(250,100); P[2]:=Point(100,200); Canvas.Polygon(P); for i:=1 to 1000 do begin RP:=RandPointT(P); Canvas.Ellipse(RP.X,RP.Y-1,RP.X+1,RP.Y+1); end; end;

← →
КаПиБаРа © (2005-09-16 15:07) [56]

11. Можно из центра финуры или любой произвольной точке генерировать угол и расстояние (входящее в фигуру для данного угла) в полярных координатах.

← →
Igorek © (2005-09-16 15:13) [57]

> MBo © (16.09.05 14:25) [53]
> А для треугольника нужно маленько подумать.
А если взять треугольник, в одну вершину поставить начало координат, а оси - по сторонам с длинами А и Б. Генерируем точку (х, у) в прямоугольнике А на Б. Если она выше той диагонали, что не проходит через 0.0, то отзеркаливаем ее ниже диагонали. На треугольник ставим ее сумой векторов, паралельных сторонам с длинами x, y.

← →
Igorek © (2005-09-16 15:15) [58]

> Проще всего сделать для круга, тут никаких хитростей нет.

Если принять, что каждая точка должна быть использована, то вроде без интегралов не обойтись.

← →
MBo © (2005-09-16 15:15) [59]

>КаПиБаРа © (16.09.05 15:07) [56]
Проверка [56] - явно не равномерное распределение:

[code]
function RandPointC(const CX,CY,R: Integer):TPoint;
var
a,b:Double;
begin
a:=Random*R;
b:=Random*2*Pi;
Result.X:=Round(CX+a*Cos(b));
Result.Y:=Round(CY+a*Sin(b));
end;

procedure TForm1.Button3Click(Sender: TObject);
var
CX,CY,R: Integer;
i:Integer;
RP:TPoint;
begin
Randomize;
CX:=200;
CY:=200;
R:=150;
Canvas.Ellipse(CX-R,CY-R,CX+R,Cy+R);
for i:=1 to 5000 do begin
RP:=RandPointC(CX,CY,R);
Canvas.Ellipse(RP.X,RP.Y-1,RP.X+1,RP.Y+1);
end;
end;

[/code]

← →
SergP. (2005-09-16 15:17) [60]

> 6. В комнату внесли два плотных снежка, один по диаметру
> вдвое больше другого.
> Какая часть объема меньшего снежка останется, когда растает
> половина объема большого?

(4^(1/3) - 1)^3 = 0,2027

← →
MBo © (2005-09-16 15:19) [61]

> Igorek © (16.09.05 15:13) [57]
Звучит логично. В коде на базе [55] как это будет выглядеть?

← →
Igorek © (2005-09-16 15:20) [62]

> Igorek © (16.09.05 15:13) [57]

Фигню написал.

← →
Igorek © (2005-09-16 15:21) [63]

> Звучит логично.

Фигня. Допустим на диагональ прямоугольника упадет сто точек. А соотв. сторона треугольника будет очень маленькая..

← →
MBo © (2005-09-16 15:24) [64]

>SergP. (16.09.05 15:17) [60]
> (4^(1/3) - 1)^3 = 0,2027
Правильно.

← →
Igorek © (2005-09-16 15:24) [65]

> MBo © (16.09.05 15:19) [61]
> > Igorek © (16.09.05 15:13) [57]
> Звучит логично. В коде на базе [55] как это будет выглядеть?

Нет, все таки правильно. Преобразование треугольника линейное - потому равномерность сохранится. Код долго писать. :)

← →
palva © (2005-09-16 15:26) [66]

8. Трехмерный случай.
У меня получился общий член ряда (то есть вероятность возврата на шаге 2n) такой:
( (2n)! / ( n!^2 * 2^(2n) ) ) ^ 3

Ряд сходится плохо. 2000 членов дают сумму 0.38517 Дальше надо оценивать хвост, поскольку вычисление общего члена дает переполнение, а сумма ряда при продолжении суммирования все еще ощутимо растет. Упрощать общий член по формуле Стирлинга, как-то стремно.
Ну будет сумма где-то 0.40 что соответствует вероятности возврата 0.29

← →
Igorek © (2005-09-16 15:27) [67]

11. А вот как сделать то же самое выпуклого четырехугольника?
Поделить на два треугольника, взять сумму их площадей за 1.
Случайную точку сначала определить на какой ставить. :)

← →
Igorek © (2005-09-16 15:32) [68]

11. Для круга.
Преобразование (x, y) в:
угол - х(0, 360)
длина вектора - y(0, r) = r * (площать круга радиуса y / площадь круга радиуса r)

MBo © (16.09.05 15:02) [55]
похоже тоже неравномерно будет, ибо если треугольник разграфить равноотстоящими отрезками параллельными какой-то его стороне, то при генерации примерно одинаковое число точек будет приходиться на каждый отрезок, но отрезки разные по длине стало быть хоть на каждом отрезке точки и будут примерно на одинаковом расстоянии, но вообщем будет неравномерность

>palva © (16.09.05 15:26) [66]
>( (2n)! / ( n!^2 * 2^(2n) ) ) ^ 3

Да, так. Сам я не считал, в книжке приведена сумма 18 членов 0.315
и соотв. вероятность возвращения 1-1/(1+0.315)~0.24

SergP. (16.09.05 13:55) [46]
R(n)=R(n-1)*(sqrt(2)-1)/(sqrt(2)+1)

у меня немного не так получилось
R[N] = R[N-1] * (sqrt(2) - 1) / (2 + sqrt(2))

R[N] = ((sqrt(2) - 1) / (2 + sqrt(2)))^N * 1/2
S[N] = sqr((sqrt(2) - 1) / (2 + sqrt(2)))^N * 1/4 * Pi

S = (Pi/4) / (1 - ((sqrt(2) - 1) / (2 + sqrt(2))) = 0,797130834

11 для круга:

function GetRandomPointFromCircle(R, x0, y0: Integer): TPoint; var P, F: Extended; begin P := sqrt(Random) * R; F := Random * 2 * Pi; Result.X := x0 + Trunc(P * cos(F)); Result.Y := y0 + Trunc(P * sin(F)); end;

> S = (Pi/4) / (1 - ((sqrt(2) - 1) / (2 + sqrt(2))) =
> 0,797130834

S = (Pi/4) / (1 - sqr((sqrt(2) - 1) / (2 + sqrt(2))) = 0,797130834

Огласите нерешенные плз.

3. 7

Пятничные задачки. Разомнем извилины. Найти похожие ветки