forum.opennet.ru - "Нужна помощь при написании программы (псевдокод или C++)" (30)

форумы

помощь

поиск

регистрация

майллист

вход/выход

слежка

"Нужна помощь при написании программы (псевдокод или C++)"

Форум Программирование под UNIX (C/C++)
Вариант для распечатки		Пред. тема \| След. тема
Изначальное сообщение		[ Отслеживать ]

"Нужна помощь при написании программы (псевдокод или C++)"	+/–
Сообщение от nastr (??) on 22-Ноя-13, 00:01
Условие: План прямоугольного сада размером 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
Ответить \| Правка \| Cообщить модератору

Оглавление

Нужна помощь при написании программы (псевдокод или C++), pavlinux, 00:53 , 22-Ноя-13, (1) +3
Нужна помощь при написании программы (псевдокод или C++), parad, 11:51 , 22-Ноя-13, (2) +1

Нужна помощь при написании программы (псевдокод или C++), nastr, 12:41 , 22-Ноя-13, (3) –1

Нужна помощь при написании программы (псевдокод или C++), pavlinux, 15:42 , 22-Ноя-13, (4) +1
Нужна помощь при написании программы (псевдокод или C++), LSTemp, 00:10 , 23-Ноя-13, (10)
Нужна помощь при написании программы (псевдокод или C++), parad, 01:59 , 24-Ноя-13, (15) +1

Нужна помощь при написании программы (псевдокод или C++), LSTemp, 22:08 , 22-Ноя-13, (5) +1
Нужна помощь при написании программы (псевдокод или C++), skb7, 22:46 , 22-Ноя-13, (6) +1

Нужна помощь при написании программы (псевдокод или C++), skb7, 22:54 , 22-Ноя-13, (7)

Нужна помощь при написании программы (псевдокод или C++), LSTemp, 00:03 , 23-Ноя-13, (9)

Нужна помощь при написании программы (псевдокод или C++), skb7, 05:27 , 23-Ноя-13, (11)

Нужна помощь при написании программы (псевдокод или C++), LSTemp, 17:51 , 23-Ноя-13, (12)

Нужна помощь при написании программы (псевдокод или C++), pavlinux, 21:47 , 23-Ноя-13, (13)

Нужна помощь при написании программы (псевдокод или C++), LSTemp, 22:11 , 23-Ноя-13, (14)

Нужна помощь при написании программы (псевдокод или C++), skb7, 02:15 , 24-Ноя-13, (16)

Нужна помощь при написании программы (псевдокод или C++), Аноним, 04:24 , 24-Ноя-13, (17)

Нужна помощь при написании программы (псевдокод или C++), pavlinux, 14:54 , 24-Ноя-13, (18)

Нужна помощь при написании программы (псевдокод или C++), ну_я_же, 04:50 , 25-Ноя-13, (25)

Нужна помощь при написании программы (псевдокод или C++), pavlinux, 17:51 , 26-Ноя-13, (26)

Нужна помощь при написании программы (псевдокод или C++), LSTemp, 23:53 , 24-Ноя-13, (20)

Нужна помощь при написании программы (псевдокод или C++), skb7, 02:15 , 25-Ноя-13, (23)
Нужна помощь при написании программы (псевдокод или C++), pavlinux, 18:06 , 26-Ноя-13, (27)

Нужна помощь при написании программы (псевдокод или C++), LSTemp, 13:07 , 10-Дек-13, (31)

Нужна помощь при написании программы (псевдокод или C++), pavlinux, 22:31 , 10-Дек-13, (32) +1
Нужна помощь при написании программы (псевдокод или C++), LSTemp, 03:55 , 14-Дек-13, (35)
Нужна помощь при написании программы (псевдокод или C++), skb7, 15:33 , 14-Дек-13, (36)
Нужна помощь при написании программы (псевдокод или C++), skb7, 02:24 , 11-Дек-13, (33) +2
Нужна помощь при написании программы (псевдокод или C++), pavlinux, 04:59 , 11-Дек-13, (34) +1
Нужна помощь при написании программы (псевдокод или C++), skb7, 19:31 , 14-Дек-13, (37)
Нужна помощь при написании программы (псевдокод или C++), pavlinux, 19:44 , 14-Дек-13, (38)

Сообщения по теме [Сортировка по времени | RSS]

1. "Нужна помощь при написании программы (псевдокод или C++)" +3 +/–

Сообщение от pavlinux (ok) on 22-Ноя-13, 00:53

> Составьте программу, которая
Ура, сессия началась!!! :D

Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

2. "Нужна помощь при написании программы (псевдокод или C++)" +1 +/–

Сообщение от parad (ok) on 22-Ноя-13, 11:51

вот охламон!

Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

3. "Нужна помощь при написании программы (псевдокод или C++)" –1 +/–

Сообщение от nastr (??) on 22-Ноя-13, 12:41

почему не получается инициализировать массив следующим образом:
int[][] apples = new int[4][] { { 3, 3 }, { 1, 2, 3 }, { 1, 2, 3 }, { 1, 2, 3 } };

Ответить | Правка | ^ к родителю #2 | Наверх | Cообщить модератору

4. "Нужна помощь при написании программы (псевдокод или C++)" +1 +/–

Сообщение от pavlinux (ok) on 22-Ноя-13, 15:42

> почему не получается инициализировать массив следующим образом:
Если бы тебе сказали, "купи водки 500".
Ты б сколько купил?  500 грамм, бутылок или ящиков?
Ах да, для перевозки водки не обязательно покупать new машину.

Ответить | Правка | ^ к родителю #3 | Наверх | Cообщить модератору

10. "Нужна помощь при написании программы (псевдокод или C++)" +/–

Сообщение от LSTemp (ok) on 23-Ноя-13, 00:10

