Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[13.58.185.199] |
|
Сообщ.
#1
,
|
|||||||||||||
|
Всем хай! Сходу к делу!
Есть такая задачка: Иван-дурак бьется с многоголовой гидрой (N - число голов, N <= 100K). Иван головы отрубает так: если у гидры четное число голов - он отрубает 9 голов, а если нечетное - 11 голов одним ударом. После каждого удара, если у гидры осталась не срубленной хотя бы одна голова, то отрастает еще 8 новых голов. Гидра побеждена, если после очередного удара мечом у нее не осталось ни одной головы. Нужно вычислить, сколько ударов мечом потребуется Ивану для победы, а также, сколько совокупно голов он срубит в течение сражения. Разумеется, задача простецкая и легко кодируется, правда, думал, что будет еще проще, т к какую-то сложность добавила проверка последнего удара мечом(многовато if-ов получилось). int main(void) { const unsigned short HEAD_CHOP_9 = 9; const unsigned short HEAD_CHOP_11 = 11; const unsigned short HEAD_GROW = 8; int N; // число голов у чудовища unsigned int countChops = 0; // кол-во отрубаний unsigned int countChopHeads = 0; // кол-во отрубленных голов cin >> N; // пока не все головы срублены у змия while(N > 0) { if(N % 2 == 0) // четное кол-во голов { if(N < HEAD_CHOP_9) // происходит последнее отрубание (голов может быть меньше 9) countChopHeads = countChopHeads + N; else countChopHeads = countChopHeads + HEAD_CHOP_9; N = N - HEAD_CHOP_9; } else // нечетное кол-во голов { if(N < HEAD_CHOP_11) // происходит последнее отрубание (голов может быть меньше 11) countChopHeads = countChopHeads + N; else countChopHeads = countChopHeads + HEAD_CHOP_11; N = N - HEAD_CHOP_11; } countChops++; // если головы остались, то дополнительно еще отрастают 8 штук if(N > 0) N = N + HEAD_GROW; } cout << endl << countChops << "\t" << countChopHeads << endl; fflush(stdin); cin.get(); return 0; } но задачу эту нужно решить с ПОМОЩЬЮ МЕТОДА ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ хм... опр. Динам.программирование - метод решения задачи путем ее разбиения на несколько однотипно решаемых подзадач, рекуррентно связанных между собой. Как я понимаю, ключевое слово в этом определении - рекуррентно. опр. Рекуррентая формула - формула, которая позволяет текущий член некоторой последовательности выразить через какое-то кол-во предыдущих членов этой же последовательности. Для применения динам.программирования нужно иметь: 1. рекуррентную зависимость элементов динамики 2. значение начальных состояний 3. элементарный случай (конец всех вычислений) Применительно к поставленной задаче. 1. Не будем применять никакие рекурсии 2. Будем использовать одномерный массив для запоминания всех вычислений (этот массив будет выражать нужную нам последовательность, элементы которой связаны рекуррентно).
Какая тут рекуррентность? Получается такая: 1. a[i] = a[i - 1] - 9, если N - четное 2. a[i] = a[i - 1] - 11, если N - нечетное 3. a[i] = 0, если N - четное И N < 9 4. a[i] = 0, если N - нечетное И N < 11 хотя №3 и №4 не чисто какие-то рекуррентные вроде... также немного смущает, что во всех 4-рех зависимостях нужно обращаться к N (текущее кол-во голов гидры) Какие минусы такого подхода (с массивом): 1. требуется использовать доп.память 2. выводить рекуррентные соотношения (в данной задаче они вроде простые, а иногда они абсолютно не очевидны) 3. нет мемоизации вычислений, т к любое промежуточное вычисление используется лишь ОДНАЖДЫ 4. нет упрощения кодирования по сравнению с простым циклом без всяких рекуррентностей Плюсы: 1. ВАЖНЕЙШИЙ ПЛЮС: можно получить информацию промежуточную, например, сколько голов было у гидры на 5, 7, 23 ударе (эту информацию можно запросить ПОСЛЕ окончания всех вычислений) других плюсов вроде нет )) (плюсом могла быть мемоизация, но здесь ее вроде нет..) вопрос: правильно ли я составил алгоритм решения поставленной задачи методом динам.программирования?? подскажите как быть-то... |
Сообщ.
#2
,
|
|
|
Цитата FasterHarder @ азумеется, задача простецкая и легко кодируется, правда, думал, что будет еще проще, т к какую-то сложность добавила проверка последнего удара мечом(многовато if-ов получилось). Ты просто через одно место решал #include <iostream> #include <algorithm> int main() { int n = 42; int heads = 0, chops = 0; while(1) { int delta; if (n % 2 == 0) delta = 9; else delta = 11; delta = std::min(delta, n); n -= delta; chops += 1; heads += delta; if(n > 0) n += 8; else break; } std::cout << chops << " " << heads; } Не говоря уже о том, что тут в общем-то элементарно выводится прямая формула (достаточно заметить, что если n велико, то два взмаха уменьшат число голов ровно на 4) и, соответственно, задача решается вообще без циклов. |
Сообщ.
#3
,
|
|
|
OpenGL, а я ведь специально выделяю красненьким вопрос, для таких как ты, чтобы было понятно, что же хочет ТС...
за код тебе спс, правда он мне не нужен, в нем нет ничего такого, что мне пригодилось бы...)) |
Сообщ.
#4
,
|
|
|
Да вопрос в принципе странный просто. Ты бы ещё суффиксные деревья или тернарный поиск приплёл сюда. Они ровно так же в тему будут при решении этой задачи.
|
Сообщ.
#5
,
|
|
|
Кстати, действительно. Для конкретно этой задачи динамическое программирование чуть ли не худший способ решения.
Вообще, эта задача лучше всего решается прямой формулой. А если прямая формула не подходит (эта задача всего лишь модель другой задачи с более сложными зависимостями), проще и быстрее просто промоделировать процесс рубки голов. |