Пятничные задачки. Повтор нерешенного, и кое-что новое...

← →
MBo © (2005-11-03 10:20) [0]

1. Когда самолет пролетает со скоростью V на высоте H прямо
над ракетной установкой, запускается ракета со скоростью U>V,
оборудованная системой наведения, так что ракета все время
выдерживает направление на самолет. Курс самолета не меняется.
Какое время потребуется для поражения цели?

2. Отсортировать стек (например, TStack из Contnrs), содержащий целые числа.
Можно использовать только штатные стековые операции - Push,Pop, Peek,
проверку на пустоту, т.е. не манипулировать внутренним списком напрямую.
Можно использовать дополнительные стеки, но никаких других структур данных.

3. Посчитать количество структурных изомеров алканов (предельных углеводородов СnH(2n+2))
в зависимости от N. Стереоизомеры не учитываются.
Примеры: N=4 (бутан) M=2; N=8 (октан) M=18

4. Миллион водомерок разбежались из одной точки на берегу реки в различных
направлениях, с постоянной скоростью V (вектор) относительно воды.
Скорость течения u линейно растет с расстоянием х от берега: u=k*x.
Какую геометрическую фигуру будут образовывать водомерки в
некоторый момент времени t?

5. Сумма цифр десятичной записи числа 4444^4444 равна A.
Сумма цифр числа А равна B. Найти сумму цифр числа B.

6. Правильный тетраэдр со стороной в 1 метр находится в подвешенном состоянии.
Hа одну из его вершин села муха точечных размеров и поползла по прямой
по грани (не ребру) тетраэдра. С грани на грань муха переползает так, что на
развертке тетраэдра ее путь оставался бы прямолинейным. Преодолев расстояние
в целое число метров, не превосходящее десяти, муха вновь оказалась в вершине.
Сколько метров проползла муха и сколько раз побывала при этом на грани, с
которой начала движение?

7. На автобусном маршруте 14 остановок, 91 вариант билетов в зависимости от
нач. и крнечной остановки пассажира. Пассажиры входят и выходят, но одновременно
едет не более 25 человек. Какое максимальное количество сортов билетов может быть
выдано кондуктором за рейс в одну сторону?

8. Поезд проходит мимо столба за время t1, а по мосту длиной L за время t2.
(от въезда локомотива до схода последнего вагона)
Найти длину и скорость поезда

9. Натуральные числа выписаны подряд в одну строку 12345678910111213...
Найти цифру на n-м месте.

← →
VICTOR_ (2005-11-03 10:42) [1]

сегодня же четверг :(

← →
КаПиБаРа © (2005-11-03 10:50) [2]

8)
V=(t2-t1)/L
l=V*t1,

где V - скорость поезда
l - длина поезда

← →
novice (2005-11-03 11:03) [3]

8)
Скорость V=L/(t2-t1)
Длина a=L*t1/(t2-t1)

← →
wal © (2005-11-03 11:16) [4]

2.
Сделаем три стека:
S1 - Исходный
S2 - Рабочий (вначале пустой)
S3 - Отстойник (вначале пустой)
A, B, C - переменная типа данных в стеке
Flag - булева переменная
B := минимально возможное значение while (S1 не пуст) do begin Pop(S1, A) if A >= B then // Если больше, чем вершина рабочего стека begin Push(S2, A); // кладем в рабочий стек, B := A; // запоминаем новую вершину рабочего стека end else begin Push(S3, A) // иначе кладем в отстойник end; end; // после первого цикла в рабочем стеке имеем отсортированные данные, но не все. while (S3 не пуст) do begin Pop(S3, B); Flag := True; Pop(S2, C); Push(S1, C); while (S2 не пуст) do begin Pop(S2, A); if Flag and (B >= Min(A,C)) and (B<=Max(A,C)) then // если B между A и C begin Push(S1, B); // то втыкаем B в стек; Flag:= False end; end; Swap (S1, S2) // меняем местами указатели на рабочий и исходный стек. end; // После этого данные в S2 отсортированы, S1 и S3 - пустые
Такой вот оп-код. Возможны ошибки, но идея, думаю, понятна. Уже вижу варианты оптимизации, но описать внятно пока не могу.