> почему не получается инициализировать массив следующим образом:
> int[][] apples = new int[4][] { { 3, 3 }, { 1,
> 2, 3 }, { 1, 2, 3 }, { 1, 2,
> 3 } };
потому, что это похрен. тут гавное алгоритм решения задачи, а не как его реализовать на данном этапе.

Ответить | Правка | ^ к родителю #3 | Наверх | Cообщить модератору

15. "Нужна помощь при написании программы (псевдокод или C++)" +1 +/–

Сообщение от parad (ok) on 24-Ноя-13, 01:59

потому что есть стандарт в котором описаны правила объявления массива.
ты своим вопросом показал нулевые знания даже в базовых вещах.

Ответить | Правка | ^ к родителю #3 | Наверх | Cообщить модератору

5. "Нужна помощь при написании программы (псевдокод или C++)" +1 +/–

Сообщение от LSTemp (ok) on 22-Ноя-13, 22:08

> Условие:
> План прямоугольного сада размером mxn состоит из квадратных зон. В каждой зоне
> растёт по дереву. С каждого дерева любой зоны могут упасть несколько
> яблок.
> В левом верхнем квадратике находится ёжик, который должен дойти до правого нижнего
> квадратика. В саду существуют ограничения относительно способа передвижения: ёжик может
> двигаться из текущего квадратика только в один из двух соседних правый
> либо нижний.
> Составьте программу, которая вычисляет максимальное количество яблок, которое может собрать
> ёжик, передвигаясь к нужному квадратику.
Абстрагируясь от ежиков ИМХО имеем простую работу с матрицами. Прокачайте это и потом задавайте вопросы на счет самой программы.

Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

6. "Нужна помощь при написании программы (псевдокод или C++)" +1 +/–

Сообщение от skb7 (ok) on 22-Ноя-13, 22:46

>[оверквотинг удален]
> Текстовый файл "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. Вызвав по очереди функции чтения из файла, алгоритма нахождения пути и функции записи в файл -- вы решите задачу.

Ответить | Правка | ^ к родителю #0 | Наверх | Cообщить модератору

7. "Нужна помощь при написании программы (псевдокод или C++)" +/–

Сообщение от skb7 (ok) on 22-Ноя-13, 22:54

>[оверквотинг удален]
>    - fprintf(), fscanf()
>    - malloc(), free()
> Есть отличный сайт-справка по функциям Си: www.cplusplus.com . С примерами использования.
> Также очень удобно использовать маны по функциям стандартной библиотеки Си. Например "man
> fopen" (в консоли) покажет справку по функции fopen().
> 4. Функция записи в файл. Должна создавать файл и записывать одно число.
> Протестируйте работу.
> 5. Напишите функцию, реализующую выбранный алгоритм.
> 6. Вызвав по очереди функции чтения из файла, алгоритма нахождения пути и
> функции записи в файл -- вы решите задачу.
а вообще, в вашем случае, если нет требований к скорости алгоритму, и объем данных небольшой -- наверно проще всего использовать обычный перебор -- пройти по всем возможным путям, оставив в конце самый удачный.

Ответить | Правка | ^ к родителю #6 | Наверх | Cообщить модератору

9. "Нужна помощь при написании программы (псевдокод или C++)" +/–

Сообщение от LSTemp (ok) on 23-Ноя-13, 00:03

> а вообще, в вашем случае, если нет требований к скорости алгоритму, и
> объем данных небольшой -- наверно проще всего использовать обычный перебор --
> пройти по всем возможным путям, оставив в конце самый удачный.
Вообще - Все в сад - слушать песни ). Размер сада не определен (задается файлом конфигурации). Сделайте выборку по возможным вариантам сада хотя бы 10х10  - сколько комбинаций получится?
ИМХО из моего личного опыта такие задачи не просто так даются (особенно, когда ежики не ходят куда хотят). Так что рассчитывать на решение "перебрать все" тут не катит .. ИМХО опять же.
PS
Есть вес каждой клетки матрицы, есть ограничение связей м/ду клетками (доступные движения ежа), задача набрать max.

Ответить | Правка | ^ к родителю #7 | Наверх | Cообщить модератору

11. "Нужна помощь при написании программы (псевдокод или C++)" +/–

Сообщение от skb7 (ok) on 23-Ноя-13, 05:27

>[оверквотинг удален]
>> пройти по всем возможным путям, оставив в конце самый удачный.
> Вообще - Все в сад - слушать песни ). Размер сада не
> определен (задается файлом конфигурации). Сделайте выборку по возможным вариантам сада
> хотя бы 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. Автор, решите задачу самостоятельно, хотя бы самым простым способом. И только после этого переходите по ссылке.

Ответить | Правка | ^ к родителю #9 | Наверх | Cообщить модератору

12. "Нужна помощь при написании программы (псевдокод или C++)" +/–

Сообщение от LSTemp (ok) on 23-Ноя-13, 17:51

>[оверквотинг удален]
>> "перебрать все" тут не катит .. ИМХО опять же.
>> 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. Автор, решите задачу самостоятельно, хотя бы самым простым способом. И только
> после этого переходите по ссылке.

Ответить | Правка | ^ к родителю #11 | Наверх | Cообщить модератору

13. "Нужна помощь при написании программы (псевдокод или C++)" +/–

Сообщение от pavlinux (ok) on 23-Ноя-13, 21:47

> Брут-форс не выход для решения этой задачи (даже на сессии). Именно это я и хотел сказать.
Эта задача не решается кроме как брут-форсом.

Ответить | Правка | ^ к родителю #12 | Наверх | Cообщить модератору

14. "Нужна помощь при написании программы (псевдокод или C++)" +/–

Сообщение от LSTemp (ok) on 23-Ноя-13, 22:11

