Перейти к содержимому

Фото
- - - - -

Algoritm zada4i )


  • Вы не можете создать новую тему
  • Please log in to reply
45 ответов в этой теме

#31 StаPet

StаPet
  • Постоялец
  • 849 сообщений

Отправлено 19 Октябрь 2005 - 20:37

DTGgirl, решать должен комп а не ты...

ты просто можешь задать данные
и решить сама - своим методом подбора

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

математику знать хорошо надо
особенно приветствуется аналитический склад ума...
  • 0

#32 Warvick

Warvick
  • Пользователь
  • 411 сообщений
  • Откуда:Tallinn

Отправлено 19 Октябрь 2005 - 20:44

Весь алгоритм написан в ссылке.
Он конечно адаптирован под пролог, потому что такого рода задачи на нём и решаются, но я думаю, разобраться можно. Советую посмотреть приводимый там полный код(ссылчка там имеется)
Тебе только расширить туда условия carry с привинченным r(там 1<=r<2)
и newstate ещё state(M3, C3, Boat) добавить.. вроде и всё...
  • 0
Да, я такой!

#33 G.I.A.

G.I.A.
  • Пользователь
  • 203 сообщений

Отправлено 19 Октябрь 2005 - 20:44

$t@P3t,
да я согласна что комп должен решать, тока вот я вот смарю этот вариант с 14 человеками и не получается (
  • 0

#34 StаPet

StаPet
  • Постоялец
  • 849 сообщений

Отправлено 19 Октябрь 2005 - 20:53

DTGgirl, прибавляй людей тогда получится.
  • 0

#35 G.I.A.

G.I.A.
  • Пользователь
  • 203 сообщений

Отправлено 19 Октябрь 2005 - 20:56

$t@P3t,
куда прибавлять? нужно же учитывать, скока на берегу остается людей с каннибалами.. и причем на одно и на другой стороне )
  • 0

#36 StаPet

StаPet
  • Постоялец
  • 849 сообщений

Отправлено 19 Октябрь 2005 - 21:08

прибавля к общему количеству

типа 9 людей и 7 проглотов...
и решай

не решается - ещё прибавляй...

проглотов пускай останется 7...

или возми мой вариант

naprimer v lodku vmeshaetsja 5max из гих 2 должно грести...
dano 7m 5n
bereg 1 - 5m 3n v lodke 2m 2n - bereg2 2m 2n - lodka obratno 1n - bereg2 2m 1n
bereg 1 - 5m 4n v lodke 3m 2n - bereg2 5m 3n - lodka obratno 2m - bereg2 3m 3n
bereg 1 - 4m 2n v lodke 3m 1n - bereg2 7m 4n - lodka obratno 1m - bereg2 6m 4n
bereg 1 - 1m 1n v lodke 1m 1n - bereg2 7m 5n - lodka oratno 0m 0n


  • 0

#37 G.I.A.

G.I.A.
  • Пользователь
  • 203 сообщений

Отправлено 19 Октябрь 2005 - 21:15

$t@P3t,
спасибо тебе большое :-)
  • 0

#38 StаPet

StаPet
  • Постоялец
  • 849 сообщений

Отправлено 19 Октябрь 2005 - 21:24

да пожалуйста
  • 0

#39 Warvick

Warvick
  • Пользователь
  • 411 сообщений
  • Откуда:Tallinn

Отправлено 20 Октябрь 2005 - 10:17

Сейчас подумаю,
Если не влом, скинь своё видение.
Таки интересно.

DTGgirl,
Если нетрудно, отрапортуй от результатах сюда тоже
:)
  • 0
Да, я такой!

#40 ParadoxL

ParadoxL
  • Постоялец
  • 4 756 сообщений
  • Откуда:Edinburg

Отправлено 20 Октябрь 2005 - 13:09

Если будет еще нужно ... пишите. Как буду у компа, то напишу то что треба.
  • 0
Victoria nulla est, Quam quae confessos animo quoque subjugat hostes ...
Верю в смерть после жизни, любовь после секса и в крем после бритья ...

