21 / 21 / 16
Регистрация: 30.09.2013
Сообщений: 262
|
|
1 | |
Перебор сумм чисел массива12.11.2014, 00:23. Показов 4280. Ответов 16
Метки нет (Все метки)
Собственно по одному предмету делаю курсач, и хотелось бы себя наверняка перепроверить, да и попрактиковать лишний раз C++.
Нужно грамотно научить программу перебирать массив следующим образом: Есть любые числа, например: 1, 8, 4, 2 Есть последовательность чисел: 0 1 2 ... 8 9 Получается некая таблица размером 4*10 Нужно следующее: Беру 0 из столбика и смотрю какие числа рядка мне надо взять что бы получить 0? Соответственно никакое не нужно, ставлю четыре нуля (0 0 0 0) (смотрите ниже) Беру 1 из столбика и смотрю какие числа рядка мне надо взять что бы получить 1? Соответственно беру 1 и на пересечение ставлю 1 0 0 0 ......... Беру 7 из столбика и смотрю какие числа рядка мне надо взять что бы получить 7? Соответственно беру сумму 1, 2 и 4 и на пересечение ставлю 1 0 1 1 ......... В конце получится должна получится таблица: * 1 8 4 2 0|0 0 0 0 1|1 0 0 0 2|0 0 0 1 3|1 0 0 1 4|0 0 1 0 5|1 0 1 0 6|0 0 1 1 7|1 0 1 1 8|0 1 0 0 9|1 1 0 0 Как мне научить этому программу? Я бы мог написать программу привязанную к 4м переменным, но а если мне надо будет больше переменных?
0
|
12.11.2014, 00:23 | |
Ответы с готовыми решениями:
16
Полный перебор чисел массива Перебор массива и поиск повторяющихся чисел Массив из сумм чисел исходного массива Перебор чисел |
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
|
|
12.11.2014, 09:05 | 2 |
-MaZaHaKa-, сколько строк и столбцов будет максимум? И до скольки числа?
0
|
236 / 196 / 21
Регистрация: 04.06.2014
Сообщений: 1,309
|
|
12.11.2014, 09:22 | 3 |
Не трудно подсчитать, что комбинация сумм всех цифр исходной строки будет N! и как следствие, ограничена либо временем вычислений, либо размером оперативки. То-же относится и к количеству строк.
0
|
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
|
|
12.11.2014, 10:49 | 4 |
SmittWesson, что значит комбинация сумм всех цифр в исходной строке? если это все возможные наборы чисел в заданной строке, то их 2^m, m - кол-во столбцов.
0
|
236 / 196 / 21
Регистрация: 04.06.2014
Сообщений: 1,309
|
|
12.11.2014, 12:21 | 5 |
Да-да. Точно. Спутал с полной перестановкой позиций цифр.
В таком случае, берём очередную цифру и прогоняем её через двоичное представление количества цифр в строке - 1 т.к. комбинация 0000 не имеет смысла.
0
|
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
|
|
12.11.2014, 12:48 | 6 |
SmittWesson, эту задачу можно решить быстрее, чем за n * 2^m.
0
|
236 / 196 / 21
Регистрация: 04.06.2014
Сообщений: 1,309
|
|
12.11.2014, 12:59 | 8 |
Вы сами себе противоречите. Не за n * 2^m, а за 2^m-1. Согласен, можно несколько ускорить, если в исходной строке имеются нули. Исключаем все двоичные комбинации совпадающие с суммированием нулей.
Например, для строки 5 0 6 0 исключить можно комбинации:0101, 0100, 0001 ну и само-собой - 0000.
0
|
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
|
|
12.11.2014, 13:02 | 9 |
SmittWesson, время работы(асимптотика) такого алгоритма(перебора) O(n * 2 ^ m), я говорю что эту задачу можно решить быстрее совсем другим способом.
0
|
236 / 196 / 21
Регистрация: 04.06.2014
Сообщений: 1,309
|
|
12.11.2014, 13:05 | 10 |
n - то откуда взялась? Строки добавляются по мере совпадения сумм чисел и вначале итераций не определены. Или Вы имеете в виду постоянную алгоритма?
А вот на счёт "другим способом", можно ли поподробней?
0
|
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
|
|
12.11.2014, 13:12 | 11 |
SmittWesson, нам надо каждое из N чисел представить в виде суммы M чисел. одно число мы можем представить в виде суммы M других за O(2 ^ m * m), ну и поэтому чтобы N чисел представить надо будет сделать N * 2 ^ M * M операций.
клик
0
|
236 / 196 / 21
Регистрация: 04.06.2014
Сообщений: 1,309
|
|
12.11.2014, 13:36 | 12 |
Любые вещественные числа. Просто, если числа не целые, их придётся округлять до предела точности иначе рзультат может быть неопределённым.
SlavaSSU согласен со статьёй в Вики. Спасибо за ссылочку.
0
|
236 / 196 / 21
Регистрация: 04.06.2014
Сообщений: 1,309
|
|
12.11.2014, 17:03 | 14 |
0
|
56 / 50 / 22
Регистрация: 17.03.2014
Сообщений: 143
|
|
12.11.2014, 17:52 | 15 |
допускает ли верхняя строка "1 8 4 2" повторяющиеся значения? скажем "1 1 4 2"
0
|
21 / 21 / 16
Регистрация: 30.09.2013
Сообщений: 262
|
||||||
14.11.2014, 21:36 [ТС] | 16 | |||||
SlavaSSU, SmittWesson, ValeryS, kaznachei67, Спасибо что откликнулись на моё сообщение. Таки нашел время зайти на форум и максимально внимательно ответить на каждое сообщение)
За неделю у меня было время подумать, и я пришел к выводу что здесь будет 10 строк железно и 4 столбца максимум (у всех курсовые имеют лишь 4 столбца). Также там могут быть отрицательные числа в строке. Все числа будут целыми. Думаю числа строки подобраны таким образом что бы данные ситуации не случались. По этому нужно будет вывести ошибку и прекратить программу. Учитывая то что числа в принципе могут быть от -9 до 9 - то варианты различных комбинаций возрастает. Спросил у преподавателя по программированию как можно реализовать такую систему, дал наводку на:
1+8+4+2 8+4+2 4+2 2 Но не прыгает через значения 1+8+4 1+8+2 1+4+2 8+2 и тд.
0
|
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
|
||||||
14.11.2014, 22:05 | 17 | |||||
Сообщение было отмечено -MaZaHaKa- как решение
Решение
-MaZaHaKa-,
1
|
14.11.2014, 22:05 | |
14.11.2014, 22:05 | |
Помогаю со студенческими работами здесь
17
перебор чисел и умножение Быстрый перебор восьмизначных чисел на С++ Как сделать перебор чисел в массиве Перебор элементов массива Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи | |||||
Какой язык программирования лучший для разработки нейронных сетей
InfoMaster 20.01.2025
В современном мире технологий искусственные нейронные сети становятся неотъемлемой частью множества инновационных решений, от распознавания речи до автоматического управления транспортными. . .
|
Как подключить JavaScript файл в другом JavaScript файле
InfoMaster 20.01.2025
В современной веб-разработке организация кодовой базы играет ключевую роль в создании масштабируемых и поддерживаемых приложений. Модульность и правильное структурирование кода стали неотъемлемыми. . .
|
Как откатить изменения в исходниках, не внесенные в Git
InfoMaster 20.01.2025
При работе с системой контроля версий Git разработчики часто сталкиваются с необходимостью отменить внесенные изменения в исходном коде. Особенно актуальной становится ситуация, когда изменения еще. . .
|
В чем разница между px, in, mm, pt, dip, dp, sp
InfoMaster 20.01.2025
В мире цифрового дизайна и разработки интерфейсов правильный выбор единиц измерения играет ключевую роль в создании качественного пользовательского опыта. История развития систем измерений для. . .
|
Как изменить адрес удалённого репозитория (origin) в Git
InfoMaster 20.01.2025
В терминологии Git термин origin является стандартным именем для основного удаленного репозитория, с которым взаимодействует локальная копия проекта. Когда разработчик клонирует репозиторий с. . .
|
Как переместить последние коммиты в новую ветку (branch) в Git
InfoMaster 20.01.2025
При работе над проектом часто возникают ситуации, когда необходимо изолировать определенные изменения от основной линии разработки. Это может быть связано с экспериментальными функциями, исправлением. . .
|
Как вернуть результат из асинхронной функции в JavaScript
InfoMaster 20.01.2025
Асинхронное программирование представляет собой фундаментальную концепцию в JavaScript, которая позволяет выполнять длительные операции без блокировки основного потока выполнения программы. В. . .
|
Какой локальный веб-сервер выбрать
InfoMaster 19.01.2025
В современной веб-разработке локальные веб-серверы играют ключевую роль, предоставляя разработчикам надежную среду для создания, тестирования и отладки веб-приложений без необходимости использования. . .
|
Почему планшеты и iPad уже не так популярны, как раньше
InfoMaster 19.01.2025
Эра революционных инноваций
История планшетов началась задолго до того, как эти устройства стали привычными спутниками нашей повседневной жизни. В начале 1990-х годов появились первые прототипы,. . .
|
Как самому прошить BIOS ноутбука
InfoMaster 19.01.2025
BIOS (Basic Input/ Output System) представляет собой важнейший компонент любого компьютера или ноутбука, который обеспечивает базовое взаимодействие между аппаратным и программным обеспечением. . .
|
Какой Linux выбрать для домашнего компьютера
InfoMaster 19.01.2025
Современные реалии выбора операционной системы
В современном мире выбор операционной системы для домашнего компьютера становится все более важным решением, которое может существенно повлиять на. . .
|
Как объединить два словаря одним выражением в Python
InfoMaster 19.01.2025
В мире программирования на Python работа со словарями является неотъемлемой частью разработки. Словари представляют собой мощный инструмент для хранения и обработки данных в формате "ключ-значение". . . .
|