Пятничные задачки ;)

← →
novill © (2006-12-22 16:21) [40]

> [39] palva © (22.12.06 16:18)

угу

← →
Кабан © (2006-12-22 16:24) [41]

MBo © (22.12.06 16:03) [26]
1/4 дал наугад :)
рискнул предположить, случайная величина, равная площади треугольника имеет равномерное распределение, видимо это не так, в частности треугольник максимальной площади = 1/2 дают только четыре тройки точек, а вот треугольников нулевой площади бесконечно много :)

← →
novill © (2006-12-22 16:28) [42]

> 7. В единичном квадрате случайным образом выбраны 3 точки.
> Какова будет средняя площадь полученного треугольника?

примерно 1/13

← →
novill © (2006-12-22 16:32) [43]

> = 1/2 дают только четыре тройки точек

ЖЖош :) таких точек бесконечность и маленькая тележка.

Чтобы площадь прямоугольника равнялась 1/2 достаточно, чтобы две точки находились в углах на одной грани, а третья может занимать любое место на противоположной грани.

← →
Кабан © (2006-12-22 16:42) [44]

ну да :) но все равно на порядок меньше :)

← →
Jeer © (2006-12-22 16:43) [45]

1. 2 датчика разнесенные на почти 180 градусов.

Электронная схема: D-триггер, на счетный вход которого подается сигнал с одного датчика, а на D-вход сигнал с другого, выход дает сигнал направления вращения - 0 или 1 (вправо-влево).

Сдвиг "почти" необходим для устранения гонок, хотя в реальности с учетом конечных размеров зон чувствительности этот сдвиг и так получится.

180 - для симметрии момента срабатывания, что и дает в среднем минимальное время ожидания решения.

← →
MBo © (2006-12-22 16:52) [46]

>Jeer © (22.12.06 16:43) [45]
1. 2 датчика разнесенные на почти 180 градусов.

Да, почти 180 или почти 0 (с инверсией) дают минимальное время ожидания в среднем

← →
Agent13 © (2006-12-22 17:10) [47]

5. 10 км

← →
oldman © (2006-12-22 17:53) [48]

> Вася Пупкин построил экспериментальную установку по измерению
> торсионных
> полей. Ротор установки представляет собой диск, который
> разделен своим диаметром
> на черную и белую половины. Оптический датчик устанавливается
> над диском и выдает код

А что такое "установка по измерению торсионных полей"???
Разве поля измеряются???
Имхо, измеряются только параметры полей...
:))))))))

← →
TUser © (2006-12-22 18:05) [49]

> 3. Массив длиной N содержит только нули и единицы. Как отсортировать массив за ОДИН проход без использования дополнительной памяти.

j := -1;
for i := 0 to high do
if Ar[i] = 0 then
inc (j);
if j < i then
Ar[j] := 0;
Ar[i] := 1;

← →
TUser © (2006-12-22 18:17) [50]

А нет ли какой-нибудь IDE для отладки программ Маркова? Желательно on-line :)

← →
Alexis © (2006-12-22 18:21) [51]

> 7. В единичном квадрате случайным образом выбраны 3 точки.
>
> Какова будет средняя площадь полученного треугольника?

Х-мм, я тоже полагал, что 1/4, но программа говорит, что нет
для 100.000 экспериментов
0.11732
для 1.000.000 экспериментов
0.118885
для 10.000.000 экспериментов
0.118982
для 20.000.000 экспериментов
0.118776

Искомое мат.ожидание где то в пределах между 1/9 и 11/90

#include <cmath> #include <cstdlib> #include <iostream> #include <vector> #include <algorithm> using namespace std; typedef unsigned int uint; int main(int argc, char *argv[]) { if (argc != 2) { cout << "Usage :" << argv[0] << " Triangle_count" << endl; return 0; } if (!atoi(argv[1])) return 1; srand((uint) time(NULL)); uint count = (uint)atoi(argv[1]); vector<double> triangle_S(count); for (uint i = 0; i < count; i++) { double x1, y1, x2, y2, x3, y3; x1 = rand() % 101 / 100; y1 = rand() % 101 / 100; x2 = rand() % 101 / 100; y2 = rand() % 101 / 100; x3 = rand() % 101 / 100; y3 = rand() % 101 / 100; double p, p12, p13, p23; p12 = sqrt( (x2 - x1) * (x2 - x1) + (y2 - y1)*(y2 - y1) ); p13 = sqrt( (x3 - x1) * (x3 - x1) + (y3 - y1)*(y3 - y1) ); p23 = sqrt( (x3 - x2) * (x3 - x2) + (y3 - y2)*(y3 - y2) ); p = p12 + p13 + p23; triangle_S[i] = sqrt(p * (p - p12) * (p - p13) * (p - p23)); } double sum = 0.0; for (uint i =0; i < count; i++) sum += triangle_S[i]; cout << "With " << count << " attempts " << sum / count << endl; return 0; }

