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

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

>Alx2 © (25.07.04 09:27) [118]
Верно

← →
SergP © (2004-07-25 23:57) [121]

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

2/3

← →
SergP © (2004-07-26 00:28) [122]

> [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)

← →
Sha © (2004-07-26 09:21) [123]

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

← →
SergP © (2004-07-26 10:04) [124]

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

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

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

> SergP ©

Архимед тоже через интеграл находил ?

← →
Sha © (2004-07-26 10:13) [126]

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 - площадь нижнего сечения.

← →
Sha © (2004-07-26 10:14) [127]

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

← →
Думкин © (2004-07-26 10:27) [128]

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

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

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

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

← →
SergP © (2004-07-26 11:05) [130]

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

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

← →
Sandman25 © (2004-07-26 12:33) [131]

[108] default © (23.07.04 19:55)

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

← →
Sandman25 © (2004-07-26 12:35) [132]

[108] default © (23.07.04 19:55)

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

← →
REA © (2004-07-26 12:49) [133]

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

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

← →
Andr © (2004-07-26 13:03) [134]

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

← →
default © (2004-07-26 13:04) [135]

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
надеюсь нигде не ошибся...

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

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

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

← →
Думкин © (2004-07-26 13:08) [137]

> [136] Думкин © (26.07.04 13:07)

Хотя симметрии нет, поспешил. :((

← →
Ertong © (2004-07-26 13:31) [138]

> MBo © (23.07.04 09:59)

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

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

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

← →
Sandman25 © (2004-07-26 14:16) [139]

[135] default © (26.07.04 13:04)

Спасибо за подробное объяснение. Просто класс! :)

← →
Думкин © (2004-07-26 14:25) [140]

> [138] Ertong © (26.07.04 13:31)

Он в отпуске до 19 августа. Есть желание - флаг в руки.

← →
Sha © (2004-07-26 15:58) [141]

Sandman25 © (26.07.04 14:16) [139]

А моего Моргана [99] кто-нибудь заметил? :)

← →
Sandman25 © (2004-07-26 16:14) [142]

[141] Sha © (26.07.04 15:58)

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

← →
SergP © (2004-07-26 18:02) [143]

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

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

← →
Sha © (2004-07-26 21:33) [144]

Sandman25 © (26.07.04 16:14) [142]

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

← →
Sandman25 © (2004-07-27 08:41) [145]

[87] Sha © (23.07.04 17:42)

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

← →
Sha © (2004-07-27 08:55) [146]

Sandman25 © (27.07.04 08:41) [145]

А что мешает совместить лучшее от обоих решений?

← →
Sandman25 © (2004-07-27 08:56) [147]

[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]))?

← →
Sandman25 © (2004-07-27 08:57) [148]

[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."

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