Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.62/13: Рейтинг темы: голосов - 13, средняя оценка - 4.62
3 / 3 / 0
Регистрация: 07.01.2017
Сообщений: 101
1

Рекурсия. Рекурсия с мемоизацией

08.06.2019, 09:53. Показов 2354. Ответов 25
Метки нет (Все метки)

Добрый день. Задача такова: У нас есть массив для длины строки (пусть будет M=20). У нас есть некие длины слов (колличество не важно пусть будет 50 слов, задаим длины, как значение "j", ну а сами слова пусть будут "i"). Смысл в том, что заполнить словами строки + с учетом пробела + еще штрафы (штрафы - место оставшееся в строке куда не влезло слово и перенесли на след. строку). С этим всё более менее понятно. Но вот тут, момент который мне не понятен следкует. Дойдя до последней строчки, мы получим последний страф, как мне сказали, его для рекурсии, нужно возвести в куб (^3) и пустить на подсчет выше по строкам, мол далее он сам всё сделает, все подсчеты "нужно довериться". Я НЕ ПОНИМАЮ! Как это и зачем, и как это сделать! Говорили, что нужно два цикла, один (внешний) на подсчет всех слов зачем-то, а второй (внутренний) , как я понял должен выполнять (что-то) и условие на пока не >0. Это рекурсия. И я не привык к такому ужасу, не могу понять. Помогите пожалста, а то уже голову сломал. Главное с рекурсией разобраться, а мемоизация, как я понял - это тоже самое, только с сохранением значений пройденный путей.

Добавлено через 8 минут
Ну и да, в куб мы возводим штраф для большей ясности, как я понял.
Вся суть в том, что не понятна работа и смысл рекурсии, как бы не разбирался. Но всё крутится вокруг 2 циклов и доверия к выполнению на других строках.
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.06.2019, 09:53
Ответы с готовыми решениями:

Рекурсия с мемоизацией...треугольник
Пути в числовом треугольнике начинаются от верхнего числа. От любого числа можно перейти к одному...

Рекурсия
Не совсем разобрался с заданиями помогите!

Рекурсия
Мне нужно что бы в рекурсии делал от большого на маленький. Вот сам код: #include <iostream> ...

Рекурсия
Кто знает как написать программу на C ++, которая рекурсивно генерирует следующий времена этой...

25
99 / 80 / 76
Регистрация: 11.05.2015
Сообщений: 193
08.06.2019, 11:34 2
Не очень понятно задание. Правильно я понимаю, что имеется множество строк длины M и необходимо заполнить их словами так, чтобы было как можно меньше штрафов (пустых мест в конце строки). Кроме того так и не понял для чего возводить что-то в куб. Что в итоге программа на выходе должна выводить?
0
3 / 3 / 0
Регистрация: 07.01.2017
Сообщений: 101
08.06.2019, 13:12  [ТС] 3
Цитата Сообщение от ivan37 Посмотреть сообщение
Не очень понятно задание.
поверьте, мне тоже не особо понятно. Да, надо наиболее выгодно распределить слова. В куб возводим, как я понял, для большей наглядности при получении результата. Но вся суть состоит в том, что когда мы доходим до конечой строки...,за чем-то нужно выполнять рекурсию с конечной строчки и до начальной. Если чесн, смысла не вижу в этом обсалютно. Но наверное это что то типо проверки нашего решения. Мол надо выполнить расчет через ^3 штрафа последней строки, а дальше просто пустить пример подсчета, и довериться. Дабы он всё сам правильно сделает. И такое же с РсМ, но там мы будем, как я понял, просто сохранять результаты этой "проверки". Не могу сделать, потому что: 1) не понимаю смысла зачем это надо вообще. 2) не понял, как это проклятие выполняется. 3) нет примеров выполнения подобного задания.
0
Комп_Оратор)
Эксперт по математике/физике
8719 / 4428 / 598
Регистрация: 04.12.2011
Сообщений: 13,276
Записей в блоге: 16
08.06.2019, 15:04 4
Цитата Сообщение от Nik Golor Посмотреть сообщение
поверьте, мне тоже не особо понятно
Но с чего вы взяли, что непонятное, пересказанное своими словами, станет роднее кому-то из читающих. Приведите текст условия дословно.
1
3 / 3 / 0
Регистрация: 07.01.2017
Сообщений: 101
08.06.2019, 18:43  [ТС] 5
IGPIGP, провести динамическое заполнениес строк фиксированной длинны, словами из массива. Провести операции рекурсии и рекурсии с мемоизацией. (более подробно я расписал то, как объясняли мне выполнять это. но вот хоть убейте, не вижу смысла в этом и не пойму, как выполнять).
0
Комп_Оратор)
Эксперт по математике/физике
8719 / 4428 / 598
Регистрация: 04.12.2011
Сообщений: 13,276
Записей в блоге: 16
08.06.2019, 20:16 6
Цитата Сообщение от Nik Golor Посмотреть сообщение
провести динамическое заполнение строк фиксированной длинны
Динамическое заполнение, это видимо противоположность статическому заполнению. Всё бы ни чего, но я понятия не имею о чём тут речь. Если тут говорится о том, что нельзя использовать c-строковые литералы, то ваши преподаватели большие затейники.
Цитата Сообщение от Nik Golor Посмотреть сообщение
Провести операции рекурсии и рекурсии с мемоизацией.
Тут не шибко понятно о чём речь. Я бы предположил, что мемоизационная таблица (хранилище полученных решений), это сама строка массива, содержащая уже имеющееся слово. Однако при чём тут рекурсия? Я не мастак в динамическом программировании и вряд ли скажу тут что-либо ценное. Но думаю, если вы кратко изложите то, что вам сообщили на лекциях по данному вопросу, то это поможет тем, кто смог бы ответить.
0
3 / 3 / 0
Регистрация: 07.01.2017
Сообщений: 101
08.06.2019, 20:35  [ТС] 7
можно использовать всё, что угодно. но с применением 2-х циклов. и работая со штрафами (место осталось свободным в строке). сама суть, что штрафы возводятся в ^3 и надо вычисление делать только с последней строкой, а дальше всё по примеру пускать, мол само сделает. В том то и дело, что это максимум информации, что нам давали. Было бы с кем поговорить, дак даже те кто сдали не знают как делать, ибо сдавали методом "чаще хожу, надоем, поставят" , а мне так не годится.