С уважением.

← →
Igorek © (2005-11-03 11:17) [5]

2. В лоб.
- завести еще два стека, перелить из исходного в первый

потом повторять процедуру пока есть элементы:
- перелить из первого во второй, запомнив макс.
- добавить макс. в исходный
- перелить из второго обратно в первый (_один_ раз отбросив значение, равное макс.)

← →
wal © (2005-11-03 11:23) [6]

> if Flag and (B >= Min(A,C)) and (B<=Max(A,C)) then // если B между A и C
> begin
> Push(S1, B); // то втыкаем B в стек;
> Flag:= False
> end;
После этого забыл вставить
Push (S1, A);

← →
default © (2005-11-03 11:36) [7]

5. я решал...

← →
default © (2005-11-03 11:45) [8]

9. то что бросается сразу - цикл
если число однозначное - то увеличиваем счётчик позиций на 1
если число двузначное - то увеличиваем счётчик позиций на 2
и тд
когда поняли что дошли до нужной позиции выделяем число из нужного
разряда

← →
DiamondShark © (2005-11-03 11:51) [9]

> 2.

Ханойские башни ;)

← →
Sandman29 © (2005-11-03 12:21) [10]

7. 66 = (13)+(6+6)+(4+4+3)+(3+3+2+2)+(2+2+2+2+2)+10

← →
Карелин Артем © (2005-11-03 12:26) [11]

1. Возможны варианты. Тупая ракета по тупой кривой, умная полетит по более оптимальному пути.

← →
Jeer © (2005-11-03 12:35) [12]

Карелин Артем © (03.11.05 12:26) [11]

См.
"так что ракета все время
выдерживает направление на самолет"

Классическая задача из теории дифференциальных игр.
Принцип максимума Понтрягина для решения оптимизационных задач.

← →
MBo © (2005-11-03 12:50) [13]

1.
>Jeer © (03.11.05 12:35) [12]
>Принцип максимума Понтрягина для решения оптимизационных задач.

Тем не менее можно решить и методами, доступными продвинутому старшекласснику.

8.
КаПиБаРа © (03.11.05 10:50) [2]
novice (03.11.05 11:03) [3]

Да, конечно. Что-то я совсем примитивную написал...

>Sandman29 © (03.11.05 12:21) [10]
>7. 66 = (13)+(6+6)+(4+4+3)+(3+3+2+2)+(2+2+2+2+2)+10
Чуть ошибся где-то

← →
Jeer © (2005-11-03 12:51) [14]

MBo © (03.11.05 12:50) [13]

Конешна:))

← →
Sandman29 © (2005-11-03 12:59) [15]

MBo © (03.11.05 12:50) [13]

Возможно. Нудноватая задача - идея сразу понятна, а перебирать много.

← →
default © (2005-11-03 13:04) [16]

7. 67?

← →
default © (2005-11-03 13:08) [17]

7. хотя способ решения у меня другой..
одним местом можно перебрать 13 билетов
двумя местами - 12 билетов
....
6 местами - 8 билетов
13+12+11+10+9+8=63
1+2+3+4+5+6=21 - столько мест займёт перебор 63 билетов в ходе рейса
остаётся 25-21=4 итого 63+4=67

← →
default © (2005-11-03 13:13) [18]

7. хотя способ решения у меня другой..
одним местом можно перебрать 13 билетов(билеты выхода на следующей остановке)
двумя местами - 12 билетов(выхода через одну остановку)
....
6 местами - 8 билетов
13+12+11+10+9+8=63
1+2+3+4+5+6=21 - столько мест займёт перебор 63 билетов в ходе рейса
остаётся 25-21=4 итого 63+4=67

← →
MBo © (2005-11-03 13:14) [19]

default © (03.11.05 13:04) [16]
7. 67?

Да.

← →
default © (2005-11-03 13:34) [20]

5. 7 (нагло списал свой результат из старой ветки по пятничным задачкам;))

← →
MBo © (2005-11-03 13:40) [21]

>default © (03.11.05 13:34) [20]
Да уж дал бы подумать тем, кто еще не решал ;)

default © (03.11.05 11:45) [8]
9. то что бросается сразу - цикл

