Пятница. Большая пачка сложных задачек...

← →
MBo © (2004-07-23 09:59) [0]

1. 100 человек стоят у трапа самолета, у всех есть билеты, в самолете как раз
100 мест. Вдруг с места срывается сумашедшая старуха и занимает первое попавшееся
место. Дальше все идут по-очереди. Так как они нормальные люди, каждый сначала
пытается занять сво± место по билету. Ну а если оно занято, то какое попало.
Какова вероятность того, что последний пассажир сядет на свое место?

2. - Я слышу, что в саду играют дети, - сказал Иванов. - Неужели все они ваши?
- Боже упаси, конечно, нет, - воскликнул профессор Интегралов, известный специалист по теории чисел. - Там, кроме моих детей, играют еще дети троих соседей, но наша семья самая большая.
У Лавочкиных детей меньше, чем у меня, а у Скамейкиных - еще меньше, а меньше всего детей у Табуреткиных.
- А сколько всего детей? - спросил Иванов.
- На этот вопрос я так отвечу, - сказал Интегралов. - Детей меньше восемнадцати, а если перемножить между собой число детей в семьях, то получится номер моего дома, который вы видели, когда пришли.
Иванов достал из кармана блокнот и карандаш и принялся за вычисления. Через некоторое время он поднял голову и сказал:
- Нужна еще какая-то информация. У Табуреткиных больше одного ребенка?
Как только Интегралов ответил, Иванов сразу нашел решение и правильно назвал число детей в каждой семье.

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

3. Можно ли на обыкновенной бумаге в клетку нарисовать выпуклый пятиугольник так, чтобы все его вершины были в узлах, и больше ни одного узла ему не принадлежало?

4. В памяти суперкомпьютера находится заполненная некоторым образом матрица А[M,N] (M и N очень большие числа). Каждая клетка матрицы может иметь значение 0 или 1.
Необходимо придумать алгоритм для преобразования матрицы следующим образом:
- Элемент в новой матрице A[i,j]=1, если в изначальной матрице в сторке i есть хоть один элемент =1 И в столбце j есть хоть один элемент =1.
- Иначе элемент в новой матрице A[i,j]=0.
Ограничение: в памяти нет места для временного размещения еще одной такой матрицы, так как первая занимает 90% всей памяти компьютера.

5. Ниже приведён список из 10 утверждений,
позволяющий однозначно определить натуральное число N.
К сожалению, некоторые из этих утверждений неверны
Но зато все остальные верны

1. По крайней мере одно из двух последних утверждений в списке верно.
2. Это или первое верное или первое неверное утверждение в списке.
3. В списке есть 3 последовательных неверных утверждения.
4. Разность между номерами последнего и первого верных утверждений есть делитель N.
5. N равно сумме номеров всех верных утверждений.
6. Это не есть последнее_верное_утверждение.
7. Номера всех верных утверждений есть делители N.
8. N% всех утверждений верны.
9. Число делителей N, отличных от 1 и N, больше суммы номеров верных утверждений.
10.В списке нет 3-х последовательных верных утверждений.

6. Едем в автобусе, окна замёрзшие. Как подручными средствами (ничего необычного, только,
скажем, пластмассовая линейка) более-менее точно измерить толщину льда на стекле?

7. Что больше |Sin(2001^2002)| или 0.5?

8. Все знают классическую задачу о бассейне - в трубу А втекает, из трубы Б вытекает.

Теперь давайте перейдем к практике. Известно, что скорость вытекания подчиняется закону Бернулли v~sqrt(плотность*g*h).

Ну а теперь сама задача.
Вы на даче расположили переносной (надувной) бассейн. Входное и выходное отверстия на уровне земли.
Бассейн заполняется с постоянной скоростью за время t1. Время слива самотеком t2. Определить время заполнения при незакрытом сливном отверстии. Считать, что бассейн имеет постоянную по высоте площадь сечения.

9. Задача Архимеда: Два цилиндра диаметром 1 пересекаются крестом под прямым углом. Каков объём общей части?

← →
MBo © (2004-07-23 10:00) [1]

10. Животный ряд:
Собака - 3
Корова - 2
Кошка - 3
Петух - 8
Ворона - ?

11. 1) Укажите 1000 идущих подряд натуральных чисел, ни одно из которых не является простым.
2) То же самое, но с дополнительным требованием, чтобы числа непосредственно слева и справа от этого интервала были простыми.

12. Один ёжик (ежиха) бежит с постоянной скоростью по прямой. Когда расстояние до нее становится минимальным, в погоню за ней устремляется ёжик, который бежит с той же скоростью и все время держит курс на неё.
Во сколько раз он сможет сократить расстояние до неё?

13. Трактор тянет за собой бревно (вдоль).
Я хочу его измерить шагами.
Шёл за трактором - насчитал 6 шагов.
В противоположную сторону - 2 шага.
Сколько на самом деле шагов в бревне?

PS
Легко написать систему с суммой и разностью скоростей.
Фишка в том, чтобы найти простое, устное решение.

14. Мои акции 100 дней росли на 1% ежедневно.
А потом стал падать тоже на 1% ежедневно.
Через сколько дней падения я вернусь (почти точно) на прежний уровень?

Токо умоляю, не запускайте калькулятор!
Лучше воспользуйтесь тем, что скорость мала.

15. Белоснежка наливает гномам молока - всем по-разному. После этого происходит следующая забавная процедура: старший гном делит всё своё молоко поровну между 6 другими братьями, потом следующий гном делит всё своё молоко (включая долитое) между 6 другими братьями (включая старшего), и так далее все гномы. После этого у каждого оказывается ровно столько молока, сколько было вначале. По сколько (граммов) разлила Белоснежка каждому?

16. Ваш друг загадал полином с целыми неотрицательными коэффициентами и готов сообщить вам
значения этого полинома сначала в одной, а потом в другой из выбранных вами целочисленных
точек ( вторую из точек можно выбрать после того, как друг выдаст значение полинома в первой точке).
Сможете ли вы отгадать загаданный полином?

