Heroes League

Lord Ts · 19 окт 2004, 20:19Сообщение

Еще одна корректировка. Первое решение работает если известно исходное состояние лампы (не прочитал пост Смерти). Общее решение - один зэк только включает, а другие выключают первые 2 раза. Включающий зэк рапортует, насчитав 197 выключений (2х98+1).

Horn · 19 окт 2004, 21:08Сообщение

Lord Ts писал(а):Еще одна корректировка. Первое решение работает если известно исходное состояние лампы (не прочитал пост Смерти). Общее решение - один зэк только включает, а другие выключают первые 2 раза. Включающий зэк рапортует, насчитав 197 выключений (2х98+1).

Уж больно неэффективно получается. А если его только 196 раз посадят, а больше не будут?

to СМЕРТЬ:
А никакого подвоха тут нет? Лампочку нельзя трогать, выворачивать и т.п.? И еще, могут какое-то время никого не сажать в карцер или каждый день кто-то сидит?

Artemis K. · 19 окт 2004, 21:36Сообщение

To Horn

напиши плиз в чем заключается метод флойда, а то я в инете его найти не могу

Artemis K. · 19 окт 2004, 21:37Сообщение

ой сорри это к СМЕРТИ вопрос

Chameleon · 19 окт 2004, 21:45Сообщение

Horn писал(а):А никакого подвоха тут нет? Лампочку нельзя трогать, выворачивать и т.п.? И еще, могут какое-то время никого не сажать в карцер или каждый день кто-то сидит?

Подвохов нет. Все время кто-то сидит. Решение не очень эффективное, но правильного и полного алгоритма у нас на форуме я еще не видел

Chameleon · 19 окт 2004, 21:55Сообщение

Artemis K. писал(а):напиши плиз в чем заключается метод флойда, а то я в инете его найти не могу

Смысл, да смысл вроде понятен. Всего то три цикла и два условия. Эффективность - кубическая. Думаю сам разберешься, вот код программы на СРР:

Код: Выделить всё

/*  метод Флоида*/

#include<fstream.h>
int i,j,w,n;
int a&#91;20&#93;&#91;20&#93;;

void main &#40;&#41;
&#123;
ifstream f1&#40;"input.txt"&#41;;
ofstream f2&#40;"output.txt"&#41;;
f1>>n;                      //количество вершин
//СЧИТЫВАHИЕ МАТРИЦЫ СМЕЖHОСТИ
for&#40;i=1;i<=n;i++&#41;
 for &#40;j=1;j<=n;j++&#41;
  &#123;
   f1>>a&#91;i&#93;&#91;j&#93;;
   if&#40;&#40;a&#91;i&#93;&#91;j&#93;==0&#41;&&&#40;i!=j&#41;&#41; a&#91;i&#93;&#91;j&#93;=9999;
  &#125;

//ФЛОИД
 for&#40;w=1;w<=n;w++&#41;
   for&#40;i=1;i<=n;i++&#41;
     for&#40;j=1;j<=n;j++&#41;
       if&#40;&#40;i!=j&#41;&&&#40;i!=w&#41;&&&#40;j!=w&#41;&#41;
	 if&#40;a&#91;i&#93;&#91;j&#93;>a&#91;i&#93;&#91;w&#93;+a&#91;w&#93;&#91;j&#93;&#41; a&#91;i&#93;&#91;j&#93;=a&#91;i&#93;&#91;w&#93;+a&#91;w&#93;&#91;j&#93;;

//ВЫВОД РЕЗУЛЬТАТА
for&#40;i=1;i<=n;i++&#41;
 &#123;
  for &#40;j=1;j<=n;j++&#41; f2<<a&#91;i&#93;&#91;j&#93;<<" ";
  f2<<"\n";
 &#125;

f1.close&#40;&#41;;
f2.close&#40;&#41;;
&#125;

Horn · 19 окт 2004, 22:01Сообщение

Artemis K. писал(а):ой сорри это к СМЕРТИ вопрос

Да можно и ко мне

, только ты лучше задачу скажи. А то с этими Флойдами, Фордами, Фалкерсонами черт ногу сломит

, каждая книжка обзывает по-своему.
Надо найти min путь в графе? Ориентированном или нет? Или нужен max поток в сети?
Пока писал, СМЕРТЬ крылатый уж ответил.

Тока С++ читать, если его не юзал - то еще удовольствие...

Chameleon · 19 окт 2004, 22:37Сообщение

Horn писал(а):Тока С++ читать, если его не юзал - то еще удовольствие...

Учи мат. часть

frodo · 20 окт 2004, 10:26Сообщение

Horn писал(а):Тока С++ читать, если его не юзал - то еще удовольствие...

Осбенно когда написано не по стандарту ANSI...

Chameleon · 20 окт 2004, 10:49Сообщение

frodo писал(а):Осбенно когда написано не по стандарту ANSI...

Студенты нынче с ним плохо знакомы