это прямой перебор, неэффективно, конечно...

>wal © (03.11.05 11:16) [4]
Честно говоря, пока не уловил.
Сам я делал примерно, как Igorek © (03.11.05 11:17) [5], но это достаточно долгий процесс.

← →
Igorek © (2005-11-03 13:42) [22]

2. Пузырьковая сортировка. Создаем еще один массив. Переливаем между ним и исходным данные, меняя местами значения в вершинах. Останавливаемся, когда при переливе не было ни одного обмена.

← →
Igorek © (2005-11-03 13:44) [23]

> Создаем еще один массив

стек, сорри

← →
default © (2005-11-03 13:53) [24]

MBo © (03.11.05 13:40) [21]
ну я же решение не дал, только результат

← →
ЯВ (2005-11-03 13:53) [25]

1.
Думаю что:
t=sqr (a1\a2) ult
a1 = h^2
a2 = (U^2 - V^2)

← →
MBo © (2005-11-03 14:26) [26]

>ЯВ (03.11.05 13:53) [25]
Я не понял, что такое ult, но все равно неверно.

← →
Jeer © (2005-11-03 14:46) [27]

U/t - видимо.

← →
Igorek © (2005-11-03 15:00) [28]

2. Быстрая сортировка. Процедура создает два стека, делает один перелив для выбора медианы (по среднему значению или просто пополам), вызывает сама себя для этих двух стеков, перед возвратом снова сливает в исходный сначала первый стек, потом второй.

> >wal © (03.11.05 11:16) [4]
> Честно говоря, пока не уловил.
На пальцах:
1. Считываем с исходного, кладем в рабочий;
2. Считываем с исходного, если больше-равно, чем вершина рабочего, кладем в рабочий, иначе кладем в отстойник.
3. Повторям 2 пока исходный не кончился.
-- Это был первый цикл
4. Считываем из рабочего.
5. Если вершина отстойника находится между вершинами рабочего и исходного, то считываем из отстойника, кладем в исходный.
6. Кладем считанный из рабочего в исходный.
7. Повторяем 4 пока рабочий не кончился.
8. Меняем местами рабочий и исходный.
9. Повторяем 4 пока не кончился отстойник.

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

С уважением.

← →
ЯВ (2005-11-03 15:22) [30]

> Я не понял, что такое ult, но все равно неверно.

ult = где
:)

а чё не верно - я пошел простым путем - приблизил траекторию полета самлета и ракеты к треугольнику и счтал по Пифагору где катет Vt = S путь (она же длина) и гипотенуза ракета (Ut = S ракеты)

> ЯВ (03.11.05 15:22) [30]

По кривой

9. ответом служит формула или есть всё-таки цикл?
вот бы из уравнения (10^g)*(9g-1)=9n-1 выразить g тогда бы можно формулу составить

>default © (03.11.05 16:31) [32]
Я 9. решал несколько лет назад. За O(logN) точно можно решить, а можно ли быстрее - уже не помню.

> Пятничные задачки. Повтор нерешенного, и кое-что новое...

слышь мужик, попей пивку, ляг, поспи и всё пройдёт...
Мозги нам колышешь...

1.

Будем отсчитывать время от момента прохождения самолета над пусковой установкой.
Возьмем систему координат, начало отсчета которой совпадает с самолетом, а ось Х в момент времени 0 проходит через ракету. В момент 0 в выбранной системе координат ракета находится на расстоянии Н от начала координат и имеет скорость U - V. Далее, согласно условию, ракета движется вдоль оси Х с постоянной скоростью. Таким образом, она попадет в начало координат через время t = H/(U - V)

>default © (03.11.05 17:50) [34]
Да, можно так.

>umbra © (04.11.05 10:09) [36]
Здравое зерно есть, но фраза " и имеет скорость U - V " - неверна, как и дальнейшее.

to MBo>

А разве 5-ая задачка не решена была в одну из пятниц? Я ж вроде видел ответ "7" и твой ответ на этот ответ "правильно". Или что-то путаю?

Кстате, если путаю, это хорошо. А то я ту ветку потерял, так и не спросив "как решал" :)

Пятничные задачки. Повтор нерешенного, и кое-что новое... Найти похожие ветки