17. Иван Царевич шел за украденной Кощеем Василисой Прекрасной и наткнулся на избушку Бабы Яги. Баба Яга его накормила, а потом и говорит:
- Не то нынче время пошло. Кощей уж больно хитер стал. Теперь он усложнил охрану своей иголки жизни. Теперь на высоком дубу на цепях в сундуке, где раньше сидел только один заяц, сегодня сидят целых три – черный, белый и серый. И в каждом зайце по утке (серая шейка, ощипанная утка и утка хромоножка), а в каждой утке по яйцу (обычное яйцо, тухлое яйцо и крашеное яйцо), а в каждом яйце по иголке (обычная иголка, цыганская иголка и кощеева игла). И в каждом своя игла, яйцо и утка сидит. И только одна игла настоящая (кощеева) и несет смерть ему. И беда то в том, что если схватить одного зайца, открыв сундук, то два других убегут. Поэтому надо точно знать какого зайца хватать, в котором та самая утка, в которой то самое яйцо, в котором та самая игла. А известно очень мало:
- Настоящей иголки кощея нет в утке хромоножке и нет в обычном яйце.
- Крашеного яйца нет в утке серой шейке.
- Тухлое яйцо находится в черном зайце.
- Цыганская игла в тухлом яйце.
- А в белом зайце сидит либо утка серая шейка, либо утка хромоножка.

Иван царевич был не дурак и сказал, что завтра по утру без труда схватит нужного зайца.

В каком зайце сидит какая утка, в которой какое яйцо, где лежит кощеева игла? И как Иван Царевич это определил?

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

← →
MBo © (2004-07-23 10:16) [2]

Пардон, забыл указать, что в задаче
>7. Что больше |Sin(2001^2002)| или 0.5?
аргумент в ГРАДУСАХ

← →
Sandman25 © (2004-07-23 10:18) [3]

4. Объявляем вектора B[M] и С[N]. Они занимают меньше 10%, если M,N > 9.
Записываем в B[I] 1, если в I-той строке есть 1.
Записываем в C[J] 1, если в J-том столбце есть 1.
Пробегаемся по A: A[I, J] = B[I] and C[J]

← →
Alx2 © (2004-07-23 10:23) [4]

7. sin больше :)))

← →
MBo © (2004-07-23 10:25) [5]

>Sandman25 © (23.07.04 10:18) [3]
ЗдОрово!
Задача, говорят, с интервью Microsoft.

← →
Sandman25 © (2004-07-23 10:25) [6]

7. Получается примерно sin (10г), то есть sin меньше.

← →
MBo © (2004-07-23 10:27) [7]

>sin (10г),
где-то ты ошибся

← →
Sandman25 © (2004-07-23 10:28) [8]

[5] MBo © (23.07.04 10:25)

:)
Сначала пытался найти решение без использования массивов, только со скалярами. ИМХО это невозможно, если в массивы нельзя записывать ничего, кроме 0 и 1.

← →
jack128 © (2004-07-23 10:37) [9]

1) Если не особо заморачиваться, то 99%

← →
Думкин © (2004-07-23 10:39) [10]

> [9] jack128 © (23.07.04 10:37)

1/2

← →
jack128 © (2004-07-23 10:41) [11]

> 9] jack128 © (23.07.04 10:37)
да, ступил..

← →
Sandman25 © (2004-07-23 10:46) [12]

7. 2001^2002=(N+X)*180, N целое, 0<=X<1
2002lg2001=lg180+lg(N+X)
lg(N+X)=6606,8413989445919237284910658068
lg(K+X)=0,8413989445919237284910658068
K+X=6,9406308230315654834043075240474
X=0,9406308230315654834043075240474

|sin(2001^2002)|=|sin(0,9406308230315654834043075240474*180)|=0,18543426182122394696410154707374 < 0.5

← →
Sandman25 © (2004-07-23 10:50) [13]

[12] Sandman25 © (23.07.04 10:46)

Опять ступил :(

← →
MBo © (2004-07-23 10:54) [14]

>Sandman25 © (23.07.04 10:28) [8]
>Сначала пытался найти решение без использования массивов, только со скалярами.

Видел псевдокод без использования доп. массивов, но еще не разбирался. Ближе к вечеру посмотрю.

← →
Sandman25 © (2004-07-23 11:08) [15]

10. Ворона - 5?

← →
MBo © (2004-07-23 11:11) [16]

>10. Ворона - 5?
нет

← →
mrcat © (2004-07-23 11:15) [17]

10. 14 ?

← →
MBo © (2004-07-23 11:18) [18]

>10. 14 ?
Нет

← →
mrcat © (2004-07-23 11:24) [19]

10. 14 ?
5 + 8 = 13 :)

← →
Sandman25 © (2004-07-23 11:29) [20]

16. Задача непонятна. Друг сообщил еще и степень полинома? Иначе найдем линейную функцию :)

← →
Fishka (2004-07-23 11:36) [21]

10. 13

← →
DimKa © (2004-07-23 11:56) [22]

2. А номер дома не указан?

← →
MBo © (2004-07-23 12:04) [23]

>5 + 8 = 13 :)
Нет.
Задачу часто легко решают дети, в отличие от взрослых.

>Sandman25 © (23.07.04 11:29) [20]
>16. Задача непонятна. Друг сообщил еще и степень полинома? Иначе найдем линейную функцию :)

Нет, степень полинома неизвестна.

>DimKa © (23.07.04 11:56) [22]
>2. А номер дома не указан?
Не указан, но нам известно, что Иванов его знает.

← →
Думкин © (2004-07-23 12:06) [24]

10. 3

← →
DimKa © (2004-07-23 12:11) [25]

14. 99 дней

← →
Sandman25 © (2004-07-23 12:25) [26]

16.
F(X)=a1*X^^n+a2*X^^(n-1)...+a(n-1)

Пусть я скажу точку 1, мне скажут Y1=a1+a2+...+a(n-1).
Потом я скажу точку 2, мне скажут Y2.
Тогда степень полинома <= [log2(Y2-Y1)].
Имеем Y2=F(X2)=2^^n*a1+2^^(n-1)*a2+..+a(n-1).
Y2-Y1=a1(2^^(n-1))+a2(2^^(n-2))...
Остается перевести число Y2-Y1 в двоичную систему и решить систему уравнений.
Например, если Y1=5, Y2=15, то
N <= 3
10=8+2

