Книги
чёрным по белому
Главное меню
Главная О нас Добавить материал Поиск по сайту Карта книг Карта сайта
Книги
Археология Архитектура Бизнес Биология Ветеринария Военная промышленность География Геология Гороскоп Дизайн Журналы Инженерия Информационные ресурсы Искусство История Компьютерная литература Криптология Кулинария Культура Лингвистика Математика Медицина Менеджмент Металлургия Минералогия Музыка Научная литература Нумизматика Образование Охота Педагогика Политика Промышленные производства Психология Путеводители Религия Рыбалка Садоводство Саморазвитие Семиотика Социология Спорт Столярное дело Строительство Техника Туризм Фантастика Физика Футурология Химия Художественная литература Экология Экономика Электроника Энергетика Этика Юриспруденция
Новые книги
Суворов С. "Танк Т-64. Первенец танков 2-го поколения " (Военная промышленность)

Фогль Б. "101 вопрос, который задала бы ваша кошка своему ветеринару если бы умела говорить" (Ветеринария)

Нестеров В.А. "Основы проэктирования ракет класса воздух- воздух и авиационных катапульных установок для них" (Военная промышленность)

Таранина И.В. "Гражданский процесс в схемах " (Юриспруденция)

Смоленский М.Б. "Адвокатская деятельность и адвокатура российской федерации" (Юриспруденция)
Реклама

Математические фантазии - Слойер С.

Слойер С. Математические фантазии — М.: Мир, 1993. — 184 c.
ISBN 5-03-002367-4
Скачать (прямая ссылка): matematfantazii1993.djvu
Предыдущая << 1 .. 2 < 3 > 4 5 6 7 8 9 .. 41 >> Следующая

если бы попали на угол
(0,2), мы должны были бы ехать на восток и через
10 мин достигли бы точки В. Все эти числа и на-
правления указаны на рис. 7.
Если же мы попадаем: ка угол (1,1) , то у нас есть
выбор между В и С. Если мы поедем на восток, то
путь займет 10 мин, а если на север-11 мин. Та-
ким образом, если мы попадаем на угол (1, 1), луч-
шее, что мы можем сделать, - это выбрать восточное
направление, и тогда нам потребуется 10 мин, чтобы
попасть в точку В. Это показано на рис. 8.
Если бы мы попали на угол (1,0), у нас был бы
выбор между северным и восточным направлениями.
Север
(c) 7 (c) 3
СО " б' **
t 7
14
Фантазия 1
Выбор северного направления означал бы, что поездка до В займет в лучшем"
случае 16 мин, а в случае выбора восточного направления пришлось бы едать
18 мкн. Значит, если мы попали на угол (1,0), луч-
А
Рис. 8
Север (c)
8 ? ' (c) <
G 5
(c)
Еосггск
Сзе.еэ
(ю) т :Т:
А
Рис. 9
Е I(r)
6 (c) 5
(б\
Восток
.131
шее, что мы можем сделать, - это ехать на север, и тогда путь до В займет
16 мин. Это показано на рнс. S.
Далее будем действовать таким же образом, помещая в каждый угол
определенное число и указывая стрелкой направление, которое нужно
выбрать. В результате мы получим схему, показанную на рис. 10.
Каи провхат* быстрее!-
1S
Теперь решение нашей задачи становится очевидным Начнем из точки А и
пойдем по стрелкам, которые,' как мы видим, указывают путь СВВС. Число,
помечающее угол А, сразу показывает нам минимальное время в минутах,
необходимое для- поездки нз
В
¦^Воспчок
Рис. 1в
А в В. Отметим, что мы получили то же самое решение СВВС, которое раньше
нашлн с помощью полного перебора. Однако новый метод намного эффективнее.
На каждом углу мы делали не более двух сложений и одно сравнение, т. е. 3
операции. Например, для схемы 30X30, в которой 31X31 = 961 углов, поиск
лучшего пути потребовал бы менее 3000 операций и компьютерное время
снизилось бы до 3/100 с.
Таким образом, мы получили следующую таблицу:
Размер
2X2 10ХЮ 30X30
2X2 10 X 1C ЗОХЗС
Число операций Вручную На компьютере
Полный перебор 23 < 10 мин -
3 695119 "= месяц ^ 3,7 г
> 101(r) - > ЮС-ООО лет
Динамическое программирование <27 <10 мин -
<363 " 10 мин <4)1000ус
<3 000 " 75 мин <ЗЛ0ОЭс
Север
ю) 1 (c) г
8 (c) 2 6
(c) СП ч (c) 5
16
Фантазия 1
Задача 1. С помощью метода динамического программирования найдите
минимальное время (в минутах), за которое можно попасть из Л в В (см.
Север
1 7 6
4 5 4
3 2 3
1 2 2
7 3 4
4 Б 9
3 4 3
Рис. 11
рис. 11). Не забудьте, что на каждом углу надо ехать или на восток, или
на север.
Рис. 12
Задача 2. С помощью метода динамического программирования найдите
минимальное время, за которое можно попасть из Л в В (см. рнс. 12). Не
забудьте, что на каждом углу надо ехать либо на север, либо на восток.
Как проехать быстрее?
17
Задача 3. В фундаменте здания надо провести водопровод. Трубы от исходной
точки А к точке В можно проложить по-разному; это показано на рис. 13.
Поскольку длины труб и характер препятствий для разных вариантов
различны, разным путям соответствуют разные затраты. Стоимость труб
указана под
В
каждым участком пути. Каждое препятствие отмечено значком (r), под которым
указана стоимость устранения этого препятствия. Какой путь следует
выбрать, чтобы минимизировать затраты?
Задача 4. Приведите пример, который показал бы, что в отсутствие
ограничения, состоящего в том, что на каждом углу можво поворачивать
только на север или на восток, метод динамического программирования не
всегда дает оптимальный путь.
18
Фантазия 2
Фантазия 2
НА ВЕРТОЛЕТЕ
Математика: алгебра, неравенства
Вертолет Сикорского может перевозить грузы или внутри фюзеляжа, или
снаружи, подвешенными под фюзеляжем. Груз, подвешенный снаружи, создает
помеху, и средняя скорость оказывается меньше, чем при перевозке грузов
внутри. Однако загрузка и разгрузка при перевозке грузов снаружи обычно
занимают меньше времени, чем при перевозке внутри фюзеляжа.
Будем считать, что груз можно перевозить любым из этих способов, но их
комбинация (часть груза внутри, часть снаружи) исключается. Предположим,
что груз надо перевезти на 80 миль и время доставки чрезвычайно важно.
Пусть числовые данные таковы:
Средняя " D
скорость ВРемя, ч (r)Ремя , ,
(миля/ч) погрузки (ч) разгрузки (ч)
Внутри 140 1/4 1/4
Снаружи 100 1/12 1/12
Заметим, что в случае перевозки груза внутри фюзеляжа время полета равно
80/140 ч, а в случае перевозки снаружи - 80/100 ч. Таким образом, общее
время доставки груза при перевозке внутри фюзеляжа равно
- +--(- - =-1^(5" 1 07 ч)
4 140 4 14' - >'
погрузка полет разгрузка
а общее время доставки груза при перевозке снаружи равно
1 I 80 I 1 29 / П П-7 Ч
12 100 12 39 0,97 Ч)-
погрузка полет разгрузка
Таким образом, на 80 миль груз лучше перевозить подвешенным под
фюзеляжем.
На вертолете
1"
Теперь предположим, что надо перевезти тот же груз на 200 миль. В этом
случае при перевозке груза внутри время полета составит 200/140, а при
Предыдущая << 1 .. 2 < 3 > 4 5 6 7 8 9 .. 41 >> Следующая