>> Брут-форс не выход для решения этой задачи (даже на сессии). Именно это я и хотел сказать.
> Эта задача не решается кроме как брут-форсом.
Бред.
Давно уже пора понять, что любой брут-форс при сколько-нибудь значительном объеме входной информацмм/исходных данных себя просто не опрравдывает. Чистый брут-форс не катит ни где, кроме как на задачах с ограниченными условиями.
PS
Для практического применения эта задача очень похожа на разводку печатных плат (про ракеты молчим:)).

Ответить | Правка | ^ к родителю #13 | Наверх | Cообщить модератору

16. "Нужна помощь при написании программы (псевдокод или C++)" +/–

Сообщение от skb7 (ok) on 24-Ноя-13, 02:15

>>> Брут-форс не выход для решения этой задачи (даже на сессии). Именно это я и хотел сказать.
>> Эта задача не решается кроме как брут-форсом.
> Бред.
> Давно уже пора понять, что любой брут-форс при сколько-нибудь значительном объеме входной
> информацмм/исходных данных себя просто не опрравдывает. Чистый брут-форс не катит ни
> где, кроме как на задачах с ограниченными условиями.
> PS
> Для практического применения эта задача очень похожа на разводку печатных плат (про
> ракеты молчим:)).
Ок, предложите тогда алгоритм без полного перебора всех ячеек, если утверждаете, что он существует. Потому что я не смог его придумать или найти.
P.S. а что про ракеты?

Ответить | Правка | ^ к родителю #14 | Наверх | Cообщить модератору

17. "Нужна помощь при написании программы (псевдокод или C++)" +/–

Сообщение от Аноним (??) on 24-Ноя-13, 04:24

>>> Эта задача не решается кроме как брут-форсом.
>> Бред.
О как! Ыгсперты в студии!
>> Давно уже пора понять, что любой брут-форс при сколько-нибудь значительном объеме входной
>> информацмм/исходных данных себя просто не опрравдывает. Чистый брут-форс не катит ни
>> где, кроме как на задачах с ограниченными условиями.
Спасибо Капитан, всё так ... и-и-и?!?! Если другого метода науке не известно?
>> Для практического применения эта задача очень похожа на разводку печатных плат
О да как ты - на верблюда :)
>> (про ракеты молчим:)).
И молчите, вы про них ... них .. них не знаете!
> Ок, предложите тогда алгоритм без полного перебора всех ячеек, если утверждаете, что
> он существует. Потому что я не смог его придумать или найти.
> P.S. а что про ракеты?
Ракеты бороздят просторы Большого театра, а ты думал чего то по делу? Зря :)
Цитирую приведённый Вами сайт: Сложность задачи - O(mn), требования к памяти - O(mn)
PS: Впрочем если "лтрум" сейчас выложит алгоритм лучше - публично извинюсь. Только не выложит :)

Ответить | Правка | ^ к родителю #16 | Наверх | Cообщить модератору

18. "Нужна помощь при написании программы (псевдокод или C++)" +/–

Сообщение от pavlinux (ok) on 24-Ноя-13, 14:54

>>>> Эта задача не решается кроме как брут-форсом.
>>> Бред.
> О как! Ыгсперты в студии!
Если твой скудный умишка не понимает, что для того, чтоб узнать сумму неизвестных,
нужно эти неизвестные просуммировать и никак иначе. То пора в первый класс, а не тут выёб..тся.

Ответить | Правка | ^ к родителю #17 | Наверх | Cообщить модератору

25. "Нужна помощь при написании программы (псевдокод или C++)" +/–

Сообщение от ну_я_же on 25-Ноя-13, 04:50

>>>>> Эта задача не решается кроме как брут-форсом.
>>>> Бред.
>> О как! Ыгсперты в студии!
> Если твой скудный умишка не понимает, что для того, чтоб узнать сумму
> неизвестных,
> нужно эти неизвестные просуммировать и никак иначе. То пора в первый класс,
> а не тут выёб..тся.
Ага ... ты опять слегка выбрит и в стельку ? :)
Аноним и пишет - только брутфорс, ну не придумали пока лучшего решения.
ну да ладно - завтра на работе перечитаешь - дойдёт :)

Ответить | Правка | ^ к родителю #18 | Наверх | Cообщить модератору

26. "Нужна помощь при написании программы (псевдокод или C++)" +/–

Сообщение от pavlinux (ok) on 26-Ноя-13, 17:51

> Ага ... ты опять слегка выбрит и в стельку ? :)
Ну не туда нажал... :)

Ответить | Правка | ^ к родителю #25 | Наверх | Cообщить модератору

20. "Нужна помощь при написании программы (псевдокод или C++)" +/–

Сообщение от LSTemp (ok) on 24-Ноя-13, 23:53

>[оверквотинг удален]
>>> Эта задача не решается кроме как брут-форсом.
>> Бред.
>> Давно уже пора понять, что любой брут-форс при сколько-нибудь значительном объеме входной
>> информацмм/исходных данных себя просто не опрравдывает. Чистый брут-форс не катит ни
>> где, кроме как на задачах с ограниченными условиями.
>> PS
>> Для практического применения эта задача очень похожа на разводку печатных плат (про
>> ракеты молчим:)).
> Ок, предложите тогда алгоритм без полного перебора всех ячеек, если утверждаете, что
> он существует. Потому что я не смог его придумать или найти.
сдается мне, что именно в Вашем посте выше была ссылка на использование графов для решения подобных задач, котороая сейчас благополучно пропала. Вышка 1-2 курс института.
2pav это опять же ответ на Ваш вопрос. ничего кроме брут-форса?
> P.S. а что про ракеты?
так - к слову пришлось.

Ответить | Правка | ^ к родителю #16 | Наверх | Cообщить модератору

23. "Нужна помощь при написании программы (псевдокод или C++)" +/–

Сообщение от skb7 (ok) on 25-Ноя-13, 02:15

> сдается мне, что именно в Вашем посте выше была ссылка на использование
> графов для решения подобных задач, которая сейчас благополучно пропала. Вышка 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.

Ответить | Правка | ^ к родителю #20 | Наверх | Cообщить модератору

27. "Нужна помощь при написании программы (псевдокод или C++)" +/–

Сообщение от pavlinux (ok) on 26-Ноя-13, 18:06

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

Ответить | Правка | ^ к родителю #20 | Наверх | Cообщить модератору

31. "Нужна помощь при написании программы (псевдокод или C++)" +/–

Сообщение от LSTemp (ok) on 10-Дек-13, 13:07

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

Ответить | Правка | ^ к родителю #27 | Наверх | Cообщить модератору

32. "Нужна помощь при написании программы (псевдокод или C++)" +1 +/–

Сообщение от pavlinux (ok) on 10-Дек-13, 22:31

>>>>[оверквотинг удален]
>>> 2pav это опять же ответ на Ваш вопрос. ничего кроме брут-форса?
>> 1. Брут-форс бывает, так сказать лобовой, когда берётся исходные данные и начинается
>> перебор.
>> 2. Брут-форс после оптимизации, например после приведения матрицы к треугольному виду.
>> 3. Брут-форс с ограничением, по действиям или элементам. (как в данном случае,
>> только вправо или вниз)
> Брут-форс только "лобовым" и бывает (по опредлению). Перебор всех данных после оптимизации
> (в данном случае п.2-3) - это уже не брут-форс.
Разбить поиск хэша мд5 на части:
- пароли до 4 символов,
- пароли до 8 символв
- ... до 9
- ... до 10
...
и брутфорсить на разных ядрах это не брутфорс с оптимизацией?
перебор только из ограниченного диапазона - это не брутфорс?
Любой подбор, подгон, генерация со сравнением - есть брутфорсы!!!

Ответить | Правка | ^ к родителю #31 | Наверх | Cообщить модератору

35. "Нужна помощь при написании программы (псевдокод или C++)" +/–

Сообщение от LSTemp (ok) on 14-Дек-13, 03:55

>[оверквотинг удален]
>>> 3. Брут-форс с ограничением, по действиям или элементам. (как в данном случае,
>>> только вправо или вниз)
>> Брут-форс только "лобовым" и бывает (по опредлению). Перебор всех данных после оптимизации
>> (в данном случае п.2-3) - это уже не брут-форс.
> Разбить поиск хэша мд5 на части:
> - пароли до 4 символов,
> - пароли до 8 символв
> - ... до 9
> - ... до 10
> ...
1) как хеши связаны с поставленой задачей (при наличие воображения конечно можно пареллель провести)?
2) раз уж унас про термин "брут-форс" разногласия  - давайте определимся, что мы под этим поразумеваем (хливар кочечно, но...). http://ru.wikipedia.org/wiki/%D0%9F%D0%B... - это вики. мое мнение выше я уже сказал - после оптимизации УСЛОВИЙ задачи применение полного перебора всех возможных решений  - это уже не "брут-форс".
> и брутфорсить на разных ядрах это не брутфорс с оптимизацией?
> перебор только из ограниченного диапазона - это не брутфорс?
> Любой подбор, подгон, генерация со сравнением - есть брутфорсы!!!
Брут-форс вообще никакую оптимизацию не предполегает (по определению).
PS
холивара не будет вообще-то. если ответите - мне будет интересно. нет - закрыли тему.

Ответить | Правка | ^ к родителю #32 | Наверх | Cообщить модератору

36. "Нужна помощь при написании программы (псевдокод или C++)" +/–

Сообщение от skb7 (ok) on 14-Дек-13, 15:33

>[оверквотинг удален]
> - это вики. мое мнение выше я уже сказал - после
> оптимизации УСЛОВИЙ задачи применение полного перебора всех возможных решений  -
> это уже не "брут-форс".
>> и брутфорсить на разных ядрах это не брутфорс с оптимизацией?
>> перебор только из ограниченного диапазона - это не брутфорс?
>> Любой подбор, подгон, генерация со сравнением - есть брутфорсы!!!
> Брут-форс вообще никакую оптимизацию не предполегает (по определению).
> 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.

Ответить | Правка | ^ к родителю #35 | Наверх | Cообщить модератору

33. "Нужна помощь при написании программы (псевдокод или C++)" +2 +/–

Сообщение от skb7 (ok) on 11-Дек-13, 02:24

> Бывает. Но данная задача совсем не этот случай.
Данная задача решена с помощью динамического программирования. Вот что пишут по поводу динамического программирования в википедии:
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". Но всё же это брут-форс.

Ответить | Правка | ^ к родителю #31 | Наверх | Cообщить модератору

34. "Нужна помощь при написании программы (псевдокод или C++)" +1 +/–

Сообщение от pavlinux (ok) on 11-Дек-13, 04:59

>  это "intelligent".
Топикстартер видимо без зачёта на новый год уйдет. :)

Ответить | Правка | ^ к родителю #33 | Наверх | Cообщить модератору

37. "Нужна помощь при написании программы (псевдокод или C++)" +/–

Сообщение от skb7 (ok) on 14-Дек-13, 19:31

>>  это "intelligent".
> Топикстартер видимо без зачёта на новый год уйдет. :)
Почему же? Решение готовое я ему дал, что прокачать, чтобы самому такое решать -- тоже написал, даже литературу посоветовал. Что такое динамическое программирование ему вроде тоже тут объяснили. Что смогли -- сделали.

Ответить | Правка | ^ к родителю #34 | Наверх | Cообщить модератору

38. "Нужна помощь при написании программы (псевдокод или C++)" +/–

Сообщение от pavlinux (ok) on 14-Дек-13, 19:44

