Какой алгоритм ?
 |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
| ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
| [216.73.217.37] |
|
|
правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке
Модераторы: Akina, shadeofgray
Какой алгоритм ?
|
Сообщ.
#1
,
|
|
|
|
Люди ! Кто знает алгоритм, подскажите пожалуйста.
Ситуация следующая: Есть M числовых массивов длиной L. Числа в массивах от 1 до 10. Нужно из каждого массива выбрать по одному числу, чтобы сумма выбранных чисел равнялась N. Все числа целые. |
|
Сообщ.
#2
,
|
|
  |
по моему надо перебором, но не всегда получиться N.
|
|
Сообщ.
#3
,
|
|
|
|
а числа в массивах как заполняются?
|
|
Сообщ.
#4
,
|
|
|
|
Тривиальная задачка на полный перебор. Я бы сделал рекурсию в случае, если M не очень велико. Если оно очень велико - тем хуже, можно вообще не дождаться решения задачи.
Идея такая. Пишешь рекурсивную функцию, которая получает на вход номер строки матрицы MxL и текущую сумму. Если Текущая сумма плюс минимальный элемент строки больше N - возвращаемся, если текущая сумма плюс максимальный элемент меньше N и это последняя строка - тоже возвращаемся. Если последняя строка - тут все понятно. Прибавляем элементы к сумме, если получилось N - хорошо, запихиваем результат куда-нибудь и возвращаемся. Если не последняя строка - крутим цикл от первого элемента строки до последнего, вызывая рекурсивно саму себя с параметром текущая строка+1 и текущая сумма + текущий элемент. Вот так. Возможно, этот перебор еще можно сократить. Но лобовой метод - такой. Можно реализовать нерекурсивно, это может дать небольшой выигрыш в скорости. |
1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
0 пользователей:
[ Script execution time: 0.1273 ] [ 14 queries used ] [ Generated: 24.10.26, 00:55 GMT ]