Пятничная разминка заскорузлых нейронов и аксонов :)

← →
MBo © (2005-02-11 09:06) [0]

1. Без вычисления длинного числа найти пропущенные цифры:
35!=1033314796638614?9296?6651337523200000000

2. Имеется текстовый поток неизвестного размера (например, TextFile), читать его можно
исключительно последовательно (Readln). Длины строк произвольные, но не больше некоторого
маленького числа L (к примеру, 2000 символов максимум).
Требуется напечатать случайную строку из этого потока.
Предполагается равномерное распределение.
(Например, если по достижении конца потока выяснилось,
что в нем всего было три миллиона строк, можно было бы попросить датчик случайных
чисел выдать число в диапазоне он 1 до 3,000,000 и напечатать строку с тем самым номером,
но у нас нет возможности хранить все строки и повторно читать файлк нельзя)

3. Кто уже знает подобную задачу, могут отдохнуть ;)
По легенде, сия задача была кем-то задана Сахарову на каком-то рауте.
Тот ее решил на салфетке за 1 мин.

Итак, на стене сидит паучок. В месте сидения паучка к стене прикреплен
абсолютно эластичный шнур длиной 1 метр, второй конец которого зажат в руке
человека. Шнур перпендикулярен стене. Человек начинает идти от стены со скоростью 1 м/с.
В этот же момент паучок начинает бежать по шнуру со скоростью 1 см/с.
Догонит ли паучок человека?

4. Дан квадрат со стороной 1. Внутри выбирается случайная точка.
Какова вероятность, что точка ближе к центру квадрата, чем к одной из сторон?

5. Последовательность чисел a0, a1, a2,...ai... определена так :
a0 = 1, aN+1 = aN + сумма цифр aN.
т.е. она начинается:
1,2,4,8,16,23,28,38,49,62,70,77,...
Является ли число 123456789 ее членом, и если да, то под каким номером?

6. Двор представляетс собой равност. единичный треугольник.
В углах стоят столбы высотой a, b, и c.
Найти точку P на полу двора, веревки от которой к каждой вершине столба
имеют одинаковую длину

Картинки к этой,9 и 10 задачам:
http://mbo88.narod.ru/t20.gif

7. Вася Пупкин пригласил на свой ДР 100 друзей. Каждый из них пригласил еще 99, каждый
из которых пригласил по 98 и т.д...
Полагая, что никто не был приглашен двумя и более людьми, найти, сколько же человек
соберется у Васи?

8. Почта UPS принимает посылки, сумма длины (наибольшего измерения) и обхвата (периметра) по
перп. сечению не превышает 130 дюймов.
Каков должен быть размер квадратного окна для приема посылок?

9. Дан график y = x2, в некоторой отличной от нуля точке проведена нормаль к нему,
Эта нормаль пересекает параболу еще в одной точке, образуя некоторую замкнутую область.
Будет ли минимум у этой площади и если да, что в какой точке нужно провести нормаль?

10. Теннисист при подаче подпрыгивает, в частности, чтобы увеличить диапазон углов, под которым мяч попадет
на половину противника. Как высоко нужно прыгать, чтобы угол (alpha на рисунке) был максимальным?

11. Пусть имеется две тетраэдрических игральных кости с числами на гранях 1, 2 , 3, 4.
Вероятность выпадения сумм:
sum 2 3 4 5 6 7 8
prob 1/16 2/16 3/16 4/16 3/16 2/16 1/16
Если же взять одну кость с числами 1, 2, 2, 3, а другую с 1, 3, 3, 5, то получим
то же самое распределение!

Возможно ли промаркировать пару обычных кубических костей так, чтобы они давали то же распределение,
что и стандартная пара с 1, 2, 3, 4, 5, 6?

12. Дан набор из N<27 неповторяющихся последовательных символов "A".."Z" (set, array или string).
Предложите алгоритм получения всех комбинаций из K элементов (самих комбинаций, а не нахождения числа C(n,k)).
Пример для N=4, K=2
AB AC AD BC BD CD

← →
default © (2005-02-11 17:44) [1]

сранно, что-то никто задачи не решает..
2.
MBo © (11.02.05 09:06)
а можно, например, хранить массив дополний размера каждой строки до L?

