Войти
ФлеймФорумПрограммирование

Задачки с собеседований!

Страницы: 1 2 310 11 Следующая »
#0
20:00, 18 авг. 2017

Сабж. Делимся задачками, обсуждаем решения. Начну с задачки, которую я не решил.

Есть поле n*n, состоит из значений - высоты. Ты стоишь в верхнем левом углу, твоя цель находится в правом нижнем. Можно шагать по вертикали и горизонтали - за каждый твой шаг поле заливается водой на одну единицу высоты. По воде ходить нельзя. После первого шага непроходимыми становятся клетки со значением 1, после второго - 2, после третьего - три и так далее.
Задача - разработать алгоритм, который за полиномальное время ответит, можно ли пройти от начала до цели за m ходов.

Формулировка задачи подсказывает, что нужно испольовать методы динамического программирования, но что конкретно и как делать - я растерялся.


#1
20:16, 18 авг. 2017

Полиномиальное? Это N, NlogN и N^a?
1) Решить задачу с "невозвращением" и "без затопления". Если ты вернулся на клетку, в которой уже был, то это уже цикл. И можно просто пройтись DFS/BFS и посчитать, что пришли за меньше, чем m. Можно начало поставить 0, и остальные клетки ++i. И если i == m и не пришли, то return false.
2) Разрулить с затоплениями.

#2
20:21, 18 авг. 2017

В первом приближении я бы использовал модифицированный волновой алгоритм.

#3
20:22, 18 авг. 2017

Обсуждение не под спойлером?
Так вроде вчистую волновой алгоритм.
Даже и модифицировать  разве что условие проходимости.

#4
20:25, 18 авг. 2017
+ Показать
#5
20:29, 18 авг. 2017

beejah

Кстати да, если от цели идти обратно тут можно быстрее сделать.

#6
20:41, 18 авг. 2017

dave
По другому и не получится, скорее всего.

#7
20:42, 18 авг. 2017

пишешь симулятор мира, а потом строишь дерево состояний мира проверяя каждое новое состояние на соответствие терминальному. если найдено, то сверяешь длину пути до корня с m. ну и растить дерево дальше m смысла нет.

#8
20:54, 18 авг. 2017

Adler
> пишешь симулятор мира
Не, это задача для матрицы из n*n транспьютеров, плюс пара линеек по бокам для особо одаренных.

#9
20:55, 18 авг. 2017

HotkeyM
> поле n*n, состоит из значений - высоты. Ты стоишь в верхнем левом углу, твоя цель находится в правом нижнем
> После первого шага непроходимыми становятся клетки со значением 1
То есть уже после первого шага поле с целью, находящееся в правом нижнем углу, становиться не проходимым. То есть поле достижимо только, если n = 1 и m >= 0

Мой алгоритм отвечает за полиномиальное время. За О(1)

Давай следующую

#10
21:14, 18 авг. 2017

beejah
А всё-таки, чем прямой волновой алгоритм не подходит?
http://rextester.com/COSPE47345

O(n^2), что оптимально.

#11
21:22, 18 авг. 2017

FordPerfect

Так задумано?

if(vx>=0&&vx<n&&vy>=0&vy<n)
#12
21:28, 18 авг. 2017

dave
Я бы && отделил пробелами (заодно сразу видно будет), а < отделять бы не стал, потеряется выразительность. Из-за этого я не люблю, когда кодостайл в этом плане слишком жёсткий. У нас на работе везде пробелы надо пихать, например.

#13
21:29, 18 авг. 2017

dave
Задумано &&.
Опечатка.

Но работает вроде правильно.

#14
22:20, 18 авг. 2017

Задачки — фигня. Я спрашиваю в каких случаях выгоднее применять ООП, а в каких ФП.

Страницы: 1 2 310 11 Следующая »
ФлеймФорумПрограммирование

Тема в архиве.