a1+a2+a3=5
4a1+2a2+a3=15

Вычитаем уравнения
3a1+a2=10
a1=3
a2=1
F(X)=3x^^2+x+1

← →
Sandman25 © (2004-07-23 12:28) [27]

"Остается перевести число Y2-Y1 в двоичную систему"
и
"10=8+2" в решении не принимают участия, ошибся

← →
Думкин © (2004-07-23 12:33) [28]

> [26] Sandman25 © (23.07.04 12:25)
> 16.
> F(X)=a1*X^^n+a2*X^^(n-1)...+a(n-1)

у = 10*x-5
y(1) = 5
y(2) = 15

← →
Sandman25 © (2004-07-23 12:37) [29]

[28] Думкин © (23.07.04 12:33)

Понятно. Такое ощущение, что X должны быть простыми и как можно больше :)
Например, X1=103. получаем Y=120022. Тогда X2=101^^3

← →
Agent13 © (2004-07-23 12:54) [30]

5. 420. Многовато что-то, но вроде подходит.

← →
DimKa © (2004-07-23 12:58) [31]

15. последнему гному вообще не налилили?
Если это так, то я на првильном пути, если нет, ну ее задачу эту )

← →
MBo © (2004-07-23 13:00) [32]

>Думкин © (23.07.04 12:06) [24]
10. 3

да

>DimKa © (23.07.04 12:11) [25]
14. 99 дней
Да

← →
MBo © (2004-07-23 13:15) [33]

>DimKa © (23.07.04 12:58) [31]
Правильным путем идете, товарищ! ;)

>Agent13 © (23.07.04 12:54) [30]
5. 420. Многовато что-то, но вроде подходит.

Верно!

>Sandman25 © (23.07.04 12:25) [26]
Кое-что верно (сначала P(1) спрашиваем), и ключевая идея близко

← →
Думкин © (2004-07-23 13:28) [34]

16. Да ключевая фраза - неотрицательные. Поэтому мой пример отпадает.
P(1) - оценка, потом любое простоте болше ответа - и далее ясно.

← →
MBo © (2004-07-23 13:31) [35]

>Думкин © (23.07.04 13:28) [34]
простое - не обязательно

← →
Думкин © (2004-07-23 13:36) [36]

> [35] MBo © (23.07.04 13:31)

Верно. :-)

← →
default © (2004-07-23 13:41) [37]

MBo © (23.07.04 10:54) [14]
можно без массивов сделать создать теже массивы что и у Sandman25
но записать их в верхнюю строку матрицы и левый столбец
по ним заполнить "внутреннюю матрицу"
но при записи строк будет перекрытие элемента (1, 1)
надо это учесть сохранив нужные(ое) значения(ие) при "конечном" заполнении левого столбца и верхней строки

← →
default © (2004-07-23 13:47) [38]

"но при записи строк будет перекрытие элемента (1, 1)"-->
но при записи верхней строки и левого столбца будет перекрытие элемента (1, 1)

← →
DimKa © (2004-07-23 14:05) [39]

11. А такое вообще возможно?

← →
Sandman25 © (2004-07-23 14:10) [40]

Думкин, MBo

Растолкуйте, пожалуйста, принцип отображения в 10 задаче...

← →
ИдиотЪ (2004-07-23 14:10) [41]

1. 1/100

← →
MBo © (2004-07-23 14:18) [42]

>Sandman25 © (23.07.04 14:10) [40]
>Растолкуйте, пожалуйста, принцип отображения в 10 задаче...
собака - гав

>DimKa © (23.07.04 14:05) [39]
>11. А такое вообще возможно?
11.1 - возможно
11.2 - под вопросом

← →
Sandman25 © (2004-07-23 14:22) [43]

[42] MBo © (23.07.04 14:18)

Lol :)
А я то уже почти нашел последовательность...
Собака - сумма порядковых номеров букв в русском алфавите mod 16 = 3
Кошка - 3
Корова - 2
Петух - 7 (вместо 8).

← →
default © (2004-07-23 14:22) [44]

MBo © (23.07.04 14:18) [42]
вороно кар - 3 буквы)

← →
Sandman25 © (2004-07-23 14:24) [45]

11.
1) 1000!+N, 1<N<1000
2) написал программу, запустил, за полтора часа дошла до 2 миллиардов, ответа все еще не было, остановил.

← →
DimKa © (2004-07-23 14:26) [46]

> 11.1) 1000!+N, 1<N<1000

Ужас )

← →
Sandman25 © (2004-07-23 14:30) [47]

Точнее,
1001!+N, 1<N<1001

← →
Sandman25 © (2004-07-23 14:30) [48]

или еще точнее
1001!+N, 1<N<=1001

← →
MBo © (2004-07-23 14:37) [49]

>Sandman25 © (23.07.04 14:24) [45]
11.2) написал программу, запустил, за полтора часа дошла до 2 миллиардов, ответа все еще не было, остановил.

;)
Есть очень простое соображение, которое сразу дает ответ - возможно ли.

← →
Agent13 © (2004-07-23 14:37) [50]

> 2) написал программу, запустил, за полтора часа дошла до
> 2 миллиардов, ответа все еще не было, остановил.

LOL. Терпеливый :) Я сделал тоже самое, меня хватило на 15 минут...

← →
Sandman25 © (2004-07-23 14:40) [51]

[49] MBo © (23.07.04 14:37)

Понятно. Буду думать о числе 1000 :)

[50] Agent13 © (23.07.04 14:37)

Я на обед уходил :)

← →
Sandman25 © (2004-07-23 14:43) [52]

11.
2)
Разница между простыми числами всегда четная.
А в нашем случае она получается 1001.

Самое смешное, что я по этому признаку еще в самом начале проверял, но почему-то посчитал, что разница 1000 :)

← →
default © (2004-07-23 14:59) [53]

17.
заяц: серый
утка: ощипанная
яйцо: крашеное
иголка(по условию): кощеева
в решении есть два варианта, но в обоих из них нужное лежит в сером зайце

← →
Agent13 © (2004-07-23 15:00) [54]

17.
Заяц - белый, серый, чёрный.
Утка - ?, ощипанная, ?.
Яйцо - обычное, крашеное, тухлое.
Игла - обычная, КОЩЕЕВА, цыганская.

