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

← →
MBo © (2004-12-10 10:06) [0]

1. Пират решил закопать на острове свое сокровище. На этом острове росло всего три
дерева: береза, осина и дуб. Место, куда закопать сокровище, пират выбрал таким
образом:
От березы дошел до осины, сосчитав количество шагов. У осины повернул направо и
прошел такое же количество шагов. Вбил колышек.
Вернулся к березе.
От березы дошел до дуба, сосчитав количество шагов. У дуба повернул налево и про
шел такое же количество шагов. Вбил второй колышек.
Нашел середину отрезка между двумя колышками и там закопал сокровище.
Вернувшись на остров через 50 лет, пират обнаружил, что от осины и дуба остались
только пеньки, а следов березы разыскать вообще не удалось.
Сможет ли пират выкопать свое сокровище?

2. Есть массив, упорядоченный по возрастанию, например, 0123456789
Надо его переупорядочить "горкой в центре": 0246897531
Цифры приведены для примера, на самом деле массив может быть любой заданной длины N,
и числа там тоже любые, только что упорядоченные.
Основная проблема - сделать это за время O(N) с затратами памяти меньшими, чем O(N).
Решение лучше всего оформить в виде процедуры ReOrder(a:array of Integer);

3. Дан равносторонний треугольник. Его площадь равна S. Каждая сторона разделена на
три равные части, к которым из противоположной вершины проведены отрезки.
Итого шесть отрезков. Пересекаются. Чему равна площадь получившегося (неправильного)
шестиугольника в центре?

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

5. По реке Миссисипи из города А в город Б пароход без остановок доплывает за три дня,
а из города Б в город А - за четыре дня. Сколько дней уйдет у Гека Финна,
что бы сплавиться на своем плоту из города А в город Б?

6. Доказать
tg(3Pi/11)+4sin(2Pi/11)=Sqrt(11)

7. Найти число из 9 различных цифр 1..9, d1d2d3d4d5d6d7d8d9, такое, что d1 - простое,
d1d2 делится на 2, d1d2d3 делится на 3, ... , d1d2d3d4d5d6d7d8 делится на 8, и
d1d2d3d4d5d6d7d8d9 - на 9.

8. Дан набор из всех нат. чисел 1...1 000 000. Из него случайно выбирается одно число
с удалением, потом второе. Вероятность какого случая больше - сумма этих чисел четна
или нечетна? Или эти случаи равновероятны?

9. Между двумя деревьями натянут канат, закрепленный на высоте 100 и 50 футов.
Расстояние между деревьями 100 футов. Длина каната 120 футов.
http://mbo88.narod.ru/task9.jpg
На канате висит ролик, человек спускается на этом блоке, канат при этом натягивается.
Какую траекторию (алгебраически и геометрически) описывает ролик при движении?
В какой точке он ближе всего к земле?

10. Фокусник просит загадать пятизначное число, перевернуть его наоборот, и вычесть
из большего из этих двух меньшее, и сказать ему три последних цифры разности, после чего
он сообщает две первых цифры. Как он это делает? Можно написать соответствующую функцию.

11. Круглый пирог единичного радиуса нарезан на несколько кусков-секторы с углом Fi.
Найти минимальный радиус тарелки, на которую поместится один кусок.

← →
TUser © (2004-12-10 10:25) [1]

2. вопрос - O(N) памяти надо на хранение самого массива. Как может быть меньше?
8. четное - больше

← →
Александр Иванов © (2004-12-10 10:30) [2]

5. 24 дня.

← →
Johnmen © (2004-12-10 10:39) [3]

1. Да. Восстановит треугольник Б-Д-О по трем сторонам и найдет точку пересечения его высот.

← →
VICTOR_ (2004-12-10 10:40) [4]

8.Нечетноя сумма - большая вероятность

← →
VICTOR_ (2004-12-10 10:41) [5]

8.Нечетная сумма - большая вероятность

← →
Sandman25 © (2004-12-10 10:50) [6]

7.
38165472
Хорошая задача, понравилась.

← →
Sandman25 © (2004-12-10 10:51) [7]

[6] Sandman25 © (10.12.04 10:50)

Забыл дописать последнюю цифру.
7. 381654729

← →
TUser © (2004-12-10 10:55) [8]

8. лопухнулся. нечет.

← →
Sandman25 © (2004-12-10 11:01) [9]

8. P(Четная сумма)=P(четное первое)*P(четное второе|при четном первом) + P(четное первое)*P(нечетное второе|при нечетном первом)
В силу симметрии
= 2*P(четное первое)*P(четное второе|при четном первом)=2*(1/2)*(499999/5000000*1/2)=499999/10000000 < 0.5

← →
Sandman25 © (2004-12-10 11:01) [10]

8. P(Четная сумма)=P(четное первое)*P(четное второе|при четном первом) + P(нечетное первое)*P(нечетное второе|при нечетном первом)
В силу симметрии
= 2*P(четное первое)*P(четное второе|при четном первом)=2*(1/2)*(499999/5000000*1/2)=499999/10000000 < 0.5

