Семинарские занятия (Решения задач) (1157996), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

A(Y1 ) ← B(Y1 ), not(D(Y1 ));2. B(a) ← ;3. B(b) ← ;4. D(U4 ) ← C(Y4 ), !, E(U4 , Y4 );5. C(a) ← ;6. C(b) ← ;7. E(a, b) ← ;8. E(b, a) ← ;32?A(X)(1){X/Y1 }(2){Y1//b}{Y 1(3)a}?B(Y1 ), not(D(Y1 ))?not(D(a))?not(D(b)){}{}X=a* ? D(a)* ? D(b)(4){U4 /b}(4){U4 /a}? C(Y4 ), !, E(b, Y4 )(6){Y4/? !, E(b, a){}{}* ? E(b, a)(7){}33{}(8){}(8)(7){}* ? E(a, a)6? !, E(a, a)(6)6(6)(5){Y4/b}a}? C(Y4 ), !, E(a, Y4 )Упражнение 7.4% max (L , X )m_max ([ X ] , X ).m_max ([ A | L ] , A ) : - m_max (L , Y ) , A >= Y , !.m_max ([ _ | L ] , A ) : - m_max (L , A ).% max_occur ( L1 , L2 ).max_occur ([ W ] , W ).max_occur ([ X | L ] , W ) : - max_occur (L , S ) , max_list (X , S , W ).max_list (X , S , X ) : - length (X , XL ) , length (S , SL ) , XL >= SL , !.max_list (_ , S , S ).% short_path ( V1 , V2 , G , L ).short_path ( V1 , V2 , G , [ V1 | L ]) : - sh or t _ pa t h_ w i th _ le n ( V1 , V2 , G , L , _ ).shor t _p a th _ w it h _l e n ( V1 , V2 , G , L , New_len ) : ma rk _p oss ib le _wa ys ( V1 , G , New_G , Beg ) ,try_some_ways ( Beg , New_G , V2 , L , Len ) ,New_len is Len + 1.shor t _p a th _ wi t h _l e n (F , F , _ , [] , 0).mark _p oss ib le _wa ys ( V1 , [[ V1 , T ]| G ] , New_G , [ T | Beg ]) : ma rk _p oss ib le _wa ys ( V1 , G , New_G , Beg ) , !.mark _p oss ib le _wa ys ( V1 , [[ _ , V1 ]| G ] , New_G , Beg ) : ma rk _p oss ib le _wa ys ( V1 , G , New_G , Beg ) , !.mark _p oss ib le _wa ys ( V1 , [[ F , T ]| G ] , [[ F , T ]| New_G ] , Beg ) : V1 \= F , ma rk_ po ss ibl e_ wa ys ( V1 , G , New_G , Beg ) , !.mark _p oss ib le _wa ys (_ , [] , [] , []).try_some_ways ([ P ] , G , V2 , [ P | L ] , Len ) : s ho r t _p a th _ wi t h _l e n (P , V2 , G , L , Len ).try_some_ways ([ P | Beg ] , G , V2 , [ P | L ] , Len ) : s ho r t _p a th _ wi t h _l e n (P , V2 , G , L , Len ) ,try_some_ways ( Beg , G , V2 , _ , T_Len ) , Len < T_Len .try_some_ways ([ P | Beg ] , G , V2 , T_L , T_Len ) : s ho r t _p a th _ wi t h _l e n (P , V2 , G , _ , Len ) ,try_some_ways ( Beg , G , V2 , T_L , T_Len ) , Len >= T_Len .try_some_ways ([ P | Beg ] , G , V2 , T_L , T_Len ) : not ( s ho r t_ p at h _ wi t h_ l e n (P , V2 , G , _ , Len )) ,try_some_ways ( Beg , G , V2 , T_L , T_Len ).try_some_ways ([ P | Beg ] , G , V2 , [ P | L ] , Len ) : s ho r t _p a th _ wi t h _l e n (P , V2 , G , L , Len ) ,not ( try_some_ways ( Beg , G , V2 , _ , T_Len )).Упражнение 7.534% reach (V , E , x , y ).reach (_ , E , X , Y ) : - short_path (X , Y , E , _ ).% short_path (V , E , x , y , L ).short_path (_ , E , X , Y , L ) : - short_path (X , Y , E , L ).% color (V , E , R ).358Экзаменационные задачи% % Дан текст, разбить его на 2 множества слов так, что слова из разных множеств% % не имеют общих букв.% % elem(L, X) %%elem ([ X | _ ] , X ).elem ([ _ | A ] , X ) : - elem (A , X ).% % mult (L, X, Y)mult ([] , _ , 0).mult ([ X | L ] , X , Y ) : - ! , mult (L , X , Z ) , Y is Z + 1.mult ([ _ | L ] , X , Y ) : - mult (L , X , Y ).text_split (L , X , Y ) : - sublist (L , X ) , delete (L , X , Y ) , no_lett (X , Y ).sublist (_ , []).sublist ([ C | L ] , [ C | X ]) : - ! , sublist (L , X ).sublist ([ _ | L ] , X ) : - sublist (L , X ).delete (L , [] , L ).delete ([ C | L ] , [ C | X ] , Y ) : - delete (L , X , Y ) , !.delete ([ C | L ] , X , [ C | Y ]) : - delete (L , X , Y ).no_lett ([] , _ ).no_lett ([ X | L ] , Y ) : - no_lett1 (X , Y ) , no_lett (L , Y ).no_lett1 (_ , []).no_lett1 (X , [ Y | L ]) : - cap (X , Y , []) , no_lett1 (X , L ).cap ([] , _ , []).cap ([ C | X ] , Y , []) : - not ( elem (Y , C )) , cap (X , Y , []).% % Для данного текста построить список наиболее встречающихся% % в нем слов.max_text (L , L1 ) : - max_count (X , L ) , get_words (L , L1 , X ).max_count (X , L ) : - elem (L , C ) , mult (L , C , X ) , not ( exists_gt (L , X )).exists_gt (L , M ) : - elem (L , C ) , mult (L , C , N ) , N > M .get_words ([] , [] , _ ).get_words ([ X | L ] , [ X | L1 ] , N ) : - mult ([ X | L ] , X , N ) , ! , get_words (L , L1 , N ).get_words ([ _ | L ] , L1 , N ) : - get_words (L , L1 , N ).% % Для данного графа построить кратчайший путь между двумя вершинами% % в нем.s_path ( V1 , V2 , G , L ) : - path ( V1 , V2 , G , L ) , m_length (L , N ) ,not ( exists_lt ( V1 , V2 , G , N )).path (V , V , _ , []).path ( V1 , V2 , G , [[ V1 , V3 ] | L ]) : - elem (G , [ V1 , V3 ]) , path ( V3 , V2 , G , L ).36exists_lt ( V1 , V2 , G , N ) : - path ( V1 , V2 , G , L ) , m_length (L , M ) , M < N .m_length ([] , 0).m_length ([ _ | L ] , M ) : - m_length (L , N ) , M is N + 1.% % Для данного множества точек построить список наиболее удаленных друг% % от друга парg_pair (L , X ) : - max_dist (L , N ) , get_pairs (L , X , N ).max_dist (L , N ) : - elem (L , X ) , elem (L , Y ) , dest (X , Y , N ) ,not ( exists_gt_point (L , N )).dest ([ X1 , X2 ] , [ Y1 , Y2 ] , N ) : - N is sqrt (( X1 - Y1 )^2+ ( X2 - Y2 )^2).exists_gt_point (L , N ) : - elem (L , X ) , elem (L , Y ) , dest (X , Y , M ) , M > N .m_concat ([] , L , L ).m_concat ([ A | L1 ] , L2 , [ A | RES ]) : - m_concat ( L1 , L2 , RES ).get_pairs ([] , [] , _ ).get_pairs ([ X | L ] , RES , N ) : - build_pairs (X , L , TT_RES , N ) ,get_pairs (L , T_RES , N ) , m_concat ( TT_RES , T_RES , RES ).build_pairs (_ , [] , [] , _ ).build_pairs (X , [ C | L ] , [[ C , X ]| RES ] , N ) : - dest (X , C , N ) ,! , build_pairs (X , L , RES , N ).build_pairs (X , [ _ | L ] , RES , N ) : - build_pairs (X , L , RES , N ).% % Для данного графа построить его максимальную кликуclique (G , V , X ) : - sublist (V , X ) , is_clique (G , X ) , m_length (X , N ) ,not ( exists_gt_clique (G , V , N )).exists_gt_clique (G , V , N ) : - sublist (V , X ) , is_clique (G , X ) ,m_length (X , M ) , M > N .is_clique (_ , []).is_clique (G , [ X | L ]) : - edge_to_all (X , L , G ) , is_clique (G , L ).edge_to_all (_ ,[] , _ ).edge_to_all (X , [ C | L ] , G ) : - elem (G , [X , C ]) , ! , edge_to_all (X , L , G ).edge_to_all (X , [ C | L ] , G ) : - elem (G , [C , X ]) , edge_to_all (X , L , G ).% % Для данного графа построить его максимальное независимое подмножество% % (ни какие две вершины не соеденины ребром).indep_set (G , V , X ) : - sublist (V , X ) , is_indep (G , X ) , m_length (X , N ) ,not ( exists_gt_indep (G , V , N )).exists_gt_indep (G , V , N ) : - sublist (V , X ) , is_indep (G , X ) ,m_length (X , M ) , M > N .is_indep (_ , []).is_indep (G , [ X | L ]) : - no_edges (X , L , G ) , is_indep (G , L ).37no_edges (_ ,[] , _ ).no_edges (X , [ C | L ] , G ) : - not ( elem (G , [X , C ])) , not ( elem (G , [C , X ])) ,no_edges (X , L , G ).% % Для данного множества чисел построить максимальное его подмножество,% % свободное от суммsum_free (L , X ) : - sublist (L , X ) , not ( sum_non_free_set ( X )) , m_length (X , N ) ,not ( exi st s_ gt_ su m_ fre e (L , N )).sum_non_free_set ( X ) : - elem (X , A ) , elem (X , B ) , elem (X , C ) ,A \= B , S is A + B , C = S .exis ts _gt _s um _fr ee (L , N ) : - sublist (L , X ) , not ( sum_non_free_set ( X )) ,m_length (X , M ) , M > N .% % Для данных текстов L1 и L2 построить текст L3, состоящий из тех слов L1, которые% % содержат хотя бы одну букву, не встречающуюся ни в одном слове из L2mk_text ( L1 , L2 , L3 ) : - build_letters ( L2 , Lett ) , filter_text ( L1 , Lett , L3 ).build_letters ([] , []).build_letters ([ C | L ] , R ) : - build_letters (L , TR ) , m_concat ( TR , C , R ).filter_text ([] , _ , []).filter_text ([ C | L1 ] , Lett , [ C | L3 ]) : - has_uniq_letter (C , Lett ) , ! ,filter_text ( L1 , Lett , L3 ).filter_text ([ _ | L1 ] , Lett , L3 ) : - filter_text ( L1 , Lett , L3 ).has_uniq_letter (C , Lett ) : - elem (C , X ) , not ( elem ( Lett , X )).38.

Характеристики

Список файлов семинаров