← →
Antonn © (2005-02-11 17:50) [2]

4. может глупость скажу: вероятность быть ближе к центру меньше вероятности быть ближе к стенки в 4 раза.

← →
Antonn © (2005-02-11 17:53) [3]

8 И еще одна глупость: не более 91,92 дюйма.

← →
MBo © (2005-02-11 17:55) [4]

> можно, например, хранить массив дополний размера каждой строки до L?

Да, можно.

> центру меньше вероятности быть ближе к стенки в 4 раза
неверно

← →
MBo © (2005-02-11 17:57) [5]

>8 И еще одна глупость: не более 91,92 дюйма.
совсем не то

← →
default © (2005-02-11 17:59) [6]

MBo © (11.02.05 17:55) [4]
ну так после прочтения файла и создав такой массив по ходу этого мы разыгрываем датчиком номео строки из полученного числа строк затем по данному массиву определяем позицию и размер выпавшей строки позиционируем указатель файла в расчитнное место и читаем нужное число байт тобишь строку, так подойдёт?

← →
default © (2005-02-11 18:03) [7]

4.
0.25Pi?

← →
default © (2005-02-11 18:05) [8]

4. [7] не то
(0.125^2)Pi?

← →
default © (2005-02-11 18:10) [9]

4. [8] не то:)
(0.25^2)Pi?

← →
MBo © (2005-02-11 18:16) [10]

>default © (11.02.05 17:59) [6]
я понял вопрос в [1] как возможность использовать дополнительную память размером в одну строку длиной L - это делать можно. А вот второй раз прочитать файл - нельзя (например, входной поток читается с консоли, на которой неизвестное число бабуинов набьют по одной строчке)

>4.0.25Pi? (0.125^2)Pi?
нет. Могу сказать для ориентировки, что эта вероятность будет более 1/6 но менее 1/4

← →
default © (2005-02-11 18:24) [11]

MBo © (11.02.05 18:16) [10]
я знаю что она меньше площади квадрата со стороной 0.5(0.5^2=0.25=1/4)
и больше площади круга радиуса 0.25(~3.14*0.25^2~0.19>1/6)
а считал площадь за круг хотя знал что неверно....таv наверно какая-то замысловатая фигура получится...подумаю

← →
default © (2005-02-11 18:51) [12]

4.
4*Intergral(0, Pi/2)[df/(2+sinf+cosf)]

← →
jack128 © (2005-02-11 18:53) [13]

4)
(S sqrt(1/4+x^2)dx - 1/8) * 4 где S - интеграл от 0 до 1/2. Как такие интегралы берутся - я не знаю, и не знаю, берущиеся ли они вообще..

← →
Vit@ly © (2005-02-11 19:02) [14]

4.
1/3

← →
VMcL © (2005-02-11 19:13) [15]

1. Слева направо: 4, 6.

← →
jack128 © (2005-02-11 19:23) [16]

default © (11.02.05 18:51) [12]
4*Intergral(0, Pi/2)[df/(2+sinf+cosf)]
это как это ты такое получил??
Vit@ly © (11.02.05 19:02) [14]
нет. см [10] и [11]

← →
default © (2005-02-11 19:29) [17]

jack128 © (11.02.05 19:23) [16]
я знаю что неверно, но думаю ход верен...
посчитай свой интеграл в маткаде к примеру и скажи число

← →
jack128 © (2005-02-11 19:43) [18]

блин, да, я ошибся.

← →
Vit@ly © (2005-02-11 19:50) [19]

jack128 © (11.02.05 19:43) [18]
блин, да, я ошибся.
Это ты к чему (кому)?

← →
jack128 © (2005-02-11 20:00) [20]

Vit@ly © (11.02.05 19:50) [19]
к default"у.
не беспокойся, [14] - не верно :-)

← →
Vit@ly © (2005-02-11 20:23) [21]

Похоже, что столбы высотой a, b, и c
требует уточнения (относительно стороны единичного треугольника). Поскольку, например при а=1, в=1 и с=100, на полу двора такой точки не существует
Возможно, я и не прав

← →
хм © (2005-02-11 20:28) [22]

