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

← →
MBo © (2006-12-22 14:08) [0]

1. Вася Пупкин построил экспериментальную установку по измерению торсионных
полей. Ротор установки представляет собой диск, который разделен своим диаметром
на черную и белую половины. Оптический датчик устанавливается над диском и выдает код
1 при переходе с черного на белое и 0 при обратном переходе. Какое минимальное
количество датчиков понадобится для определения направления вращения диска,
и как их нужно расположить для наиболее быстрого в среднем определения направления
при начале действия торсионных полей?

2. Вася Пупкин должен отобрать для участия в тараканьих бегах три самых быстрых
насекомых из 25 имеющихся. За какое минимальное число забегов можно это сделать,
если в забеге участвуют 5 тараканов, скорость каждого постоянна от забега к забегу.

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

4. На основе вихревых торсионных полей Вася Пупкин построил лабораторную пушку,
стреляющую на несколько метров стальными шариками, которую можно выставить на столе под любым углом.
Требуется поставить эксперимент - за два выстрела (на большее пока не хватает сгустков поля)
определить зону поражения пушки на полу (хотя бы одну точку). В наличии имеется
видеокамера, линейка достаточной длины, и лаборант-имбецил, который может выполнить заданную заранее последовательность
примитивных действий, но не способен произвести никаких вычислений, а сам Вася опасается приближаться к
источнику торсионных полей до конца эксперимента, покуда находится в репродуктивном возрасте.

5. Из пункта А в пункт Б по одной прямой дороге выехали две машины, навстречу им
еще две, все с постоянной скоростью. Встречи произошли на расстоянии от пункта А
3, 4, 6 и 7 километров. Какое же расстояние между пунктами А и Б?

6. Алгоритм Маркова - программа для преобразования одной символьной строки
в другую, записываемая в следующем виде:
1. <substr 1> -> <str 1>
2. <substr 2> -> <str 2>
3. <substr 3> -> <str 3>
.......
n. <substr n> -> <str n>
вместо -> в некоторых строках программы может быть символ |->

Работает так:
исходная строка проверяется на наличие подстроки <substr 1>, если найдено,
то подстрока <substr 1> заменяется на <str 1> (выполнено правило 1),
если нет, то проверяется на наличие <substr 2> и т.д. Если замена произошла,
то полученая строка снова проверяется на наличие <substr 1> и т.д.,
пока не наступит конец программы.

Конец программы наступает если
1) не выполнено ни одно правило
2) выполнено правило с символом |->
Пустая подстрока входит в любую строку
Разрешается использовать любые символы, в том числе и не входящие в исходную
и результирующие строки, пустые строки обозначим {}

Например, имеется строка состоящая из n символов "x", надо написать программу, заменяющую эту строку на строку из 2n символов "x"
программа
1) x->xx
работать не будет, точнее говоря, она никогда не остановится
правильная программа:
1) 1x->xx1
2) x1|->x
3) x->xx1
проверим на примере строки xxx
xxx (3) xx1xx (1) xxxx1x (1) xxxxxx1 (2) xxxxxx
А теперь несколько задачек:

а) Преобразовать строку из n символов x в двоичную запись числа n (например, из xxxxxx должно получиться 110)
б) Преобразовать строку, являющуюся двоичной записью числа n в строку из n символов x (например, из 101 должно получиться xxxxx)
в) Преобразовать строку из символов a и b в строку-перевертыш (например из aababba должно получиться abbabaa)
г) Преобразовать строку из n символов x в строку из n^2 символов y

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

8. N человек выстроены в круг, счет идет по кругу, выбывает каждый M-й
из оставшихся. Найти номер человека в первоначальном круге, который останется последним.

9. Числа Стирлинга 2 рода определяются так:
S(n,1) = 1
S(n,n) = 1
S(n,k) = S(n-1, k-1) + k*S(n-1,k)
По определению нетрудно составить рекурсивную функцию, но она будет довольно
медленной для значений параметров, скажем, до миллиона. Как более эффективно вычислить S(n,k)?

← →
boriskb © (2006-12-22 14:12) [1]

MBo © (22.12.06 14:08)
Вася Пупкин построил экспериментальную установку

Этот Вася...
Всё ему надо. В каждой бочке затычка.
Интересный должен быть мужик :))

← →
MBo © (2006-12-22 14:18) [2]

Еще одну забыл дописать:

