Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/6: Рейтинг темы: голосов - 6, средняя оценка - 5.00
vvm28
Учусь всегда.
441 / 54 / 24
Регистрация: 22.12.2013
Сообщений: 390
Записей в блоге: 11
Завершенные тесты: 1
#1

Задача о двух принтерах, печатающих с разной скоростью

19.02.2017, 13:24. Просмотров 1149. Ответов 6

Подскажите, пожалуйста алгоритм решения задачи.
Задача о двух принтерах, печатающих с разной скоростью.
Java

Даны два принтера.
Требуется напечатать документ состоящий из N страниц.
Принтеры работают с неодинаковой скоростью. Один печатает страницу за X секунд, а другой за Y.
И вот теперь Джон и Мэри пытаются подсчитать какое минимальное время
они могут затратить на печать всего документа.

Пример.
входные данные: 2 количество тестов. x y n , x - скорость печати одной страницы первым принтером
y - скорость печати одной страницы вторым принтером, n - количество страниц

2
1 1 5
3 5 4

ответ:
3 9

2 это количество тестов.
1(x) - скорость печати одной страницы первым принтером
1(y) - скорость печати одной страницы вторым принтером
5(n)- количество страниц.

3 (x)- скорость печати одной страницы первым принтером
5 (y) - скорость печати одной страницы вторым принтером
4 (n) - количество страниц.

Ответ в первом случае 3, 5 страниц разделили между двумя принтерами.
Один печатает 3 страницы за 3 секунды , другой 2 страницы за 2 секунды. В итоге они затратили 3 секунды.
Во втором случае 4 страницы разделили между двумя принтерами один напечатал 3 страницы за 9 секунд
и одну страницу за 5 секунд . В итоге они затратили 9 секунд.

Как я понимаю, нужно разделить количество страниц, оптимальным образом, между
двумя принтерами. Количество страниц может быть как четное, так и нечетное.
Но как это сделать. Помогите пожалуйста составить пошаговый алгоритм.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.02.2017, 13:24
Ответы с готовыми решениями:

Поезд ехал t1 ч со скоростью v1 км / ч, t2 ч со скоростью v2 и t3 ч со скоростью v3. Определить пройденные пути с разной
Поезд ехал t1 ч со скоростью v1 км / ч, t2 ч со скоростью v2 и t3 ч со...

Задача на нахождение расстояния между автомобилями, движущимися с разной скоростью
скорость первого автомобиля v1км\ч,второго v2 км/ч. определить расстояние...

Потоки работают с разной скоростью
public class Person extends Thread{ private boolean isCancel = false;...

Выдача udp с разной скоростью
Всем добра. Пытаюсь выдавать данные размером по 1000 байт с разной скоростью...

Передвижение спрайтов с разной скоростью
Проблема в следующем, что имеем 2 многоугольника, у одного скорость 0.5, у...

6
Shamil1
Модератор
2109 / 1419 / 322
Регистрация: 26.03.2015
Сообщений: 5,146
19.02.2017, 14:52 #2
На первый взгляд решается просто, но нужно проверять (возможна ошибка в алгоритме).
C#
1
2
3
4
5
int PrintingTime(int x, int y, int n)
{
    int nx = n * y / (x + y);
    return Math.Min((n - nx) * y, (nx + 1) * x);
}
1
vvm28
Учусь всегда.
441 / 54 / 24
Регистрация: 22.12.2013
Сообщений: 390
Записей в блоге: 11
Завершенные тесты: 1
19.02.2017, 17:09  [ТС] #3
Shamil1, Спасибо. Переписал на java.
Протестировал на 19 значениях. Ответ правильный.
Не могли бы вы подробно рассказать, как вы пришли к такой формуле.
0
Shamil1
Модератор
2109 / 1419 / 322
Регистрация: 26.03.2015
Сообщений: 5,146
19.02.2017, 18:01 #4
Цитата Сообщение от vvm28 Посмотреть сообщение
как вы пришли к такой формуле
Поделил листы между принтерами пропорционально производительности. Но получившееся дробное значение можно округлить вверх или вниз.

nx - округление вниз (второму принтеру больше работы)
ny = n - nx
время работы второго принтера ny * y = (n - nx) * y

nx + 1 - округление вверх
время работы первого принтера (nx + 1) * x
0
vvm28
Учусь всегда.
441 / 54 / 24
Регистрация: 22.12.2013
Сообщений: 390
Записей в блоге: 11
Завершенные тесты: 1
22.02.2017, 18:18  [ТС] #5
Спасибо за подробные объяснения.
0
Lightblash
0 / 0 / 0
Регистрация: 09.02.2018
Сообщений: 1
09.02.2018, 20:29 #6
Все равно не могу понять, что такое nx и как вы пришли к вот этой формуле:int nx = n * y / (x + y);
Можете, пожалуйста, объяснить?
0
Shamil1
Модератор
2109 / 1419 / 322
Регистрация: 26.03.2015
Сообщений: 5,146
10.02.2018, 18:54 #7
Lightblash,
Поделил страницы пропорционально скорости.
Например, если один принтер печатает 2 стр/мин, а другой 3 стр/мин, то первому даём 2/5 всех страниц, а второму 3/5.
Если надо напечатать 10 страниц, то всё просто - первому 4, второму 6, за 2 минуты напечатают. А если надо напечатать 12 страниц, то получится, что первому надо дать 4.8, а второму 7.2. Так как дробное число страниц дать не можем, то проверяем два варианта: 4 и 8, 5 и 7.
1
10.02.2018, 18:54
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.02.2018, 18:54

Движение шариков по окружности с разной скоростью
Здравствуйте. Дана квадратная область с координатами от 1 до 100, внутри...

Движение pictureBox с разной скоростью по эллиптической траектории
Как сделать движение нескольких pictureBox с разной скоростью по эллипсу ...

USB модем работает с разной скоростью в течение дня
Есть два модема от МТС: 7,2 и 21,6 мбит/с. Недавно обратил внимание, что с утра...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru