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

@Никита Однороб · Регистрация: 21.08.2012

Студворк — интернет-сервис помощи студентам

Нужно распредилить большой отрезок на маленькие (кол-во и размер указаны). Вот допустим, заданы параметры: 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

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

И по такому принципу нужно сравнить все варианты и выбрать самый оптимальный.Подскажите, КАК??? Может в инете похожее что-то валяется

@Neo-n06 · 09.10.2013, 21:48

Ну первое что мне приходит в голову это составить все сочетания цифр по 2 цифр заем суммировать как показано в примере затем ищем остаток и счетчик остатков увеличивае на один .... а потом выводим кмбинацию с наимньшим числом остатков

@Никита Однороб · 09.10.2013, 21:51 **[ТС]**

Neo-n06, это был пример, а в реале может быть до 14 цифр. Это будет очень долго (4^14)

@Neo-n06 · 10.10.2013, 10:25

Хорошо тогда по другому берем большой отрезок и начинаем делить на маленькие те которые даны с остатком и без. Деление нацело нам даст кол-во маленьких отрезков в большом деление с остатком нам даст то сколько неиспользованых метров в большом отрезке осталось.
Пример на основе твоего:
10 / 5 = 2;
10 mod 5 = 0;
значит сюда без остатка укладывается 2 отрезка; используем сюда 2 отрезка по 5; (остался один)
далее
10 / 5 = 2; (проверяем каждый раз остаток данных отрезков если есть берем 2)
10 mod 5 = 0;

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

Единственное что вижу это надо начинать делить с больших маленьких отрезков.

@Qwertiy · 10.10.2013, 12:09

Сколько мелких отрезков и насколько они мелкие?

@Никита Однороб · 10.10.2013, 12:15 **[ТС]**

2 отрезка по 3м и 4 отрезка по 5м

@Qwertiy · 10.10.2013, 12:24

Сообщение от Никита Однороб

2 отрезка по 3м и 4 отрезка по 5м

Это как? Если число отрезков ограничено, то ими большую длину никак не набрать...

@Никита Однороб · 12.10.2013, 22:10 **[ТС]**

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

@Neo-n06 · 14.10.2013, 12:04

ну так смотри
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 метра .....

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .

@Neo-n06 22 / 3 / 0 Регистрация: 21.06.2009 Сообщений: 38
	09.10.2013, 21:48
	Ну первое что мне приходит в голову это составить все сочетания цифр по 2 цифр заем суммировать как показано в примере затем ищем остаток и счетчик остатков увеличивае на один .... а потом выводим кмбинацию с наимньшим числом остатков 0

@Никита Однороб 109 / 88 / 28 Регистрация: 21.08.2012 Сообщений: 371
	09.10.2013, 21:51 [ТС]
	Neo-n06, это был пример, а в реале может быть до 14 цифр. Это будет очень долго (4^14) 0

@Neo-n06 22 / 3 / 0 Регистрация: 21.06.2009 Сообщений: 38
	10.10.2013, 10:25
	Хорошо тогда по другому берем большой отрезок и начинаем делить на маленькие те которые даны с остатком и без. Деление нацело нам даст кол-во маленьких отрезков в большом деление с остатком нам даст то сколько неиспользованых метров в большом отрезке осталось. Пример на основе твоего: 10 / 5 = 2; 10 mod 5 = 0; значит сюда без остатка укладывается 2 отрезка; используем сюда 2 отрезка по 5; (остался один) далее 10 / 5 = 2; (проверяем каждый раз остаток данных отрезков если есть берем 2) 10 mod 5 = 0; ну и остается 3+3 =) Единственное что вижу это надо начинать делить с больших маленьких отрезков. 1

@Qwertiy 835 / 643 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	10.10.2013, 12:09
	Сколько мелких отрезков и насколько они мелкие? 0

@Никита Однороб 109 / 88 / 28 Регистрация: 21.08.2012 Сообщений: 371
	10.10.2013, 12:15 [ТС]
	2 отрезка по 3м и 4 отрезка по 5м 0

@Neo-n06 22 / 3 / 0 Регистрация: 21.06.2009 Сообщений: 38
	14.10.2013, 12:04
	ну так смотри 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