← →
Agent13 © (2004-07-23 15:03) [55]

Блин и как всегда меня опередили

← →
default © (2004-07-23 15:04) [56]

Agent13 © (23.07.04 15:00) [54]
а ведь надо было таблицу написать, да одна фигня...

← →
Dmitriy O. © (2004-07-23 15:20) [57]

1 1/100

← →
clickmaker © (2004-07-23 15:35) [58]

> 6. Едем в автобусе, окна замёрзшие. Как подручными средствами
> (ничего необычного, только,
> скажем, пластмассовая линейка) более-менее точно измерить
> толщину льда на стекле?

1.Приложить линейку к кромке окна, запомнить размер от поверхности до края рамы
2.Растопить пальцем лед у кромки окна, приложить линейку, запомнить размер
3.Толщина льда = 2-1

← →
MBo © (2004-07-23 15:39) [59]

>clickmaker © (23.07.04 15:35) [58]
А если толщина льда порядка 1 мм, а измерить хочется с точностью 0.1 мм ?

← →
Agent13 © (2004-07-23 15:45) [60]

18. ~0,608

← →
clickmaker © (2004-07-23 15:53) [61]

> MBo © (23.07.04 15:39) [59]
> >clickmaker © (23.07.04 15:35) [58]
> А если толщина льда порядка 1 мм, а измерить хочется с точностью
> 0.1 мм ?

А какая цена деления у линейки ? :)

← →
Sandman25 © (2004-07-23 15:56) [62]

[61] clickmaker © (23.07.04 15:53)

Соскабливаем лед с 10 разных окон и кладем стопкой :)

← →
clickmaker © (2004-07-23 15:58) [63]

> Sandman25 © (23.07.04 15:56) [62]
> [61] clickmaker © (23.07.04 15:53)
>
> Соскабливаем лед с 10 разных окон и кладем стопкой :)

Под недоумевающими взглядами обалдевших пассажиров :) Особенно в час пик можно так приколоться попробовать...

← →
MBo © (2004-07-23 15:59) [64]

>clickmaker © (23.07.04 15:53) [61]
Цена деления 1 мм.
З.Ы.
Отсутствие необычных предметов не отрицает наличия обычных ;)

>Agent13 © (23.07.04 15:45) [60]
>18. ~0,608
Численно - примерно так. А алгебраическая формула получилась?

← →
clickmaker © (2004-07-23 16:18) [65]

> MBo © (23.07.04 15:59) [64]
> >clickmaker © (23.07.04 15:53) [61]
> Цена деления 1 мм.
> З.Ы.
> Отсутствие необычных предметов не отрицает наличия обычных
> ;)

Хм... Я бы склонился тогда к варианту Sandman25 © (23.07.04 15:56) [62], если бы был уверен, что можно запросто соскоблить пласт льда с окна, пользуясь только обычными предметами

← →
Sandman25 © (2004-07-23 16:23) [66]

[65] clickmaker © (23.07.04 16:18)

Лучше не так. Снимаем 10 окон, соскабливаем лед с наружней стороны, кладем их очищенными сторонами друг к другу (по очереди), чтобы избежать зазоров, измеряем суммарную высоту :)

← →
Agent13 © (2004-07-23 16:25) [67]

> Численно - примерно так. А алгебраическая формула получилась?

Считано на Делфи по следующему алгоритму:

P := 1; for I := 2 to <сколько не жалко> do if IsPrime(I) then P := P - P*1/SQR(I);

где IsPrime - проверка, является ли число простым.
В нормальном алгебраическом виде я такое записывать не умею.

← →
clickmaker © (2004-07-23 16:27) [68]

> 13. Трактор тянет за собой бревно (вдоль).
> Я хочу его измерить шагами.
> Шёл за трактором - насчитал 6 шагов.
> В противоположную сторону - 2 шага.
> Сколько на самом деле шагов в бревне?

Ну если рассуждать так, что Длина бревна - Путь трактора = 2, а Длина бревна + Путь трактора = 6, то получится 4

← →
Sandman25 © (2004-07-23 16:33) [69]

[67] Agent13 © (23.07.04 16:25)

Подозреваю, что придем к золотому сечению.
Только непонятно, почему.

← →
Sha © (2004-07-23 16:39) [70]

MBo © (23.07.04 15:59) [64]
Нагретая линейка прикладывается к стеклу и краю окна под углом.
Она протапливает лед, после чего решаем подобные треугольники.

← →
MBo © (2004-07-23 16:42) [71]

>Agent13 © (23.07.04 16:25) [67]
>Sandman25 © (23.07.04 16:33) [69]
Нет, это не золотое сечение (fi=0.618...)
Выкладки весьма непростые, получается предел суммы некоего довольно известного ряда.

>clickmaker © (23.07.04 16:27) [68]
нет

← →
Sha © (2004-07-23 16:44) [72]

18. Как наугад выбрать натуральное число?

← →
clickmaker © (2004-07-23 16:47) [73]

> Sandman25 © (23.07.04 16:23) [66]
> Лучше не так. Снимаем 10 окон, соскабливаем лед с наружней
> стороны, кладем их очищенными сторонами друг к другу (по
> очереди), чтобы избежать зазоров, измеряем суммарную высоту
> :)

Причем, все это надо проделать, не останавливая автобус, и чтоб водила ничего не просек :)

← →
MBo © (2004-07-23 16:47) [74]

>Sha © (23.07.04 16:39) [70]
ОК, можно так, но есть более точный способ - используется предмет, который обычно есть у каждого (едущего в автобусе)

← →
Sha © (2004-07-23 16:48) [75]

Монета?

← →
Sandman25 © (2004-07-23 16:53) [76]

[71] MBo © (23.07.04 16:42)

Я понимаю. Я построил выражения для первых трех пассажиров, но затем потонул в глубине собственных рассуждений :)

← →
MBo © (2004-07-23 16:58) [77]

>Sha © (23.07.04 16:48) [75]
Да. Ширина процарапанной (движением поперек плоскости монеты) полоски - хорда длиной d, приближенно h=d^2/8R

← →
Sha © (2004-07-23 16:59) [78]

