Компьютерный форум OSzone.net  

Компьютерный форум OSzone.net (http://forum.oszone.net/index.php)
-   Программирование и базы данных (http://forum.oszone.net/forumdisplay.php?f=21)
-   -   Математическая задача (http://forum.oszone.net/showthread.php?t=151945)

pirojok750 01-10-2009 00:17 1231562
Математическая задача
 
Суть вот в чем.с клавиатуры вводится путь S, скорость на такси -V1,скорость пешком V2.так же вводится обшее время пути t и стоимость р1-рублей за километр на такси.необходимо расчитать как выгоднее преодолеть путь,чтобы получились минимальные затраты.если двигаться пешком то затрат нет,оплачивается только поездка на такси.язык может быть си или паскаль,но не делфи.

pva 01-10-2009 08:08 1231721
Цитата:
Цитата pirojok750
Суть вот в чем.с клавиатуры »
будем надеяться, что в этой фразе зашифровано "здравствуйте мною глубокоуважаемые обитатели форума, да восхвалится имя ваше..."
В чём возникли проблемы при решении задачи? в математике или в кодировании? что сделано самостоятельно?

lxa85 01-10-2009 09:08 1231764
pirojok750, говорю полностью от своего имени.
Данная задача может быть предложена на первом(втором "условия и циклы") лаб. занятии по программированию. Где в первую очередь необходимо написать мат. модель, а затем ее запрограммировать.
Полностью решать от и до, я не буду. В лучшем случае, задам наводящий вопрос.
Заодно прошу всех, далее отвечающих, не расписывать решение задачи полностью. А лишь задавать вопросы, без вариантов ответа.
У меня самого группа в 20 студентов. :)
pirojok750, пишите, рассуждайте в слух, задавайтесь числами, решайте на примерах, потом выводите общий случай.

Drongo 01-10-2009 11:55 1231860
pirojok750, Задачка не трудная, нужно её разбаить на ряд отдельных подзадач:

1. Решение чисто математическое, с учётом формул.
2. Составление псевдокода. (обычный текст, но понятный где, как и откуда что вычислять.)
3. Перевод псевдокода в нужный язык программирования.

Например часть псевдокода:
Цитата:
Цитата pirojok750
с клавиатуры вводится путь S, скорость на такси -V1,скорость пешком V2 »
Определение количества переменных: Определяем нужное кол-во переменных и объявляем их.
Ввод данных: Предлагаем пользователю ввести их и сохраняем считаные значения в переменные.
Расчёт: Условия\Формулы вычисления

Прикольная постановка задачи:
Цитата:
Цитата pirojok750
если двигаться пешком то затрат нет,оплачивается только поездка на такси. »
Причём оплата поездки на такси, при ходьбе пешком? Мне кажется или точки\запятые расставлены не там где надо или формулировка должна быть несколько иной.

lxa85 01-10-2009 12:29 1231876
Цитата:
Цитата Drongo
Определение количества переменных: Определяем нужное кол-во переменных и объявляем их.
Ввод данных: Предлагаем пользователю ввести их и сохраняем считаные значения в переменные.
Расчёт: Условия\Формулы вычисления »
Все это выплывает из формул.

Привожу кусок моего письма старосте группы.

Привожу пример тебе, задачу решали вместе с <student_name>
Любимая задача Коли Сорокина из мультика. Она же приведена одной из первых в сборнике задач по физике под ред. Гольдфарба.

Из пункта А в пункт Б вышел товарный поезд со скоростью V1,
в тоже время на встречу ему из пункта Б вышел курьерский поезд со скоростью V2.
Найти расстояние от пункта А до места встречи поездов.

Дано:
V1, V2: скорость поездов (км/ч)
L : расстояние между пунктами А и Б (км)
---------
Найти
AC. (С - место встречи)

Решение:
Очевидно скорость сближения равна
V = V1 + V2 (1)
Время в пути
t=L/V (2)
AC = V1*t (3)
В необъязательном развернутом виде
V1 * L
AC = ------------ (3')
(V1 + V2)

Все, задача решена. У нас есть формула, подставляя значения в которую мы можем найти все, что нам требуется.
(Можно конечно поиграть с дополнительными условиями, выражением одной скорости через другую и т.д., но не в этом суть)
И "вбить" ее в Pascal уже не представляет сложности.

Код:
var
V1,V2,V:real; //скорости
AC,L:real; //расстояния
t:real; // время
begin
writeln('всякая вводная фигня+условия задачи');
readln(V1,V2,L); // вводим данные;
V:= V1+V2;        // (1) номер формулы в документации
t:= L/V;        // (2)
AC:= V1*t;        // (3)
writeln(t:4,' ',AC:4); //форматированный вывод в соотв с Техническим заданием (ТЗ).
readln; //пауза для просмотра результата. В реальных программах не ставится.
end.
Вот это требовалось от вас. Т.к. задай я эту задачу, все равно, как не крути, а пришлось бы столкнуться с математикой.
Правда найдутся умельцы, которые захотят сразу задаться цифрами, и уйти от формул.
Что бы этого не происходило, я требую мат. модель задачи. Т.е. все расчетные формулы до того как их начать программировать.

pirojok750 01-10-2009 16:40 1232046
Уважаемые форумчане.как сказал lxa85, за меня все решать не надо,ее и вправду проходят по программированию.вопрос вот в чем.я вывел зависимость что S=V1*t1+V2*t2 и общее время пути будет определятся по формуле Tобщее=t1+t2.
Вводимыми переменными являются:длина всего пути-S, скорость движения такси-V1, скорость движения пешехода- V2, общее время веделенное на прохождение всего пути T, стоимость проезда на такси рублей за километр- р1.необходимо преодолеть весь путь S за выделенное время чтобы затраты на дорогу были минимальны.

Drongo 01-10-2009 20:23 1232231
Цитата:
Цитата pirojok750
общее время пути будет определятся по формуле Tобщее=t1+t2. »
Общее время преодоления пути на такси + пешком или для каждого вида передвижения? У вас появилась новая переменная t2 которой в постановке задачи её нет.

Итак, переменные (C++):
Код:
...
  int S;    // Длина всего пути
  int V1;  // Скорость движения такси
  int V2;  // Скорость движения пешехода
  int T;  // Общее время выделенное на прохождение всего пути
  // Наверное стоит выделить две переменные для определения
  // общего времени преодоления пути (такси и пешеход)
  int p1;  // Стоимость проезда на такси рублей за километр
  // Переменная в которой будет храниться значение:
  // Сколько времени выделено на преодоление пути
...
Время общего преодоления пути (такси + пешеход) зачем так? думаю вычислить так.

T = S * V1 + S * V2;

pirojok750 01-10-2009 20:39 1232247
Drongo, простите,вы видать меня не правильно поняли.как вы скорость умножаете на пройденый путь?что получится то?

Разъясняю еще раз суть задачи.Задается путь S и время за которое этот путь должен быть преодолен.у путника 2 варианта-это такси со скоростью V1 и пешком со скоростью v2. если он двигается на такси то платит р1 руб/км или пешком бесплатно.нужно расчитать как ему выгоднее преодолеть весь путь S с минимальными затратами на такси,успев во время T. Путник может двигаться на такси и пешком если ему позволяет время

Drongo 01-10-2009 20:55 1232259
Цитата:
Цитата pirojok750
.как вы скорость умножаете на пройденый путь?что получится то? »
Да, торможу, делить нужно. :(

lxa85 01-10-2009 21:01 1232265
Цитата:
Цитата Drongo
T = S * V1 + S * V2; »
t=S/v ;)
pirojok750,
Цитата:
Цитата pirojok750
Путник может двигаться на такси и пешком если ему позволяет время »
Ни на какую мысль не наводит?
Двигаться пешком, если позволяет время.
Надо проехать столько, чтобы потом сравнять текущее время, с выделенным, пройдя оставшийся кусок дороги.
В математике условия пишутся через фигурную скобку. Пример - раскрытие знака модуля.
Рассуждаем дальше :)

pirojok750 01-10-2009 21:17 1232274
математически решить вроде получается.а вот пока закодировать не очень.буду пробовать сегодня.при помощи 2х формул возможно ведь решение S=V1*t1+V2*t2 Tобщее=t1+t2.??

lxa85, решить систему из 2 уравнений я могу.
для примера я брал такие значения s=1000, v1=100, v2=10, T=15
1000=100*t1+10*t2 (S=t1*v1+t2*v2)
15=t1+t2( Tобщее=t1+t2)
t2=T-t1
1000=100*t1+10*15-10t1
1000=90t1+150
850=90t1
t1=9.4444

t2=15-9.4444
t1=5.5556

lxa85 02-10-2009 00:27 1232432
Цитата:
Цитата pirojok750
решить систему из 2 уравнений я могу.»
Переводя в формулы это выглядит так:
S = v1t1 + v2t2;
t2 = T - t1;
S = v1t1 + v2T - v2t1;
t1=?.
Дальше задача "распадается", писать не интересно.
Операторы С++ читать читаю, писать, не пишу. Поэтому пишу Pascal версию.
Код:
var
  v1,v2:real; // на всякий случай, дробной пешей скорости 3,5 км/ч
  T,t1,t2:real; // никогда час в час не получится. :(
  S:integer; // простим сотни метров, округлим до целого кол-ва км.
  Z,p1:real; //Z - затраты на путь. p1 - стоимость км.
begin
  write('Input <S,v1,v2,T>' );
  readln(S,v1,v2,T);
  t1:=?; // номер формулы в описании;
  t2:=T-t1; //
  writeln('t1 = 't1);
  writeln('t2 = 't2);
  Z:=?;
  writeln('Стоимость пути = ', Z);
end.

pirojok750 02-10-2009 01:20 1232466
lxa85, дальше путь пройденый на такси умножается на р1.

t1:=?; // номер формулы в описании; t1 изначально неизвестен.есть только обшее время T

pva 02-10-2009 07:22 1232516
правильно ли я понимаю постановку задачи?
Код:
  T1 +    T2 = T
v1*T1 + v2*T2 = S

          | 1,  1|
{T1,T2} * |v1, v2| = {T,S}

Если матрица не вырождена, то решение уравнения,
если вырождена, то либо решения нет (v1=v2, T<>S), либо всё время идти пешком (v1=v2, T=S)
Или это всё-таки задача линейного программирования?
Код:
c1*T1 -> min
T1 >= 0
T2 >= 0
  T1 +    T2 <= T
v1*T1 + v2*T2 = S

lxa85 02-10-2009 08:49 1232545
Цитата:
Цитата pirojok750
t1:=?; »
я знаю, что не известен. :)
Меня интересует формула получения t1. из предыдущей. S= ...
Поэтому я и не стал писать ее, предоставив эту возможность тебе.
Цитата:
Цитата pirojok750
дальше путь пройденный на такси умножается на р1. »
Это я тоже знаю. Но опять таки, написание формулы за автором топика :)
pva, ИМХО сначала пусть работает "топорно", затем уже вводить ограничения на отрицательную скорость, отношения скоростей пешеход-такси. Предусмотреть, чтобы с сверхзвуковой скоростью не ездили и т.д.

