Пятничные задачки. Вася Пупкин потрясает интеллектом...

← →
MBo © (2007-02-09 08:43) [0]

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

2. Сколько существует различных решений уравнения
x1 + x2 +...+xM = N
а) в натуральных числах
б) в целых неотрицательных числах

3. Два прямых круговых цилиндра пересекаются под прямым углом.
Радиусы обоих цилиндров равны единице.
Чему равен объем пространственной фигуры, образованной пересечением цилиндров?
(Задача Архимеда, давал ее не однажды, но решения, кажется, не было)

4. Вася Пупкин оказался в незнакомом городе N, деньги быстро кончились ;(
Через несколько недель он ожидает перевод на крупную сумму.
Самой дорогой из его вещей была золотая цепочка, состоявшая из двадцати
трех звеньев. Вася договорился с хозяйкой гостиницы, что будет в качестве
залога давать ей каждый день одно звено - и так в течение двадцати трех дней.
Ему, конечно, хотелось как можно меньше портить цепь. Вместо того,чтобы
каждый день отпиливать по звену, он может в первый день дать хозяйке одно звено,
во второй день забрать у нее это звено, поставив взамен короткую цепочку
из двух звеньев и т.д., комбинации обязаны удовлетворить единственному условию: каждый день
у хозяйки гостиницы должно быть столько звеньев, сколько прошло дней со дня
приезда Васи. Вскоре он понял, что цепь можно распилить многими разными способами, не нарушая договора
с хозяйкой. Задача заключается в том, чтобы определить,какое минимальное число звеньев должен распилить
Вася, чтобы, выплачивая по звену в день, заплатить за все двадцать три дня.

5. В город N Вася приехал не просто так, а для прохождения конкурса в компанию
ГиперПуперАлгоКалк. Вначале он получил следующую задачу:
Дан массив целых чисел. Инверсией называется такая пара элементов (i,j), что
для i<j A[i]>A[j]. Понятно, что для неубывающего массива число инверсий равно нулю,
а максимальной число инверсий в массиве - когда он убывает. Васе нужно найти быстрый
метод нахождения числа инверсий в массивах размером до 40000 элементов.

6. Далее Васе задали написать процедуру, не использующую вещественной арифметики,
для данного натурального числа N находящую максимальное число, квадрат которого
не превосходит N, и остаток.
Например, для N = 61 нужно получить Q=7, QSqr =49, Rem = 6

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

type TMatrix = array of array of Double; procedure MatMul(const a, b: TMatrix; var c: TMatrix); var n, x, y, k: Integer; begin n := Length(a); for y := 0 to n - 1 do for x := 0 to n - 1 do for k := 0 to n - 1 do c[y, x] := c[y, x] + a[y, k] * b[k, x]; end; var a, b, c: TMatrix; n, x, y: Integer; t: Dword; begin n := 600; SetLength(a, n, n); SetLength(b, n, n); SetLength(c, n, n); for y := 0 to n - 1 do for x := 0 to n - 1 do begin a[y, x] := Random; b[y, x] := Random; end; t := GetTickCount; MatMul(a, b, c); Caption := Format("Mult time: %d", [GetTickCount - t]);

Однако в этот момент коварный конкурент Зильберштуцер перекусил зубами провод Васиной клавиатуры,
и со злорадной ухмылкой стал реализовывать алгоритм Штрассена.
Но Пупкины не сдаются! С помощью небывалого напряжения извилин, работая только
мышью, Вася смог ускорить процедуру раза в полтора.
Как он смог этого добиться?

8. Вернувшись домой после конкурса, Вася решил неслабо оттянуться с девушками.
Он взял с собой друга Петю, и они подцепили двух подружек Люсю и Таню. В ходе предварительной
беседы выяснилось, что каждый из 4-х имеет легкое венерическое заболевание, причем все разные,
а в наличии имеется всего два презерватива. Однако и Васе, и Пете нравятся обе девушки,
и обоим хотелось бы интима с каждой. Могут ли все партнеры не получить новой заразы?

← →
MBo © (2007-02-09 08:46) [1]

пардон, в примере к 6 задаче остаток, конечно, Rem= 12

← →
MBo © (2007-02-09 08:56) [2]

6. аналогично - решить в целых неотрицательных числах N = Q^2 + Rem

← →
evvcom © (2007-02-09 09:08) [3]

1. = 1 - ((N-1)/N)^N

← →
Гарри Поттер © (2007-02-09 09:08) [4]

4. Поясни плз, что значит распилил? Например, если распилить третье звено, то на руках будет 3 "цепочки" длиной в 1, 2, и 20 звеньев? Так?

← →
evvcom © (2007-02-09 09:17) [5]

8. :))) Тут, видимо, биологию знать надо. С резинки на резинку зараза передается? Ну если одеть один на другой?