Добавлено через 1 минуту
IGPIGP, что с образованием творится капец, ладно бы как всегда ничего не дали "знаний" прогуглил и научился сам. А тут в сети роюсь уже неделю, и не малейшей зацепки и примера. А они требуют. PS: Страна самообразования.
0
3247 / 2049 / 351
Регистрация: 24.11.2012
Сообщений: 4,902
08.06.2019, 22:01 8
По обрывочному описанию кажется, что нужно решить задачу расстановки переносов в тексте методом динамического программирования. Готовое решение: https://www.geeksforgeeks.org/... lem-dp-19/. Может отличаться от ожидаемого, но подойдет как точка входа для поиска решения.
1
3 / 3 / 0
Регистрация: 07.01.2017
Сообщений: 101
08.06.2019, 22:07  [ТС] 9
Добавлено через 21 секунду
0x10, сам перенос и распределение слов в сроки - это ясное дело, я писал, что не проблема. А вот именно расчет с последней строчки штрафа и шага вверх "не контролируемого", вот это не понятно вообще.
0
3 / 3 / 0
Регистрация: 07.01.2017
Сообщений: 101
09.06.2019, 08:59  [ТС] 10
Вообще, понятие такое. Программа работает как Microsoft Word документ - это ясно-понятно. Но вот сама рекурсия и РсМ, вот эта часть программы меня в замешательство погружает.
0
Комп_Оратор)
Эксперт по математике/физике
8719 / 4428 / 598
Регистрация: 04.12.2011
Сообщений: 13,276
Записей в блоге: 16
09.06.2019, 10:30 11
Цитата Сообщение от Nik Golor Посмотреть сообщение
РсМ
если русскими символами то это российский союз молодежи, а если английскими, то это возможно импульсно-кодовая модуляция. Даже в такой малости ребус.
Nik Golor, если ваши преподаватели говорят вам нечто вроде: "НдлсмддбтпыфолоС но смотрите не вшпо дфшаыывпдрот!!!", это значит, что либо они идиоты, либо вы должны понять о чём речь исходя из пройденного материала. Но глядя на ваш вопрос, трудно сказать в чём тут дело. Сферический конь в вакууме конфликтует с кубическим штрафом PcM. Рекурсивно, причем.
Пока не ощущаю ни чего кроме сочувствия.
0
3 / 3 / 0
Регистрация: 07.01.2017
Сообщений: 101
10.06.2019, 07:27  [ТС] 12
IGPIGP, Рекурсия - Р. Рекурсия с мемоизацией - РсМ. А преподаватели придумывают с головы всё, не задумываясь, что нам это искать потом (но надо знать, что искать. и было бы что искать).
0
Комп_Оратор)
Эксперт по математике/физике
8719 / 4428 / 598
Регистрация: 04.12.2011
Сообщений: 13,276
Записей в блоге: 16
10.06.2019, 09:37 13
Цитата Сообщение от Nik Golor Посмотреть сообщение
Рекурсия с мемоизацией - РсМ.
А почему ни кто Гугл об этом не знает? Ваши преподы придумали? Дело в том что россоюз молодёжи плачет. В формате PCM. Ни чем не сжатом и 24-х битном. Горючими сэмплАми.
1
3 / 3 / 0
Регистрация: 07.01.2017
Сообщений: 101
10.06.2019, 09:44  [ТС] 14
IGPIGP, да уже вариантов не осталось, очень долго пытаюсь сделать всё это дело..., а кончается всё фразой "это не то, что мы хотим". Ну я уже не знаю, что делать если честно. По ходу из за одного долга с этим заданием придется отчисляться. Обидно очень, уже почти отучился.
0
Комп_Оратор)
Эксперт по математике/физике
8719 / 4428 / 598
Регистрация: 04.12.2011
Сообщений: 13,276
Записей в блоге: 16
10.06.2019, 09:59 15
Цитата Сообщение от Nik Golor Посмотреть сообщение
По ходу из за одного долга с этим заданием придется отчисляться. Обидно очень, уже почти отучился.
Цитата Сообщение от Nik Golor Посмотреть сообщение
А вот именно расчет с последней строчки штрафа и шага вверх "не контролируемого", вот это не понятно вообще.
Мне тоже не понятно. В ссылке от 0x10, вроде показано, как сохраняется уже выполненный расчёт. Может попробовать сделать так же? Или пойти к преподавателю и объяснить почему вас не было на соответствующем занятии?
Алгоритм контроля распределения интересный, кстати.
0
3 / 3 / 0
Регистрация: 07.01.2017
Сообщений: 101
10.06.2019, 10:44  [ТС] 16
IGPIGP, я попробую сделать еще вариантов 5 выполнения, и принети в ближайшее время. Может хоть одно утсроит их. Но предчувствую очередное "Это не то, что я хочу"
0
Комп_Оратор)
Эксперт по математике/физике
8719 / 4428 / 598
Регистрация: 04.12.2011
Сообщений: 13,276
Записей в блоге: 16
10.06.2019, 10:56 17
Цитата Сообщение от Nik Golor Посмотреть сообщение
Но предчувствую очередное "Это не то, что я хочу"
Узнайте, что они хотят. Если есть героическое прошлое отношений с кем-то из "них" - постарайтесь сделать так, чтобы "они" забыли. Для остальных случаев есть варианты. Быстро но дорого или как крайность, взять учебный план, свой вариант выполнения, который соответствует, но "не такой". И устроить разборку. В любом разе, нанимать киллера для препода рановато (имхо). Да и дороговато, если не найдётся количества желающих поучаствовать материально, в складчину.
0
3 / 3 / 0
Регистрация: 07.01.2017
Сообщений: 101
10.06.2019, 11:04  [ТС] 18
IGPIGP, да что уж, буду думать еще. Выбор не велик уже. Подходил, спрашивал, но бормочат постоянно одно и то же. Придумаю что-нибудь, не в первой.
0
Комп_Оратор)
Эксперт по математике/физике
8719 / 4428 / 598
Регистрация: 04.12.2011
Сообщений: 13,276
Записей в блоге: 16
10.06.2019, 11:10 19
Удачи.
0
3 / 3 / 0
Регистрация: 07.01.2017
Сообщений: 101
12.06.2019, 06:17  [ТС] 20
IGPIGP, в общем, препод не захотел принемать. Сказал приходить 13-ого. Ладно, опытаюсь еще что-то придумать до завтра, может получится угодить наконец-то.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.06.2019, 06:17

Рекурсия
Помогите с лабой!!! Нужен код Спасибо заранее

Рекурсия
Помогите написать функцию которая будет считать эту рекуррентную формулу с помощью рекурсии

рекурсия в С++
Изучаю использование рекурсивной функции в С++. Правильно ли я понял: - что нет ограничений в max...

Рекурсия
Помогите с рекурсией


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.