← →
Sandman25 © (2004-12-10 11:03) [11]

С нулями ошибся.
2*(1/2)*(499 999/500 000*1/2)=499 999/1 000 000=0.499 999 < 0.5

← →
VICTOR_ (2004-12-10 11:13) [12]

11.
R = sqrt(2-2*cos(Fi))

← →
Alx2 © (2004-12-10 11:19) [13]

9. Навскидку - эллипс, вернее его часть :)
Так как сумма расстояний от ролика до мест крепления каната есть величина постоянная.

← →
ЮЮ © (2004-12-10 11:34) [14]

Johnmen © (10.12.04 10:39) [3]
>1. Да. Восстановит треугольник Б-Д-О по трем сторонам

Непонял. через 50 лет осталась только сторона Д-О

← →
Александр Иванов © (2004-12-10 11:40) [15]

ЮЮ © (10.12.04 11:34) [14]

Из каждой точки Д и О проводится окружность радиусом ДБ и ОБ, соответственно, в точке пересечения - Б.

← →
TUser © (2004-12-10 11:43) [16]

> ЮЮ © (10.12.04 11:34) [14]
> Johnmen © (10.12.04 10:39) [3]
> >1. Да. Восстановит треугольник Б-Д-О по трем сторонам
>
> Непонял. через 50 лет осталась только сторона Д-О

Береза модет быть где угодно.

← →
Johnmen © (2004-12-10 12:05) [17]

>ЮЮ © (10.12.04 11:34) [14]
>Непонял. через 50 лет осталась только сторона Д-О

Ну он же шагами-то мерил расстояние. Наверное, запомнил...:)

← →
Johnmen © (2004-12-10 12:08) [18]

>TUser © (10.12.04 11:43) [16]
>Береза модет быть где угодно.

Не может.

← →
MBo © (2004-12-10 12:16) [19]

>Александр Иванов © (10.12.04 10:30) [2]
>5. 24 дня.
да

>Sandman25 © (10.12.04 10:51) [7]
>7. 381654729
да

>VICTOR_,TUser,Sandman25
8 - да, нечетная сумма вероятней

>VICTOR_ (10.12.04 11:13) [12]
>11.R = sqrt(2-2*cos(Fi))
нет. Контрпример: при Fi->0 у тебя получается 0

>Alx2 © (10.12.04 11:19) [13]
>9. Навскидку - эллипс, вернее его часть :)
Угу

← →
Sandman25 © (2004-12-10 12:17) [20]

10. Я неверно понял задачу или в задаче ошибка.
54y21-12y45=xx976
65z32-23z56=xx976
По трем последним цифрам можно только найти, что
5-1 = 10-6
4-2 = 9-7
Третья цифра разницы всегда 9.

← →
VICTOR_ (2004-12-10 12:32) [21]

11.
R = sqrt(2-2*cos(Fi)), sqrt(2-2*cos(Fi)) > 1
R = 1, sqrt(2-2*cos(Fi)) <= 1

← →
MBo © (2004-12-10 12:32) [22]

>Sandman25 © (10.12.04 12:17) [20]
>10. Я неверно понял задачу или в задаче ошибка
найти первые цифры разности, а не исходных чисел.
В твоем примере для 976 найдется 41 - 41976

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

[22] MBo © (10.12.04 12:32)

Понятно, спасибо. Тогда это не фокус :)

10. Из 100 вычитаем число, составленное из двух последних цифр разности, в результате меняем цифры местами и отнимаем единицу.
Для моего примера:
100-76=24 -> 42 -> 41

← →
VICTOR_ (2004-12-10 12:38) [24]

11.
Предидущий ответ тоже неверный :(, еще подумаю :)

← →
MBo © (2004-12-10 12:38) [25]

>VICTOR_ (10.12.04 12:32) [21]
нет.

← →
MBo © (2004-12-10 12:41) [26]

>Sandman25 © (10.12.04 12:38) [23]
ты привел ответ только для одного из возможных случаев

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

[26] MBo © (10.12.04 12:41)

Если две последние цифры равны 00, то и все остальные цифры равны 00.

← →
MBo © (2004-12-10 13:13) [28]

Sandman25 © (10.12.04 12:46) [27]
с твоим алгоритмом:

procedure TForm1.Button2Click(Sender: TObject); function Reverse(i: Integer): Integer; begin Result := (i mod 10) * 10000 + ((i div 10) mod 10) * 1000 + ((i div 100) mod 10) * 100 + ((i div 1000) mod 10) * 10 + i div 10000; end; function Find12(i: Integer): Integer; var m100: Integer; begin m100 := i mod 100; if m100 = 0 then Result := 0 else begin m100 := 100 - m100; Result := (m100 mod 10) * 10 + m100 div 10 - 1; end; end; var i, ri, diff, f12: Integer; Success: string; begin Success := "Success"; for i := 10000 to 99999 do begin ri := Reverse(i); diff := abs(i - ri); f12 := Find12(diff mod 1000); if f12 <> diff div 1000 then begin Success := "Failure at " + IntToStr(i); Break; end; end; Caption := Success; end;

