Warning: Cannot use a scalar value as an array in /home/admin/public_html/forum/include/fm.class.php on line 757

Warning: Invalid argument supplied for foreach() in /home/admin/public_html/forum/include/fm.class.php on line 770

Warning: Invalid argument supplied for foreach() in /home/admin/public_html/forum/topic.php on line 737
Форумы портала PHP.SU :: Задача № 1. Лабиринт

 PHP.SU

 Программирование на PHP, MySQL и другие веб-технологии
PHP.SU Портал     На главную страницу форума Главная     Помощь Помощь     Поиск Поиск     Поиск Яндекс Поиск Яндекс     Вакансии  Пользователи Пользователи


 Страниц (1): [1]   

> Без описания
Поиск в теме | Версия для печати
valenok Модератор
Отправлено: 04 Сентября, 2007 - 19:38:02
Post Id



Здесь могла бы быть ваша реклама


Покинул форум
Сообщений всего: 4574
Дата рег-ции: Июль 2006  
Откуда: Israel


Помог: 3 раз(а)
Далее задачка в основном не на знание языка, а на умение программировать, думать, не давать серым клеткам помирать..
Принимаются любые варианты, теории, гипотезы и ответы.
Призов нет, но тем не менее чем короче код, читабельней, понятней - тому плюс.

И так у вас есть файл содержащий текстовую картинку лабиринта

(текстовый файл прилагается)

Нужно дойти из точки а в точку б
Что такое дойти - написать путь, координаты клеток в которых вы проходите.

Пожалуйста публикуйте ваш код при помощи сервиса .

(для продвинутых своего рода - найти кратчайший путь.)

* ещё прохода из а в б может и не быть. (в данном примере есть)
Скрипт должен работать и с другим примером, так что скрипт типа
PHP:
скопировать код в буфер обмена
  1.  
  2. <?PHP
  3. echo "(2,2) (2,3) (2,4) ..";
  4.  

это не то что мы ищем ..

Удачи.
Скачать файл: 1.txt
Скачан раз: 244


-----
Truly yours, Sasha.
 
My status
 Top
Zeta-johns
Отправлено: 05 Сентября, 2007 - 14:41:25
Post Id



Новичок


Покинул форум
Сообщений всего: 12
Дата рег-ции: Июль 2007  
Откуда: Deutschland, Plauen


Помог: 0 раз(а)

[+]
сначала пусть попытаются решить простенькую задачу, которую нам давали на треньках по подготовке к олимпиаде по программированию.
скажем, даны переменные a и b. нужно поменять значения переменных не используя при этом третьей переменной.

подумайте. интересная задачка! Закатив глазки


-----
Amy Lee ab jetzt in Vogtland
 
 Top
valenok Модератор
Отправлено: 05 Сентября, 2007 - 14:45:37
Post Id



Здесь могла бы быть ваша реклама


Покинул форум
Сообщений всего: 4574
Дата рег-ции: Июль 2006  
Откуда: Israel


Помог: 3 раз(а)
Слишком просто помоему.
А если они имеют стрококовой формат - слабо?
А что за олимпиада такая? У нас в школе сложнее были ..


-----
Truly yours, Sasha.
 
My status
 Top
Zeta-johns
Отправлено: 05 Сентября, 2007 - 15:06:59
Post Id



Новичок


Покинул форум
Сообщений всего: 12
Дата рег-ции: Июль 2007  
Откуда: Deutschland, Plauen


Помог: 0 раз(а)

[+]
valenok
valenok пишет:
Слишком просто помоему.

раз вы так сказали, хотелось бы увидеть решение... слова на ветер не бросаем! ;)
valenok пишет:
А что за олимпиада такая? У нас в школе сложнее были .

это была первая задачка для новичков. в те года когда мне впервые выдали эту задачку, потратил я немало времени на ее решение. ... о вот собственно и ссылка на сайт, где мы тренируемся www[dot]olymp[dot]krsu[dot]edu[dot]kg ... кроме него посещаю часто Саратовский АСМ и Алтайский Улыбка


-----
Amy Lee ab jetzt in Vogtland
 
 Top
valenok Модератор
Отправлено: 05 Сентября, 2007 - 18:01:39
Post Id



Здесь могла бы быть ваша реклама


Покинул форум
Сообщений всего: 4574
Дата рег-ции: Июль 2006  
Откуда: Israel


Помог: 3 раз(а)
Решение задачи с переменными



Для того чтобы не показывать код желающим подумать самим
я запустил новый "сервис" позволяющий вам загружать свои скрипты
и получать ссылку на их просмотр


-----
Truly yours, Sasha.
 
My status
 Top
evgenijj
Отправлено: 05 Сентября, 2007 - 20:19:58
Post Id



Участник


Покинул форум
Сообщений всего: 1212
Дата рег-ции: Авг. 2006  
Откуда: Москва


Помог: 10 раз(а)
valenok пишет:
Слишком просто помоему.
А если они имеют стрококовой формат - слабо?


Скачать файл: ab.txt
Скачан раз: 250
 
 Top
valenok Модератор
Отправлено: 05 Сентября, 2007 - 21:07:02
Post Id



Здесь могла бы быть ваша реклама


Покинул форум
Сообщений всего: 4574
Дата рег-ции: Июль 2006  
Откуда: Israel


Помог: 3 раз(а)
А мне такой вариант пришёл в голову после постановки задачи смены значений строковых переменных.


-----
Truly yours, Sasha.
 
My status
 Top
Джур
Отправлено: 06 Сентября, 2007 - 06:47:54
Post Id



Посетитель


Покинул форум
Сообщений всего: 423
Дата рег-ции: Март 2007  


