21 / 21 / 16
Регистрация: 30.09.2013
Сообщений: 262
|
|
Перебор сумм чисел массива12.11.2014, 00:23. Показов 4337. Ответов 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
Полный перебор чисел массива Перебор массива и поиск повторяющихся чисел Массив из сумм чисел исходного массива |
![]() 236 / 196 / 21
Регистрация: 04.06.2014
Сообщений: 1,309
|
|
12.11.2014, 09:22 | |
Не трудно подсчитать, что комбинация сумм всех цифр исходной строки будет N! и как следствие, ограничена либо временем вычислений, либо размером оперативки. То-же относится и к количеству строк.
0
|
![]() 236 / 196 / 21
Регистрация: 04.06.2014
Сообщений: 1,309
|
|
12.11.2014, 12:21 | |
Да-да. Точно. Спутал с полной перестановкой позиций цифр.
В таком случае, берём очередную цифру и прогоняем её через двоичное представление количества цифр в строке - 1 т.к. комбинация 0000 не имеет смысла.
0
|
Модератор
![]() 8962 / 6728 / 921
Регистрация: 14.02.2011
Сообщений: 23,752
|
|
12.11.2014, 12:58 | |
0
|
![]() 236 / 196 / 21
Регистрация: 04.06.2014
Сообщений: 1,309
|
|
12.11.2014, 12:59 | |
Вы сами себе противоречите. Не за n * 2^m, а за 2^m-1. Согласен, можно несколько ускорить, если в исходной строке имеются нули. Исключаем все двоичные комбинации совпадающие с суммированием нулей.
Например, для строки 5 0 6 0 исключить можно комбинации:0101, 0100, 0001 ну и само-собой - 0000.
0
|
![]() 236 / 196 / 21
Регистрация: 04.06.2014
Сообщений: 1,309
|
|
12.11.2014, 13:05 | |
n - то откуда взялась? Строки добавляются по мере совпадения сумм чисел и вначале итераций не определены. Или Вы имеете в виду постоянную алгоритма?
А вот на счёт "другим способом", можно ли поподробней?
0
|
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
|
|
12.11.2014, 13:12 | |
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 | |
Любые вещественные числа. Просто, если числа не целые, их придётся округлять до предела точности иначе рзультат может быть неопределённым.
SlavaSSU согласен со статьёй в Вики. Спасибо за ссылочку.
0
|
Модератор
![]() 8962 / 6728 / 921
Регистрация: 14.02.2011
Сообщений: 23,752
|
|
12.11.2014, 14:15 | |
тогда возможен вариант что число не представится суммой по количеству равной 1
например 1 3 7 9 тогда как представить число 2? комбинация два раза 1?? т.е 2 0 0 0 ???
0
|
21 / 21 / 16
Регистрация: 30.09.2013
Сообщений: 262
|
||||||
14.11.2014, 21:36 [ТС] | ||||||
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 | ||||||
![]() Решение
-MaZaHaKa-,
1
|
14.11.2014, 22:05 | ||||||
Помогаю со студенческими работами здесь
17
Перебор чисел перебор чисел и умножение Быстрый перебор восьмизначных чисел на С++ Как сделать перебор чисел в массиве Перебор элементов массива Искать еще темы с ответами Или воспользуйтесь поиском по форуму:
|
|
Новые блоги и статьи
![]() |
||||
Списки и кортежи в Python: различия, особенности, применение
py-thonny 13.04.2025
Python славится своей гибкостью при работе с данными. В арсенале языка есть две основные последовательные структуры данных, которые программисты используют ежедневно — списки и кортежи. Эти структуры. . .
|
Middleware в ASP.NET Core
UnmanagedCoder 13.04.2025
В ASP. NET Core термин "middleware" занимает особое место. Что же это такое? Middleware представляет собой программные компоненты, которые формируют конвейер обработки HTTP-запросов в приложении. . . .
|
Таблицы лута в Unity с MinMaxCurve и AnimationCurve
GameUnited 12.04.2025
Создание сбалансированного лута в играх — задача не из простых. Разработчики постоянно ищут способы настройки систем выпадения предметов, которые будут одновременно справедливыми для игроков и. . .
|
std::expected в C++: Управление ошибками
bytestream 12.04.2025
Обработка ошибок всегда была важной и одновременно сложной задачей в программировании на C++. На протяжении долгого времени разработчики использовали различные подходы: возвращаемые коды ошибок,. . .
|
Nullable типы и операторы объединения null в C#
UnmanagedCoder 12.04.2025
Многие шутят, что null — это миллиардная ошибка в программировании. И в этой шутке только доля шутки. Тони Хоар, создатель null-ссылки, сам назвал её своей "ошибкой на миллиард долларов". Почему?. . .
|
Аутентификация и авторизация JWT в микросервисах с API Gateway
stackOverflow 12.04.2025
В традиционных монолитных приложениях безопасность часто реализуется как единый защитный периметр - пользователь проходит аутентификацию один раз, после чего получает доступ ко всем функциям системы. . . .
|
TypeScript: Интерфейсы vs Типы
run.dev 11.04.2025
Современная разработка на JavaScript сталкивается с множеством проблем при масштабировании проектов. Типизация кода стала хорошим инструментом, помогающим избежать ошибок во время выполнения,. . .
|
Управление топиками и разделами Kafka
Javaican 11.04.2025
Apache Kafka — распределенная платформа потоковой передачи данных, которая стала стандартом для построения высоконагруженных систем обмена сообщениями. В современной архитектуре микросервисов,. . .
|
Миграция монолита в Event-Driven микросервисную архитектуру на C#
stackOverflow 11.04.2025
Монолитная архитектура – классический подход к разработке программного обеспечения. Это приложение, построенное как единое целое, где все компоненты тесно связаны между собой. Большинство проектов. . .
|
Go в Kubernetes: Управление ресурсами
golander 11.04.2025
Разработчики Go-приложений в Kubernetes часто сталкиваются с неожиданными проблемами производительности и даже внезапными отказами контейнеров. Причина этого кроется в особенностях взаимодействия. . .
|