#13
6 шагов туда, 6 шагов обратно, всего 12.
При этом мимо меня проедет 1+3=4 бревна.
Столько бревен мимо меня могли проехать,
если бы я все это время стоял на месте.
Длина бревна = 12 / 4 = 3 шага.

← →
MBo © (2004-07-23 17:04) [79]

>Sha © (23.07.04 16:59) [78]
#13 3 шага.
Верно.
или так - человек сделал 8 шагов, пока трактор проехал 4, скорость отличается в два раза, так что 6 шагов вдоль движ. - 3 шага вдоль стоячего.

← →
Sha © (2004-07-23 17:07) [80]

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

← →
Sandman25 © (2004-07-23 17:10) [81]

[80] Sha © (23.07.04 17:07)

От 2 до N, N->oo

← →
Sha © (2004-07-23 17:11) [82]

Sandman25 © (23.07.04 17:10) [81]
Не понял. Я про распределение вероятности случайного выбора.

← →
Sandman25 © (2004-07-23 17:12) [83]

Равномерное от 2 до N, N стремится к бесконечности

← →
Sha © (2004-07-23 17:15) [84]

Как тебе удалось прочитать это между строк? :)

← →
MBo © (2004-07-23 17:16) [85]

>Sha © (23.07.04 17:07) [80]
Это вопрос сложный. Распределение, если о нем можно тут говорить - равномерное.
предварительный анализ - пусть случайно выбраны числа M и N.
Вероятность, что M делится на простое p = 1/p. Для N - то же самое. Поскольку M и N выбраны независимо, вероятность, что они оба делятся на p = 1/p^2, а что оба не делятся 1-1/p^2.
Для всего множества простых чисел получается
Пi(1-1/P(i)^2)=(1-1/2^2)(1-1/3^2)....

← →
Sandman25 © (2004-07-23 17:18) [86]

N=4, p=2/3
N=5, p=5/6
N=6, p=6/10
N=?, p=?
Получается, в знаменателе N*(N-1)/2,
в числителе реккурентная формула...

← →
Sha © (2004-07-23 17:42) [87]

Про матрицу. Или я чего-то не понял, или проходит простое решение в лоб:
a[i,j]:=a[i,1] or a[i,2] or ... a[i,n] or a[1,j] or a[2,j] or ... a[m,j];

← →
Sandman25 © (2004-07-23 17:44) [88]

[87] Sha © (23.07.04 17:42)

Только что измененный с 0 на 1 элемент будет учитываться как 1 для расчета соседних элементов.

← →
Sha © (2004-07-23 17:46) [89]

А, понятно, тогда, похоже, не обойтись боз временных векторов.

← →
Sandman25 © (2004-07-23 17:48) [90]

[89] Sha © (23.07.04 17:46)

В принципе, можно попробовать задействовать рекурсию, тогда получится без временных векторов. Обход матрицы в ширину :)

← →
Sha © (2004-07-23 17:49) [91]

Хотя, черт его знает. Завтра подумаю, если время будет.

← →
Sandman25 © (2004-07-23 17:51) [92]

Только ведь все равно при подсчете последнего элемента придется "помнить" первоначыальные значения всех использующихся для его расчетов элементов. А уж где они храниться будут - в векторе или стеке, не суть важно.

← →
Sha © (2004-07-23 17:52) [93]

Не совсем понял, хотя возможно мы думаем в одном направлении :)

← →
Sandman25 © (2004-07-23 17:54) [94]

← →
ИдиотЪ (2004-07-23 17:56) [95]

18.
Пусть чисел всего n, возьмем одно простое S(<n), тогда он может иметь делители только с числами i*S, где i=2..m, m - целое деление n на S
Имеем:
вероятность, что встретился с непростым P=(1-m/(n)), n->бескон,
получится ли нормальная вероятность в пределе ?
по-моему, нет предела

← →
Sha © (2004-07-23 17:58) [96]

Sandman25 © (23.07.04 17:54) [94]
еще идея, и без рекурсии
a|b=~((~a)&(~b))

← →
Sandman25 © (2004-07-23 17:58) [97]

[95] ИдиотЪ (23.07.04 17:56)

Вероятность взять число m равна 1/n -> 0

← →
Sandman25 © (2004-07-23 18:00) [98]

[96] Sha © (23.07.04 17:58)

Только учти, что N и M могут быть неизвестны на этапе компиляции. Развернуть цикл в последовательность операторов не получится. Если я правильно понял твою идею...

все, до понедельника :)

← →
Sha © (2004-07-23 18:02) [99]

Sandman25 © (23.07.04 18:00) [98]

Никто развораивать не собирается.
Тот же цикл в лоб с заменой or на and, только инверсия до и после.

← →
ИдиотЪ (2004-07-23 18:03) [100]

Sandman25 ©
я неправильно написал
вероятность встретиться не с тем, кто делится на него
и вроде есть предел, единице равен

← →
Sha © (2004-07-23 18:04) [101]

тоже ухожу.

← →
ИдиотЪ (2004-07-23 18:06) [102]

вероятность равна P=1-1/S
так что на примере простых видно, как различаются вероятности

← →
SergP © (2004-07-23 18:36) [103]

> Sha © (23.07.04 17:42) [87]
> Про матрицу. Или я чего-то не понял, или проходит простое
> решение в лоб:
>
> a[i,j]:=a[i,1] or a[i,2] or ... a[i,n]
> or a[1,j] or a[2,j] or ... a[m,j];

> Sandman25 © (23.07.04 17:44) [88]
> [87] Sha © (23.07.04 17:42)
>
> Только что измененный с 0 на 1 элемент будет учитываться
> как 1 для расчета соседних элементов.

Но на конечный результат это не повлияет. Так что можно и так...

← →
SergP © (2004-07-23 18:42) [104]

А можно делать не совсем векторы, а 2 одномерных массива элементами которых будут номера столбцов и строк исходного массива где встречается 1. А потом заполнить единицами все возможные координаты которые можно получить из наших двух массивов.
По крайней мере будет работать быстрее чем вариант с векторами...

← →
default © (2004-07-23 19:03) [105]

4.
а чем Вам [37] + [38] не нравится?без всяких векторов...

← →
SergP © (2004-07-23 19:08) [106]

