@Xhunty

Вот опять зашёл в тупик Такая задача: Создать отношение, реализующее функцию M(n,k)
так что M(n,k)=0 при n,k<0, M(0,0)=1.
M(n,k)=k*M(n-1,k)+k*M(n-1,k-1).

Вот что-то не получается раскрутить эту функцию

0

@Грымзик

1

@Xhunty

Хм, Что то не получается заставить её работать нормально(

0

@Xhunty

вот, получилось
вроде всё хорошо, но в задании написано высчитать m(1000,500).
На что выдаёт ошибку переполнения стека, как быть?(

0

@Грымзик

Я даже дождаться этого сообщения не смогла.
Если SWI Prolog, то там можно задавать размеры стека через Settings->Stack sizes

0

@Xhunty

Увеличение размера стека не помогло. Препод сказал что нужно самому что нить придумать что бы сделать m(1000,500). Но у меня что то даже мыслей нет по этому поводу. Да и почему то m(6,2) считает а m(2,6) уже не считает, как доработать?. Но самая главная проблема это со стеком. В каком направлении хоть мыслить, что б уместить столь огромное число.

0

@Грымзик

Что сделать для ускорения пока не знаю. А вот m(2,6) считается правильно, там действительно 0.

0

@Xhunty

ну тут скорее дело не в ускорении, а в том как хранить такое огромное число. ведь при m(10,5) уже
5103000.

0

@Грымзик

Нет, дело не в этом, SWI Prolog с огромными числами может работать.

0

@Xhunty

m(4,1)
k m1 k m2
1*1 + 1*0
____________
m(4,2)
k m1 k m2
1*1 + 1*0
2*6 + 2*1
____________
m(4,3)
k m1 k m2
1*1 + 1*0
2*6 + 2*1
3*6 + 3*6
____________
m(4,4)
k m1 k m2
1*0 + 1*1
2*0 + 2*1
3*0 + 3*2
4*0 + 4*6
____________
m(5,1)
k m1 k m2
1*1 + 1*0
_____________
m(5,2)
k m1 k m2
1*1 + 1*0
2*14 + 2*1
_____________
m(5,3)
k m1 k m2
1*1 + 1*0
2*6 + 2*1
3*36 +3*14
______________
m(5,4)
k m1 k m2
1*1 + 1*0
2*2 + 2*1
3*6 + 3*6
4*24 + 3*36
_______________
m(5,5)
k m1 k m2
1*0 + 1*1
2*0 + 2*1
3*0 + 3*2
4*0 + 4*6
5*0 + 5*24
__________________
******************************
Собственно вот так формируется ответ при m(n,k).
Можно ли при думать такую формулу, которая в зависимости от n и k формировала такой же ответ какой приводится выше, но только без рекурсии?
Читал про Вывод рекуррентной формулы, Но там надо знать закономерность в формировании ряда, а тут я что то не могу проследить закономерность. Может кто то поможет с формулой, или хоть подскажет закономерность.

0

@Грымзик

Насколько у меня получилось, то если n<k, то результат 0.
Если n=k, то результат n!
Если n>k, то результат (сумма всех чисел от 1 до k)*k!=k*(k+1)*k!/2

Добавлено через 4 минуты
Хотя нет, ошиблась

0

@Xhunty

ну то что, Если n=k, то результат n! и если m(N,1) то 1.
а вот если если n>k, тут не понимаю как.

Добавлено через 4 минуты
результат (сумма всех чисел от 1 до k)*k!=k*(k+1)*k!/2
это выполняется при k=n-1.

0

@Грымзик

Не, вроде тут формулы никакой нету. Я даже не знаю как делать. Там проблема в том, что одно и то же значение по несколько раз высчитывается. Это решается динамическим программированием, но на прологе же нет обращения к элементу по индексу, это всеравно будет очень медленно.

Добавлено через 5 минут
Неужели препод не может подсказать или поменять задание?

0

@Deleten

Препод молчит и улыбается...
У меня тоже на подобии задание M(n,k)=M(n-1,k)+n*M(n-1,k-1).
Было еще 3е подобное, но к нему формулу подобрали и посчитали ответ где-то знаков 50-70
Ну вот с эти 2мя оставшимися вообще ничего сделать не можем...

Добавлено через 3 часа 49 минут
хотя там формула тоже неверная и ответ неправильный, но прокатила...

0

@Грымзик

Сделала, надо использовать динамическое программирование, только тут не в массиве промежуточные результаты хранятся, а в базе данных.
m(1000,500) у меня считает секунд 5. Только вот мне первая строчка не нравиться, глупо сначала удалять из базы элемент, а потом его снова возвращать, но на просто b(N,K,M) выдается ошибка, что такого предиката нет.
Deleten, я думаю, что Вы сможете написать аналогично.

Добавлено через 10 минут
С изъятием элемента из базы вопрос решился
И считается больше 5 секунд, это просто до этого были запущены не такие огромные тесты и база частично заполнилась. А если сразу с all(1000,500,M) начинать, то где-то полминуты наверно.

2

@Xhunty

Нет слов, одни эмоции ^_^ Спасибо наиогромнейшее! Даже не знаю как и благодарить.
С базами не приходилось сталкиваться, поэтому некоторые моменты пока не понятны.
на сколько я понял:
или другими словами как это работает =)

0

@Грымзик

После assert(b(1,2,3)) будет все то же самое, как если бы я изначально прописала b(1,2,3) в программе.
Поскольку в данной программе рекурсия устроенна так, что значение функции M при одной и той же паре параметров будет запрашиваться несколько раз, то это значение надо сохранять. Поэтому первым делом проверяется не было ли оно уже вычислено m(N,K,M):-b(N,K,M),!. Если же оно не было еще вычислено, то делаем это и заносим в базу assert(b(N,K,Ans)).

all(N,K,M):-assert(b(0,0,1)),m(N,K,M). Это нужно только потому, что если бы у нас еще не было занесено в базу ни одного факта b, то при первой же попытке выполнить правило m(N,K,M):-b(N,K,M),!. выдавалась бы ошибка, что предиката b не существует. Поэтому мы сначала заносим один факт, и только потом вызываем наш главный предикат вычисления функции.

2

maxbestua

поставили задание решить вот такую задачу.... Может кто поможет. Заранее благодарен!!!!