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

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

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

0

Не очень понятно задание. Правильно я понимаю, что имеется множество строк длины M и необходимо заполнить их словами так, чтобы было как можно меньше штрафов (пустых мест в конце строки). Кроме того так и не понял для чего возводить что-то в куб. Что в итоге программа на выходе должна выводить?

0

Сообщение от ivan37 Не очень понятно задание.

поверьте, мне тоже не особо понятно. Да, надо наиболее выгодно распределить слова. В куб возводим, как я понял, для большей наглядности при получении результата. Но вся суть состоит в том, что когда мы доходим до конечой строки...,за чем-то нужно выполнять рекурсию с конечной строчки и до начальной. Если чесн, смысла не вижу в этом обсалютно. Но наверное это что то типо проверки нашего решения. Мол надо выполнить расчет через ^3 штрафа последней строки, а дальше просто пустить пример подсчета, и довериться. Дабы он всё сам правильно сделает. И такое же с РсМ, но там мы будем, как я понял, просто сохранять результаты этой "проверки". Не могу сделать, потому что: 1) не понимаю смысла зачем это надо вообще. 2) не понял, как это проклятие выполняется. 3) нет примеров выполнения подобного задания.

0

Сообщение от Nik Golor поверьте, мне тоже не особо понятно

Но с чего вы взяли, что непонятное, пересказанное своими словами, станет роднее кому-то из читающих. Приведите текст условия дословно.

1

IGPIGP, провести динамическое заполнениес строк фиксированной длинны, словами из массива. Провести операции рекурсии и рекурсии с мемоизацией. (более подробно я расписал то, как объясняли мне выполнять это. но вот хоть убейте, не вижу смысла в этом и не пойму, как выполнять).

0

Сообщение от Nik Golor провести динамическое заполнение строк фиксированной длинны

Динамическое заполнение, это видимо противоположность статическому заполнению. Всё бы ни чего, но я понятия не имею о чём тут речь. Если тут говорится о том, что нельзя использовать c-строковые литералы, то ваши преподаватели большие затейники.

Сообщение от Nik Golor Провести операции рекурсии и рекурсии с мемоизацией.

Тут не шибко понятно о чём речь. Я бы предположил, что мемоизационная таблица (хранилище полученных решений), это сама строка массива, содержащая уже имеющееся слово. Однако при чём тут рекурсия? Я не мастак в динамическом программировании и вряд ли скажу тут что-либо ценное. Но думаю, если вы кратко изложите то, что вам сообщили на лекциях по данному вопросу, то это поможет тем, кто смог бы ответить.

0

можно использовать всё, что угодно. но с применением 2-х циклов. и работая со штрафами (место осталось свободным в строке). сама суть, что штрафы возводятся в ^3 и надо вычисление делать только с последней строкой, а дальше всё по примеру пускать, мол само сделает. В том то и дело, что это максимум информации, что нам давали. Было бы с кем поговорить, дак даже те кто сдали не знают как делать, ибо сдавали методом "чаще хожу, надоем, поставят" , а мне так не годится.

Добавлено через 1 минуту
IGPIGP, что с образованием творится капец, ладно бы как всегда ничего не дали "знаний" прогуглил и научился сам. А тут в сети роюсь уже неделю, и не малейшей зацепки и примера. А они требуют. PS: Страна самообразования.

0

По обрывочному описанию кажется, что нужно решить задачу расстановки переносов в тексте методом динамического программирования. Готовое решение: https://www.geeksforgeeks.org/... lem-dp-19/. Может отличаться от ожидаемого, но подойдет как точка входа для поиска решения.

1

Добавлено через 21 секунду
0x10, сам перенос и распределение слов в сроки - это ясное дело, я писал, что не проблема. А вот именно расчет с последней строчки штрафа и шага вверх "не контролируемого", вот это не понятно вообще.

0

Вообще, понятие такое. Программа работает как Microsoft Word документ - это ясно-понятно. Но вот сама рекурсия и РсМ, вот эта часть программы меня в замешательство погружает.

0

Сообщение от Nik Golor РсМ

если русскими символами то это российский союз молодежи, а если английскими, то это возможно импульсно-кодовая модуляция. Даже в такой малости ребус.
Nik Golor, если ваши преподаватели говорят вам нечто вроде: "НдлсмддбтпыфолоС но смотрите не вшпо дфшаыывпдрот!!!", это значит, что либо они идиоты, либо вы должны понять о чём речь исходя из пройденного материала. Но глядя на ваш вопрос, трудно сказать в чём тут дело. Сферический конь в вакууме конфликтует с кубическим штрафом PcM. Рекурсивно, причем.
Пока не ощущаю ни чего кроме сочувствия.

0

IGPIGP, Рекурсия - Р. Рекурсия с мемоизацией - РсМ. А преподаватели придумывают с головы всё, не задумываясь, что нам это искать потом (но надо знать, что искать. и было бы что искать).

0

Сообщение от Nik Golor Рекурсия с мемоизацией - РсМ.

А почему ни кто Гугл об этом не знает? Ваши преподы придумали? Дело в том что россоюз молодёжи плачет. В формате PCM. Ни чем не сжатом и 24-х битном. Горючими сэмплАми.

1

IGPIGP, да уже вариантов не осталось, очень долго пытаюсь сделать всё это дело..., а кончается всё фразой "это не то, что мы хотим". Ну я уже не знаю, что делать если честно. По ходу из за одного долга с этим заданием придется отчисляться. Обидно очень, уже почти отучился.

0

Сообщение от Nik Golor По ходу из за одного долга с этим заданием придется отчисляться. Обидно очень, уже почти отучился.

Сообщение от Nik Golor А вот именно расчет с последней строчки штрафа и шага вверх "не контролируемого", вот это не понятно вообще.

Мне тоже не понятно. В ссылке от 0x10, вроде показано, как сохраняется уже выполненный расчёт. Может попробовать сделать так же? Или пойти к преподавателю и объяснить почему вас не было на соответствующем занятии?
Алгоритм контроля распределения интересный, кстати.

0

IGPIGP, я попробую сделать еще вариантов 5 выполнения, и принети в ближайшее время. Может хоть одно утсроит их. Но предчувствую очередное "Это не то, что я хочу"

0

Сообщение от Nik Golor Но предчувствую очередное "Это не то, что я хочу"

Узнайте, что они хотят. Если есть героическое прошлое отношений с кем-то из "них" - постарайтесь сделать так, чтобы "они" забыли. Для остальных случаев есть варианты. Быстро но дорого или как крайность, взять учебный план, свой вариант выполнения, который соответствует, но "не такой". И устроить разборку. В любом разе, нанимать киллера для препода рановато (имхо). Да и дороговато, если не найдётся количества желающих поучаствовать материально, в складчину.

0

IGPIGP, да что уж, буду думать еще. Выбор не велик уже. Подходил, спрашивал, но бормочат постоянно одно и то же. Придумаю что-нибудь, не в первой.

0

Удачи.

0

IGPIGP, в общем, препод не захотел принемать. Сказал приходить 13-ого. Ладно, опытаюсь еще что-то придумать до завтра, может получится угодить наконец-то.

0