1 / 1 / 0
Регистрация: 03.06.2013
Сообщений: 89
|
|||||||||||
1 | |||||||||||
Разложение числа на неповторяющиеся слагаемые16.12.2014, 23:08. Показов 5899. Ответов 7
Метки нет (Все метки)
Собственно, задача сказана. Вот код для количества:
0
|
16.12.2014, 23:08 | |
Ответы с готовыми решениями:
7
Разложение числа на слагаемые Разложение числа на слагаемые Разложение числа на слагаемые Разложение числа на слагаемые. |
1911 / 773 / 108
Регистрация: 01.10.2012
Сообщений: 4,197
|
|
18.12.2014, 11:21 | 2 |
Что хотите разобраться хорошо, но по коду (тем более без всяких примечаний) это непросто.
В стеке содержатся пары, у каждой first - текущая сумма, и second - последнее слагаемое. Как только это (структура данных) ясна, дальше все проще. Пока сумма меньше заданной - просто добавляем новую пару, second растет на 1 и сумма соответственно. Сумма равна заданной - фиксируем рез-т (count++). Переход к след варианту - последнее удаляем (pop), а предпоследнее как бы "забываем", наращивая последнюю пару. Напр слагаемые были 1, 2, 3. 4, стали 1, 2, 4, т.е. опять пытаемся но уже без тройки.
0
|
834 / 642 / 101
Регистрация: 20.08.2013
Сообщений: 2,524
|
|
18.12.2014, 12:55 | 3 |
Чего бы просто рекурсию с ленивой динамикой не сделать?
Добавлено через 16 секунд И что выводится-то?
0
|
1 / 1 / 0
Регистрация: 03.06.2013
Сообщений: 89
|
|
18.12.2014, 19:54 [ТС] | 4 |
Как? Рекурсию понятно, куда пихать ленивку? И как это вообще должно выглядеть?
количество комбинаций и сами комбинации. Спасибо. А Асимптотика тут какая? Я затрудняюсь с ее подсчетом. Уж как-то слишком странно. Добавлено через 5 минут Извините, до ленивки с рекурсией допер. Код предоставите? Добавлено через 7 минут Нет, не предоставляйте. Я сам выложу, хочу поломаться. С асимптотикой лучше помогите, у меня проблемы с ее подсчетом. Там квадрат чтоль получается?
0
|
834 / 642 / 101
Регистрация: 20.08.2013
Сообщений: 2,524
|
|
18.12.2014, 20:48 | 5 |
Ассимптотика посчсёта числа комбинаций - квадрат или куб - до меня сейчас дошло, что то, про что я думал изначально, немнонго неверно. Тем не менее, идея с ленивой данамикой, либо с динамикой с обновлением впрерёд (надо понять, какая в данном случае удобнее) остаётся в силе. На вскидку приходит в голову кубический вариант (квадрат состояний и n переходов), но есть стойкое подозрение, что эта оценка неверна, либо алгоритм может быть оптимизирован.
Что касается вывода всех комбинаций - если он действительно нужен, то имеет смысл просто делать перебор и с динамикой не муддрить. Т. е. обычный рекурсивный алгоритм, который выводит всё что требуется и считает количество.
0
|
1911 / 773 / 108
Регистрация: 01.10.2012
Сообщений: 4,197
|
|
19.12.2014, 09:47 | 6 |
Так он фактически и предъявлен, только рекурсия заменена стеком, что более грамотно. Технически было проще использовать std::vector (вместо std::stack), тогда не пришлось бы городить 2 варианта.
2Qwertiy Ваши любознательность/упорство "заслуживают лучшего применения". Но увидев задачу посерьезнее - Вы убегаете
0
|
834 / 642 / 101
Регистрация: 20.08.2013
Сообщений: 2,524
|
||||||
19.12.2014, 23:18 | 7 | |||||
Я всё ещё тут
А код не читал, что должно ясно следовать из вопроса "И что выводится-то?" Добавлено через 12 часов 55 минут Вот код (ассимптотика - куб):
Код
1 1 2 1 3 2 4 2 5 3 6 4 7 5 8 6 9 8 10 10 11 12 12 15 13 18 14 22 15 27 16 32 17 38 18 46 19 54 20 64 21 76 22 89 23 104 24 122 25 142 26 165 27 192 28 222 29 256 30 296 31 340 32 390 33 448 34 512 35 585 36 668 37 760 38 864 39 982 40 1113 41 1260 42 1426 43 1610 44 1816 45 2048 46 2304 47 2590 48 2910 49 3264 50 3658 51 4097 52 4582 53 5120 54 5718 55 6378 56 7108 57 7917 58 8808 59 9792 60 10880 61 12076 62 13394 63 14848 64 16444 65 18200 66 20132 67 22250 68 24576 69 27130 70 29927 71 32992 72 36352 73 40026 74 44046 75 48446 76 53250 77 58499 78 64234 79 70488 80 77312 81 84756 82 92864 83 101698 84 111322 85 121792 86 133184 87 145578 88 159046 89 173682 90 189586 91 206848 92 225585 93 245920 94 267968 95 291874 96 317788 97 345856 98 376256 99 409174 100 444793 101 483330 102 525016 103 570078 104 618784 105 671418 106 728260 107 789640 108 855906 109 927406 110 1004544 111 1087744 112 1177438 113 1274118 114 1378304 115 1490528 116 1611388 117 1741521 118 1881578 119 2032290 120 2194432 121 2368800 122 2556284 123 2757826 124 2974400 125 3207086 126 3457027 127 3725410 128 4013544
0
|
1911 / 773 / 108
Регистрация: 01.10.2012
Сообщений: 4,197
|
|
20.12.2014, 08:38 | 8 |
Вы поняли с точностью до наоборот Ну зачем Вы тратите время/силы на очередную комбинаторную задачу? Конечно дело Ваше, но ведь ясно что дальше олимпиады это никуда не пойдет, чисто "зарядка для хвоста". А ведь есть задачи где Ваше умение было бы куда больше к месту (и совсем не безвозмездно). Но они у Вас почему-то интереса не вызывают
0
|
20.12.2014, 08:38 | |
20.12.2014, 08:38 | |
Помогаю со студенческими работами здесь
8
Разложение числа на слагаемые [рекурсия] Разложение натурального числа на слагаемые Разложение натурального положительного числа на слагаемые? НЕ Рекурсивное разложение числа на слагаемые. Алгоритм Эрлиха Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Блоги программистов | |||||
Обновление сайта www.historian.by
Reglage 05.01.2025
Обещал подвести итоги 2024 года для сайта. Однако начну с того, что изменилось за неделю. Добавил краткий урок по последовательности действий при анализе вредоносных файлов и значительно улучшил урок. . .
|
Как использовать GraphQL в C# с HotChocolate
Programming 05.01.2025
GraphQL — это современный подход к разработке API, который позволяет клиентам запрашивать только те данные, которые им необходимы. Это делает взаимодействие с API более гибким и эффективным по. . .
|
Модель полного двоичного суматора с помощью логических операций (python)
AlexSky-coder 04.01.2025
def binSum(x:list, y:list):
s=^y]
p=x and y
for i in range(1,len(x)):
s. append((x^y)^p)
p=(x and y)or(p and (x or y))
return s
x=list()
y=list()
|
Это мы не проходили, это нам не задавали...(асихронный счётчик с управляющим сигналом задержки).
Hrethgir 04.01.2025
Асинхронный счётчик на сумматорах (шестиразрядный по числу диодов на плате, но наверное разрядов будет больше - восемь или шестнадцать, а диоды на старшие), так как триггеры прошли тестирование и. . .
|
Руководство по созданию бота для Телеграм на Python
IT_Exp 04.01.2025
Боты для Телеграм представляют собой автоматизированные программы, которые выполняют различные задачи, взаимодействуя с пользователями через интерфейс мессенджера. В данной статье мы рассмотрим,. . .
|
Применение компонентов PrimeVue в Vue.js 3 на TypeScript
BasicMan 04.01.2025
Введение в PrimeVue и настройка окружения
PrimeVue представляет собой мощную библиотеку компонентов пользовательского интерфейса для Vue. js 3, которая предоставляет разработчикам богатый набор. . .
|
Как стать Senior developer
cpp_developer 04.01.2025
В современной индустрии разработки программного обеспечения позиция Senior Developer представляет собой не просто следующую ступень карьерной лестницы, а качественно новый уровень профессионального. . .
|
Что известно о дате выхода Windows 12 и чего от нее ждать
IT_Exp 04.01.2025
В мире технологий постоянно происходят изменения, и операционные системы не являются исключением. Windows 11, выпущенная в октябре 2021 года, принесла множество инноваций и улучшений, но. . .
|
Что новенького в .NET Core 9
Programming 04.01.2025
Обзор ключевых изменений в . NET Core 9
Платформа . NET Core продолжает активно развиваться, и версия 9 представляет собой значительный шаг вперед в эволюции этой технологии. Новый релиз. . .
|
Инструкция по установке python3.13.1 в Debian 12
AlexSky-coder 03.01.2025
sudo apt update
sudo apt install build-essential zlib1g-dev libncurses5-dev libgdbm-dev libnss3-dev libssl-dev libreadline-dev libffi-dev
wget. . .
|
Затестил триггеры. архив проекта прилагаю с GOA файлами в настройках архиватора проектов.
Hrethgir 03.01.2025
В этот раз нет закольцованности, потому что от неё только глюки, как я понял, логика не вырезанная. Триггеры очень быстрые если верить измерениям с помощью анализатора от Gowin.
Есть ещё регистры,. . .
|
Python в помощь DevOps
IT_Exp 03.01.2025
Причины использования Python в работе DevOps
Python стал неотъемлемой частью мира DevOps, и это не случайно. Этот язык программирования обладает множеством преимуществ, которые делают его. . .
|