4. 0.22

← →
jack128 © (2005-02-11 20:35) [23]

4. 0.191?

← →
default © (2005-02-11 20:38) [24]

jack128 © (11.02.05 20:35) [23]
неа
4.
млин, эти геометрические вероятности мать их:)
вроде всё верно думаешь, а получается чёрти что...:)
аля парадокс Бертрана...

← →
Agent13 © (2005-02-11 20:55) [25]

2. Допустим S - строка, которая пойдёт на вывод.
Читая строку с номером N с вероятностью 1/N присваиваем S значение только что прочитанной строки, иначе оставляем то, какое было.

← →
Vit@ly © (2005-02-11 20:58) [26]

см. Vit@ly © (11.02.05 19:02) [14] :))))
Чем не нравится:) и при чем здесь эти геометрические вероятности мать их:)
):(

← →
jack128 © (2005-02-11 21:07) [27]

default © (11.02.05 20:38) [24]
вроде всё верно думаешь, а получается чёрти что...:)
default © (11.02.05 20:38) [24]
jack128 © (11.02.05 20:35) [23]
неа
4.
млин, эти геометрические вероятности мать их:)
вроде всё верно думаешь, а получается чёрти что...:)

Но ведь хм(с) - решил ;-)

Ну вот смотри. Я никаких заумностей не делаю, напролом шел:
центр координат в центре квадрата. для x > 0 и y > x sqrt(x^2 + y ^2) = 1/2 - y
-> y = 1/4 - x^2
теперь проведи диагональ в квадрате к правому-верхнему углу. Нужно найти площадь фигуры между y = f(x) и диагональю (y = x). Находим точку пересечения x_пересечения = 1/(2*(sqrt(2) + 1)) Соответственно
(Интеграл_от_нуля_до_x_пересечения(1/4 - x^2)dx - 1/2 * x_пересечения^2) * 8 = 0.219, где
1/2 * x_пересечения^2 - площадь треугольника под диагональю,
Интеграл_от_нуля_до_x_пересечения(1/4 - x^2)dx - 1/2 * x_пересечения^2 - площадь той фигуры между диагональю и кривой. Ну и домножаем на 8 из соображений симметрии.

← →
SergP © (2005-02-11 21:37) [28]

> 2.

Наверное что-то типа:

i:=1;
while not eof(f) do
begin
readln(f,s);
if random(i)=0 then L:=s;
inc(i);
end;

← →
SergP © (2005-02-11 21:37) [29]

> 2.

Наверное что-то типа:

i:=1; while not eof(f) do begin readln(f,s); if random(i)=0 then L:=s; inc(i); end;
?

← →
SergP © (2005-02-11 21:43) [30]

> [25] Agent13 © (11.02.05 20:55)
> 2. Допустим S - строка, которая пойдёт на вывод.
> Читая строку с номером N с вероятностью 1/N присваиваем
> S значение только что прочитанной строки, иначе оставляем
> то, какое было.

Блин... опередил....

← →
default © (2005-02-11 23:03) [31]

jack128 © (11.02.05 21:07) [27]
ага
точно также делал только в полярных координатах и там где-то напутал...
SergP © (11.02.05 21:37) [29]
угу и этот алгоритм очень просто доказать по индукции

← →
palva © (2005-02-11 23:28) [32]

Математики! скоро вас запретят.
http://www.polit.ru/fiction/2005/01/24/smyatkin.html

← →
palva © (2005-02-12 00:55) [33]

Ну вот, сразу разбежались. Пошутил я.

← →
default © (2005-02-12 01:20) [34]

palva © (12.02.05 00:55) [33]
хочешь какую-нить задачку порешать?

← →
SergP © (2005-02-12 03:55) [35]

> 12. Дан набор из N<27 неповторяющихся последовательных символов
> "A".."Z" (set, array или string).
> Предложите алгоритм получения всех комбинаций из K элементов
> (самих комбинаций, а не нахождения числа C(n,k)).
> Пример для N=4, K=2
> AB AC AD BC BD CD

procedure BrutForce(const s,z:string;const p,k:integer); var i:integer; begin for i:=p to length(s)-k+1 do if k=1 then SOMEPROCEDURE(z+s[i]) else BrutForce(s,z+s[i],i+1,k-1); end;

