|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
25.11.2013, 21:07 | #1 |
Пользователь
Регистрация: 02.10.2011
Сообщений: 45
|
доработать алгоритм сравнения чисел.
Доброго времени суток.
задача. пользователь вводит некоторое кол-во чисел(отрезков времени)к примеру 8. программа должна разбить на 2 кучи эти числа, чтобы сумма в каждой кучке была примерно равна. Пример: числа 1,2,3,4,5,6,7,8 должно распределить кучка1(1+2+4+5+6=18) и кучка2(3+7+8=18). мой код . Код:
p/s желательно обойтись без банальной сортировки=)))) Последний раз редактировалось GoldSieg; 25.11.2013 в 21:11. |
26.11.2013, 00:58 | #2 | |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
посмотрите на эту тему.
возможно, что ссылки в пост #2 немного Вам помогут. Успехов! p.s. Цитата:
|
|
26.11.2013, 05:34 | #3 |
Форумчанин
Регистрация: 13.11.2013
Сообщений: 149
|
Полностью согласен со вторым постом.
Последний раз редактировалось nikmoon; 26.11.2013 в 06:59. |
26.11.2013, 15:23 | #4 |
Пользователь
Регистрация: 02.10.2011
Сообщений: 45
|
Serge_Bliznykov,
за ссылку конечно благодарствую, но мне мне интерестно как можно без сортировки обойтись. |
26.11.2013, 16:46 | #5 |
Форумчанин
Регистрация: 11.01.2013
Сообщений: 149
|
А если решить задачу в лоб? Тут понятное дело нужны знания в комбинаторике. Во первых нужно вычислить количество комбинаций без повторения. Ну вот смысл в том чтобы запомнить разность полученных ответов от этих самых кучек, соответственно по модулю, и эту минимальную разность считать ответом. А что касается реализации функции в которой будет разбиваться на кучки, то это конечно нужно продумать сейчас времени на это нет но задачка интересная. ТО есть примерно должно работать так:
итерация1: мин = 1+2+3+4+5+6+7+8; куч1 = 1; куч2 = 2+3+4+5+6+7+8; if (мин > abs(куч1-куч2)) мин = abs(куч1-куч2) итерация2: куч1 = 1+2; куч2 = 3+4+5+6+7+8; if (мин > abs(куч1-куч2)) мин = abs(куч1-куч2) итерация2: куч1 = 1+3; куч2 = 2+4+5+6+7+8; if (мин > abs(куч1-куч2)) мин = abs(куч1-куч2) И так далее пока не найдется нужные кучки. Но алгоритм надо продумать до конца. Единственное время выполнение одних и тех же участков кода может разнится.
Может это и чушь, но это моя чушь и я ее никому не отдам.
|
27.11.2013, 00:23 | #6 |
Пользователь
Регистрация: 02.10.2011
Сообщений: 45
|
Shad0wF1rst,Вот!. мне тоже эта задача показалась очень забавной, но все составленные мной условия заваливались.
Предложенный вами код конечно работать будет. но что если переменных будет не 8, а 108?) как бы так делать что было универсально.) |
27.11.2013, 09:23 | #7 | |
Форумчанин
Регистрация: 11.01.2013
Сообщений: 149
|
Цитата:
Да и вроде если логически подумать то помимо всего того что я говорил выше, количество всех комбинаций для правильного решения должно сократиться вдвое, а если начинать с конца, то сходимость должна быть выше. но тогда все значения должны быть отсортированы. Знаю это все в теории.
Может это и чушь, но это моя чушь и я ее никому не отдам.
Последний раз редактировалось Shad0wF1rst; 27.11.2013 в 09:51. |
|
27.11.2013, 10:37 | #8 |
Пользователь
Регистрация: 02.10.2011
Сообщений: 45
|
Если работать с отсортированым массивом, то чем плоха моя программа вроде с любыми значениями работает оптимально.
Код:
|
27.11.2013, 11:41 | #9 | |
Форумчанин
Регистрация: 11.01.2013
Сообщений: 149
|
Цитата:
Сорри написал чушь выше, единственная рекомендация начинать с больших чисел и идти на уменьшение Для убедительности своих слов относительно обратного порядка следования от больших чисел к меньшим скажу что при использования прмого порядка от 2..size для вашего примера где числа от 1..8 получаются числа 16 и 20 при обратном же получается 18 18
Может это и чушь, но это моя чушь и я ее никому не отдам.
Последний раз редактировалось Shad0wF1rst; 27.11.2013 в 12:26. |
|
27.11.2013, 13:25 | #10 |
Пользователь
Регистрация: 02.10.2011
Сообщений: 45
|
я имел ввиду, что моё условие будет работать оптимально в отсортированном по убыванию. т.е 1е два будут самыми большими значениями, но как без сортировки, то сделать).
з.ы подскажите как правильно параметры кода в шапке в функцию передать. Код:
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Алгоритм сравнения спектров (звуков) | chertovich | Общие вопросы по программированию, компьютерный форум | 3 | 09.02.2013 14:53 |
Не срабатывает условие сравнения чисел. | Solvinder | Помощь студентам | 1 | 28.04.2011 23:01 |
алгоритм сравнения больших чисел со сдвигом | WOLFak | Паскаль, Turbo Pascal, PascalABC.NET | 0 | 29.12.2008 22:36 |
Алгоритм сравнения | f3nix | Общие вопросы Delphi | 1 | 16.02.2008 11:12 |