2

Есть задача под названием 100.
Смысл в ней такой:

Имея последовательность 1,2,3,4,5,6,7,8,9 нужно поставить между ними 3 знака + или -, так чтобы получилось 100.
Собственно я предполагаю, что последовательность можно представить сначала в виде списка и каждый раз генерировать следующие варианты:

X = 1, Y = 2, Z = 3, K = [4,5,6,7,8,9].
X = 1, Y = 2, Z = [3,4], K = [5,6,7,8,9].

И так до того момента пока len(Y,Z,K) != 1 и sum != 100, ну как-то так.
На других языках в принципе могу сделать, а вот с Prolog запара...
Если у вас есть время, то не откажусь от пары слов по решению данной задачи на Prolog.

1 ответ 1

2

Решение:

:- use_module( library( lists )).

plus_minus( plus ).
plus_minus( minus ).

game100( NumList ) :-
    group( NumList, Sum1, L1 ),
    group( L1, Sum2, L2 ),
    group( L2, Sum3, L3 ),
    subtract( NumList, L3, L4 ),
    sum_list1( L4, Sum4 ),
    sum_list1( [ Sum1, Sum2, Sum3, Sum4 ], Sum ),
    Sum \== 100 -> fail;true.

group( L, Sum, NewL ):-
    length( L, Len  ),
    numlist( 1, Len, PosList ),
    member( Pos, PosList ),% integer list
    permutation_length( L, Pos, Lp ),
    subtract( L, Lp, NewL ),
    sum_list1( Lp, Sum ).

% генерирует подсписок длиной L для списка Xs
% при возврате генерирует остальные подсписки
permutation_length( _, 0, [] ) :- !.
permutation_length([ X | Xs ], L, [ X | Ys ]) :-
    L1 is L - 1,
    permutation_length( Xs, L1, Ys ).

permutation_length([ _ | Xs ], L, Ys ) :-
    L > 0,
    permutation_length( Xs, L, Ys ).

%сумма списка Xs c подставновкой знака арифм операции
sum_list1( [], 0 ).
sum_list1( [ X ], X ).
sum_list1( [ X | Xs ], Sum ) :-
    sum_list1( Xs, Sum1 ),
    plus_minus( Sign ),
    Sign == plus  ->
       Sum is Sum1 + X;
       Sum is Sum1 - X.

:- initialization( numlist( 1, 9, NumList ), game100( NumList )).

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.