pva 02-10-2009 15:07 1232774
Цитата:
Цитата lxa85
затем уже вводить ограничения на отрицательную скорость, отношения скоростей пешеход-такси. Предусмотреть, чтобы с сверхзвуковой скоростью не ездили и т.д. »
Я написал типовые постановки задач (и уже назвал классификацию). Это обозначает что решение задачи существует (доказано), известно (есть алгоритм решения) и нужно тупо следовать алгоритму (лучше ничего не придумали).
ИМХО надо приучать студентов к общему алгоритму решения любой (абстрактной) задачи:
1. физическая постановка
2. математическа постановка
3. классификация (мат.постановка согласно постановке типовых задач)
4. решение методом согласно классификации
классическая задача линейного программирования (решается в общем случае симплекс-методом) выглядит так:
Код:
  c1*x1 + c2*x2 + c3*x3 + ... ->min
  x1 >= 0
  x2 >= 0
  x3 >= 0
  ...
  a11*x1 + a12*x2 + a13*x3 + ... <= b1
  a21*x1 + a22*x2 + a23*x3 + ... <= b2
  a31*x1 + a32*x2 + a33*x3 + ... <= b3
  ...

pirojok750 02-10-2009 15:21 1232781
Уважаемые pva, и lxa85, в начале поста я просил помоч мне решить простую задачу.вы ушли от простой математики к задачам линейного программирования,усложнив мне ее решение.можно как нибудь попроще решить данную зачаду??