> default © (23.07.04 13:41) [37]
> MBo © (23.07.04 10:54) [14]
> можно без массивов сделать создать теже массивы что и у
> Sandman25
> но записать их в верхнюю строку матрицы и левый столбец
> по ним заполнить "внутреннюю матрицу"
> но при записи строк будет перекрытие элемента (1, 1)
> надо это учесть сохранив нужные(ое) значения(ие) при "конечном"
> заполнении левого столбца и верхней строки
>
>
> default © (23.07.04 13:47) [38]
> "но при записи строк будет перекрытие элемента (1, 1)"-->
> но при записи верхней строки и левого столбца будет перекрытие
> элемента (1, 1)

Лучше находим первый попавшийся элемент равный единице и его строку и столбец используем как эти самые векторы. получится что инфа полученая в этих "векторах" не испортит нам итоговые данные, так как будет такой-же самой...

← →
default © (2004-07-23 19:27) [107]

SergP © (23.07.04 19:08) [106]
покажи код(

← →
default © (2004-07-23 19:55) [108]

var
M: Array[1..N, 1..M] of Boolean;
Col: Boolean;
i, j: Cardinal;
begin
// ...
for i := 1 to N do
if M[i,1] then begin
Col := True;
Break
end;
for j := 2 to M do
if M[1,j] then begin
M[1,1] := True;
Break
end;
for i := 2 to N do
for j := 2 to M do
if M[i,j] then begin
M[i,1] := True;
M[1,j] := True;
Break
end;
for i := 2 to N do
for j := 2 to M do
M[i,j] := M[i,1] and M[1,j];
for j := 2 to N do M[1,j] := M[1,j] and M[1,1];
for i := 1 to N do M[i,1] := M[i,1] and Col;

вот...используется только одна дополнительная переменная Col

← →
Alx2 © (2004-07-23 20:18) [109]

Ребята, коль не составит труда, скажите, что не решено еще? Хочется после страшной рабочей пятницы расслабиться :)

← →
MBo © (2004-07-24 07:41) [110]

>Alx2 © (23.07.04 20:18) [109]
>скажите, что не решено еще?
2 3 8 9 12 18

← →
Alx2 © (2004-07-24 12:01) [111]

9. объем равен 2/3. Решаем через тройной интеграл.
x^2+y^2=1/4, x^2+z^2=1/4.
=>
V = int(int(int(1,z=-sqrt(1/4-x^2)..sqrt(1/4-x^2)),y=-sqrt(1/4-x^2)..sqrt(1/4-x^2)),x=-1/2..1/2) = 2/3.

В общем случае V = 2/3*D^3 где D - диаметр цилиндров

← →
Думкин © (2004-07-24 12:03) [112]

> [111] Alx2 © (24.07.04 12:01)

Бедный Архимед. В этом случае - Ньютон отдыхает.

← →
GrayFace © (2004-07-24 12:37) [113]

3) Очень легко

>5. 420. Многовато что-то, но вроде подходит.
>
>Верно!
5) Нет. 20. Верные утверждения:2,3,4,5,6.
6) открыть форточку и измерить.
8) Че значит "Слив самотеком"?
9) Я решал это с произвольным числом цилиндров, только тетрадь надо найти.

← →
MBo © (2004-07-24 12:56) [114]

>GrayFace © (24.07.04 12:37) [113]
8) Че значит "Слив самотеком"?
вода вытекает под действием силы тяжести.
Это непростая расчетная задача, без упрощающих трюков.

9) Я решал это с произвольным числом цилиндров, только тетрадь надо найти.

с произвольным числом цилиндров - не нужно, а вот простое решение существует.

← →
Alx2 © (2004-07-24 13:01) [115]

>Думкин © (24.07.04 12:03) [112]
Ну не Архимед я :)

8. t=t2/t1*(t1+1/2*t2*ln(abs(2*t1/t2-1)));

свелось к решению диффура h"=h0/t1-a*sqrt(h). Где a=2*sqrt(h0)/t2. h0 - макс. уровень воды в бассейне

← →
GrayFace © (2004-07-24 13:39) [116]

2) 2 3 4 5
Номер дома - 120. У Иванова было 3 варианта:
1) 2 3 4 5
2) 1 4 5 6
3) 1 3 5 8
Профессор сказал, что ребенок не один и результат стал очевидным.

← →
MBo © (2004-07-24 13:43) [117]

>GrayFace © (24.07.04 13:39) [116]
Верно

← →
Alx2 © (2004-07-25 09:27) [118]

12. Пусть минимальное расстояние было равным a.
Тогда при времени погони стремящимся к бесконечности растояние между ними станет a/2.

← →
ИдиотЪ (2004-07-25 12:54) [119]

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

← →
MBo © (2004-07-25 13:46) [120]

> 9. Задача Архимеда: Два цилиндра диаметром 1 пересекаются
> крестом под прямым углом. Каков объём общей части?

2/3

> [121] SergP © (25.07.04 23:57)
>
> > 9. Задача Архимеда: Два цилиндра диаметром 1 пересекаются
>
> > крестом под прямым углом. Каков объём общей части?
>
>
> 2/3

Положим наш какую-нить плоскость A. Очевидно что сечение этой общей части цилиндров плоскостью B параллельной плоскости А будет представлять собой квадрат. Пусть R-радиус цилиндров, x-расстояние между плоскостями A и B. тогда сторона квадрата = 2*sqrt(R^2-(R-x)^2), а площадь соответственно:
S(x)=8*R*x-4*x^2

Тогда объем общей части цилиндров равен
V=интеграл от 0 до 2*R S(x)dx
V=16/3*R^3 = 2/3*D^3 (D-диаметр, D=2*R)

SergP © (26.07.04 00:28) [122]

v = h * (s1 + 4 * s2 + s3) / 6

h = 1 - высота,
s1 = 0 - площадь верхнего сечения,
s2 = 1 - площадь среднего сечения,
s3 = 0 - площадь нижнего сечения,

v = 2/3

> v = h * (s1 + 4 * s2 + s3) / 6

Откуда эта формула?

← →
ИдиотЪ (2004-07-26 10:10) [125]

SergP © (26.07.04 10:04) [124]

теорема из старой школы, 10 класс:

если площадь основания фигуры зависит от ее высоты как
s = a * h^2 + b * h + c, где a, b, c - любые,
то объем фигуры равен
v = h * (s1 + 4 * s2 + s3) / 6, где
h - высота,
s1 - площадь верхнего сечения,
s2 - площадь среднего сечения,
s3 - площадь нижнего сечения.

читатать так:
если площадь сечения фигуры зависит от ее высоты как

> [125] ИдиотЪ (26.07.04 10:10)

Он пользовался техникой практически эквивалентной - суммировал и устремлял. ТО есть зачатки интегрального были, только в менее абстрактном и поэтому каждый раз частном случае.

← →
ИдиотЪ (2004-07-26 10:33) [129]

то Думкин ©
я это проходил, но я имел в виду то, что неужели здесь необходим интеграл ?
По крайней мере тут пересечение можно расчленить на более простые составляющие, у меня получилось несколько конусов

> ИдиотЪ (26.07.04 10:33) [129]
> то Думкин ©
> я это проходил, но я имел в виду то, что неужели здесь необходим
> интеграл ?
> По крайней мере тут пересечение можно расчленить на более
> простые составляющие, у меня получилось несколько конусов

Попробовал по разному.... С интегралом все же проще....

[108] default © (23.07.04 19:55)

Решил разобраться на примере, но не работает для простейшего случая: A[1,3] = 1, остальные 0. Массив не изменился.
Идея не совсем понятна, можно объяснить на пальцах? Или поправить код.

[108] default © (23.07.04 19:55)

И самое главное - не вижу, чтобы в рсчетах принимали участие элементы непервой строки и непервого слолбца.

>Какова вероятность того, что последний пассажир сядет на свое место?

Если пассажир №2 пристрелит старушку, то 100%

4. Вероятность того, что и в строке, и в столбце такого огромного массива не окажется "1" очень мала. Так что можно смело заполнять массив единицами. (Шутка с долей истины)
3. Действительно легко. Но предлагаю Ещё задачу
из этого же рода, но сложнее:
Представьте себе сетку из правильных треугольников (то есть три группы параллельных прямых пересекаются под углом 60 гр.). Можно ли построить квадрат так, чтобы все его вершины находились в узлах этой сетки?

Sandman25 © (26.07.04 12:33) [131]
в коде, наверно, где-то наврал...писал тут
есть матрица такая, например
0 1 0 0 0
0 0 1 0 0
0 1 0 1 0
0 0 0 0 0
1)пробегаемся по первому столбцу матрицы и пишем в переменную
Column 1 или 0 в зависимости от того есть там хоть один единичный элемент или нет
в нашем случае Column = 0
2)теперь пробегаемся по строкам матрицы и пишем в элементы первого столбца соотв-нно 1 или 0 в зав-ти от того есть ли в соответствующей строке хоть один единичный элемент
получим такую матрицу
1 1 0 0 0
1 0 1 0 0
1 1 0 1 0
0 0 0 0 0
то есть столбец описывает Ваш вектор B
поскольку предыдущие значения элементов столбца затираются мы и выполняли шаг 1)
3)теперь пробегаемся по столбцам начиная со второго и пишем в верхнюю строку 1 или 0 в зависимости от того есть ли в соот-ем столбце хоть один единичный элемент
получим матрицу
1 1 1 1 0
1 0 1 0 0
1 1 0 1 0
0 0 0 0 0
то есть без первого элемента мы сформировали Ваш вектор С
4)теперь по полученным векторам можно заполнить "внутреннюю" матрицу
получим
1 1 1 1 0
1 1 1 1 0
1 1 1 1 0
0 0 0 0 0
5)теперь надо заполнить первую строку и первый столбец
используя Column и значения первого столбца формируем его конечный вариант без первого элемента(он пригодится для заполнения верхней строки, его мы заполним в самом конце)
получим
1 1 1 1 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0
теперь по первому элементу верхней строки и другим элементом её же заполняем опять же её без первого элемента получим
1 1 1 1 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0
теперь получим первый элемент верхней строки как Column and (1,1)
и в конце получим
0 1 1 1 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0
надеюсь нигде не ошибся...

> [134] Andr © (26.07.04 13:03)
> 4. Вероятность того, что и в строке, и в столбце такого
> огромного массива не окажется "1" очень мала. Так что можно
> смело заполнять массив единицами. (Шутка с долей истины)

Но а как с симметрией:
Вероятность того, что и в строке, и в столбце такого огромного массива не окажется "0" очень мала. Так что можно смело заполнять массив нулями. (Шутка с долей истины)
???

> MBo © (23.07.04 09:59)

У меня есть предложение: почему бы не придлагать на "пьятничные задачки" больше задач хотя-бы смежных с программированием. Это кроме пищи для мозгов, может принести какую-то реальную помощь в работе. Согласитесь, что кроме 4-й задачи, ничего сильно связанного с программированием здесь нету.

Я имею ввиду задачи на написания алгоритмов. Т.е. использование теории графов, работы с "длинными" числами, динамического программирования и т.д и т.п.

ИМХО для программиста это будет полезнее.

[141] Sha © (26.07.04 15:58)

Заметить-то заметил, а вот понять... :)
Имеем черный ящик со входом и выходом. Что в этом ящике -
1) a or b
или
2) not (not a and not b),
совершенно неважно c точки зрения его работы.

> REA © (26.07.04 12:49) [133]
> >Какова вероятность того, что последний пассажир сядет на
> свое место?
>
> Если пассажир №2 пристрелит старушку, то 100%

А вообще-то если имеем дело с самолетами, то там этой сумасшедшей старухе быстро мозги вправят... Последний сядет на свое место 100%, а вот вероятность того что старуха вообще полетит будет довольно низкой... Выкинут нафиг за нарушение порядка... :-)))

Sandman25 © (26.07.04 16:14) [142]

Действительно, результат будет одинаковым - нам это и надо.
А вот реализовать инверсию элементов и умножение можно прямо по месту - никакой дополнительной памяти не потребуется :)

[87] Sha © (23.07.04 17:42)

Действительно, это решение проходит. но оно имеет сложность порядка
O(n*m*(n+m)), в то время как алгоритм от default - O(n*m)