Вызов процедуры: brutforce(S,"",1,K); // S-исходный набор символов

← →
jack128 © (2005-02-12 06:18) [36]

8)
30.641

← →
default © (2005-02-12 10:26) [37]

3. нет
насколько я понял задачу, она равносильна задаче о движении точек по прямой где одна точка изначально расположена правее другой(если движение идёт вправо) притом движется быстрее
11.возможно
например, работает такая комбинация:
1,2,2,3,3,4 1,3,4,5,6,8

← →
вредитель (2005-02-12 11:23) [38]

default © (12.02.05 10:26) [37][Ответить]
3. нет

Попытаюсь на пальцах, ибо лень.
Если паук не движется.
При растяжении шнура паучище, держась за него всеми лапами, отъезжает вперед, при наступлении очередной секунды всегда остается в середине шнура (в середину перемещается точка, которая находилась на конце шнура, ибо длина его была 1м и чел. двежется со скоростью 1 м/с). При движении человека скорость движения недвижимого (своими лапами:) паука относительно человека постоянно уменьшается т.е. сначала длина шнура прибавилась на 1/2, потом на 1/3, потом на 1/4 и т.д., в общем в пределе стремится к нулю. Двигаясь с постоянной, относительно человека, скоростью паучище обязательно должен догнать этого живодера и очень больно его укусить.

← →
default © (2005-02-12 12:10) [39]

вредитель (12.02.05 11:23) [38]
я условия не понял сначала
"При растяжении шнура паучище, держась за него всеми лапами, отъезжает вперед, при наступлении очередной секунды всегда остается в середине шнура (в середину перемещается точка, которая находилась на конце шнура, ибо длина его была 1м и чел. двежется со скоростью 1 м/с). "
это почему же ВСЕГДА?
после первой секунды это так иначе - нет
можно же растяжение представить так - есть отрезок прямой изначально длиной 1 м
растяжение означает смещение каждой старой точки в сторону растяжения на заданную величину(1м)
то есть паук(точка) если сам ползти не будет всегда будет оставаться в метре от человека
естественно если поползёт до догонит его обязательно

← →
palva © (2005-02-12 12:49) [40]

default © (12.02.05 01:20) [34]
> хочешь какую-нить задачку порешать?

Конечно, хочу, но не всё понимаю. Вот, например, 6. Что значит найти точку? Указать ее координаты? Геометрически построить ее несложно. Нужно описать окружность вокруг треугольника, образуемого вершинами столбов, и через центр этой окружности перпендкулярно плоскости треугольника провести прямую до пересечения с плоскостью земли. Если это пересечение окажется внутри двора, то это и будет искомая точка P. Будет ли такой ответ решением задачи?

← →
palva © (2005-02-12 13:08) [41]

8. 65/Sqrt(2)
Правильно?

← →
default © (2005-02-12 13:09) [42]

опс, глупость в [39] сморозил

← →
Alx2 © (2005-02-12 13:14) [43]

9. точки (1/2,1/4) или (-1/2,1/4) площадь = 4/3
S = 1/48*(1/x0+4*x0)^3 где x0 - абсцисса точки из которой проводится нормаль.

4. (3-sqrt(2))/3 * ctg(3/8*Pi)

12.
{$APPTYPE CONSOLE} const dic: String="ABCDEFGHIJKLMNOPQRSTUVWXYZ"; N = 5; K = 3; var cc: array [1..K] of 1..4; i, j, d: Integer; begin for i := 1 to K do cc[i] := i; while(True) do begin for i := 1 to K do Write(dic[cc[i]]); WriteLn; d := 0; for j:=K downto 1 do begin if cc[j] < N - K + j then begin d := j; break end end; if d > 0 then begin Inc(cc[d]); j := cc[d] + 1; for i := d + 1 to K do begin cc[i] := j; Inc(j) end end else begin break; end end end.

9. 0.5

9. Можно ли предположить, что площадь будет тем меньше, чем меньше разность по X между 2-мя точками пересечения параболы и прямой? Если да, то [45].