← →
MBo © (2006-12-22 19:01) [52]

>TUser © (22.12.06 18:17) [50]
>А нет ли какой-нибудь IDE для отладки программ Маркова?

http://cmcmsu.no-ip.info/1course/alg.schema.nam.htm
сейчас у меня эта страничка не открылась, но раньше заходил.

>Alexis © (22.12.06 18:21) [51]
> 7. В единичном квадрате случайным образом выбраны 3 точки.
>0.118776
Должно получаться порядка 0.07-0.08
у тебя где-то ошибка, похоже, в формуле Герона - полупериметр нужен.
А вообще площадь по трем точкам лучше считать через векторное произведение
S= 1/Abs((X3-X1)*(Y2-Y1)-(X2-X1)*(Y3-Y1))

← →
Alexis © (2006-12-22 20:24) [53]

MBo © (22.12.06 19:01) [52]
> Должно получаться порядка 0.07-0.08
> у тебя где-то ошибка, похоже, в формуле Герона - полупериметр
> нужен.

Да, да, точно ошибся в формуле Герона, спасибо.

← →
default © (2006-12-22 21:58) [54]

а 6 мне оставили?:)

← →
Думкин © (2006-12-23 06:36) [55]

А если в первой задаче, не на два сектора. Есть нить по диаметру. При проходе под датчиком - его состояние меняется. Как тогда с детекторами?

← →
default © (2006-12-23 23:05) [56]

6. размачу счёт в этой задаче:)
a)
1) 2xx->x2
2) 2x->1
3) 2->0
4) xx->x2
5) x->1
6) {}->0

забавно да смотрится известный алгоритм перевода в форме алгоритма Маркова?:)

← →
default © (2006-12-23 23:45) [57]

> TUser © (22.12.06 18:17) [50]
> А нет ли какой-нибудь IDE для отладки программ Маркова?
> Желательно on-line :)

нафига? я для тестирования использовал код
Function MarkovStep(ByRef s As String, ByVal leftStr As String, ByVal rightStr As String) As Boolean Dim ind As Integer = s.IndexOf(leftStr) If ind = -1 Then Return False s = s.Remove(ind, leftStr.Length).Insert(ind, rightStr) "Console.WriteLine(s) Return True End Function Sub Main() Dim s As String = "" For i As Integer = 0 To 15 Start: "If MarkovStep(s, "", "0") Then GoTo Start If MarkovStep(s, "2xx", "x2") Then GoTo Start If MarkovStep(s, "2x", "1") Then GoTo Start If MarkovStep(s, "2", "0") Then GoTo Start If MarkovStep(s, "xx", "x2") Then GoTo Start If MarkovStep(s, "x", "1") Then GoTo Start Console.WriteLine(s) s = "" For j As Integer = 0 To i s += "x" Next Next Console.ReadLine() End Sub

← →
default © (2006-12-23 23:48) [58]

или я шутку юмора не понял;)

← →
Горгер © (2006-12-24 17:45) [59]

2) Запустить 5 забегов одновременно и выбрать 3 лидеров.

← →
MBo © (2006-12-25 06:48) [60]

>Agent13 © (22.12.06 17:10) [47]
5. 10 км

Верно

>default © (23.12.06 23:05) [56]
Угу.

← →
Jeer © (2006-12-25 11:00) [61]

> Думкин © (23.12.06 06:36) [55]
>
> А если в первой задаче, не на два сектора. Есть нить по
> диаметру. При проходе под датчиком - его состояние меняется.
> Как тогда с детекторами?
>

"Нить" - это дельта-функция единичного скачка, т.е. дифференциал, значит надо вернуться через интеграл к первому условию.
Интегратор нулевого порядка - счетный триггер.
Подаем сигналы с двух датчиков на два независимых счетных триггера и при прохождении датчиков через нить состояние счетчиков будет меняться, фиксируя переход.
Далее, выходы триггеров подаются на вход D-триггера: один на D- другой на C-вход, т.е. вернулись к первой схеме.