← →
alex_s (2007-02-09 09:21) [6]

4. 1+2+4+8+8=23

← →
MBo © (2007-02-09 09:31) [7]

>если распилить третье звено, то на руках будет 3 "цепочки" длиной в 1, 2, и 20 звеньев? Так?

Да

← →
wal © (2007-02-09 09:33) [8]

8. Могут. Имеем 4 органа и четыре поверхности на презервативах. Дальше извращения расписывать? ;)

← →
Bless © (2007-02-09 09:37) [9]

> 2. Сколько существует различных решений уравнения
> x1 + x2 +...+xM = N

например,решения
x1=1, x2=2, x3=3
и
x1=1, x2=3, x3=2
считаются различными?

← →
MBo © (2007-02-09 09:47) [10]

>например,решения
x1=1, x2=2, x3=3
и
x1=1, x2=3, x3=2
считаются различными?

Да, различными

← →
novill © (2007-02-09 09:51) [11]

> [0] MBo © (09.02.07 08:43)

8. Не получить новой заразы - могут. А вот получить удовольствие - врядли!

← →
begin...end © (2007-02-09 09:52) [12]

8. Например, так:

Вася одевает два презерватива и --> Люсю, после чего верхний отдаёт Пете. Теперь Петя --> Люсю, а Вася --> Таню. Наконец, Петя одевает второе изделие и --> Таню.

← →
Алхимик © (2007-02-09 09:57) [13]

> 8. Вернувшись домой после конкурса, Вася решил неслабо оттянуться
> с девушками.
> Он взял с собой друга Петю, и они подцепили двух подружек
> Люсю и Таню. В ходе предварительной
> беседы выяснилось, что каждый из 4-х имеет легкое венерическое
> заболевание, причем все разные,
> а в наличии имеется всего два презерватива. Однако и Васе,
> и Пете нравятся обе девушки,
> и обоим хотелось бы интима с каждой. Могут ли все партнеры
> не получить новой заразы?

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

← →
novill © (2007-02-09 10:01) [14]

4. С учетом [7]
нужно сделать два распила - четвертое и одиннадцатое звено

← →
Jeer © (2007-02-09 11:27) [15]

6.
//c[y, x] := c[y, x] + a[y, k] * b[k, x];

MatTranspose( b );
c[y, x] := c[y, x] + a[y, k] * b[x, k];

реальный выигрыш около 2 раз;

← →
novill © (2007-02-09 12:21) [16]

> 6. Далее Васе задали написать процедуру, не использующую
> вещественной арифметики,
> для данного натурального числа N находящую максимальное
> число, квадрат которого
> не превосходит N, и остаток.
> Например, для N = 61 нужно получить Q=7, QSqr =49, Rem =
> 12

Это не слишком интересно - понятно что вариантов приближения есть много, а вот относиттельно чего оптимизировать решение...

← →
evvcom © (2007-02-09 12:29) [17]

