Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Prolog
Перезагрузить страницу Решето Эратосфена
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
F@nt@zy F@nt@zy вне форума
Новичок
 
Сообщений: 5
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.12.2008
По умолчанию Решето Эратосфена - 08.12.2008, 10:55

Помогите пожалуйста. Ну просто очень нужна помощь!!!
Мне нужно написать предикат, например simp(N,L). Предикат должен составить список L из всех простых чисел не превосходящих N.
Нужно воспользоваться алгоритмом, известным как решето Эратосфена.
Уже совсем замучилась с этой задачкой.
Ответить с цитированием
  (#2 (permalink)) Старый
aag aag вне форума
ушёл... не вернётся)))
 
Сообщений: 3,400
Сказал(а) спасибо: 0
Поблагодарили 82 раз(а) в 82 сообщениях
Регистрация: 29.11.2008
По умолчанию 08.12.2008, 19:35

вроде молотит
Код:
domains    i=integer  il=i*

predicates  
        simp(i,i,il,il)     % simp(2,N,[],Out)
           makeNo(i,i,i,il,il) % makeNo(0,Ch,Max,....
           insert(i,il,il)

clauses

simp(Ch,N,_,[]):- Ch>N,!.
simp(Ch,N,[Ch|NoIn],Out):- !, Cnew=Ch+1, simp(Cnew,N,NoIn,Out).
simp(Ch,N,NoIn,[Ch|Out]):-   makeNo(0,Ch,N,NoIn,List),
                             Cn=Ch+1, simp(Cn,N,List,Out).

makeNo(I,Ch,N,NoIn,Out):- M=Ch*Ch+I*Ch, M<=N, !,
                          insert(M,NoIn,NoNew),In=I+1, makeNo(In,Ch,N,NoNew,Out).
makeNo(_,_,_,List,List).
                               
insert(I,[],[I]):-!.
insert(I,[I|H],[I|H]):-!.
insert(I,[G|H],[G|O]):- I>G,!, insert(I,H,O).
insert(I,L,[I|L]).

goal  simp(2,50,[],Out), write(Out)
Ответить с цитированием
  (#3 (permalink)) Старый
F@nt@zy F@nt@zy вне форума
Новичок
 
Сообщений: 5
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.12.2008
По умолчанию 08.12.2008, 20:20

Ой спасибо большое!!! я прям очень рада. Щас буду разбираться.
Ответить с цитированием
  (#4 (permalink)) Старый
F@nt@zy F@nt@zy вне форума
Новичок
 
Сообщений: 5
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.12.2008
По умолчанию 08.12.2008, 20:31

А можно я если что вопросы задавать буду?
А можно узнать что такое domains? я просто с этим в прологе еще не сталкивалась. А еще тут тоже создаются классы?
Ответить с цитированием
  (#5 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 8,035
Сказал(а) спасибо: 2
Поблагодарили 323 раз(а) в 322 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 08.12.2008, 23:02

Цитата:
А можно узнать что такое domains?
Раздел программы, в котором описываются используемые типы данных.
Цитата:
А еще тут тоже создаются классы?
Вообще то в Прологе создавать классы можно, но в этой проге они не используются. Не путайте clauses и class.
А простые числа были на форуме. Поищите если есть желание на ключевую фразу "протые числа". Там по-моему приведено эффективное решение.
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,786
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 25.12.2008, 19:48

Гораздо более эффективно будет так (хоть и это, конечно, тоже не самый эффективный способ ):
Код:
domains
il=integer*
predicates
determ prime(integer,il)
prime(integer,integer,il,il)
determ divide(integer,il)
reverse(il,il,il)
clauses
prime(2,[2]):- !.
prime(N,ResL):- N>2,
    prime(3,N,[2],Res),
    reverse(Res,[],ResL).

prime(K,N,L,L):- K>N, !.
prime(K,N,L,ResL):-
    divide(K,L),
    !,
    K1=K+2,
    prime(K1,N,L,ResL).
prime(K,N,L,ResL):-
    K1=K+2,
    prime(K1,N,[K|L],ResL).

divide(K,[A|_]):- K mod A = 0, !.
divide(K,[_|L]):- divide(K,L).

reverse([A|L],S,R):-
    reverse(L,[A|S],R).
reverse([],L,L).    
goal
prime(50,L).
Ответить с цитированием
  (#7 (permalink)) Старый
aag aag вне форума
ушёл... не вернётся)))
 
Сообщений: 3,400
Сказал(а) спасибо: 0
Поблагодарили 82 раз(а) в 82 сообщениях
Регистрация: 29.11.2008
По умолчанию 25.12.2008, 23:27

Цитата:
Нужно воспользоваться алгоритмом, известным как решето Эратосфена
что-то я у Вас решета этого самого не нашёл... с уважением
Ответить с цитированием
  (#8 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,786
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 25.12.2008, 23:46

К реализации любого алгоритма нужно подходить творчески!
Код:
domains
il=integer*
predicates
determ prime(integer,il)
prime(integer,integer,il,il)
determ divide(integer,il)
reverse(il,il,il)
clauses
% 'Вычеркнуть все числа, кратные 2'= их после 2-ки не будет никогда, 
% так что они здесь и не возникнут
prime(2,[2]):- !.
prime(N,ResL):- N>2,
    prime(3,N,[2],Res), % начинаем с 3
    reverse(Res,[],ResL).

prime(K,N,L,L):- K>N, !.
% берем очередное число и проверяем - вычеркивать или не вычеркивать
prime(K,N,L,ResL):-
    divide(K,L),   % вычеркиваем, т.к. оно кратно некоторому ранее встреченному числу, 
    !,             % кратные которому мы должны вычеркнуть (мы его уже вычеркнули в уме, 
                   % а теперь - в программе, этого числа как бы уже нет, мы его и не берем)
    K1=K+2,
    prime(K1,N,L,ResL).
prime(K,N,L,ResL):-  % оставляем, т.к. оно не кратно ни одному из предыдущих чисел
    K1=K+2,        
    prime(K1,N,[K|L],ResL).

divide(K,[A|_]):- K mod A = 0, !.
divide(K,[_|L]):- divide(K,L).

reverse([A|L],S,R):-
    reverse(L,[A|S],R).
reverse([],L,L).    
goal
prime(50,L).
Ответить с цитированием
  (#9 (permalink)) Старый
aag aag вне форума
ушёл... не вернётся)))
 
Сообщений: 3,400
Сказал(а) спасибо: 0
Поблагодарили 82 раз(а) в 82 сообщениях
Регистрация: 29.11.2008
По умолчанию 26.12.2008, 00:09

тогда это уже решето Эратосфена-Alison, если творчески, а в условии сказанно только про Эратосфена... гм... с уважением... А творчески -- придём к решету Аткина, если не ошибаюсь, которое самое эффективное...
Ответить с цитированием
  (#10 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,786
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 26.12.2008, 15:51

По-моему, как раз решето Эратосфена. При его реализации не обязательно тупо по списку многократно лишние разы бегать.
Скорее, в Вашем решении его не очень-то видно, а в моем прозрачно все.
Ответить с цитированием
  (#11 (permalink)) Старый
aag aag вне форума
ушёл... не вернётся)))
 