[144] Sha © (26.07.04 21:33)

Не понял. Можно поподробнее?
Вместо
a[i,j]:=(a[i,1] or a[i,2] or ... a[i,n])
and (a[1,j] or a[2,j] or ... a[m,j]);
писать
a[i,j]:=not(not (a[i,1] or a[i,2] or ... a[i,n])
or not (a[1,j] or a[2,j] or ... a[m,j]))?

[146] Sha © (27.07.04 08:55)

Это как? Алгоритм default еще можно оптимизировать, но ИМХО при этом не будет использоваться твой алгоритм.

> Sandman25 © (27.07.04 08:56) [147]
> Не понял. Можно поподробнее?

Идея в следующем.
1. Сначала инвертируем все элементы.
2. Затем вычисляем каждый элемент как логическое
произведения "креста", составленного из элементов,
стоящих в той же строке или столбце. Тут простор для
оптимизации, можно сделать наподобии решения от Default.
3. Напоследок инвертируем все элементы еще раз.

> Sandman25 © (27.07.04 08:57) [148]
> Это как? Алгоритм default еще можно оптимизировать,
> но ИМХО при этом не будет использоваться твой алгоритм

Я имел ввиду, что вроде сложность моего варианта можно
уменьшить до сложности Default. А может быть, и скрестить оба
варианта.

[149] Sha © (27.07.04 09:18)

ИМХО ничего не изменилось.
На втором шаге для каждого элемента просматривается "крест".
В твоем первоначальном варианте то же самое. Зачем добавлять еще 2 прохода по всему массиву для его инвертирования?

> ИМХО ничего не изменилось.
> Зачем добавлять еще 2 прохода по всему массиву для его инвертирования?

Для того, чтобы можно было умножать, не заботясь о последействии.
Есть ощущение, что эти проходы можно частично совместить с основным шагом работы алгоритма.

> В твоем первоначальном варианте то же самое.

Это и есть первоначальный вариант. Вроде, до него ничего не было.

Если время будет, попробую реализовать, но не раньше выходного.
Пока все на уровне ощущений.

[151] Sha © (27.07.04 09:42)

Последействия нет, я ошибался! 1 остаются 1, 0 могут стать 1. Но если 0 стал 1, то это то же самое, что он с самого начала был 1 - ведь он мог стать 1 только в том случае, если в данной строке и данном столбце УЖЕ были 1 и поэтому появление в строке/столбце ЕЩЕ одной 1 ни на что не влияет. Вот если бы мы сумму единиц считали, тогда последействие было бы.

Sandman25 © (27.07.04 09:46) [152]

Ты был прав. Последействие есть.

Пусть имееем
0 0 0
0 1 0

Считаем по строкам. После вычисления a[1,1]:
0 0 0
0 1 0

После вычисления a[1,2]:
0 1 0
0 1 0

После вычисления a[1,3]:
0 1 1
0 0 0
Ошибка: правильное эначение a[1,3]=0

После вычисления a[1,3]:
0 1 1
0 1 0
Ошибка: правильное эначение a[1,3]=0

То есть:
for I := 1 to N do begin for J := 1 to M do if A[I,J] then begin for J1 := 1 to M do if not A[I,J1] then for I1 := 1 to N do if A[I1,J1] then begin A[I, J1] := 1; break; end; break; end; end;

[153] Sha © (27.07.04 09:52)

Если имеем
0 0 0
0 1 0
то и результат будет
0 0 0
0 1 0

Я тоже запутался тогда - нужно не
единица в строке ИЛИ столбце, а в строке И столбце

> тогда - нужно не единица в строке ИЛИ столбце, а в строке И столбце

Для этого и потребовался Морган.

Перечитай задачу.
"- Элемент в новой матрице A[i,j]=1, если в изначальной матрице в сторке i есть хоть один элемент =1 И в столбце j есть хоть один элемент =1."

Ну да, оказывается, все это время думал над другой задачей :(
Зато решил более сложную :)

Я тоже немного подумал, получается примерно так: (вариант похожий на default"овский, но немножко усовершенствованный...
Правда может где и ошибся... Я не проверял...

// Подготавливаем один вектор на месте первой строки A[1..M,1] x:=a[1,1]; for i:=2 to M do begin x:=x or a[i,1]; // в конце цикла в х будет true, если в строке есть хотя бы один true for j:=2 to N do // формируем вектор begin a[i,1]:=a[i,1] or a[i,j]; if a[i,1] then break; // если уже true то далее незачем проверять end; end; // Заполнение массива for j=2 to N do begin // для начала узнаем есть ли в данной строке A[1..M,j] true z:=A[1,j] for i:=2 to M do begin z:=z or A[i,j]; if z then break; end; // если есть то сразу же и заполняем строку... // как видно второй вектор нам не требуется if z then for i:=1 to M do a[i,j]:=z and a[1,j]; end; // Если в первой строке не было true, то ставим там везде false if not x then for i:=1 to M do a[i,1]:=false;

Есть еще простой вариант но с большой сложностью:
for i:=1 to M do for j:=1 to N do if a[i,j] then for x:=1 to M do for y:=1 to N do if a[x,y] then a[i,y]:=true;

> Sandman25 © (27.07.04 12:32) [166]
> [165] SergP © (27.07.04 12:31)
>
> Это одно и то же :)

Это понятно. Просто писать проще if a[i,j] чем if a[i,j]=1
:)))

> SergP © (27.07.04 12:41) [167]
> Есть еще простой вариант но с большой сложностью:
>
> for i:=1 to M do for j:=1 to N do
> if a[i,j] then for x:=1 to M do for y:=1 to N do
> if a[x,y] then a[i,y]:=true;

Или чуть побыстрее, типа так:

for i:=1 to M do for j:=1 to N do
if a[i,j] then for y:=1 to N do for x:=1 to M do
if a[x,y] then a[i,y]:=true else break else break;

Ой, блин, ошибся...

for i:=1 to M do
for j:=1 to N do
if a[i,j] then
begin
for y:=1 to N do
for x:=1 to M do
if a[x,y] then
begin
a[i,y]:=true;
break;
end;
break;
end;

Пятница. Большая пачка сложных задачек... Найти похожие ветки