6. Я когда-то в школе еще умел корни в столбик вычислять, сейчас уже давно забыл :(
http://ivr.webzone.ru/articles/dop_ar/ "Квадратные и другие корни. Возведение в любую степень."

← →
MBo © (2007-02-09 13:15) [18]

>evvcom © (09.02.07 09:08) [3]
>1. = 1 - ((N-1)/N)^N

Верно, это сходится к 1 - 1/e ~ 0.62

>novill © (09.02.07 10:01) [14]
>4.нужно сделать два распила - четвертое и одиннадцатое звено

Верно

>wal © (09.02.07 09:33) [8]
>8. Могут. Имеем 4 органа и четыре поверхности на презервативах
Ну стоило бы ;)
>begin...end © (09.02.07 09:52) [12]
>8. Например, так:
ага ;)

>Jeer © (09.02.07 11:27) [15]
>MatTranspose( b );
Ну так будет ускорение, но мышью транспонирование набрать тяжеловато...

← →
Jeer © (2007-02-09 13:46) [19]

> >Jeer © (09.02.07 11:27) [15]
> >MatTranspose( b );
> Ну так будет ускорение, но мышью транспонирование набрать
> тяжеловато...

Пусть привыкает к трудностям:)

// for y := 0 to n - 1 do
// for x := 0 to n - 1 do

for x := 0 to n - 1 do
for y := 0 to n - 1 do

← →
novill © (2007-02-09 13:53) [20]

Решение для 6 из учебника

Квадратный корень из целого числа равен количеству последовательных нечётных чисел, которое можно из него вычесть

Вот только как оно доказывается?

← →
Думкин © (2007-02-09 13:54) [21]

> novill © (09.02.07 13:53) [20]

(a+1)^2=a^2+a+(a+1)

← →
MBo © (2007-02-09 14:01) [22]

>Jeer © (09.02.07 13:46) [19]
Ну почти так

На моей машине бОльший выигрыш дает
for y := 0 to n - 1 do
for k := 0 to n - 1 do
for x := 0 to n - 1 do

Поясню для остальных:
Смысл перестановки, как и в приеме с транспонировании матрицы, состоит в обеспечении последовательного доступа к памяти (правда, транспонирование дает еще возможность использования векторных операций процессоров, SSE).
Современные процессоры очень неплохо справляются с арифметикой, а вот подсистема памяти может не успевать поставлять им данные, особенно если они разнесены по далеким адресам.
Внутренний цикл крутится быстрее внешних, и если он по k, то b[k, x] прыгает по первому измерению массива, т.е. по далеким адресам.
Поменяв местами циклы по k и x, получаем инвариантность в этом цикле
a[y, k], а для c[y, x] и b[k, x] изменяется второй индекс, т.е. проход по элементам, последовательно расположенным в памяти, так что прекэширование данных повышает производительность.

← →
MBo © (2007-02-09 14:04) [23]

>novill © (09.02.07 13:53) [20]
>Решение для 6 из учебника
>Квадратный корень из целого числа равен количеству последовательных нечётных чисел, которое можно из него вычесть

Верно, это один из подходящих под условие методов.
procedure GetNums(N: Integer; var Q, QSqrt, Rem: Integer); begin Rem := -N; QSqrt := -1; while Rem < 0 do begin Inc(QSqrt, 2); Inc(Rem, QSqrt); end; QSqrt := QSqrt div 2; Q := QSqrt * QSqrt; if N - Q < Rem then Rem := N - Q else begin Q := N + Rem; Inc(QSqrt) end; end;

>Вот только как оно доказывается?
сумма арифметической прогрессии

← →
TUser © (2007-02-09 14:19) [24]

8. Презики надевать по два на член.
Вася - А - В - Леся
Петя - В - Леся
Вася - А - Таня
Петя - В - А - Таня

← →
novill © (2007-02-09 14:27) [25]

> [21] и [23]

Объясните тупому.

По условию - N число из которого надо "извлечь корень" - найти максимальное целое квадрат екоторого не превышает N.

Арифметическая последовательность.
A1 – первый член, d нашем случае =1
An – член c номером n
d – разность между последовательными членами в нашем случае =2

An=A1+(n-1)*d

Сумма первых n членов арифметической прогрессии
S=n*(A1+An)/2=n*(A1+A1+(n-1)*d)/2=n*(2*A1+(n-1)*d)/2

Подставляю наши значения
S=n*(2+(n-1)*2)/2
S=n*n/2
n^2=2*S