5. Допустим, что 123456789 является членом этой последовательности. Предыдущий член этой последовательности не более чем 9-значный, поэтому имеет сумму цифр не более 81. Следовательно предыдущий член имеет следующую десятичную запись: 1234567xy, где x и y целые в диапазоне от 0 до 9. Теперь смотрим, как получились последние две цифры в числе 123456789 и составляем уравнение:

10x+y+10x+y+28+x+y=89 или после приведения подобных
21x+3y+28=89

Слева стоит число вида 3k+1, а справа число вида 3k+2, поэтому уравнение не имеет решения в целых числах.

Таким образом число 123456789 не является членом последовательности.

Верные ответы:
1. 4,6
2. Очередная строка с вероятностью 1/N (N-ее номер) заменяет имеющуюся
4. (4*Sqrt(2)-5).3=~0.2189
5. Не является. можно доказывать также через сумму цифр по модулю 9
9. x=+-1/2, S=4/3
10. 1,2,2,3,3,4 1,3,4,5,6,8
12. ОК, даны рекурсивный и нерекурсивный алгоритмы.
Теперь интересно рассмотреть такой подход - каждая комбинация соответствует n-разрядному числу, в двоичной записи которого установлено k единичных бит. Это соответствует устройству set (для указанного размера вместится в 4 байта, что приводимо к Integer). Вот как бы поэффективнее получить набор этих чисел?

35! Делится на 11. Расположим столбиком частное от деления на 11, это же частное, сдвинутое влево на один разряд, и само число 35! Имея ввиду, что сумма первых двух чисел равна третьему можно заняться восстановлением цифр частного. Восстановление можно вести с обоих концов числа, причем процесс упирается в неизвестные цифры числа 35! Вот что у нас получилось:

_093937708785328uxxxxx6968303411200000000 093937708785328uxxxxx6968303411200000000 1033314796638614a9296b6651337523200000000
Сразу же замечаем, что либо u=5, либо u=6

Далее, перебираем варианты b=0,1...9 и, восстанавливая цифры x от конца к началу, смотрим чему получается равным b. Не все варианты получаются допустимыми. Мы выпишем здесь 2 варианта:

b=0
_0939377087853286357236968303411200000000 0939377087853286357236968303411200000000 10333147966386149929606651337523200000000
b=1
_093937708785328u448146968303411200000000 093937708785328u448146968303411200000000 1033314796638614a929616651337523200000000
Дальше восстанавливать цифры невозможно, поскольку u не может здесь быть ни 5, ни 6. Это единственный недопустимый вариант.

Удобнее и быстрее проводить этот процесс в текстовом редакторе.

Всего получается 9 вариантов:
a=0 b=2 a=1 b=3 a=2 b=4 a=3 b=5 a=4 b=6 a=5 b=7 a=6 b=8 a=7 b=9 a=9 b=0
Из этих вариантов возможен только тот, который дает сумму цифр, деляющуся на 9 (поскольку 35! делится на 9). Если посчитать сумму всех цифр кроме a и b, то получается 134, следовательно сумма цифр a и b может быть либо 1, либо 10. У нас это дает единственный вариант: 4 6

Ответ: 4 6

2 MBo
А как по поводу реплики по 6 задаче Vit@ly © (11.02.05 20:23) [21]
Мне кажется, что на высОты столбов необходимы, какие-то дополнительные ограничения?

10.
о какой высоте идёт речь? чем выше прыгнешь тем больше угол обстрела...

>Vit@ly © (12.02.05 21:05) [50]
А зачем ограничения?
Решение задачи может подразумевать, что они будут даны в ответе.
Даже и без ограничений - такая точка на плоскости существует, пусть даже она за пределами двора.

>default © (13.02.05 00:24) [51]
если прыгнешь на 200 м., угол будет меньше, чем при прыжке на 100 м. ;)

11. Если допускать, что числа могут быть произвольными целыми, то имеются тривиальные решения: можно взять две традиционные кости, на одной из них увеличить все числа на гранях на k, а на другой - уменьшить. Интереснее, если все числа должны быть целыми положительными. Здесь, наверно, можно составить программу для перебора грубой силой, которая выполнялась бы за приемлемое время.