← →
VICTOR_ (2004-12-10 13:15) [29]

11.
R = Min(sqrt(2-2*cos(Fi)), 1/(2*sin(90-Fi/2))

← →
megabyte-ceercop © (2004-12-10 13:28) [30]

Задача 1:
найти середину между колышками и копать. =)

← →
Alx2 © (2004-12-10 13:37) [31]

6.
Рассмотрим (tan(3*Pi/11)+4*sin(2*Pi/11))^2 в комплексной форме:

Это есть (-I*(exp(3/11*I*Pi)^2-1)/(exp(3/11*I*Pi)^2+1)-2*I*(exp(2/11*I*Pi)-1/exp(2/11*I*Pi)))^2

= 10+(-1)^(3/11)-(-1)^(6/11)-(-1)^(2/11)+(-1)^(9/11)+(-1)^(1/11)+(-1)^(5/11)-(-1)^(4/11)-(-1)^(10/11)-(-1)^(8/11)+(-1)^(7/ 11)

Полагая x=(-1)^(1/11) получим в виде
x-x^2+x^3-x^4+x^5-x^6+x^7-x^8+x^9-x^10+10 =
(-x^11+x)/(x+1) + 10 = (подставляя x = (-1)^(1/11) ) = (1+x)/(1+x) + 10 = 11.
То есть квадрат исходного выражения есть 11.
Принимая во внимания, величины аргументов в исходном выражении получаем, что tan(3*Pi/11)+4*sin(2*Pi/11) = sqrt(11)
Доказано.

← →
Sandman25 © (2004-12-10 13:58) [32]

10.
procedure TForm1.bt1Click(Sender: TObject); function Reverse(i: Integer): Integer; begin Result := (i mod 10) * 10000 + ((i div 10) mod 10) * 1000 + ((i div 100) mod 10) * 100 + ((i div 1000) mod 10) * 10 + i div 10000; end; function Reverse2(i: Integer): Integer; begin Result := (i mod 10) * 10 + i div 10; end; function Find12(i: Integer): Integer; var m1000 : Integer; begin m1000 := i mod 1000; if m1000 = 0 then Result := 0 else if m1000 div 100 = 0 then Result := Reverse2(100 - m1000 mod 100 - 1) else begin m1000 := 100 - i mod 100; Result := Reverse2(m1000) - 1; end; end; var i, ri, diff, f12 : Integer; Success : string; begin Success := "Success"; for i := 10000 to 99999 do begin ri := Reverse(i); diff := abs(i - ri); f12 := Find12(diff mod 1000); if f12 <> diff div 1000 then begin Success := "Failure at " + IntToStr(i) + ":" + IntToStr(f12) + ":" + IntToStr(diff div 1000) + " = " + IntToStr(diff); Break; end; end; Caption := Success; end;

← →
Sandman25 © (2004-12-10 14:13) [33]

function Find12(i: Integer): Integer;
begin
if i = 0 then
Result := 0
else
Result := Reverse2(100 - i mod 100 - Ord(i <=100)) - Ord(i > 100);
end;

← →
Sandman25 © (2004-12-10 14:18) [34]

function Reverse2(i: Integer): Integer;
begin
Result :=
(i mod 10) * 10 + i div 10;
end;

>Alx2 © (10.12.04 13:37) [31]
Ух ты, глаза разбегаются ;)
Есть еще чисто тригонометрическое решение:
умножаем равенство на косинус первого угла, возводим в квадрат, проводим преобразования, получаем
Сумма(i=0..5)[Cos(2*i*Pi/11)]=0
а это сумма проекций на OX пучка единичных векторов, которая равнв нулю.

>Sandman25 © (10.12.04 14:13) [33]
ЗдОрово!

приведу еще один код, подходящий для счета в уме (для чего можно также заменить арифметику по модулю 99 на модуль 100):
function Find12Ex(d: Integer): Integer;
begin
d := d - 99 * (d div 99);
if d>0 then
d:=99-d;
Result := (d mod 10) * 10 + d div 10;
end;

[35] MBo © (10.12.04 14:28)

d := d - 99 * (d div 99);
можно заменить на
d := d mod 99

а если с условием, то имеем
d := (99 - d mod 99) mod 99;

11.

1/2*ctg(Fi/2), Fi<=180
1, Fi>=180

Точнее
max[ (1/2)/cos(Fi/2) , sin(Fi/2) ] при Fi<=180
1 при Fi>=180 (Если возможны разые Fi)

даже скажем так
(1/2)/cos(Fi/2) Fi от 0 до 60
sin(Fi/2) Fi от 60 до 180

2 MBo [0]

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

MBo © (10.12.04 10:06)

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

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

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

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

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

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

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

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

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

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

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)

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