Сообщений: 3,400
Сказал(а) спасибо: 0
Поблагодарили 82 раз(а) в 82 сообщениях
Регистрация: 29.11.2008
По умолчанию 26.12.2008, 22:19

Цитата:
Решето Эратосфена
Материал из Википедии — свободной энциклопедии
В математике, решето́ Эратосфе́на — простой старинный алгоритм нахождения всех простых чисел до некоторого целого числа n. Он является предшественником современного Решета Аткина, более быстрого, но и более сложного алгоритма. Он был создан древнегреческим математиком Эратосфеном.

Пример для n = 20
Запишем натуральные числа начиная от 2 до 20 в ряд:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Первое число в списке 2 — простое. Пройдём по ряду чисел, вычёркивая все числа кратные 2 (каждое второе, начиная с 2^2 = 4):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Следующее невычеркнутое число 3 — простое. Пройдём по ряду чисел, вычёркивая все числа кратные 3 (каждое третье, начиная с 3^2 = 9):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Цитата:
При его реализации не обязательно тупо по списку многократно лишние разы бегать.
-- боюсь, смысл Эратосфена именно тупое беганье по списку... Или Википедия что-то перепутала...
Ответить с цитированием
  (#12 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,786
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 27.12.2008, 19:05

Хорошо.
Но Ваша программа имеет к этому алгоритму не менее далекое отношение, чем моя.
Мой алгоритм описан в программе. Пр наличии фантазии вполне сойдет за реализацию алгоритма построения множества простых чисел с помощью решета Эратосфена.
Ваш алгоритм такой.
Отдельно строятся список вычеркиваемых (составных) и список оставляемых (простых) чисел.
Сначала - список чисел, кратных двум, начиная с 4 и список [2].
Дальше в первый список добавляются числа, кратные 3, начиная с 9, второй список - [2,3].
Дальше из первого списка выкидывается 4.
Дальше - то, что было раньше для 5. И т.д.

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

Ну, ладно.
Вот буквальная реализация алгоритма Эратосфена. Берется исходный список всех чисел от 2 до N, и из него честно и последовательно вычеркивается (удаляется) все, что положено. В результате остаются только простые.
Код:
domains
il=integer*
predicates
list_of_numbers(integer,integer,il)
sieve(integer,il,il,il)
strike_out(integer,integer,il,il)
prime_numbers(integer,il)
reverse(il,il,il)
clauses
list_of_numbers(C,N,[C|L]):- 
    C<=N, !, C1=C+1,
    list_of_numbers(C1,N,L).
list_of_numbers(_,_,[]).

sieve(N,[A|L],PrL,Res):-
    C=A*A, C<=N, !,
    strike_out(C,A,L,L1),
    sieve(N,L1,[A|PrL],Res).
sieve(_,L,PrL,Res):- 
    reverse(PrL,L,Res).
    
strike_out(C,A,[C|L],L1):- !,
    C1=C+A,
    strike_out(C1,A,L,L1).
strike_out(C,A,[K|L],[K|L1]):- 
    K<C, !, 
    strike_out(C,A,L,L1).
strike_out(C,A,[K|L],[K|L1]):- 
    C1=C+A,
    strike_out(C1,A,L,L1).        
strike_out(_,_,[],[]).    

reverse([A|L],S,R):- 
    reverse(L,[A|S],R).
reverse([],L,L).

prime_numbers(N,PrimeL):-
   list_of_numbers(2,N,L),
   sieve(N,L,[],PrimeL).
goal
prime_numbers(50,L).
В любом случае, эта реализация, хоть и менее эффективная, чем моя предыдущая, но гораздо более эффективная, чем Ваша. Ваш вариант на моем компьютере не берет уже N=4000 (Gstack overflow), а последний легко берет и N=500000 (полмиллиона). По идее, этот "буквальный Эратосфен" должен реализовываться еще эффективнее.
Ответить с цитированием
Ads
  (#13 (permalink)) Старый
aag aag вне форума
ушёл... не вернётся)))
 
Сообщений: 3,400
Сказал(а) спасибо: 0
Поблагодарили 82 раз(а) в 82 сообщениях
Регистрация: 29.11.2008
По умолчанию 27.12.2008, 20:31

ага...
Ответить с цитированием
  (#14 (permalink)) Старый
frikorsar frikorsar вне форума
Member
 
Сообщений: 26
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 07.12.2008
По умолчанию 15.01.2009, 13:34

А можно ли это решето реализовать просто для рекурсии? Чтобы выводился не список, а просто все значения X, не превышающие заданное N
Ответить с цитированием
  (#15 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 8,035
Сказал(а) спасибо: 2
Поблагодарили 323 раз(а) в 322 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 16.01.2009, 14:36

Можно. Написать можно всё!
Только это будет не рекурсия, а рекурсия рекурсий. Причём предикаты должны буть недетерминированные, чтобы каждое следующее простое число возвращалось при откате от предыдущего.
Если Вы поняло, что я тут понаписал, то попробуйте сами.
Ответить с цитированием
Ответ

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

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

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




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