Форум: "Потрепаться";
Текущий архив: 2005.01.02;
Скачать: [xml.tar.bz2];
ВнизПятничные задачи. Вася Пупкин сегодня отдыхает. Найти похожие ветки
← →
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;
← →
MBo © (2004-12-10 14:28) [35]>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;
← →
Sandman25 © (2004-12-10 14:33) [36][35] MBo © (10.12.04 14:28)
d := d - 99 * (d div 99);
можно заменить на
d := d mod 99
а если с условием, то имеем
d := (99 - d mod 99) mod 99;
← →
GuAV © (2004-12-10 20:43) [37]11.
1/2*ctg(Fi/2), Fi<=180
1, Fi>=180
← →
GuAV © (2004-12-10 20:58) [38]Точнее
max[ (1/2)/cos(Fi/2) , sin(Fi/2) ] при Fi<=180
1 при Fi>=180 (Если возможны разые Fi)
← →
GuAV © (2004-12-10 21:07) [39]даже скажем так
(1/2)/cos(Fi/2) Fi от 0 до 60
sin(Fi/2) Fi от 60 до 180
2 MBo [0]
Что есть O(N) ?
← →
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. Есть нюансы, но они не принципиальные.
Страницы: 1 2 вся ветка
Форум: "Потрепаться";
Текущий архив: 2005.01.02;
Скачать: [xml.tar.bz2];
Память: 0.56 MB
Время: 0.038 c