Ну что, программу написал
{$APPTYPE CONSOLE} type TDice=array [1..6] of 1..11; var Dice1, Dice2: TDice; // Это шестигранные кости var g: Integer; // Число вызовов функции test procedure test; forward; // Функция проверки procedure init_dice(var Dice: TDice); forward; function next_dice(var Dice: TDice): Boolean; forward; procedure main; var i: Integer; begin (* На обоих костях числа должны начинаться с единицы и не убывать Наибольшие значения каждой кости в сумме должны равняться 12; из соображений симметрии можно также считать, что первое значение не превышает второе. Числа кроме первого и последнего должны быть в диапазоне 2..11, отсюда в частости вытекает, что наибольшие числа кости должны быть не меньше трех. *) // Начальные присваивания Dice1[1] := 1; Dice2[1] := 1; for i:=3 to 11 do begin // Цикл по наибольшему числу writeln("Step ", i - 2); Dice1[6] := i; Dice2[6] := 12 - i; init_dice(Dice1); repeat // Цикл по первой кости init_dice(Dice2); repeat // Цикл по второй кости test; until next_dice(Dice2); until next_dice(Dice1); end; end; procedure test; type Tptrn = array [2..12] of byte; const ptrn: TPtrn = (1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1); var i, j, k: Integer; freq: TPtrn; OK: Boolean; begin Inc(g); for k := 2 to 12 do freq[k] := 0; for i := 1 to 6 do for j := 1 to 6 do Inc(freq[Dice1[i] + Dice2[j]]); OK := True; for k := 2 to 12 do begin if freq[k] <> ptrn[k] then begin OK := False; break; end end; if OK then begin // Печать костей Write("OK! "); for i:=1 to 6 do Write(Dice1[i]:3); Write(" "); for i:=1 to 6 do Write(Dice2[i]:3); WriteLn; end; end; procedure init_dice(var Dice: TDice); var i: Integer; begin for i := 2 to 5 do Dice[i] := 2; end; function next_dice(var Dice: TDice): Boolean; var i, j, k, d6m1: Integer; begin d6m1 := Dice[6] - 1; j := 1; for i:=5 downto 2 do begin if Dice[i] < d6m1 then begin j := i; break; end; end; if j > 1 then begin k := Dice[j]; Inc(k); Dice[j] := k; for i := j + 1 to 5 do Dice[i] := k; Result:=False; end else begin Result:=True; end end; begin g := 0; main; writeln("Number of test function calls ", g); end.
Выдача:
Step 1 Step 2 OK! 1 2 2 3 3 4 1 3 4 5 6 8 Step 3 Step 4 OK! 1 2 3 4 5 6 1 2 3 4 5 6 Step 5 Step 6 OK! 1 3 4 5 6 8 1 2 2 3 3 4 Step 7 Step 8 Step 9 Number of test function calls 5830
Кроме традиционного случая выдало еще два варианта, которые симметричны друг другу.

Окончательный ответ
1 2 2 3 3 4 1 3 4 5 6 8

palva © (13.02.05 13:13) [55]
уже решено было 11
см выше
только MBo номер 10 поставил а не 11
а решал я перебором(не самым тупым) без компа...

palva © (13.02.05 13:13) [55]
наверное, более оптимальный перебор это если идти с концов
то есть рассматривать суммы 2,12 потом 3,11 и тд
вручную достаточно быстро так перебирать уж никак не
5830 вариантов...

6. Высоты z1 z2 z3
при вершинах первая - в начале оси координат, третья - на оси абсцисс:
координата x есть (z3^2-z1^2+1)/2, по y : sqrt(3)/6 * (1+2*z2^2-z1^2-z3^2)

10. ~=15m

← →
аштшл (2005-02-14 00:24) [60]

так что в 6 задаче длина верёвки дана?

← →
аштшл (2005-02-14 00:31) [61]

Нашёл длины сторон треугольника построенного по вершинам столбов. А нужно ли ? =)
sqrt(1+b^2+a^2-2ab)
sqrt(1+c^2+a^2-2ac)
sqrt(1+b^2+c^2-2cb)

Пятничная разминка заскорузлых нейронов и аксонов :) Найти похожие ветки