Как это связать с "корнем" из N?

← →
MBo © (2007-02-09 14:37) [26]

>Как это связать с "корнем" из N?
складываем нечетные числа, пока сумма не превысит N
количество слагаемых = корню
в приведенном коде я количество их не считаю впрямую, а последнее число пополам делю (2n+1)

← →
Alarm © (2007-02-09 15:23) [27]

Понравилось begin...end © (09.02.07 09:52) [12]
Но в наше время (я достаточно старый) была другая постановка задачи:)
У Васи было три подружки (освободите меня от описания их венерических заболеваний:)), а у него стоял(а) задача поиметь их и не "заразиться". Предложите "последовательность действий смены презервативов (решение существует)

← →
wal © (2007-02-09 15:40) [28]

Ну раз в "[8] wal © (09.02.07 09:33)" не описал, а "[18] MBo © (09.02.07 13:15)" настаивает, то распишу "[27] Alarm © (09.02.07 15:23)"
"поиметь их и не "заразиться"" - для этого нужен 1 презервантив, я думаю "поиметь, не заразиться и никого не заразить ничем новым".
Опять же имеем 4 органа и 4 поверхности.
1. Надеваем оба и на первую
2. Верхний снимаем и на вторую
3. Снятый выворачиваем, снова надеваем и на третью.

5. Есть простое in-place решение на n*log(n) времени. Возьмут Васю или им надо линейное?

>TUser © (09.02.07 15:44) [29]
>5. Есть простое in-place решение на n*log(n) времени. Возьмут Васю или им надо линейное?

Я склонен считать, что линейное невозможно

А вот n*log(n) инплейс - очень интересно, у меня такая асимптотика с O(N) памяти.
Что за идея?

> 3. Два прямых круговых цилиндра пересекаются под прямым
> углом.
> Радиусы обоих цилиндров равны единице.
> Чему равен объем пространственной фигуры, образованной пересечением
> цилиндров?
> (Задача Архимеда, давал ее не однажды, но решения, кажется,
> не было)

У меня получилось 16/3

> [32] SergP © (09.02.07 19:35)
> > 3. Два прямых круговых цилиндра пересекаются под прямым
>
> > углом.
> > Радиусы обоих цилиндров равны единице.
> > Чему равен объем пространственной фигуры, образованной
> пересечением
> > цилиндров?
> > (Задача Архимеда, давал ее не однажды, но решения, кажется,
>
> > не было)
>
>
> У меня получилось 16/3

Решение не привожу, ибо оно тупое, т.е. в лоб, с помощью вычисления интеграла...

> Я склонен считать, что линейное невозможно
>
> А вот n*log(n) инплейс - очень интересно, у меня такая асимптотика
> с O(N) памяти.
> Что за идея?

Что считать O(N)? N - это что?
Стандартный способ возведения в степень за логарифм потребует максимум O(n*log(n)) шагов.

+ интересно как автор [3] решал 1-ую задачу. Я вот могу решить используя число беспорядков. (N! - N!/e) / N!

3. -16/3+4*pi ~= 7.233 vs [33] 16/3 ~= 5.333
Ищу площадь 1/16 части получившейся фигуры двойным интегралом. Мой ответ мне вроде нравится меньше.. Надо оценку нормальную придумать.. Можем ли мы утверждать что если убрать 2-ой цилиндр то объём лишь только уменьшится. Если да то объём должен быть больше объёма одного цилиндр pi*r^2*h = pi * 2 ~= 6.28. Где я вру?

2.
a)
вроде так
F(N)=M^k + 1
k это максимальное натуральное число удовлетворяющее неравенству M <= n-k

хотя нет не так там всё просто

>ferr © (09.02.07 19:47) [34]
>Что считать O(N)? N - это что?
>Стандартный способ возведения в степень за логарифм потребует максимум O(n*log(n)) шагов.

Пост относился к 5 задаче про количество инверсий. Вычисление по определению - квадратичное.

Порешали с коллегой 3-ю задачку. Получили 2*Pi.

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