Помог: 0 раз(а)
Цитата:
Пожалуйста пишите в начале сообщения жирным шрифтом что следует в сообщении, для того чтобы не открывать ответ желающим.

что имелось в виду совершенно не ясно, поэтому придется код выкладывать так:
http://flower2[dot]info/phpsu/files/[dot][dot][dot]160446248_50[dot]txt


-----
Тамбовский каджит тебе товарищ
 
 Top
EuGen Администратор
Отправлено: 07 Сентября, 2007 - 18:25:31
Post Id


Профессионал


Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)
предлагаю решить методом обобщения:
1.Завести матрицу размерности NxM (по размерностям лабиринта)
2.Заполнять ее значениями: 1 для свободных клеток и X для занятых, где X равно числу свободных клеток
3.Находить путь из (A) в (B) так, чтобы сумма, накапливаемая во время прохода из значений в клетках была минимальна.
4. Задача '3.' решается общеизвестным методом динамического программирования.
5. В силу постановки '3.' будет найден не только какой-то путь из (A)в (B), но и, более того, кратчайший путь.
6. Если полученная сумма значений для найденного пути больше, чем X, то это значит, что найденный путь пролегает через занятую клетку и таким образом задача не имеет решения.

(Добавление)
PHP:
скопировать код в буфер обмена
  1.  
  2. <?
  3. $a="jsdlfkjsdf";
  4. $b="835kdfngdfg";
  5. echo("a is: $a; b is: $bn");
  6. $a=$a ^ $b;
  7. $b=$a ^ $b;
  8. $a=$a ^ $b;
  9. echo("a is: $a; b is: $b");
  10. ?>
  11.  

вот кстати решение задачки с обменом переменных для любых типов данных.. я потратил на ее решение ровно столько времени, сколько мне потребовалось вспомнить, как в PHP вычисляется XOR для двоичного представления переменных.. (около 3 мин.)
Умышленно не приводил переменные к типу строк (чтобы работало для случая разнотиповых переменных), чтобы простота была виднее..
валенок - замечу, что ваш метод решения здесь не подойдет, так как вы неявно используете третью переменную - массив, возвращаемый функцией ... хотя, если не считать структуру из начальных переменных отдельной переменной, ваш метод корректен.


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
valenok Модератор
Отправлено: 07 Сентября, 2007 - 23:07:42
Post Id



Здесь могла бы быть ваша реклама


Покинул форум
Сообщений всего: 4574
Дата рег-ции: Июль 2006  
Откуда: Israel


Помог: 3 раз(а)
Решение задачи № 1[dot] Лабиринт

(Добавление)
Мне понравилась теория:

3. Находить путь из (A) в (B) так, чтобы сумма, накапливаемая во время прохода из значений в клетках была минимальна.
4. Задача '3.' решается общеизвестным методом динамического программирования.

Динамическое программирование:
Совокупность приемов, позволяющих находить оптимальные решения (вычисляются последствия каждого решения и вырабатываются оптимальные стратегии для последующих решений).

В переводе звучит так: найти все решения, потом проверить какое самое эффективное

Правильно я понимаю?


(Добавление)
Что касается замены переменных
значени возвращаемое функцие можно записывать не в третюю область памяти
а в тот же самый $b
и получается тоже самое что у Евгения

А вот с XOR мне понравилось
в первый раз вижу такое решение
+


-----
Truly yours, Sasha.
 
My status
 Top
red-alex
Отправлено: 08 Сентября, 2007 - 09:36:54
Post Id



Новичок


Покинул форум
Сообщений всего: 3
Дата рег-ции: Сент. 2007  


Помог: 0 раз(а)
Ну тут вроде бы просто обход графа в ширину...И все.
 
 Top
Джур
Отправлено: 10 Сентября, 2007 - 07:01:44
Post Id



Посетитель


Покинул форум
Сообщений всего: 423
Дата рег-ции: Март 2007  


Помог: 0 раз(а)
топик - офтопик... начали с одной задачи, а закончили задачей про переменные... Улыбка


-----
Тамбовский каджит тебе товарищ
 
 Top
EuGen Администратор
Отправлено: 10 Сентября, 2007 - 09:25:07
Post Id


Профессионал


Покинул форум
Сообщений всего: 9095
Дата рег-ции: Июнь 2007  
Откуда: Berlin


Помог: 707 раз(а)
valenok - нет, динамическое программирование состоит как раз в том, чтобы построить оптимальное решение, а не перебирать все возможные, в этом его изюминка и скорость работы. Если интересно, то я могу привести полное решение задачи обхода матрицы с набором минимального/максимального числа очков методом динамического программирования.


-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.
 
 Top
valenok Модератор
Отправлено: 10 Сентября, 2007 - 18:27:11
Post Id



Здесь могла бы быть ваша реклама


Покинул форум
Сообщений всего: 4574
Дата рег-ции: Июль 2006  
Откуда: Israel


Помог: 3 раз(а)
EuGen, Очень интересно =)


-----
Truly yours, Sasha.
 
My status
 Top
Поиск в теме | Версия для печати
Страниц (1): [1]
Сейчас эту тему просматривают: 0 (гостей: 0, зарегистрированных: 0)
« Программирование на PHP »


Все гости форума могут просматривать этот раздел.
Только зарегистрированные пользователи могут создавать новые темы в этом разделе.
Только зарегистрированные пользователи могут отвечать на сообщения в этом разделе.
  



Powered by PHP  Powered By MySQL  Powered by Nginx  Valid CSS  RSS

 
Powered by ExBB FM 1.0 RC1. InvisionExBB