Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Prolog
Перезагрузить страницу Треугольник Паскаля*
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
Diman545 Diman545 вне форума
Новичок
 
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 02.07.2013
По умолчанию Треугольник Паскаля* - 02.07.2013, 04:13

Всем привет. Есть задачка по прологу, которая строит треугольник паскаля, не могли бы вы объяснить часть кода программы:
prolog Код:
CLAUSES

  % Вычисление значения K-ого элемента N-ой строки; E - результат
    fact(0,0,P):-P=1,!.
    fact(_,0,P):-P=1,!.
    fact(B,B,P):-P=1,!.
    fact(B,M,P):-BM=B-M,M1=M+1,!,mul(B,BM,M1,1,1,P).
    mul(B,NM,B,NM,P,PP):-PP=P*B/NM.
    mul(B,NM,IB,INM,P,P1):-IB1=IB+1,
    !,INM1=INM+1,!,PP=P*IB/INM,!,mul(B,NM,IB1,INM1,PP,P1).
Ответить с цитированием
  (#2 (permalink)) Старый
aag aag вне форума
А.А.Г.
 
Аватар для aag
 
Сообщений: 3,374
Сказал(а) спасибо: 0
Поблагодарили 82 раз(а) в 82 сообщениях
Регистрация: 29.11.2008
Адрес: Адмиралтейская)))
По умолчанию 02.07.2013, 18:09

Вся эта индексация - лишнее. Очередная строка запросто выдёргивается из предидущей:

Visual Prolog Код:
implement main
    open core, console

clauses
    run():-
        init(),
        Size = 14,
        StringS = [ J || J = std::downTo(Size, 0) ],
        First = [1],
        _RowSizePlus1 = list::fold(StringS, {(J,Row) = [1|nextRow(Row)] :- write(J,": ",Row,"\n")}, First),
        write("\n..................................\n"),
        _ = readChar().

class predicates
    nextRow : (integer* Row) -> integer* NextRow.
clauses
    nextRow([A,B|C]) = [A+B|nextRow([B|C])] :-
        !.
    nextRow(_) = [1].

end implement main

goal
    mainExe::run(main::run).


Цитата:
0: [1]
1: [1,1]
2: [1,2,1]
3: [1,3,3,1]
4: [1,4,6,4,1]
5: [1,5,10,10,5,1]
6: [1,6,15,20,15,6,1]
7: [1,7,21,35,35,21,7,1]
8: [1,8,28,56,70,56,28,8,1]
9: [1,9,36,84,126,126,84,36,9,1]
10: [1,10,45,120,210,252,210,120,45,10,1]
11: [1,11,55,165,330,462,462,330,165,55,11,1]
12: [1,12,66,220,495,792,924,792,495,220,66,12,1]
13: [1,13,78,286,715,1287,1716,1716,1287,715,286,78,13, 1]
14: [1,14,91,364,1001,2002,3003,3432,3003,2002,1001,364 ,91,14,1]

..................................


импортирован с progz.ru
Ответить с цитированием
  (#3 (permalink)) Старый
Diman545 Diman545 вне форума
Новичок
 
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 02.07.2013
По умолчанию 03.07.2013, 03:07

Цитата:
Сообщение от aag Посмотреть сообщение
Вся эта индексация - лишнее. Очередная строка запросто выдёргивается из предидущей:

Visual Prolog Код:
implement main
    open core, console

clauses
    run():-
        init(),
        Size = 14,
        StringS = [ J || J = std::downTo(Size, 0) ],
        First = [1],
        _RowSizePlus1 = list::fold(StringS, {(J,Row) = [1|nextRow(Row)] :- write(J,": ",Row,"\n")}, First),
        write("\n..................................\n"),
        _ = readChar().

class predicates
    nextRow : (integer* Row) -> integer* NextRow.
clauses
    nextRow([A,B|C]) = [A+B|nextRow([B|C])] :-
        !.
    nextRow(_) = [1].

end implement main

goal
    mainExe::run(main::run).
А можно пошагово закоментировать)
Ответить с цитированием
  (#4 (permalink)) Старый
aag aag вне форума
А.А.Г.
 
Аватар для aag
 
Сообщений: 3,374
Сказал(а) спасибо: 0
Поблагодарили 82 раз(а) в 82 сообщениях
Регистрация: 29.11.2008
Адрес: Адмиралтейская)))
По умолчанию 03.07.2013, 22:42

