Форум программистов, компьютерный форум, киберфорум
Наши страницы

Алгоритмы

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 1, средняя оценка - 5.00
vvm28
Учусь всегда.
23 / 24 / 5
Регистрация: 22.12.2013
Сообщений: 287
Записей в блоге: 11
Завершенные тесты: 1
#1

Задача о двух принтерах, печатающих с разной скоростью - Алгоритмы

19.02.2017, 13:24. Просмотров 936. Ответов 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
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Задача о двух принтерах, печатающих с разной скоростью (Алгоритмы):

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

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

Потоки работают с разной скоростью - Java SE
public class Person extends Thread{ private boolean isCancel = false; private int count = 0; public Person (String...

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

Движение pictureBox с разной скоростью по эллиптической траектории - C#
Как сделать движение нескольких pictureBox с разной скоростью по эллипсу private void button1_Click_1(object sender, EventArgs e) ...

USB модем работает с разной скоростью в течение дня - Периферийные устройства
Есть два модема от МТС: 7,2 и 21,6 мбит/с. Недавно обратил внимание, что с утра и ночью модемы работаю хорошо (но не всегда), а днем...

6
Shamil1
Модератор
2056 / 1362 / 264
Регистрация: 26.03.2015
Сообщений: 4,959
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
Учусь всегда.
23 / 24 / 5
Регистрация: 22.12.2013
Сообщений: 287
Записей в блоге: 11
Завершенные тесты: 1
19.02.2017, 17:09  [ТС] #3
Shamil1, Спасибо. Переписал на java.
Протестировал на 19 значениях. Ответ правильный.
Не могли бы вы подробно рассказать, как вы пришли к такой формуле.
0
Shamil1
Модератор
2056 / 1362 / 264
Регистрация: 26.03.2015
Сообщений: 4,959
19.02.2017, 18:01 #4
Цитата Сообщение от vvm28 Посмотреть сообщение
как вы пришли к такой формуле
Поделил листы между принтерами пропорционально производительности. Но получившееся дробное значение можно округлить вверх или вниз.

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

nx + 1 - округление вверх
время работы первого принтера (nx + 1) * x
0
vvm28
Учусь всегда.
23 / 24 / 5
Регистрация: 22.12.2013
Сообщений: 287
Записей в блоге: 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
Модератор
2056 / 1362 / 264
Регистрация: 26.03.2015
Сообщений: 4,959
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
Привет! Вот еще темы с ответами:

Нарисовать часы с вращающимися с разной скоростью часовой и минутной стрелками - Pascal ABC
Напишите программу которая выводит динамическое изображение часов с вращающимися с разной скоростью часовой и минутной стрелками

Путник двигался t1 часов со скоростью v1, затем t2 часов- со скоростью v2 и t3 часов со скоростью v3. За какое время он одолел первую половину пути - C++
Путник двигался t1 часов со скоростью v1, затем t2 часов- со скоростью v2 и t3 часов со скоростью v3. За какое время он одолел первую...

Путник двигался t1 часов со скоростью v1, затем t2 часов - со скоростью v2 и t3 часов – со скоростью v3. За какое время он одолел половину пути? в с++ - C++
Путник двигался t1 часов со скоростью v1, затем t2 часов - со скоростью v2 и t3 часов – со скоростью v3. За какое время он одолел половину...

Сложение двух чисел разной разрядности - Assembler
Здравствуйте, подскажите, как правильно сложить два числа, если одно из них 16 разрядное, а другое 32-х? Я просто не совсем могу понять сам...


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

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

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