10. Для векторов X и Y известны ненулевая сумма a, скалярное произведение p = (X.Y) и векторное произведение b = [X*Y]
Найти вектора X, Y

← →
MBo © (2006-12-22 14:22) [3]

к 3) задаче: O(1) памяти, конечно, можно использовать.

← →
Ega23 © (2006-12-22 14:30) [4]

2 - уточните, в каждом забеге регистрируется только занятое место, или ещё и время для каждого из тараканов?

← →
MBo © (2006-12-22 14:39) [5]

>2 - уточните, в каждом забеге регистрируется только занятое место
Только место.

← →
Ega23 © (2006-12-22 14:43) [6]

> Только место.

2 - 11 забегов.

← →
jack128 © (2006-12-22 14:44) [7]

MBo © (22.12.06 14:08)
3. Массив длиной N содержит только нули и единицы. Как отсортировать массив за ОДИН
проход без использования дополнительной памяти.

type TDynBooleanArray = array of Integer; procedure SortBooleanArray(var Arr: TDynBooleanArray); var FalseIndex, TrueIndex: Integer; Temp: boolean; begin if Length(Arr) < 2 then Exit; FalseIndex := Low(Arr); TrueIndex := High(Arr); while (FalseIndex < TrueIndex) and not Arr[FalseIndex] do Inc(FalseIndex); while (FalseIndex < TrueIndex) and Arr[TrueIndex] do Dec(TrueIndex); if FalseIndex >= TrueIndex then Exit; // массив отсортирован while FalseIndex < TrueIndex do begin Arr[FalseIndex] := False; Arr[TrueIndex] := True; while (FalseIndex < TrueIndex) and not Arr[FalseIndex] do Inc(FalseIndex); while (FalseIndex < TrueIndex) and Arr[TrueIndex] do Dec(TrueIndex); end; end;

← →
jack128 © (2006-12-22 14:44) [8]

jack128 © (22.12.06 14:44) [7]
TDynBooleanArray = array of boolean;

← →
Alx2 © (2006-12-22 14:44) [9]

Блин, как поздно-то. Мне уже пора уходить :(
3. Два счетчика. Один N0 - сколько нулей, другой N1 - сколько единиц. За проход по массиву сразу получаем сортированную последовательность из N0 нулей и N1 единиц.
Либо пускаем навстречу друг другу два индекса-бегунка пока они не встретятся. Левый стопорится, если в ячейке 1. Правый - если 0. Когда на правом 0, а на левом 1, то меняем местами содержимое ячеек.
Это почти этап partition из QuickSort.

← →
MeF Dei Corvi © (2006-12-22 14:45) [10]

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

В ячейку массива можно записать только 1 или 0, или другие числа также допускаются?

← →
DprYg © (2006-12-22 14:52) [11]

> Найти вектора X, Y

А поподробнее? Что значит найти (найти координаты или что)?

← →
MBo © (2006-12-22 15:02) [12]

>MeF Dei Corvi
>В ячейку массива можно записать только 1 или 0, или другие числа также допускаются?
Не допускаются. Даже если можно было бы, подсчет подразумевает не единичный проход по массиву, а это главное ограничение

>DprYg Что значит найти (найти координаты или что)?
выразить через известные a,b,p

← →
Кабан © (2006-12-22 15:18) [13]

7) 1/4

← →
Zeqfreed © (2006-12-22 15:25) [14]

#include <stdio.h> #include <stdlib.h> #include <string.h> int main() { char buf[300]; gets(buf); int swapped = 0; int i = 0; int len = strlen(buf) - 1; int j = len; while (i < len) { if ((buf[i] != "0") && (buf[i] != "1")) { fprintf(stderr, "Invalid input at %d\n", i); exit(1); } if (buf[i] == "1") { while (j > i) { if (buf[j] == "0") { buf[j] = "1"; buf[i] = "0"; break; } j--; } } i++; } printf("Sorted list: %s\n", buf); return 0; }

Это на третью задачу. Вроде условия выполняются, код работает, хотя не могу гарантировать на 100% :) Извиняюсь, что на си.

← →
palva © (2006-12-22 15:30) [15]

2 - Можно за 9.
Сначала разбить по пятеркам это пять забегов. В каждом из них двух отставших можно отбросить.
Потом забег лидеров, после чего двух отставших вместе с их пятерками (уже тройками) можно отбросить.
Оставшиеся девять претендентов участвуют в произвольном порядке в трех забегах, после каждого из них отбрасываем два. Здесь наверно можно как-то сэкономить забеги. Но если не экономить получается 9 забегов.

← →
Ega23 © (2006-12-22 15:37) [16]

Хм.. вроде и вправду 9...

← →
jack128 © (2006-12-22 15:38) [17]

palva © (22.12.06 15:30) [15]
Оставшиеся девять претендентов участвуют в произвольном порядке в трех забегах, после каждого из них отбрасываем два.
как это можно по 2 отбрасывать? Ведь в одном забеге могут участвовать самые быстрые тараканы, а двух других - самые медленные из этих 9ти..

← →
Zeqfreed © (2006-12-22 15:38) [18]

program sort; {$IFNDEF ON_LINUX} {$APPTYPE CONSOLE} {$ENDIF} uses SysUtils; var s : String; i, j : Integer; begin Write("Type a string: "); ReadLn(s); i := 1; j := length(s); repeat if not (s[i] in ["0","1"]) then begin WriteLn("Invalid input at " + IntToStr(i)); exit; end; if (s[i] = "1") then begin while (j > i) do begin if (s[j] = "0") then begin s[j] := "1"; s[i] := "0"; break; end; Dec(j); end; end; Inc(i); until (i >= length(s)); WriteLn("Sorted list: ", s); end.

Вот, переписал на FPC :)

← →
jack128 © (2006-12-22 15:39) [19]

jack128 © (22.12.06 15:38) [17]
а. Туплю.

← →
Ega23 © (2006-12-22 15:40) [20]

> как это можно по 2 отбрасывать? Ведь в одном забеге могут
> участвовать самые быстрые тараканы, а двух других - самые
> медленные из этих 9ти..
>

Пускаем 5, отбрасываем двух, добавляем двух, отбрасываем двух, добавляем двух.
3 забега. Итого с предыдущими 6 - 9.

← →
palva © (2006-12-22 15:42) [21]

1 - достаточно 2
Если представить диск циферблатом, то один устанавливаем над цифрой 3, друой над цифрой 6. Как только первый выдаст 1 следим за вторым датчиком. Если он выдаст 1, то по часовой стрелке, если 0, то против часовой.

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

2 MBo

> 9. Числа Стирлинга 2 рода определяются так:
> S(n,1) = 1
> S(n,n) = 1
> S(n,k) = S(n-1, k-1) + k*S(n-1,k)
> По определению нетрудно составить рекурсивную функцию, но
> она будет довольно
> медленной для значений параметров, скажем, до миллиона.
> Как более эффективно вычислить S(n,k)?

Динамическое программирование использовать? Или правильным решением является другой метод?
Дополнительную память можно использовать неограниченно (напримердинамический массив)или решение этого не допускает?

← →
MBo © (2006-12-22 15:57) [23]

>Дополнительную память можно использовать неограниченно (напримердинамический массив)или решение этого не допускает?

Можно, но не слишком расточительно

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

1) устраиваем забег 5-ок
2) в каждой 5-ке отбрасываем по два таракана
2) устраиваем забег лидеров
3) отбрасываем две 3-ки
4) остаются следующие тараканы (номер тройки, место)
11 12 13
21 22 23
31 32 33
5) 11 - автоматически проходит в финал
6) 23, 32, 33 в финал попасть уже не могут,
7) устраиваем забег из тараканов 12, 13, 21, 22 и 31, в финал проходят два таракана

итого 7 забегов

← →
GRAND25 © (2006-12-22 16:02) [25]

> Извиняюсь, что на си.

Очень хорошо, что извинился. Молодец! Все бы так...

← →
MBo © (2006-12-22 16:03) [26]

>palva © (22.12.06 15:30) [15]
Логика правильная, но не всё учтено, можно еще оптимизировать

>palva © (22.12.06 15:42) [21]
>1 - достаточно 2

Это верно, а вот обеспечивает ли помещение датчиков под углом 90 градусов лучшее ожидаемое время?

>Кабан © (22.12.06 15:18) [13]
>7) 1/4

Моделирование показывает заметно меньшую величину.

← →
novill © (2006-12-22 16:03) [27]

тараканов можно определить в 4 забега

← →
palva © (2006-12-22 16:06) [28]

2 - Когда у нас осталось 9 претендентов, то победивший в забеге лидеров является самым быстрым, поэтому мы его можем уже считать отобранным. Из оставшихся восьми возьмем 5 для очередного забега. Трое пришедших последними определенно не принадлежат тройке лидеров, поскольку двое оередили их в данном забеге, а еще один уже признан самым быстрым. Поэтому трех последних можно отбросить. Среди оставшихся пяти провести еще один забег и снова отбросить трех. Всего получается 8 забегов.

← →
novill © (2006-12-22 16:06) [29]

> [27] novill © (22.12.06 16:03)

соврал ( тура четыре

← →
MBo © (2006-12-22 16:06) [30]

>Кабан © (22.12.06 15:58) [24]
>итого 7 забегов
Всё верно!

← →
Alexis © (2006-12-22 16:06) [31]

2 MBo

> 8. N человек выстроены в круг, счет идет по кругу, выбывает
> каждый M-й
> из оставшихся. Найти номер человека в первоначальном круге,
> который останется последним

А счет начинается с человека, стоящего сразу следующим после выбывшего или с некого условного начала круга? Т.е. если M=2, то 1-2-3-4-5-...
2-ой выбыл 1-3-4-5-... 4-ый выбыл 1-3-5-...
или
2-ой выбыл 1-3-4-5-... 3-ий выбыл 1-4-5-...

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

> [28] palva © (22.12.06 16:06)

та же фигня :)

← →
palva © (2006-12-22 16:08) [33]

Кабан © (22.12.06 15:58) [24]
Согласен

← →
novill © (2006-12-22 16:09) [34]

> [30] MBo © (22.12.06 16:06)

> 4) остаются следующие тараканы (номер тройки, место)
> 11 12 13
> 21 22 23
> 31 32 33
> 5) 11 - автоматически проходит в финал
> 6) 23, 32, 33 в финал попасть уже не могут

Почему?

← →
novill © (2006-12-22 16:11) [35]

> [34] novill © (22.12.06 16:09)

почему 32 не может быть быстрее 22?

← →
MBo © (2006-12-22 16:13) [36]

Пусть 5 человек, нумеруем, например, от 0 до 4, выбывает каждый второй.
Тогда последовательность отстрела
1 3 0 4, остается 2
Если удобнее нумерация с единицы, то 2 4 1 5, остается 3

← →
MBo © (2006-12-22 16:17) [37]

>novill © (22.12.06 16:11) [35]
>почему 32 не может быть быстрее 22?

11>21>31>32
32 никак не может попасть в тройку

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

2 novill © (22.12.06 16:11) [35]

а разве кто-то сказал, что 32 не может быть быстрее 22?

← →
palva © (2006-12-22 16:18) [39]

novill © (22.12.06 16:11) [35]
> почему 32 не может быть быстрее 22?
Может, но он медленне чем 31 21 11, и потому не попадает в призеры.

← →
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 лидеров.

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

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

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

> 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 © (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

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

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, круто?

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% :)

Ой, опечатался. Последняя строка 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) и б) независимые, мне одни выстрелом удалось решить две задачи:)
да фиг с ним с раздутием:)

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

Вот блин, я не знал, что пустые строки можно ставить в левой части оператора :)
Мне пришлось извращаться поэтому, чтобы выбирался именно первый символ для сдвига :))

В 6 трудность (для меня, по крайней мере) в том, что думать надо совсем непривычным (нехарактерным для Паскаля и др. процедурных языков)образом. Надо, наверно, о функциональных языках почитать. Kerk когда-то давал несколько задачек для решения в чисто функц. стиле (без переменных), дык тоже нетривиально было...

offtop:
Кстати, Абельсона "Структура и интерпретация комп. программ" кто-нибудь читал? Как впечатление?

MBo © (29.12.06 11:15) [82]
да, для меня тоже это составляло трудность
вот с переворачиванием левых и правых частей для получения обратный преобразований интересно кто-то этим занимался, интересно насколько общий такой метод
Абельсона "Структура и интерпретация комп. программ"
надо поискать
в электронном она есть?

> электронном она есть?
В принципе существует издание 2004 года в эл. виде, но ссылок живых не попалось. В издании 2006 года добавился еще один автор, так что, видимо, какие-то изменения есть.
Книга базируется на Lisp/Scheme, и являлась учебником для общего курса программирования MIT. По слухам, теперь там вводный курс на Python решили перевести.

На английском она легально доступна
http://mitpress.mit.edu/sicp/

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