Легко:
Цитата:
Каждое число равно сумме двух расположенных над ним чисел.


импортирован с progz.ru
Ответить с цитированием
  (#5 (permalink)) Старый
Diman545 Diman545 вне форума
Новичок
 
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 02.07.2013
По умолчанию 07.07.2013, 13:18

А можно все таки код,который я написал,подробно разъяснить?
Ооочень нужна ваша помощь, препод уже рвет и мечет, а я не могу в коде разобраться.
Цитата:
Сообщение от aag Посмотреть сообщение
Легко:
Цитата:
Каждое число равно сумме двух расположенных над ним чисел.
Если не трудно,то прокомментируй каждую строчку плз..

Последний раз редактировалось Dark King; 07.07.2013 в 15:39
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
Diman545 Diman545 вне форума
Новичок
 
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 02.07.2013
По умолчанию 31.03.2014, 14:12

prolog Код:
mul(B,NM,IB,INM,P,P1):-IB1=IB+1,
    !,INM1=INM+1,!,PP=P*IB/INM,!,mul(B,NM,IB1,INM1,PP,P1).
Народ,кто может рассказать про этот кусок кода, какая рекурсия тут и почему?
Ответить с цитированием
  (#7 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 31.03.2014, 16:10

Вы приводите глючный вариант хорошей программы.
Чтобы была не глючная, надо нормально отсечения поставить:
Visual Prolog Код:
fact(0,0,1):- !.
    fact(_,0,1):- !.
    fact(B,B,1):- !.
    fact(B,M,P):-
        BM=B-M,M1=M+1,    
        mul(B,BM,M1,1,1,P).
   
    mul(B,NM,B,NM,P,PP):- !, PP=P*B/NM.
    mul(B,NM,IB,INM,P,P1):-
        IB1=IB+1,INM1=INM+1,
        PP=P*IB/INM,
        mul(B,NM,IB1,INM1,PP,P1).
Рекурсия здесь хвостовая, восходящая.
Ответить с цитированием
  (#8 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 31.03.2014, 16:38

Предикат mul "в лоб" находит C из N по K: (K+1)*...*N/(N-K)!.
Фактически перемножается N-K дробей: столько сомножителей и в числителе, и в знаменателе.

Элемент треугольника Паскаля по номеру ряда и позиции элемента в ряду с помощью нисходящей рекурсии определить красиво легко, но вычисления далеко не уйдут, это невыгодно.

С помощью восходящей рекурсии приходится считать непосредственно (если иметь только номер ряда и номер элемента в ряду), что и делается в программе.

Другие способы - использовать assert или списки, это просто.

P.S. Первую строчку в программе можно удалить, второй хватает.
Ответить с цитированием
  (#9 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 31.03.2014, 16:57

А что, в Visual Prolog появилась оптимизация нисходящей рекурсии?

Работает очень круто! Не нужно никаких выкрутасов с дробями, которые тут есть.
Ответить с цитированием
  (#10 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 31.03.2014, 17:08

Нет, показалось.
Просто само по себе хорошо работает (и в 5.2 тоже). Но с хвостовой все-таки лучше.
Ответить с цитированием
  (#11 (permalink)) Старый
aag aag вне форума
А.А.Г.
 
Аватар для aag
 
Сообщений: 3,374
Сказал(а) спасибо: 0
Поблагодарили 82 раз(а) в 82 сообщениях
Регистрация: 29.11.2008
Адрес: Адмиралтейская)))
По умолчанию 31.03.2014, 22:57

Цитата:
Сообщение от Alison Посмотреть сообщение
Но с хвостовой все-таки лучше.
Канэшна)))
Кто-то, когда-то, наверное, просто...
Там в листе много и, главное, не совсем понятно зачем так закручено(((
А может я ещё чего не понимаю))))