>>>  это "intelligent".
>> Топикстартер видимо без зачёта на новый год уйдет. :)
> Почему же? Решение готовое я ему дал, что прокачать, чтобы самому такое
> решать -- тоже написал, даже литературу посоветовал. Что такое динамическое программирование
> ему вроде тоже тут объяснили. Что смогли -- сделали.
Зачётная сессия состоит минимум из 4 экзаменов и 6-8 зачётов.
Сессия - это 4 экзамена + хвосты с зачётной сессии.
Сюда не ходят те, кому нужны советы. Сюда за готовым решением приходят.

Ответить | Правка | ^ к родителю #37 | Наверх | Cообщить модератору

Архив | Удалить

Рекомендовать для помещения в FAQ | Индекс форумов | Темы | Пред. тема | След. тема

Партнёры:

Хостинг:

Закладки на сайте
Проследить за страницей

Created 1996-2024 by Maxim Chirkov
Добавить, Поддержать, Вебмастеру

1. "Нужна помощь при написании программы (псевдокод или C++)"	+3 +/–
Сообщение от pavlinux (ok) on 22-Ноя-13, 00:53
> Составьте программу, которая Ура, сессия началась!!! :D
Ответить \| Правка \| ^ к родителю #0 \| Наверх \| Cообщить модератору

2. "Нужна помощь при написании программы (псевдокод или C++)"	+1 +/–
Сообщение от parad (ok) on 22-Ноя-13, 11:51
вот охламон!
Ответить \| Правка \| ^ к родителю #0 \| Наверх \| Cообщить модератору


	3. "Нужна помощь при написании программы (псевдокод или C++)"	–1 +/–
	Сообщение от nastr (??) on 22-Ноя-13, 12:41
	почему не получается инициализировать массив следующим образом: int[][] apples = new int[4][] { { 3, 3 }, { 1, 2, 3 }, { 1, 2, 3 }, { 1, 2, 3 } };
	Ответить \| Правка \| ^ к родителю #2 \| Наверх \| Cообщить модератору


	4. "Нужна помощь при написании программы (псевдокод или C++)"	+1 +/–
	Сообщение от pavlinux (ok) on 22-Ноя-13, 15:42
	> почему не получается инициализировать массив следующим образом: Если бы тебе сказали, "купи водки 500". Ты б сколько купил? 500 грамм, бутылок или ящиков? Ах да, для перевозки водки не обязательно покупать new машину.
	Ответить \| Правка \| ^ к родителю #3 \| Наверх \| Cообщить модератору


	10. "Нужна помощь при написании программы (псевдокод или C++)"	+/–
	Сообщение от LSTemp (ok) on 23-Ноя-13, 00:10
	> почему не получается инициализировать массив следующим образом: > int[][] apples = new int[4][] { { 3, 3 }, { 1, > 2, 3 }, { 1, 2, 3 }, { 1, 2, > 3 } }; потому, что это похрен. тут гавное алгоритм решения задачи, а не как его реализовать на данном этапе.
	Ответить \| Правка \| ^ к родителю #3 \| Наверх \| Cообщить модератору


	15. "Нужна помощь при написании программы (псевдокод или C++)"	+1 +/–
	Сообщение от parad (ok) on 24-Ноя-13, 01:59
	потому что есть стандарт в котором описаны правила объявления массива. ты своим вопросом показал нулевые знания даже в базовых вещах.
	Ответить \| Правка \| ^ к родителю #3 \| Наверх \| Cообщить модератору

5. "Нужна помощь при написании программы (псевдокод или C++)"	+1 +/–
Сообщение от LSTemp (ok) on 22-Ноя-13, 22:08
> Условие: > План прямоугольного сада размером mxn состоит из квадратных зон. В каждой зоне > растёт по дереву. С каждого дерева любой зоны могут упасть несколько > яблок. > В левом верхнем квадратике находится ёжик, который должен дойти до правого нижнего > квадратика. В саду существуют ограничения относительно способа передвижения: ёжик может > двигаться из текущего квадратика только в один из двух соседних правый > либо нижний. > Составьте программу, которая вычисляет максимальное количество яблок, которое может собрать > ёжик, передвигаясь к нужному квадратику. Абстрагируясь от ежиков ИМХО имеем простую работу с матрицами. Прокачайте это и потом задавайте вопросы на счет самой программы.
Ответить \| Правка \| ^ к родителю #0 \| Наверх \| Cообщить модератору