← →
Alexis © (2006-12-27 15:54) [62]

2 MBo
Странно, что-то никто не смог решить задачу 7...
Может стоит уже выложить ответы, а то народ притих :)

← →
MBo © (2006-12-27 16:20) [63]

>Alexis © (27.12.06 15:54) [62]
>Странно, что-то никто не смог решить задачу 7...
Ответ 11/144

← →
Alexis © (2006-12-27 19:27) [64]

> MBo © (22.12.06 19:01) [52]
> > 7. В единичном квадрате случайным образом выбраны 3 точки.
>
> >0.118776
> Должно получаться порядка 0.07-0.08
> у тебя где-то ошибка, похоже, в формуле Герона - полупериметр
> нужен.

Вот странно, я исправил одну строчку в программе, периметр на полупериметр, а множественные эксперименты дают результат порядка 0.00029-0.00030
#include <cmath> #include <cstdlib> #include <iostream> #include <vector> #include <algorithm> using namespace std; typedef unsigned int uint; int main(int argc, char *argv[]) { if (argc != 2) { cout << "Usage :" << argv[0] << " Triangle_count" << endl; return 0; } if (!atoi(argv[1])) return 1; srand((uint) time(NULL)); uint count = (uint)atoi(argv[1]); vector<double> triangle_S(count); for (uint i = 0; i < count; i++) { double x1, y1, x2, y2, x3, y3; x1 = rand() % 101 / 100; y1 = rand() % 101 / 100; x2 = rand() % 101 / 100; y2 = rand() % 101 / 100; x3 = rand() % 101 / 100; y3 = rand() % 101 / 100; double p, p12, p13, p23; p12 = sqrt( (x2 - x1) * (x2 - x1) + (y2 - y1)*(y2 - y1) ); p13 = sqrt( (x3 - x1) * (x3 - x1) + (y3 - y1)*(y3 - y1) ); p23 = sqrt( (x3 - x2) * (x3 - x2) + (y3 - y2)*(y3 - y2) ); p = (p12 + p13 + p23) / 2; triangle_S[i] = sqrt(p * (p - p12) * (p - p13) * (p - p23)); } double sum = 0.0; for (uint i =0; i < count; i++) sum += triangle_S[i]; cout << "With " << count << " attempts " << sum / count << endl; return 0; }

> Ответ 11/144

Да ответ то пофигу! :) Как решается-то? Если можно, хотя бы парой слов описать метод решения...

← →
Alexis © (2006-12-28 17:25) [65]

Alexis © (27.12.06 19:27) [64]

> MBo © (22.12.06 19:01) [52]
> > 7. В единичном квадрате случайным образом выбраны 3 точки.
>
> >0.118776
> Должно получаться порядка 0.07-0.08
> у тебя где-то ошибка, похоже, в формуле Герона - полупериметр
> нужен.

Вот странно, я исправил одну строчку в программе, периметр на полупериметр, а множественные эксперименты дают результат порядка 0.00029-0.00030

#include <cmath> #include <cstdlib> #include <iostream> #include <vector> #include <algorithm> using namespace std; typedef unsigned int uint; int main(int argc, char *argv[]) { if (argc != 2) { cout << "Usage :" << argv[0] << " Triangle_count" << endl; return 0; } if (!atoi(argv[1])) return 1; srand((uint) time(NULL)); uint count = (uint)atoi(argv[1]); vector<double> triangle_S(count); for (uint i = 0; i < count; i++) { double x1, y1, x2, y2, x3, y3; x1 = rand() % 101 / 100; y1 = rand() % 101 / 100; x2 = rand() % 101 / 100; y2 = rand() % 101 / 100; x3 = rand() % 101 / 100; y3 = rand() % 101 / 100; double p, p12, p13, p23; p12 = sqrt( (x2 - x1) * (x2 - x1) + (y2 - y1)*(y2 - y1) ); p13 = sqrt( (x3 - x1) * (x3 - x1) + (y3 - y1)*(y3 - y1) ); p23 = sqrt( (x3 - x2) * (x3 - x2) + (y3 - y2)*(y3 - y2) ); p = (p12 + p13 + p23) / 2; triangle_S[i] = sqrt(p * (p - p12) * (p - p13) * (p - p23)); } double sum = 0.0; for (uint i =0; i < count; i++) sum += triangle_S[i]; cout << "With " << count << " attempts " << sum / count << endl; return 0; }