импортирован с progz.ru
Ответить с цитированием
  (#12 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 01.04.2014, 11:24

В классе list много хороших предикатов, они вполне понятны.

Но очень жаль, что предикат list::fold определен без хвостовой рекурсии. Например, он может найти сумму элементов списка [1 || _ = std::fromTo(1, N)] максимум для N = 23522.

А если его определить с помощью хвостовой рекурсии, то можно дописать 3 нуля:
Visual Prolog Код:
class predicates
    fold: (Elem*, function{Elem, OutElem, OutElem}, OutElem) -> OutElem.
clauses
    fold([], _, A) = A.
    fold([H | T], Fct, A) = fold(T, Fct, Fct(H, A)).

clauses
    run():-
        console::init(),
        L = [1 || _ = std::fromTo(1, 23522000)],
        stdio::write(">\n"),
        Res = fold(L, {(X, S) = X + S}, 0),
        stdio::write(Res), stdio::nl,
        L1 = [1 || _ = std::fromTo(1, 23522)],
        Res1 = list::fold(L1, {(X, S) = X + S}, 0),
        stdio::write(Res1),
        _ = stdio::readLine().
Может быть, это стоит изменить?

Последний раз редактировалось Alison; 01.04.2014 в 11:30
Ответить с цитированием
Ads
  (#13 (permalink)) Старый
SergeMukhin78 SergeMukhin78 вне форума
Member
 
Сообщений: 486
Сказал(а) спасибо: 17
Поблагодарили 33 раз(а) в 33 сообщениях
Регистрация: 28.03.2012
По умолчанию 01.04.2014, 13:14

Цитата:
Сообщение от Alison Посмотреть сообщение
А если его определить с помощью хвостовой рекурсии
1. К сожалению, в этом случае меняется порядок применения, т.е. формально выполнение будет не таким. Хотя в большинстве случаях на это можно не обращать внимание.
2. В свое время мы обсуждали это. Нашел переписку аж 2009 года, они сопротивляются попробую еще раз.
Ответить с цитированием
  (#14 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,771
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 01.04.2014, 18:07

Я тоже давно это заметила.
Мне кажется, что выход может быть простой: надо быстрый fold переименовать, и тот, что есть, тоже оставить. Будет хорошо
Ответить с цитированием
Пользователь сказал cпасибо:
rrrFer (02.04.2014)
  (#15 (permalink)) Старый
SergeMukhin78 SergeMukhin78 вне форума
Member
 
Сообщений: 486
Сказал(а) спасибо: 17
Поблагодарили 33 раз(а) в 33 сообщениях
Регистрация: 28.03.2012
По умолчанию 02.07.2014, 12:33

Цитата:
Сообщение от Alison Посмотреть сообщение
надо быстрый fold переименовать, и тот, что есть, тоже оставить. Будет хорошо
жизнь сама их заставила это сделать!

добавили два предиката foldr и foldl, оба с ТСО
первый работает как и fold но медленней, второй, как Alison советовала.
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
перевести код из паскаля на с++. Киры4 Задания за деньги 1 29.05.2013 19:32
C паскаля на с++ cfexe Вопросы начинающих программистов 3 17.12.2011 01:34
ПОМОГИТЕ перевести с паскаля на С или С++ Ииринка Вопросы начинающих программистов 0 29.04.2011 00:13
Перевести с Паскаля на С++ =Anet= Задания за деньги 4 21.03.2011 12:08
Перевод из Паскаля в С++ как реализовать links С/С++ 7 11.09.2009 16:56
Преобразовать из Паскаля в Си. Niko Prolog 1 04.10.2007 21:07
Треугольник Паскаля на Прологе imported_Sniper Prolog 6 23.11.2006 02:18
Треугольник и точка chip Pascal 8 31.10.2006 12:18
Треугольник Паскаля на Лиспе imported_Sniper Lisp 2 11.05.2005 18:16
Как создать треугольник Паскаля, где количество строк вводится пользователем fonda Вопросы начинающих программистов 1 13.04.2005 20:44
Перевод программы с паскаля на c++ Werti C++ Builder 1 29.10.2004 11:01
Помогите с установкой Паскаля swater Pascal 2 09.03.2004 15:26



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов