|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
30.12.2013, 19:41 | #1 |
Новичок
Джуниор
Регистрация: 30.12.2013
Сообщений: 13
|
Задача на паскале: Разделить элементы массива на 2 группы так, что бы разность между ними была минимальна.
Всем привет! Помогите оформить или подсказать код к вот такой задаче:
1. Вводится число, означающее количество элементов массива. 2. Разделить элементы массива на 2 группы так, что бы разность между ними была минимальна. Например, вводим: 3 1 3 5 Получаем: 1 Или ещё 4 1 1 1 1 Получаем: 0 Как я решил эту задачу: (Допустим, входные данные были: 3 1 3 5) 1. Ищем сумму и делим на два (1+3+5)/2=4,5. 2. Нужен массив, длина которого будет в 2 раза меньше, чем длина введённого. 2.1. Если длина массива нечётная, то округлить длину массива в меньшую сторону. 3. "Засовываем" все возможные комбинации чисел в наш обрезанный массив и искать разность чисел с тем, что получилось в п. 1. 3.1. Разность брать по модулю, чтобы не было геморроя. 4. Наименьшая возможная разность и будет решением, но не будет ответом, так как ответом будет эта минимальная разность умноженная на два. Как теперь всё это оформить в виде кода? |
30.12.2013, 20:00 | #2 | |
Форумчанин
Регистрация: 28.09.2013
Сообщений: 115
|
по-моему вы не верно понимаете условия задачи
Цитата:
Вот только не понятно какая разность имеется ввиду? а) разность суммы элементов в группах или б) разность между количеством элементов в группах
Что бы еще такого сделать, чтобы ничего не делать?
Последний раз редактировалось DpolenST; 30.12.2013 в 20:05. |
|
30.12.2013, 20:04 | #3 | |
Новичок
Джуниор
Регистрация: 30.12.2013
Сообщений: 13
|
Цитата:
Т.е. a[1]:=1 a[2]:=3 a[3]:=5 а сумма будет 9 У меня там не условие идёт, а моё решение . Там же ниже написал, что потом я беру массив (в теории: кода нет), который в два раза меньше входного и округляю его в нечётную сторону (чтобы памяти меньше использовалось). |
|
30.12.2013, 20:21 | #4 |
Форумчанин
Регистрация: 28.09.2013
Сообщений: 115
|
1. Сортировать элементы основного массива по убыванию
2. Найти минимальную разность двух массивов Основная идея поиска состоит в том, что берется максимальный элемент (после сортировки он у нас на "0" месте) в первый массив, второй во второй, находится разница сумм элементов, если разница больше нуля, то есть во втором массиве элемент меньше чем в первом, то во второй массив добавляется еще один элемент, если же разность снова положительная значит во второй массив добавляется еще один элемент и так далее пока разность не будет отрицательна, это как раз и значит, что во втором массиве сумма элементов превысила сумму элементов первого массива, значит следующий элемент нужно добавить в первый массив Это не совсем полноценный вариант, но хотя бы направление в какую сторону двигаться)
Что бы еще такого сделать, чтобы ничего не делать?
Последний раз редактировалось Stilet; 31.12.2013 в 09:15. |
30.12.2013, 23:18 | #5 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Оптимальный ответ даст только ПОЛНЫЙ перебор. При количестве предметов (очень примерно) больше 30 это уже не реально (банально время перебора превышает все мыслимые допустимые ожидания).
Но есть алгоритмы, которые достаточно быстро дают решение БЛИЗКОЕ к оптимальному. Вот, сходите по ссылочке - ТЫРК |
31.12.2013, 06:16 | #6 | |
Новичок
Джуниор
Регистрация: 30.12.2013
Сообщений: 13
|
Цитата:
Я так понимаю, этот алгоритм работает примерно так: Вводим 4 2 1 19 18 Программа будет работать так: Берутся 19 и 18 К 19 идёт 1 а к 18 идёт 2. Разница между ними будет 0. Это я понял, но как реализовать? Результат нужен точный, а не приближённый. Последний раз редактировалось Rhc; 31.12.2013 в 06:37. |
|
31.12.2013, 08:40 | #7 | |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Цитата:
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
|
31.12.2013, 10:43 | #8 | |
Новичок
Джуниор
Регистрация: 30.12.2013
Сообщений: 13
|
Цитата:
По предложенной здесь идеи я сделал программу, но она вообще ни разу правильный ответ не выдала. Точнее, она может выдать правильный ответ, но только в частных случаях. |
|
31.12.2013, 10:56 | #9 | |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
Цитата:
|
|
31.12.2013, 11:13 | #10 | |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Цитата:
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Последний раз редактировалось Аватар; 31.12.2013 в 11:15. |
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
задача:задать два смежных графа,провести операции над ними пересечение ,объединение и разность | dgulij | Паскаль, Turbo Pascal, PascalABC.NET | 0 | 14.05.2013 17:32 |
Мне надо сделать так что бы на главной странице картинка была по центру и под ней находился текст | Чайник = ) | HTML и CSS | 1 | 21.10.2010 18:39 |
разделить элементы данного массива на три подмассива с одинаковой суммой элементов | astr_al | Помощь студентам | 3 | 19.12.2009 20:05 |
Вычислить максимальную разность между К и суммой двух соседних эллементов массива. | Luska | Помощь студентам | 3 | 22.03.2009 19:22 |