lxa85 02-10-2009 17:27 1232890
pirojok750, никуда мы не уходили.
Математика - это математика.
Линейное программирование - это последовательно выполнение ряда действий над переменными. (В данном случае T,t1,V1,t2,V2,S и т.д.)
Оно(линейное программирование) самое простое. Вот когда добавятся условия, векторы чисел, объекты и потоки, там да, там возникают сложности.
Сейчас надо про них забыть, и решать так, как решается!
Т.е. по шагам, в одном единственном направлении.
Это и называется линейное программирование. (Не путать с линейной алгеброй :))

Сейчас от вас требуется из формулы
S = v1t1 + v2T - v2t1;
выразить t1.

Полученную формулу вписать в алгоритм и всё. Всё остальное лирика и красивые слова.

pirojok750 02-10-2009 19:06 1232966
Спасибо lxa85, все оказалось достаточно просто.я думаю закодировать это мне не составит труда.

pva 03-10-2009 12:36 1233377
Цитата:
Цитата pirojok750
Всё остальное лирика и красивые слова »
Не совсем :) если ограничение на время нестрогое ( <= ), то:
1. у этой задачи всегда есть решение (следовательно программа не заглючит, а в предложенном варианте нет проверки на вырожденные случаи, когда например даже на такси не успеешь доехать, и не используется условие "с минимальными затратами")
2. надо добавить пару ветвлений алгоритма

pirojok750, простейший пример пренебрежения проверкой ограничений: компьютерный червь Kido использует переполнение строкового буффера чтобы проникнуть в чужую систему. Ну забыли проверить что строчка меньше определённой длины должна быть...
Надо приучаться не лениться даже на простых примерах.

И ещё: простота решения не связана простотой рассуждений. Бывает что вспомнишь все теории на свете, чтобы прийти к решению типа "result = a + b", и объяснить, почему имено так, без теории не получается.


Время: 05:40.

Время: 05:40.
© OSzone.net 2001-