#41 Warvick

Warvick
  • Пользователь
  • 411 сообщений
  • Откуда:Tallinn

Отправлено 21 Октябрь 2005 - 13:58

CyBurglar,
кидай, кидай, интересно таки :)
ещё интересней скорость работы такой программы. попробую реализовать, когда будет время.

Сообщение изменено: Warvick (21 Октябрь 2005 - 13:59 )

  • 0
Да, я такой!

#42 ParadoxL

ParadoxL
  • Постоялец
  • 4 756 сообщений
  • Откуда:Edinburg

Отправлено 24 Октябрь 2005 - 14:41

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

-- Строим матрицу переходов М(X*Y*Z).
х - людоеды.
y - миссионеры.
z - лодка слева(L) или справа® (берег)
т.е. определяется конечное число состояний, одно из состояний принимается за начальное и одно или несколько состояний определяются как искомое - терминальное. Каждый элемент матрицы М является тройкой М=(x,y,z) (читать как состояние). Итак, начальное состояние М0=(5,5, L ) и терминальное состояние Мk=(0,0, R ).
-- Заданы правила перехода между группами состояний. Введем понятие действия Д:[u, v]н, где u - число миссионеров в лодке, v - число людоедов в лодке,н - направление движения лодки (R или L).
-- Для каждого М заданы определенные условия допустимости состояний: x >= y;5-x >= 5-y ; u+v <= 2.
-- После этого из текущего М строятся переходы в новые состояния М(2,0)R...(1,1)R ... (0,1)R (обратите внимание на положение лодки).
-- Убираются все М, где наблюдется нарушение условий допустимости (миссионеры будут съедены). После первого хода остается новых состояния.
-- Далее использую бактрэкинг находится наибольший шаг связаного графа.

И всё. И пость хоть миллион надо будет перевести.


Добавлено в [mergetime]1130157680[/mergetime]
Warvick, афтару программа не нужна. Афтору нужна теория.
  • 0
Victoria nulla est, Quam quae confessos animo quoque subjugat hostes ...
Верю в смерть после жизни, любовь после секса и в крем после бритья ...

#43 Warvick

Warvick
  • Пользователь
  • 411 сообщений
  • Откуда:Tallinn

Отправлено 24 Октябрь 2005 - 16:41

CyBurglar,
Ну я всё себе так и представлял. Сказал бы сразу что с помощью графа тоже решал бы :), а то я уже слюни распустил на нетривиальное решение.
А программу интересно уже мне реализовать, вот только с IDE под Яву разберусь и в путь.. :))

только

u+v <= 2

не понял.

Сообщение изменено: Warvick (24 Октябрь 2005 - 16:44 )

  • 0
Да, я такой!

#44 ParadoxL

ParadoxL
  • Постоялец
  • 4 756 сообщений
  • Откуда:Edinburg

Отправлено 26 Октябрь 2005 - 11:46

Warvick, по условию в ложке может помещаться до двух человек ... что и выражается через u+v <= 2
  • 0
Victoria nulla est, Quam quae confessos animo quoque subjugat hostes ...
Верю в смерть после жизни, любовь после секса и в крем после бритья ...

#45 Warvick

Warvick
  • Пользователь
  • 411 сообщений
  • Откуда:Tallinn

Отправлено 26 Октябрь 2005 - 11:52

CyBurglar,
где до 2? скорее r<=u+v<=p
может помещаться от r(минимум гребцов) до p(максимум пассажиров)
ну да ладно, это уже детали...
  • 0
Да, я такой!

#46 ParadoxL

ParadoxL
  • Постоялец
  • 4 756 сообщений
  • Откуда:Edinburg

Отправлено 26 Октябрь 2005 - 12:02

Warvick, ну да. Я просто невнимательно читал условия ... все едино решается также.
  • 0
Victoria nulla est, Quam quae confessos animo quoque subjugat hostes ...
Верю в смерть после жизни, любовь после секса и в крем после бритья ...