> Ответ 11/144

Да ответ то пофигу! :) Как решается-то? Если можно, хотя бы парой слов описать метод решения...

← →
default © (2006-12-28 18:28) [66]

6.
г)
1) {} -> y
2) 2x -> kzy2
3) 2 -> {}
4) x -> kzy2
5) kz -> zk
6) yz -> zy
7) yk -> ky
8) 1k -> yk1
9) 1 -> {}
10) zk -> k1
11) k -> {}
код тестирования
Public Function ToStart(ByRef s As String, ByVal leftString As String, ByVal rightString As String) As Boolean Dim ind As Integer = s.IndexOf(leftString) If ind = -1 Then Return False s = s.Remove(ind, leftString.Length) If rightString <> "" Then s = s.Insert(ind, rightString) Return True End Function Sub Main() Dim s As String = "xxx" Start: If s = "" Then s = "y" GoTo [End] End If " xxx --> zzzkkkyyy If ToStart(s, "2x", "kzy2") Then GoTo Start If ToStart(s, "2", "") Then GoTo Start If ToStart(s, "x", "kzy2") Then GoTo Start If ToStart(s, "kz", "zk") Then GoTo Start If ToStart(s, "yz", "zy") Then GoTo Start If ToStart(s, "yk", "ky") Then GoTo Start " zzzkkkyyy --> kkkyyyyyyyyy If ToStart(s, "1k", "yk1") Then GoTo Start If ToStart(s, "1", "") Then GoTo Start If ToStart(s, "zk", "k1") Then GoTo Start " kkkyyyyyyyyy --> yyyyyyyyy If ToStart(s, "k", "") Then GoTo Start [End]: Console.WriteLine(s) Console.ReadLine() End Sub

мой мозг чуть не умер при решени этой задачи:) кошмарр!
на оптимальность решения не претендую, лишь на корректность

MBo, круто?

← →
Zeqfreed © (2006-12-29 01:03) [67]

6.в:
a*b -> !ab b*a -> !ba *a+ => a *b+ => b +*a => a +*b => b *a -> !a *b -> !b !a! -> +a !b! -> +b !a+ -> +a !b+ -> +b !aa -> a!a !ab -> b!a !ba -> a!b !bb -> b!b a -> *a b -> *a

Проверял и отлаживал тут:
http://cmcmsu.no-ip.info/1course/alg.schema.nam.htm

Кажется работает. Но я уже слишком устал, чтобы быть уверенным на 100% :)

← →
Zeqfreed © (2006-12-29 01:11) [68]

Ой, опечатался. Последняя строка b -> *b разумеется.

чтобы мою штуку протестить в [67]
надо забросить
6.
г)
2x -> kzy2
2 ->
x -> kzy2
kz -> zk
yz -> zy
yk -> ky
1k -> yk1
1 ->
zk -> k1
k ->

а то я сначалу запустил и них...а после некоторых исправлений заработало...

ой блин лучше в этой штуке не тестировать!!!
у меня при "xxxxx" фигня выдаётся, хотя в коде [66] всё великолепно работает...так что для тестирования лучше эту хрень не использовать...

> default © (29.12.06 01:35) [70]

Да нет, вроде все хорошо работает. Просто там ограничено сотней итераций. Можно сохранить страницу себе на диск и поправить ограничения :)

Осталось теперь 6.б решить :)

Zeqfreed © (29.12.06 01:38) [71]
делать мне больше нечего:)
вообщем понятно - он просто не всегда до конца считает...
тогда сорри, но слишком уж мало по времени считает...

6.
б)
x2->2xx
1->2x
0->2
x2->xx
1->x
0->
2->

Zeqfreed © (29.12.06 01:38) [71]
знаешь каким макаром я её сделал?
только громко не смейся!
перевернул левые и правые части в решении пункта a) и запустил
всё выдавало верно только в конце двойки добавлялись и добавил 2 ->
для удаления двоек:)
сильно да?:)

> default © (29.12.06 01:55) [73]

> сильно да?:)

Весьма! :)
Я бы не догадался :))

Теперь ждем MBo, чтобы он раздал нам пирожки.

