Условие:
План прямоугольного сада размером mxn состоит из квадратных зон. В каждой зоне растёт по дереву. С каждого дерева любой зоны могут упасть несколько яблок.
В левом верхнем квадратике находится ёжик, который должен дойти до правого нижнего квадратика. В саду существуют ограничения относительно способа передвижения: ёжик может двигаться из текущего квадратика только в один из двух соседних правый либо нижний.
Составьте программу, которая вычисляет максимальное количество яблок, которое может собрать ёжик, передвигаясь к нужному квадратику.Технические условия:
План сада задан таблицей apples содержащей m строк и n столбиков. Элемент apples[i,j] таблицы указывает количество яблок, упавших с дерева в зону с координатами i,j.
Текстовый файл "input.txt" содержит в первой строке числа m,n разделённые пробелом. В каждой из следующих m строк содержится по n чисел apples[i,j] разделённых пробелами.
Файл "output.txt" должен содержать одно натуральное число.Примеры файлов:
Input.txt Output.txt
3 3
1 2 3
1 2 3
1 2 3 12
> Составьте программу, котораяУра, сессия началась!!! :D
вот охламон!
почему не получается инициализировать массив следующим образом:
int[][] apples = new int[4][] { { 3, 3 }, { 1, 2, 3 }, { 1, 2, 3 }, { 1, 2, 3 } };
> почему не получается инициализировать массив следующим образом:Если бы тебе сказали, "купи водки 500".
Ты б сколько купил? 500 грамм, бутылок или ящиков?
Ах да, для перевозки водки не обязательно покупать new машину.
> почему не получается инициализировать массив следующим образом:
> int[][] apples = new int[4][] { { 3, 3 }, { 1,
> 2, 3 }, { 1, 2, 3 }, { 1, 2,
> 3 } };потому, что это похрен. тут гавное алгоритм решения задачи, а не как его реализовать на данном этапе.
потому что есть стандарт в котором описаны правила объявления массива.
ты своим вопросом показал нулевые знания даже в базовых вещах.
> Условие:
> План прямоугольного сада размером mxn состоит из квадратных зон. В каждой зоне
> растёт по дереву. С каждого дерева любой зоны могут упасть несколько
> яблок.
> В левом верхнем квадратике находится ёжик, который должен дойти до правого нижнего
> квадратика. В саду существуют ограничения относительно способа передвижения: ёжик может
> двигаться из текущего квадратика только в один из двух соседних правый
> либо нижний.
> Составьте программу, которая вычисляет максимальное количество яблок, которое может собрать
> ёжик, передвигаясь к нужному квадратику.Абстрагируясь от ежиков ИМХО имеем простую работу с матрицами. Прокачайте это и потом задавайте вопросы на счет самой программы.
>[оверквотинг удален]
> Текстовый файл "input.txt" содержит в первой строке числа m,n разделённые пробелом. В
> каждой из следующих m строк содержится по n чисел apples[i,j] разделённых
> пробелами.
> Файл "output.txt" должен содержать одно натуральное число.
> Примеры файлов:
> Input.txt Output.txt
> 3 3
> 1 2 3
> 1 2 3
> 1 2 3 12Сначала две ремарки:
1. Насчет инициализации массива -- гуглите по фразе "two dimensional array initialization in c". Первые же три ссылки -- ваши. Хотя не вижу смысла инициализировать массив вручную, если все равно по условию данные заданы в файле.
2. Еще одно: не совсем понимаю, зачем здесь C++. На чистом Си решается отлично, ведь тут просто работа с массивами будет, т.е. STL особо не нужен, ООП тоже тут не нужно, т.е. от C++ никакой выгоды в данном конкретном случае, а для вас скорее еще и сложности будут дополнительные.
Теперь по существу.
Первое. Задачу за вас никто не сделает, это не фриланс. Никто забесплатно не станет писать такую программу, куча их была исписана в школах/институтах каждым из нас. Сделать вы её должны сами. Но здесь могут подсказать какие-то конкретные технические моменты, с которыми у вас не вышло разобраться.
Второе. Любая сложная задача решаема, и ключ тут -- план. С этим я могу помочь.
1. Если вы совсем не умеете на Си программировать -- читайте Кернигана и Ричи "Язык Си", 2-е издание. Проработав там все главы и упражнения, будете уметь. Сложного там ничего, лишнего тоже.
2. Вначале нужно придумать/найти алгоритм решения задачи. Наверное это будет какой-то алгоритм на взвешенном графе. Может алгоритм Дейкстры (см. на Википедии).
3. Программа. Сначала напишите функцию чтения из файла. Протестируйте с входными данными. Т.е. вычитывание из файла в массив, распечатывание считанного массива на экран.См. функции:
- fopen(), fclose()
- fprintf(), fscanf()
- malloc(), free()Есть отличный сайт-справка по функциям Си: www.cplusplus.com . С примерами использования.
Также очень удобно использовать маны по функциям стандартной библиотеки Си. Например "man fopen" (в консоли) покажет справку по функции fopen().4. Функция записи в файл. Должна создавать файл и записывать одно число. Протестируйте работу.
5. Напишите функцию, реализующую выбранный алгоритм.
6. Вызвав по очереди функции чтения из файла, алгоритма нахождения пути и функции записи в файл -- вы решите задачу.
>[оверквотинг удален]
> - fprintf(), fscanf()
> - malloc(), free()
> Есть отличный сайт-справка по функциям Си: www.cplusplus.com . С примерами использования.
> Также очень удобно использовать маны по функциям стандартной библиотеки Си. Например "man
> fopen" (в консоли) покажет справку по функции fopen().
> 4. Функция записи в файл. Должна создавать файл и записывать одно число.
> Протестируйте работу.
> 5. Напишите функцию, реализующую выбранный алгоритм.
> 6. Вызвав по очереди функции чтения из файла, алгоритма нахождения пути и
> функции записи в файл -- вы решите задачу.а вообще, в вашем случае, если нет требований к скорости алгоритму, и объем данных небольшой -- наверно проще всего использовать обычный перебор -- пройти по всем возможным путям, оставив в конце самый удачный.
> а вообще, в вашем случае, если нет требований к скорости алгоритму, и
> объем данных небольшой -- наверно проще всего использовать обычный перебор --
> пройти по всем возможным путям, оставив в конце самый удачный.Вообще - Все в сад - слушать песни ). Размер сада не определен (задается файлом конфигурации). Сделайте выборку по возможным вариантам сада хотя бы 10х10 - сколько комбинаций получится?
ИМХО из моего личного опыта такие задачи не просто так даются (особенно, когда ежики не ходят куда хотят). Так что рассчитывать на решение "перебрать все" тут не катит .. ИМХО опять же.
PS
Есть вес каждой клетки матрицы, есть ограничение связей м/ду клетками (доступные движения ежа), задача набрать max.
>[оверквотинг удален]
>> пройти по всем возможным путям, оставив в конце самый удачный.
> Вообще - Все в сад - слушать песни ). Размер сада не
> определен (задается файлом конфигурации). Сделайте выборку по возможным вариантам сада
> хотя бы 10х10 - сколько комбинаций получится?
> ИМХО из моего личного опыта такие задачи не просто так даются (особенно,
> когда ежики не ходят куда хотят). Так что рассчитывать на решение
> "перебрать все" тут не катит .. ИМХО опять же.
> PS
> Есть вес каждой клетки матрицы, есть ограничение связей м/ду клетками (доступные движения
> ежа), задача набрать max.Ок, посчитаю за вас. Количество комбинаций при n=10 и m=10 будет равно:
C_(n+m-2)_(n-1) = (n+m-2)!/((n-1)!*(n+m-2-n+1)!) = 18!/9!^2 = 48620 вариантов путей.Что для современных процессоров не так и страшно (для учебной задачи, конечно же), т.е. за 0.1 секунду на 1GHz проце выполнится даже в худшем случае. Я не спорю, что в реальной программе брутфорс не стоит делать. И тут надо понимать, чего от человека ждут.
Вообще это, насколько я понимаю, задача динамического программирования. Гуглится примерно за 30 секунд, например тут вроде неплохо всё описано: http://informatics.mccme.ru/moodle/mod/book/view.php?id=266&... . Знаю, что не стоило давать решение, но с другой стороны, who cares? Если человек хочет чему-то научиться -- он и так сам попробует сделать или хотя бы по ссылке попробует разобраться что к чему. Если нет -- то всегда есть куча других путей, как не утруждать свой мозг :) Правда выгоняют таких до 2-го курса во всех нормальных ВУЗов.
P.S. Автор, решите задачу самостоятельно, хотя бы самым простым способом. И только после этого переходите по ссылке.
>[оверквотинг удален]
>> "перебрать все" тут не катит .. ИМХО опять же.
>> PS
>> Есть вес каждой клетки матрицы, есть ограничение связей м/ду клетками (доступные движения
>> ежа), задача набрать max.
> Ок, посчитаю за вас. Количество комбинаций при n=10 и m=10 будет равно:
> C_(n+m-2)_(n-1) = (n+m-2)!/((n-1)!*(n+m-2-n+1)!) = 18!/9!^2 = 48620 вариантов путей.
> Что для современных процессоров не так и страшно (для учебной задачи, конечно
> же), т.е. за 0.1 секунду на 1GHz проце выполнится даже в
> худшем случае. Я не спорю, что в реальной программе брутфорс не
> стоит делать. И тут надо понимать, чего от человека ждут.Несколько "но":
- количество путей - это не колическтво команд для их поиска - поэтому не надо их вязать на частоту проца и делать выводы об 1-й секунде )
- при увеличении размера исходной матрицы (а такое ожидаемо - ибо по постановке задачи входные данные конфигурируются) количество операций при брут-форсе будет возрастать отнюдь не линейно.=>
Брут-форс не выход для решения этой задачи (даже на сессии). Именно это я и хотел сказать.>[оверквотинг удален]
> Вообще это, насколько я понимаю, задача динамического программирования. Гуглится примерно
> за 30 секунд, например тут вроде неплохо всё описано: http://informatics.mccme.ru/moodle/mod/book/view.php?id=266&...
> . Знаю, что не стоило давать решение, но с другой стороны,
> who cares? Если человек хочет чему-то научиться -- он и так
> сам попробует сделать или хотя бы по ссылке попробует разобраться что
> к чему. Если нет -- то всегда есть куча других путей,
> как не утруждать свой мозг :) Правда выгоняют таких до 2-го
> курса во всех нормальных ВУЗов.
> P.S. Автор, решите задачу самостоятельно, хотя бы самым простым способом. И только
> после этого переходите по ссылке.
> Брут-форс не выход для решения этой задачи (даже на сессии). Именно это я и хотел сказать.Эта задача не решается кроме как брут-форсом.
>> Брут-форс не выход для решения этой задачи (даже на сессии). Именно это я и хотел сказать.
> Эта задача не решается кроме как брут-форсом.Бред.
Давно уже пора понять, что любой брут-форс при сколько-нибудь значительном объеме входной информацмм/исходных данных себя просто не опрравдывает. Чистый брут-форс не катит ни где, кроме как на задачах с ограниченными условиями.
PS
Для практического применения эта задача очень похожа на разводку печатных плат (про ракеты молчим:)).
>>> Брут-форс не выход для решения этой задачи (даже на сессии). Именно это я и хотел сказать.
>> Эта задача не решается кроме как брут-форсом.
> Бред.
> Давно уже пора понять, что любой брут-форс при сколько-нибудь значительном объеме входной
> информацмм/исходных данных себя просто не опрравдывает. Чистый брут-форс не катит ни
> где, кроме как на задачах с ограниченными условиями.
> PS
> Для практического применения эта задача очень похожа на разводку печатных плат (про
> ракеты молчим:)).Ок, предложите тогда алгоритм без полного перебора всех ячеек, если утверждаете, что он существует. Потому что я не смог его придумать или найти.
P.S. а что про ракеты?
>>> Эта задача не решается кроме как брут-форсом.
>> Бред.О как! Ыгсперты в студии!
>> Давно уже пора понять, что любой брут-форс при сколько-нибудь значительном объеме входной
>> информацмм/исходных данных себя просто не опрравдывает. Чистый брут-форс не катит ни
>> где, кроме как на задачах с ограниченными условиями.Спасибо Капитан, всё так ... и-и-и?!?! Если другого метода науке не известно?
>> Для практического применения эта задача очень похожа на разводку печатных плат
О да как ты - на верблюда :)
>> (про ракеты молчим:)).И молчите, вы про них ... них .. них не знаете!
> Ок, предложите тогда алгоритм без полного перебора всех ячеек, если утверждаете, что
> он существует. Потому что я не смог его придумать или найти.
> P.S. а что про ракеты?Ракеты бороздят просторы Большого театра, а ты думал чего то по делу? Зря :)
Цитирую приведённый Вами сайт: Сложность задачи - O(mn), требования к памяти - O(mn)PS: Впрочем если "лтрум" сейчас выложит алгоритм лучше - публично извинюсь. Только не выложит :)
>>>> Эта задача не решается кроме как брут-форсом.
>>> Бред.
> О как! Ыгсперты в студии!Если твой скудный умишка не понимает, что для того, чтоб узнать сумму неизвестных,
нужно эти неизвестные просуммировать и никак иначе. То пора в первый класс, а не тут выёб..тся.
>>>>> Эта задача не решается кроме как брут-форсом.
>>>> Бред.
>> О как! Ыгсперты в студии!
> Если твой скудный умишка не понимает, что для того, чтоб узнать сумму
> неизвестных,
> нужно эти неизвестные просуммировать и никак иначе. То пора в первый класс,
> а не тут выёб..тся.Ага ... ты опять слегка выбрит и в стельку ? :)
Аноним и пишет - только брутфорс, ну не придумали пока лучшего решения.
ну да ладно - завтра на работе перечитаешь - дойдёт :)
> Ага ... ты опять слегка выбрит и в стельку ? :)Ну не туда нажал... :)
>[оверквотинг удален]
>>> Эта задача не решается кроме как брут-форсом.
>> Бред.
>> Давно уже пора понять, что любой брут-форс при сколько-нибудь значительном объеме входной
>> информацмм/исходных данных себя просто не опрравдывает. Чистый брут-форс не катит ни
>> где, кроме как на задачах с ограниченными условиями.
>> PS
>> Для практического применения эта задача очень похожа на разводку печатных плат (про
>> ракеты молчим:)).
> Ок, предложите тогда алгоритм без полного перебора всех ячеек, если утверждаете, что
> он существует. Потому что я не смог его придумать или найти.сдается мне, что именно в Вашем посте выше была ссылка на использование графов для решения подобных задач, котороая сейчас благополучно пропала. Вышка 1-2 курс института.
2pav это опять же ответ на Ваш вопрос. ничего кроме брут-форса?
> P.S. а что про ракеты?
так - к слову пришлось.
> сдается мне, что именно в Вашем посте выше была ссылка на использование
> графов для решения подобных задач, которая сейчас благополучно пропала. Вышка 1-2
> курс института.Ссылка никуда не пропадала. На всякий случай, вот она:
http://informatics.mccme.ru/moodle/mod/book/view.php?id=266&...
Задача там называется "Путь максимальной стоимости".Графов я там не заметил, обычный двумерный массив.
И да, по этой ссылке вы можете видеть (в самом конце) подтверждение того, что говорил вам pavlinux, и что говорил я: невозможно уменьшить сложность алгоритма для этой задачи, которая есть O(n*m), что является как раз-таки сложностью брутфорса. Если вы посмотрите алгоритм, реализованный там, то убедитесь в этом, там будет что то типа:
for (i = 0; i < n; ++i) {
for (j = 0; j < m; ++j) {
/* some code */
}
}Цитата оттуда:
Сложность алгоритма нахождения пути максимальной стоимости также имеет порядок O(nm) и, очевидно, не может быть уменьшена, поскольку для решения задачи необходимо использование каждого из nm элементов данного массива P.
>>[оверквотинг удален]
> 2pav это опять же ответ на Ваш вопрос. ничего кроме брут-форса?1. Брут-форс бывает, так сказать лобовой, когда берётся исходные данные и начинается перебор.
2. Брут-форс после оптимизации, например после приведения матрицы к треугольному виду.
3. Брут-форс с ограничением, по действиям или элементам. (как в данном случае, только вправо или вниз)Но, во всех методах, и перебора, и оптимизации используются всё элементы, что всё равно есть брут-форс.
Бывают случаи когда оптимизация сложнее брут-форса, ну например вычисление определителя через алгебраические дополнения.
>>>[оверквотинг удален]
>> 2pav это опять же ответ на Ваш вопрос. ничего кроме брут-форса?
> 1. Брут-форс бывает, так сказать лобовой, когда берётся исходные данные и начинается
> перебор.
> 2. Брут-форс после оптимизации, например после приведения матрицы к треугольному виду.
> 3. Брут-форс с ограничением, по действиям или элементам. (как в данном случае,
> только вправо или вниз)Брут-форс только "лобовым" и бывает (по опредлению). Перебор всех данных после оптимизации (в данном случае п.2-3) - это уже не брут-форс.
> Но, во всех методах, и перебора, и оптимизации используются всё элементы, что
> всё равно есть брут-форс.Не есть.
> Бывают случаи когда оптимизация сложнее брут-форса, ну например вычисление определителя
> через алгебраические дополнения.Бывает. Но данная задача совсем не этот случай.
>>>>[оверквотинг удален]
>>> 2pav это опять же ответ на Ваш вопрос. ничего кроме брут-форса?
>> 1. Брут-форс бывает, так сказать лобовой, когда берётся исходные данные и начинается
>> перебор.
>> 2. Брут-форс после оптимизации, например после приведения матрицы к треугольному виду.
>> 3. Брут-форс с ограничением, по действиям или элементам. (как в данном случае,
>> только вправо или вниз)
> Брут-форс только "лобовым" и бывает (по опредлению). Перебор всех данных после оптимизации
> (в данном случае п.2-3) - это уже не брут-форс.Разбить поиск хэша мд5 на части:
- пароли до 4 символов,
- пароли до 8 символв
- ... до 9
- ... до 10
...
и брутфорсить на разных ядрах это не брутфорс с оптимизацией?
перебор только из ограниченного диапазона - это не брутфорс?
Любой подбор, подгон, генерация со сравнением - есть брутфорсы!!!
>[оверквотинг удален]
>>> 3. Брут-форс с ограничением, по действиям или элементам. (как в данном случае,
>>> только вправо или вниз)
>> Брут-форс только "лобовым" и бывает (по опредлению). Перебор всех данных после оптимизации
>> (в данном случае п.2-3) - это уже не брут-форс.
> Разбить поиск хэша мд5 на части:
> - пароли до 4 символов,
> - пароли до 8 символв
> - ... до 9
> - ... до 10
> ...1) как хеши связаны с поставленой задачей (при наличие воображения конечно можно пареллель провести)?
2) раз уж унас про термин "брут-форс" разногласия - давайте определимся, что мы под этим поразумеваем (хливар кочечно, но...). http://ru.wikipedia.org/wiki/%D0%9F%D0%B... - это вики. мое мнение выше я уже сказал - после оптимизации УСЛОВИЙ задачи применение полного перебора всех возможных решений - это уже не "брут-форс".> и брутфорсить на разных ядрах это не брутфорс с оптимизацией?
> перебор только из ограниченного диапазона - это не брутфорс?
> Любой подбор, подгон, генерация со сравнением - есть брутфорсы!!!Брут-форс вообще никакую оптимизацию не предполегает (по определению).
PS
холивара не будет вообще-то. если ответите - мне будет интересно. нет - закрыли тему.
>[оверквотинг удален]
> - это вики. мое мнение выше я уже сказал - после
> оптимизации УСЛОВИЙ задачи применение полного перебора всех возможных решений -
> это уже не "брут-форс".
>> и брутфорсить на разных ядрах это не брутфорс с оптимизацией?
>> перебор только из ограниченного диапазона - это не брутфорс?
>> Любой подбор, подгон, генерация со сравнением - есть брутфорсы!!!
> Брут-форс вообще никакую оптимизацию не предполегает (по определению).
> PS
> холивара не будет вообще-то. если ответите - мне будет интересно. нет -
> закрыли тему.Выше уже ответил. Динамическое программирование это и есть брут-форс, просто это эффективный способ делать брут форс. Т.е. если взять брут-форс и немного его оптимизировать -- алгоритм всё равно останется брут-форсом. Так что да, для решение этой задачи был применен тип общий алгоритма который можно назвать "оптимизированный брут-форс", а такая методика решения задач называется "динамическое программирование".
С той же википедии (только с нормальной, а не русской):
http://en.wikipedia.org/wiki/Dynamic_programming
Dynamic programming algorithms are used for optimization (for example, finding the shortest path between two points, or the fastest way to multiply many matrices). A dynamic programming algorithm will examine all possible ways to solve the problem and will pick the best solution. Therefore, we can roughly think of dynamic programming as an intelligent, brute-force method that enables us to go through all possible solutions to pick the best one.
http://stackoverflow.com/questions/12068927/how-to-start-wit...
I would like to start by saying that "dynamic programming", sounding like something quite esoteric, is simply an efficient way to brute-force: you try every possible combination, but you optimize your implementation in that you avoid recomputing the same values multiple times.
> Бывает. Но данная задача совсем не этот случай.Данная задача решена с помощью динамического программирования. Вот что пишут по поводу динамического программирования в википедии:
A dynamic programming algorithm will examine all possible ways to solve the problem and will pick the best solution. Therefore, we can roughly think of dynamic programming as an intelligent, brute-force method that enables us to go through all possible solutions to pick the best one
То, о чем вы говорите -- это "intelligent". Но всё же это брут-форс.
> это "intelligent".Топикстартер видимо без зачёта на новый год уйдет. :)
>> это "intelligent".
> Топикстартер видимо без зачёта на новый год уйдет. :)Почему же? Решение готовое я ему дал, что прокачать, чтобы самому такое решать -- тоже написал, даже литературу посоветовал. Что такое динамическое программирование ему вроде тоже тут объяснили. Что смогли -- сделали.
>>> это "intelligent".
>> Топикстартер видимо без зачёта на новый год уйдет. :)
> Почему же? Решение готовое я ему дал, что прокачать, чтобы самому такое
> решать -- тоже написал, даже литературу посоветовал. Что такое динамическое программирование
> ему вроде тоже тут объяснили. Что смогли -- сделали.Зачётная сессия состоит минимум из 4 экзаменов и 6-8 зачётов.
Сессия - это 4 экзамена + хвосты с зачётной сессии.Сюда не ходят те, кому нужны советы. Сюда за готовым решением приходят.