Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Никита Однороб
109 / 89 / 28
Регистрация: 21.08.2012
Сообщений: 368
1

Прошу подсказать алгоритм

09.10.2013, 20:42. Просмотров 375. Ответов 8
Метки нет (Все метки)

Нужно распредилить большой отрезок на маленькие (кол-во и размер указаны). Вот допустим, заданы параметры: 2 отрезка по 3м и 4 отрезка по 5м, большие отрезки - 3 шт. по 10м.

Вот примеры, как можно это сделать:
1. а) 5 + 5 = 10 (остаток 0)
б) 5 + 5 = 10 (остаток 0)
Тут закончились все пятёрки и остались только два по 3
в) 3 + 3 = 6 (остаток 4)
Общий остаток - 4 + 0 + 0 = 4

2. а) 5 + 3 = 8 (остаток 2)
б) 5 + 3 = 8 (остаток 2)
в) 5 + 5 = 10 (остаток 0)
Общий остаток - 2 + 2 + 0 = 4
В данном случае приоритетным является первый вариант, потому что в первом мы без остатка использовали два отрезка, а во втором случае только один.

И по такому принципу нужно сравнить все варианты и выбрать самый оптимальный.Подскажите, КАК??? Может в инете похожее что-то валяется
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.10.2013, 20:42
Ответы с готовыми решениями:

Построить алгоритм Маркова, который ищет НОД (Алгоритм Евклида)
Здравствуйте, ребята, выручайте. Весь инет перерыл, всю голову сломал, но не...

алгоритм сжатя? коке алгоритм взят?
всем доброго времени суток ест дани таком формате...

Я не прошу писать мне код, я прошу подсказать мне, что за структура требуется в задании
Написать программу для работы по запросам оператора с приоритетной очередью...

Прошу подсказать
Вопрос в следующем. Итак имеем офис с 4 компьютерами и домашней сетью между...

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

8
Neo-n06
22 / 3 / 0
Регистрация: 21.06.2009
Сообщений: 38
09.10.2013, 21:48 2
Ну первое что мне приходит в голову это составить все сочетания цифр по 2 цифр заем суммировать как показано в примере затем ищем остаток и счетчик остатков увеличивае на один .... а потом выводим кмбинацию с наимньшим числом остатков
0
Никита Однороб
109 / 89 / 28
Регистрация: 21.08.2012
Сообщений: 368
09.10.2013, 21:51  [ТС] 3
Neo-n06, это был пример, а в реале может быть до 14 цифр. Это будет очень долго (4^14)
0
Neo-n06
22 / 3 / 0
Регистрация: 21.06.2009
Сообщений: 38
10.10.2013, 10:25 4
Хорошо тогда по другому берем большой отрезок и начинаем делить на маленькие те которые даны с остатком и без. Деление нацело нам даст кол-во маленьких отрезков в большом деление с остатком нам даст то сколько неиспользованых метров в большом отрезке осталось.
Пример на основе твоего:
10 / 5 = 2;
10 mod 5 = 0;
значит сюда без остатка укладывается 2 отрезка; используем сюда 2 отрезка по 5; (остался один)
далее
10 / 5 = 2; (проверяем каждый раз остаток данных отрезков если есть берем 2)
10 mod 5 = 0;

ну и остается 3+3 =)

Единственное что вижу это надо начинать делить с больших маленьких отрезков.
1
Qwertiy
823 / 631 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
10.10.2013, 12:09 5
Сколько мелких отрезков и насколько они мелкие?
0
Никита Однороб
109 / 89 / 28
Регистрация: 21.08.2012
Сообщений: 368
10.10.2013, 12:15  [ТС] 6
2 отрезка по 3м и 4 отрезка по 5м
0
Qwertiy
823 / 631 / 100
Регистрация: 20.08.2013
Сообщений: 2,524
10.10.2013, 12:24 7
Цитата Сообщение от Никита Однороб Посмотреть сообщение
2 отрезка по 3м и 4 отрезка по 5м
Это как? Если число отрезков ограничено, то ими большую длину никак не набрать...
0
Никита Однороб
109 / 89 / 28
Регистрация: 21.08.2012
Сообщений: 368
12.10.2013, 22:10  [ТС] 8
Neo-n06, спасибо за ответ, но есть варианты (и вполне реальные), где ваш алгоритм сработает очень плохо.

Большие отрезки - 5 штук по 5 метров
Маленькие:
1 шт по 3 см
4 шт по 4 см
1 шт по 2 см
3 шт по 1 см
Без остатка ничего не делится, так что облом А правильно вот так в данном случае:
1. 3 см и 2 см
2. 4 см и 1 см
3. 4 см и 1 см
4. 4 см и 1 см
5. 4
0
Neo-n06
22 / 3 / 0
Регистрация: 21.06.2009
Сообщений: 38
14.10.2013, 12:04 9
ну так смотри
5 /3 = 1
5 mod 3 = 2
тоесть 3 укладывается полностью и 2 м из 5 остается смотрим есть у нас 2 метра или нет если есть используем идем далее
5/4 =1
5 mod 4 = 1 используем 4 и 1 и так далее
смысл аот в чем деление нацело нам показывает сколько целых отрезков уложится 5/3 =1 тоесть в 5 у нас один отрезок 3 помещается
деление с остатком нам показывает сколько метров у нас еще осталось в этих 5. 5 mod 3 =2 тоесть осталось 2 метра .....
0
14.10.2013, 12:04
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.10.2013, 12:04

Прошу подсказать
Добрый день Вкратец проблема: Я по образованию экономист. На работе по...

прошу подсказать
Подскажите, пожалуйста, как реализовать сие на перле r = hex(w +...

Прошу подсказать с делегатами
Приветствую всех. У меня трабла с делегатами... Не могу понять почему делегат...


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

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

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