Zeqfreed © (29.12.06 02:01) [74]
я совсем не был уверен что заработает:)
что ж и тебе наука, что бывают такие решения! блицкриг прям какой-то!

У меня ещё есть подозрение, что в) можно сделать покомпактней. А то у меня как-то сильно раздуто получилось.

К сожалению, времени особо нет, так что буду краток.
>Alexis
Мое моделирование:

var X,Y: array[0..2] of Integer; i, j, S, SS: Integer; begin Randomize; SS := 0; for j := 1 to 100 do begin for i := 0 to 2 do begin X[i] := Random(10); Y[i] := Random(10); end; S := Abs((X[2] - X[0])*(Y[1]-Y[0]) -(X[1] - X[0])*(Y[2]-Y[0])); SS := SS + S; end; Caption := FloatToStr(SS/20000); end;

Сам я правильный ответ не получил. Пробовал (давненько, подробности уж подзабыл) так: для 6 величин X1, X2, X3, Y1, Y2, Y3, равномерно распределенных в 0..1, пытался построить функцию распределения для формулы
Abs((X2 - X0)*(Y1-Y0) -(X1 - X0)*(Y2-Y0))
(сначала ФР разности, потом произведения и т.д.)
и проинтегрировать, однако либо ошибся где-то, либо подход неверный.

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

OK, my method. It"s basically integrating 0 to 1 for SIX coordinates. It was relatively easy and fun to calculate, but explaining it is really hard.

Firstly, the prob that all of x1,x2,x3 are below m is m^3. Drawing that probability graph and integrating gives you an average of 3/4 for the highest x value. Having done this we can scale up the traingle in the x-axis so it reaches x=1, and remember to multiply by the hi-x for each possiblity (which equates to multiplying by 3/4 overall, since that"s the average of hi-x).

So now our x1 and x2 are distributed randomly from 0 to 1. The prob that both are above m is (1-m)^2. Drawing the graph and integrating gives 2/3. The we do the same as before; scale in the x-direction again so the triangle touches both sides.

We can do the same in the y-direction, after which we can say that the average size of the bounding box for our triangles is (3/4)*(2/3)*(3/4)*(2/3) = 1/4.

Now to the area of our triangle. The prob that the point which has the in-between x-value also has the in-between y-value is 1/3. In this case, we have two opposite corners of the bounding box (which we are treating as a unit square) and a random point within it. If this random point is x,y (x>y) then A=(x-y)/2. Integrating this for x=0..1 and y=0..x, we get 1/12, which we double, to count the cases where y>x.

If the in-between x-value and y-value are not the same point, our triangle has one point at the corner of the square and two on the sides. This will occur 2/3 of the time. Assume one point is at (0,0) the orientation doesn"t change things) and the other points are (1,y) and (x,1).

We calculate the area of this one by subtracting the outer triangles from the square. A = 1-(x+y+(1-x)(1-y))/2 = (2-1-x-y-1+x+y-xy)/2 = (1-xy)/2. Integrating this over the unit square gives 3/8.

So our triangle touching the sides of the unit square averages to 1/6 for the 1/3 of the cases, and 3/8 for the 2/3 of the cases. This adds up to 11/36. We multiply by the 1/4 for scaling the bounding box and we get 11/144.

6а
1) 12 -> 20
2) 02 -> 10 - добавлено
3) 2 -> 10
3) 1x -> 2
4) 0x -> 1
5) x -> 1
6) {} |-> 0

6б
1) xx0 -> x0xx
2) x0 -> xx
3) x1 -> x0x
4) 1 -> x
5) 0 |-> {}

6в
1] ca -> ac
2] cb -> bc
3] da -> ad
4] db -> bd
5] 1a -> 1c
6] 1b -> 1d
7] 1c -> a1
8] 1d -> b1
9] 1 |-> {}
10] {} -> 1

6г
1) zy -> yz
2) zx -> xyyz
3) x -> z
4) z -> y

Zeqfreed © (29.12.06 02:04) [76]
Эх...нас даже и не похвалили...
кстати видишь в [78] решения в a) и б) независимые, мне одни выстрелом удалось решить две задачи:)
да фиг с ним с раздутием:)

>Эх...нас даже и не похвалили...
Да крутые, крутые ;))
Я сам только вторую осилил, а в первой запутался :(

Пятничные задачки ;) Найти похожие ветки