6. "Нужна помощь при написании программы (псевдокод или C++)"	+1 +/–
Сообщение от skb7 (ok) on 22-Ноя-13, 22:46
>[оверквотинг удален] > Текстовый файл "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. Вызвав по очереди функции чтения из файла, алгоритма нахождения пути и функции записи в файл -- вы решите задачу.
Ответить \| Правка \| ^ к родителю #0 \| Наверх \| Cообщить модератору


	7. "Нужна помощь при написании программы (псевдокод или C++)"	+/–
	Сообщение от skb7 (ok) on 22-Ноя-13, 22:54
	>[оверквотинг удален] > - fprintf(), fscanf() > - malloc(), free() > Есть отличный сайт-справка по функциям Си: www.cplusplus.com . С примерами использования. > Также очень удобно использовать маны по функциям стандартной библиотеки Си. Например "man > fopen" (в консоли) покажет справку по функции fopen(). > 4. Функция записи в файл. Должна создавать файл и записывать одно число. > Протестируйте работу. > 5. Напишите функцию, реализующую выбранный алгоритм. > 6. Вызвав по очереди функции чтения из файла, алгоритма нахождения пути и > функции записи в файл -- вы решите задачу. а вообще, в вашем случае, если нет требований к скорости алгоритму, и объем данных небольшой -- наверно проще всего использовать обычный перебор -- пройти по всем возможным путям, оставив в конце самый удачный.
	Ответить \| Правка \| ^ к родителю #6 \| Наверх \| Cообщить модератору


	9. "Нужна помощь при написании программы (псевдокод или C++)"	+/–
	Сообщение от LSTemp (ok) on 23-Ноя-13, 00:03
	> а вообще, в вашем случае, если нет требований к скорости алгоритму, и > объем данных небольшой -- наверно проще всего использовать обычный перебор -- > пройти по всем возможным путям, оставив в конце самый удачный. Вообще - Все в сад - слушать песни ). Размер сада не определен (задается файлом конфигурации). Сделайте выборку по возможным вариантам сада хотя бы 10х10 - сколько комбинаций получится? ИМХО из моего личного опыта такие задачи не просто так даются (особенно, когда ежики не ходят куда хотят). Так что рассчитывать на решение "перебрать все" тут не катит .. ИМХО опять же. PS Есть вес каждой клетки матрицы, есть ограничение связей м/ду клетками (доступные движения ежа), задача набрать max.
	Ответить \| Правка \| ^ к родителю #7 \| Наверх \| Cообщить модератору


	11. "Нужна помощь при написании программы (псевдокод или C++)"	+/–
	Сообщение от skb7 (ok) on 23-Ноя-13, 05:27
	>[оверквотинг удален] >> пройти по всем возможным путям, оставив в конце самый удачный. > Вообще - Все в сад - слушать песни ). Размер сада не > определен (задается файлом конфигурации). Сделайте выборку по возможным вариантам сада > хотя бы 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. Автор, решите задачу самостоятельно, хотя бы самым простым способом. И только после этого переходите по ссылке.
	Ответить \| Правка \| ^ к родителю #9 \| Наверх \| Cообщить модератору


	12. "Нужна помощь при написании программы (псевдокод или C++)"	+/–
	Сообщение от LSTemp (ok) on 23-Ноя-13, 17:51
	>[оверквотинг удален] >> "перебрать все" тут не катит .. ИМХО опять же. >> 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. Автор, решите задачу самостоятельно, хотя бы самым простым способом. И только > после этого переходите по ссылке.
	Ответить \| Правка \| ^ к родителю #11 \| Наверх \| Cообщить модератору


	13. "Нужна помощь при написании программы (псевдокод или C++)"	+/–
	Сообщение от pavlinux (ok) on 23-Ноя-13, 21:47
	> Брут-форс не выход для решения этой задачи (даже на сессии). Именно это я и хотел сказать. Эта задача не решается кроме как брут-форсом.
	Ответить \| Правка \| ^ к родителю #12 \| Наверх \| Cообщить модератору


	14. "Нужна помощь при написании программы (псевдокод или C++)"	+/–
	Сообщение от LSTemp (ok) on 23-Ноя-13, 22:11
	>> Брут-форс не выход для решения этой задачи (даже на сессии). Именно это я и хотел сказать. > Эта задача не решается кроме как брут-форсом. Бред. Давно уже пора понять, что любой брут-форс при сколько-нибудь значительном объеме входной информацмм/исходных данных себя просто не опрравдывает. Чистый брут-форс не катит ни где, кроме как на задачах с ограниченными условиями. PS Для практического применения эта задача очень похожа на разводку печатных плат (про ракеты молчим:)).
	Ответить \| Правка \| ^ к родителю #13 \| Наверх \| Cообщить модератору


	16. "Нужна помощь при написании программы (псевдокод или C++)"	+/–
	Сообщение от skb7 (ok) on 24-Ноя-13, 02:15
	>>> Брут-форс не выход для решения этой задачи (даже на сессии). Именно это я и хотел сказать. >> Эта задача не решается кроме как брут-форсом. > Бред. > Давно уже пора понять, что любой брут-форс при сколько-нибудь значительном объеме входной > информацмм/исходных данных себя просто не опрравдывает. Чистый брут-форс не катит ни > где, кроме как на задачах с ограниченными условиями. > PS > Для практического применения эта задача очень похожа на разводку печатных плат (про > ракеты молчим:)). Ок, предложите тогда алгоритм без полного перебора всех ячеек, если утверждаете, что он существует. Потому что я не смог его придумать или найти. P.S. а что про ракеты?
	Ответить \| Правка \| ^ к родителю #14 \| Наверх \| Cообщить модератору


	17. "Нужна помощь при написании программы (псевдокод или C++)"	+/–
	Сообщение от Аноним (??) on 24-Ноя-13, 04:24
	>>> Эта задача не решается кроме как брут-форсом. >> Бред. О как! Ыгсперты в студии! >> Давно уже пора понять, что любой брут-форс при сколько-нибудь значительном объеме входной >> информацмм/исходных данных себя просто не опрравдывает. Чистый брут-форс не катит ни >> где, кроме как на задачах с ограниченными условиями. Спасибо Капитан, всё так ... и-и-и?!?! Если другого метода науке не известно? >> Для практического применения эта задача очень похожа на разводку печатных плат О да как ты - на верблюда :) >> (про ракеты молчим:)). И молчите, вы про них ... них .. них не знаете! > Ок, предложите тогда алгоритм без полного перебора всех ячеек, если утверждаете, что > он существует. Потому что я не смог его придумать или найти. > P.S. а что про ракеты? Ракеты бороздят просторы Большого театра, а ты думал чего то по делу? Зря :) Цитирую приведённый Вами сайт: Сложность задачи - O(mn), требования к памяти - O(mn) PS: Впрочем если "лтрум" сейчас выложит алгоритм лучше - публично извинюсь. Только не выложит :)
	Ответить \| Правка \| ^ к родителю #16 \| Наверх \| Cообщить модератору


	18. "Нужна помощь при написании программы (псевдокод или C++)"	+/–
	Сообщение от pavlinux (ok) on 24-Ноя-13, 14:54
	>>>> Эта задача не решается кроме как брут-форсом. >>> Бред. > О как! Ыгсперты в студии! Если твой скудный умишка не понимает, что для того, чтоб узнать сумму неизвестных, нужно эти неизвестные просуммировать и никак иначе. То пора в первый класс, а не тут выёб..тся.
	Ответить \| Правка \| ^ к родителю #17 \| Наверх \| Cообщить модератору


	25. "Нужна помощь при написании программы (псевдокод или C++)"	+/–
	Сообщение от ну_я_же on 25-Ноя-13, 04:50
	>>>>> Эта задача не решается кроме как брут-форсом. >>>> Бред. >> О как! Ыгсперты в студии! > Если твой скудный умишка не понимает, что для того, чтоб узнать сумму > неизвестных, > нужно эти неизвестные просуммировать и никак иначе. То пора в первый класс, > а не тут выёб..тся. Ага ... ты опять слегка выбрит и в стельку ? :) Аноним и пишет - только брутфорс, ну не придумали пока лучшего решения. ну да ладно - завтра на работе перечитаешь - дойдёт :)
	Ответить \| Правка \| ^ к родителю #18 \| Наверх \| Cообщить модератору


	26. "Нужна помощь при написании программы (псевдокод или C++)"	+/–
	Сообщение от pavlinux (ok) on 26-Ноя-13, 17:51
	> Ага ... ты опять слегка выбрит и в стельку ? :) Ну не туда нажал... :)
	Ответить \| Правка \| ^ к родителю #25 \| Наверх \| Cообщить модератору


	20. "Нужна помощь при написании программы (псевдокод или C++)"	+/–
	Сообщение от LSTemp (ok) on 24-Ноя-13, 23:53
	>[оверквотинг удален] >>> Эта задача не решается кроме как брут-форсом. >> Бред. >> Давно уже пора понять, что любой брут-форс при сколько-нибудь значительном объеме входной >> информацмм/исходных данных себя просто не опрравдывает. Чистый брут-форс не катит ни >> где, кроме как на задачах с ограниченными условиями. >> PS >> Для практического применения эта задача очень похожа на разводку печатных плат (про >> ракеты молчим:)). > Ок, предложите тогда алгоритм без полного перебора всех ячеек, если утверждаете, что > он существует. Потому что я не смог его придумать или найти. сдается мне, что именно в Вашем посте выше была ссылка на использование графов для решения подобных задач, котороая сейчас благополучно пропала. Вышка 1-2 курс института. 2pav это опять же ответ на Ваш вопрос. ничего кроме брут-форса? > P.S. а что про ракеты? так - к слову пришлось.
	Ответить \| Правка \| ^ к родителю #16 \| Наверх \| Cообщить модератору


	23. "Нужна помощь при написании программы (псевдокод или C++)"	+/–
	Сообщение от skb7 (ok) on 25-Ноя-13, 02:15
	> сдается мне, что именно в Вашем посте выше была ссылка на использование > графов для решения подобных задач, которая сейчас благополучно пропала. Вышка 1-2 > курс института. Ссылка никуда не пропадала. На всякий случай, вот она: http://informatics.mccme.ru/moodle/mod/book/view.php?id=266&... Задача там называется "Путь максимальной стоимости". Графов я там не заметил, обычный двумерный массив. И да, по этой ссылке вы можете видеть (в самом конце) подтверждение того, что говорил вам pavlinux, и что говорил я: невозможно уменьшить сложность алгоритма для этой задачи, которая есть O(nm), что является как раз-таки сложностью брутфорса. Если вы посмотрите алгоритм, реализованный там, то убедитесь в этом, там будет что то типа: for (i = 0; i < n; ++i) { for (j = 0; j < m; ++j) { / some code */ } } Цитата оттуда: Сложность алгоритма нахождения пути максимальной стоимости также имеет порядок O(nm) и, очевидно, не может быть уменьшена, поскольку для решения задачи необходимо использование каждого из nm элементов данного массива P.
	Ответить \| Правка \| ^ к родителю #20 \| Наверх \| Cообщить модератору


	27. "Нужна помощь при написании программы (псевдокод или C++)"	+/–
	Сообщение от pavlinux (ok) on 26-Ноя-13, 18:06
	>>[оверквотинг удален] > 2pav это опять же ответ на Ваш вопрос. ничего кроме брут-форса? 1. Брут-форс бывает, так сказать лобовой, когда берётся исходные данные и начинается перебор. 2. Брут-форс после оптимизации, например после приведения матрицы к треугольному виду. 3. Брут-форс с ограничением, по действиям или элементам. (как в данном случае, только вправо или вниз) Но, во всех методах, и перебора, и оптимизации используются всё элементы, что всё равно есть брут-форс. Бывают случаи когда оптимизация сложнее брут-форса, ну например вычисление определителя через алгебраические дополнения.
	Ответить \| Правка \| ^ к родителю #20 \| Наверх \| Cообщить модератору


	31. "Нужна помощь при написании программы (псевдокод или C++)"	+/–
	Сообщение от LSTemp (ok) on 10-Дек-13, 13:07
	>>>[оверквотинг удален] >> 2pav это опять же ответ на Ваш вопрос. ничего кроме брут-форса? > 1. Брут-форс бывает, так сказать лобовой, когда берётся исходные данные и начинается > перебор. > 2. Брут-форс после оптимизации, например после приведения матрицы к треугольному виду. > 3. Брут-форс с ограничением, по действиям или элементам. (как в данном случае, > только вправо или вниз) Брут-форс только "лобовым" и бывает (по опредлению). Перебор всех данных после оптимизации (в данном случае п.2-3) - это уже не брут-форс. > Но, во всех методах, и перебора, и оптимизации используются всё элементы, что > всё равно есть брут-форс. Не есть. > Бывают случаи когда оптимизация сложнее брут-форса, ну например вычисление определителя > через алгебраические дополнения. Бывает. Но данная задача совсем не этот случай.
	Ответить \| Правка \| ^ к родителю #27 \| Наверх \| Cообщить модератору


	32. "Нужна помощь при написании программы (псевдокод или C++)"	+1 +/–
	Сообщение от pavlinux (ok) on 10-Дек-13, 22:31
	>>>>[оверквотинг удален] >>> 2pav это опять же ответ на Ваш вопрос. ничего кроме брут-форса? >> 1. Брут-форс бывает, так сказать лобовой, когда берётся исходные данные и начинается >> перебор. >> 2. Брут-форс после оптимизации, например после приведения матрицы к треугольному виду. >> 3. Брут-форс с ограничением, по действиям или элементам. (как в данном случае, >> только вправо или вниз) > Брут-форс только "лобовым" и бывает (по опредлению). Перебор всех данных после оптимизации > (в данном случае п.2-3) - это уже не брут-форс. Разбить поиск хэша мд5 на части: - пароли до 4 символов, - пароли до 8 символв - ... до 9 - ... до 10 ... и брутфорсить на разных ядрах это не брутфорс с оптимизацией? перебор только из ограниченного диапазона - это не брутфорс? Любой подбор, подгон, генерация со сравнением - есть брутфорсы!!!
	Ответить \| Правка \| ^ к родителю #31 \| Наверх \| Cообщить модератору


	35. "Нужна помощь при написании программы (псевдокод или C++)"	+/–
	Сообщение от LSTemp (ok) on 14-Дек-13, 03:55
	>[оверквотинг удален] >>> 3. Брут-форс с ограничением, по действиям или элементам. (как в данном случае, >>> только вправо или вниз) >> Брут-форс только "лобовым" и бывает (по опредлению). Перебор всех данных после оптимизации >> (в данном случае п.2-3) - это уже не брут-форс. > Разбить поиск хэша мд5 на части: > - пароли до 4 символов, > - пароли до 8 символв > - ... до 9 > - ... до 10 > ... 1) как хеши связаны с поставленой задачей (при наличие воображения конечно можно пареллель провести)? 2) раз уж унас про термин "брут-форс" разногласия - давайте определимся, что мы под этим поразумеваем (хливар кочечно, но...). http://ru.wikipedia.org/wiki/%D0%9F%D0%B... - это вики. мое мнение выше я уже сказал - после оптимизации УСЛОВИЙ задачи применение полного перебора всех возможных решений - это уже не "брут-форс". > и брутфорсить на разных ядрах это не брутфорс с оптимизацией? > перебор только из ограниченного диапазона - это не брутфорс? > Любой подбор, подгон, генерация со сравнением - есть брутфорсы!!! Брут-форс вообще никакую оптимизацию не предполегает (по определению). PS холивара не будет вообще-то. если ответите - мне будет интересно. нет - закрыли тему.
	Ответить \| Правка \| ^ к родителю #32 \| Наверх \| Cообщить модератору


	36. "Нужна помощь при написании программы (псевдокод или C++)"	+/–
	Сообщение от skb7 (ok) on 14-Дек-13, 15:33
	>[оверквотинг удален] > - это вики. мое мнение выше я уже сказал - после > оптимизации УСЛОВИЙ задачи применение полного перебора всех возможных решений - > это уже не "брут-форс". >> и брутфорсить на разных ядрах это не брутфорс с оптимизацией? >> перебор только из ограниченного диапазона - это не брутфорс? >> Любой подбор, подгон, генерация со сравнением - есть брутфорсы!!! > Брут-форс вообще никакую оптимизацию не предполегает (по определению). > 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.
	Ответить \| Правка \| ^ к родителю #35 \| Наверх \| Cообщить модератору


	33. "Нужна помощь при написании программы (псевдокод или C++)"	+2 +/–
	Сообщение от skb7 (ok) on 11-Дек-13, 02:24
	> Бывает. Но данная задача совсем не этот случай. Данная задача решена с помощью динамического программирования. Вот что пишут по поводу динамического программирования в википедии: 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". Но всё же это брут-форс.
	Ответить \| Правка \| ^ к родителю #31 \| Наверх \| Cообщить модератору


	34. "Нужна помощь при написании программы (псевдокод или C++)"	+1 +/–
	Сообщение от pavlinux (ok) on 11-Дек-13, 04:59
	> это "intelligent". Топикстартер видимо без зачёта на новый год уйдет. :)
	Ответить \| Правка \| ^ к родителю #33 \| Наверх \| Cообщить модератору


	37. "Нужна помощь при написании программы (псевдокод или C++)"	+/–
	Сообщение от skb7 (ok) on 14-Дек-13, 19:31
	>> это "intelligent". > Топикстартер видимо без зачёта на новый год уйдет. :) Почему же? Решение готовое я ему дал, что прокачать, чтобы самому такое решать -- тоже написал, даже литературу посоветовал. Что такое динамическое программирование ему вроде тоже тут объяснили. Что смогли -- сделали.
	Ответить \| Правка \| ^ к родителю #34 \| Наверх \| Cообщить модератору


	38. "Нужна помощь при написании программы (псевдокод или C++)"	+/–
	Сообщение от pavlinux (ok) on 14-Дек-13, 19:44
	>>> это "intelligent". >> Топикстартер видимо без зачёта на новый год уйдет. :) > Почему же? Решение готовое я ему дал, что прокачать, чтобы самому такое > решать -- тоже написал, даже литературу посоветовал. Что такое динамическое программирование > ему вроде тоже тут объяснили. Что смогли -- сделали. Зачётная сессия состоит минимум из 4 экзаменов и 6-8 зачётов. Сессия - это 4 экзамена + хвосты с зачётной сессии. Сюда не ходят те, кому нужны советы. Сюда за готовым решением приходят.
	Ответить \| Правка \| ^ к родителю #37 \| Наверх \| Cообщить модератору