Пятничные задачи. Вася Пупкин сегодня отдыхает.

← →
Igorek © (2004-12-11 01:24) [40]

MBo © (10.12.04 10:06)

> с затратами памяти меньшими, чем O(N).

Меньше может быть только О(1) :-)

>TUser © (10.12.04 10:25) [1][Ответить]
> 2. вопрос - O(N) памяти надо на хранение самого
> массива. Как может быть меньше?

Всегда имеется ввиду доп. память кроме той, которая нужна для условия.

Короче можно. То же, что и 123456789 -> 912345678. Есть нюансы, но они не принципиальные.

← →
Igorek © (2004-12-11 01:26) [41]

GuAV © (10.12.04 21:07) [39]

> Что есть O(N) ?

Величина прямо пропорциональна N.

← →
GuAV © (2004-12-11 02:14) [42]

> 4. Берем три цилиндра единичного радиуса, оси которых
>проходят соответственно через
> попарно перпендикулярные координатные оси 0x, 0y и 0z.
>А длина пусть будет бесконечная.
> Требуется определить объем фигуры, полученной при
> пересечении этих цилиндров.

Шара об"ёма не имеет :-)

← →
Igorek © (2004-12-11 12:34) [43]

> Меньше может быть только О(1) :-)

Сорри. Ошибся. Может. Напр. О(log(N)).
Имел ввиду, что задачу можно решить при константной памяти.

← →
Igorek © (2004-12-11 14:26) [44]

2.
procedure ReOrder(var a: array of Integer); procedure Swap(var a, b: Integer); begin a := a xor b; b := a xor b; a := a xor b; end; function NewIndex(i, N: Integer): Integer; begin if (N mod 2) = 0 then //приводим к подзадаче для нечетного колл. Result := NewIndex(i - 1, N - 1) + 1 else //четное колл. if (i mod 2) = 0 then //четные справа Result := (N - 1) - (i div 2) else //нечетные слева Result := i div 2; end; var Start, I, NewI, L: Integer; begin L := Length(a); Start := 1 - (L mod 2); I := Start; while True do begin NewI := NewIndex(I, L); if NewI = Start then break; Swap(a[Start], a[NewI]); I := NewI; end; end;
Не оптипизирован для ясности понимания. Время О(N) не очевидно, но так оно есть. Для очевидности цикл while True можно было тупо повторить колл. раз близкое N.

← →
Igorek © (2004-12-11 14:56) [45]

Igorek © (11.12.04 14:26) [44]
Лажа, сорри. Работает не всегда. А я проверял только для 9 и 10 чисел. Там возникает несколько независимых цепочек.

← →
GuAV © (2004-12-11 15:09) [46]

GuAV © (10.12.04 21:07) [39]
(1/2)/cos(Fi/2) Fi от 0 до 60
sin(Fi/2) Fi от 60 до 180

(1/2)/cos(Fi/2) Fi от 0 до 90
sin(Fi/2) Fi от 90 до 180

1. Измеряем расстояние между пнями от дуба и осины. Например L
Берем веревку длиной L*sqrt(2) , отмечаем на ней середину. Привязываем один конец к дубу, другой к осине, берем веревку за середину и отходим так чтобы обе части веревки были натянуты, а дуб чтобы был левее осины.
Копаем.

если проще, то:
1. Идем от осины к дубу. Считаем шаги (Допустим получилось N шагов). далее идем от дуба к осине. Проходим N/2 шагов, поворачиваем направо и проходим еще N/2 шагов. Копаем.

>GuAV © (11.12.04 15:09) [46]
>VICTOR_ (10.12.04 13:15) [29]
>(1/2)/cos(Fi/2) Fi от 0 до 90
Да.

>SergP © (11.12.04 19:31) [48]
Верно.
один из путей решения - ставим дуб в начало координат, осину в точку (N,0), березу - в произвольные x,y.
посчитав векторы, перпендикулярные к ним и середину нужного отрезка, увидим, что x,y сократятся, останутся только координаты (N/2, N/2)

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