Вычисление биномиального коэффициента

@iduchev · Регистрация: 15.10.2017

Студворк — интернет-сервис помощи студентам

Prolog
1
2
3
4
5
6
7
8
9
10
bc(0,N,R,R):- N>0,R is 1,!.
bc(M,0,R,R):- M>0,R is 1,!.
bc(N,N,R,R):- R is 1,!.
 
bc(M,N,R,R1):- 
    M1 is M - 1, 
    N1 is N - 1, 
    bc(M1,N1,R,R2),
    bc(M1,N,R,R3),
    R1 is R2+R3.

Я в Прологе ещё пока что только начинаю, поэтому не могу понять, почему оно возвращает false?
Запускаю не в программе, а в онлайн компиляторе. Помогите, пожалуйста, понять, в чём проблема.

Само задание звучит так:
Напишите рекурсивную процедуру C(M,N) (0 ≤ m ≤ n ) для вычисления биноминального коэффициента по формуле:
C(m,0)=C(n,0)=C(n,n)=1
C(m,n)=C(m−1,n−1)+C(m−1,n)

@Case-Man · 10.11.2017, 07:08

Сообщение от iduchev

Я в Прологе ещё пока что только начинаю

Начинать надо с понимания, а не с шаманства и алхимии.
Зачем в предикате 4 параметра?

@Catstail · 10.11.2017, 11:19

Вот расчет сразу всех биномиальных коэффициентов для заданного n:

Prolog
1
2
3
4
5
6
7
8
9
10
11
12
13
14
domains
int=integer
intl=int*
 
predicates
next(intl,intl)
combl(int,intl)
 
clauses
next([X],[X]).
next([H1,H2|T],[H|Q]) :- H=H1+H2, next([H2|T],Q).
 
combl(1,[1,1]).
combl(N,C):- N1=N-1, combl(N1,C1), next(C1,CC), C=[1|CC].

@iduchev · 10.11.2017, 11:53 **[ТС]**

4 параметра затем: 1 - M, 2 - N, 3 - результат, 4 - частный результат.
Мне надо искать именно по той формуле и именно один бином коэф. M и N это не от и до, а числа, которые пишутся справа сверху и снизу от C.

@Case-Man · 10.11.2017, 13:49

Сообщение от iduchev

4 параметра затем: 1 - M, 2 - N, 3 - результат, 4 - частный результат.

Вот проблема у Вас в том, что Вы не понимаете, чтто такое частный результат и для чего он нужен.
То есть Ваш код построен для работы БЕЗ частного результата, а в парметрах этот частный результат зачем-то есть.

Давайте чуть подробнее.

Если рекурсия без частного результата, то при погружении в рекурсию до самого дна никакого результата вообще нет.
На дне рекурсии возникает первый результат.
И начинается всплытие - на основе результата более глубокого шага рекурсии вычисляется текущий резкльтат.

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

Но вот беда: такой подход применим только при линейной рекурсии. Ваша же рекурсия нелинейна. Можно её линеаризовать, вычисляя не одно число треугольника, а какую-то строчку сразу - горизонтальную или параллельную полосе. Но не уверен, что это Вам нужно. Значит, остаётся забыть про аккумулятор, хвостовую рекурсию и сделать "в лоб".

Prolog
1
2
3
4
5
6
7
8
9
bc(_,0,1):- !.
bc(N,N,1):- !.
 
bc(M,N,R):-
    M1 is M - 1,
    N1 is N - 1,
    bc(M1,N1,R1),
    bc(M1,N,R2),
    R is R1+R2.

@iduchev · 10.11.2017, 15:41 **[ТС]**

Понял, спасибо

Новые блоги и статьи Все статьи Все блоги /
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .	Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .

@iduchev 0 / 0 / 0 Регистрация: 15.10.2017 Сообщений: 12
	10.11.2017, 11:53 [ТС]
	4 параметра затем: 1 - M, 2 - N, 3 - результат, 4 - частный результат. Мне надо искать именно по той формуле и именно один бином коэф. M и N это не от и до, а числа, которые пишутся справа сверху и снизу от C. 0

@iduchev 0 / 0 / 0 Регистрация: 15.10.2017 Сообщений: 12
	10.11.2017, 15:41 [ТС]
	Понял, спасибо 0

Вычисление биномиального коэффициента

Решение