Artemis K. · 20 окт 2004, 18:45Сообщение

To Horn

задача заключается в том что надо найти кратчайший путь между 2 точками в 3-мерном лабиринте...

но следует учитывать что лабиринт 100*100*10, т.е. при переводе его в граф получается 100000 вершин и будет ли метод флойда или дейкстры эффективнее ПП неизвестно...

я слышал что есть какой-то алгоритм волнового обхода - в чем он заключается и можно ли его применить к данной задаче?

P.S.
To All

не пишите плиз проги а лучше приведите мат.описание, тем более что я си не знаю...

Hoher · 20 окт 2004, 20:59Сообщение

Lord Ts писал(а):Еще одна корректировка. Первое решение работает если известно исходное состояние лампы (не прочитал пост Смерти). Общее решение - один зэк только включает, а другие выключают первые 2 раза. Включающий зэк рапортует, насчитав 197 выключений (2х98+1).

Прошлая корректировка была мне кажется ближе к цели.
1) Есть Пахан - только он выключает лампочку и считает сколько раз он выключил.
2) Все остальные:
Если лампочка горит - ничего не делает.
Если лампочка не горит и он ни разу не включал - включает лампочку
Если лампочка не горит и он включал уже лампочку - то нечего не делает.
3) Как только пахан выключит лампочку в сотый раз он может смело говорить, что в карцере все побывали хотя бы один раз.

Lord Ts · 20 окт 2004, 22:07Сообщение

Как я говорил, этот метод работает только если пахан знает начальное состояние лампы. Потому что, когда он входит в первый раз он не знает, горела ли лампа всегда или ее включил зэк, бывший до него. Если это был зэк, он никогда больше не включит лампу. и насчитав 98 включений пахан не сможет знать будет ли еще 99-е.
Общее решение по этому алгоритму требует, чтобы простые зэки по 2 раза меняли состояние лампы, а пахан отвечал насчитав 197 переключений.

Lord Ts · 20 окт 2004, 22:15Сообщение

Можно предложить алгоритм, когда зэки начинают переключения, только застав лампу не в том положении, в котором она была в первое посещение. Тогда пахан знает, что до него лампу не трогали и может ограничиться 99 переключениями.

Ziplen · 21 окт 2004, 00:21Сообщение

Artemis K. писал(а): я слышал что есть какой-то алгоритм волнового обхода - в чем он заключается и можно ли его применить к данной задаче?

Вполне можно - будет ли эффективнее нескажу - я не математик =)

Попробую описать по памяти на примере двумерного лабиринта
6 х 8 (не бить по голове если ошибусь)
Насколько я понял в лабиринте только два типа полей:
"пустота" и "стена"
при считывании матрицы заполняем "стены" какими-нить большими значениями, а "пустоты' нулями и определяем координаты точек
между которыми нужно найти путь А и Б и присваиваем им значение
1 в итоге получаем такую матрицу(кривовато но думаю понятно):

00 01 00 00 00 99 99
00 99 00 99 00 00 00
99 00 00 00 99 99 00
99 00 99 99 99 99 00
99 00 99 01 00 99 00
99 00 00 00 00 00 00
00 00 99 00 99 99 99
00 99 99 00 00 00 00

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

При нахождении поля с таким значением проводим поиск соседних полей:
если поле 0("пустота"), то записываем в него значение предыдущего + "цену"
если поле 99 ("стена"), пропускаем (осторожнее с значеним стены - оно ни в коем случае не должно быть достигнуто

а то путь скозь стену станет самым короктим =) )
если значение соседнего поля равно или на "цену" больше, значит найдена точка схождения.

после первого прогона получим:

02 01 02 00 00 99 99
00 99 00 99 00 00 00
99 00 00 00 99 99 00
99 00 99 99 99 99 00
99 00 99 01 02 99 00
99 00 00 02 00 00 00
00 00 99 00 99 99 99
00 99 99 00 00 00 00

после третьего:

02 01 02 03 04 99 99
03 99 03 99 00 00 00
99 00 04 00 99 99 00
99 00 99 99 99 99 00
99 00 99 01 02 99 00
99 04 03 02 03 04 00
00 00 99 03 99 99 99
00 99 99 04 00 00 00

после пятого

02 01 02 03 04 99 99
03 99 03 99 05 06 00
99 05 04 05 99 99 00
99 06 99 99 99 99 00
99 05 99 01 02 99 06
99 04 03 02 03 04 05
06 05 99 03 99 99 99
00 99 99 04 05 06 00

найдена точка схождения!

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

Ну а как записывать - это уже дело любителя

Вобще алгоритм этот наиболее эффективен когда не два а намного больше типов полей и за прохождние по ним берутся разные "цены",
тогда и алгоритм чутка посложнее выглядит...

в этом случае приведен упрощенный вариант, количество измерений на применение никаких ограничений не накладывает.. хоть 6-ти мерный лабиринт придумывай

Математика