| >> |
No.4212
>>4209>
В каком месте я прошляпился?
Первым делом в наивном алгоритме.
Если же считать, что алгоритм годный и судить только о программе, то суть токова: слишком много повторных вычислений:
1. выкинуть сплит/шаттер - это просто вредительство какое-то, гораздо проще это делается так (List = [[_|_],[_|_],[_|_]], append(List,X))
2. еще лучшей идеей будет попробовать развернуть маплист руками и делать два append/3 вместо одного append/2. Посмотри как генерируются разбиения: первый подсписок остается неизменным пока элементы перегоняются по одному из третьего во второй и каждый раз ты пересчитываешь листТуНамбер для первого подсписка.
3. Не вычислять симметричные произведения: потребовать, чтобы первый множитель не превосходил корня из произведения.
4. Посмотреть на разбиения внимательно и увидеть, что из 28-ми годными являются только два с учетом предыдущего пункта
5. Попробовать сначала генерировать разбиения, а потом их перестановки и останавливать как можно раньше (там в задаче нужно знать только сами рузультаты умножений причем без повторов).
Вот тебе вариации на тему последних двух пунктов:
isEqual_v34(M1*M2=P) :-
permutation(X, [1,2,3,4,5,6,7,8,9]),
L3 = [_,_,_,_],
append(L12, L3, X),
listToNumber(L3, P),
( L1=[_], L2=[_,_,_,_]
; L1=[_,_], L2=[_,_,_]
),
append(L1, L2, L12),
listToNumber(L1, M1),
listToNumber(L2, M2),
P =:= M1 * M2.
%%%%%%%
k_permutation([],L,L).
k_permutation([X|Xs], L, L1) :- select(X,L,Lx), k_permutation(Xs,Lx,L1).
isEqual_v5(M1*M2=P) :-
L = [1,2,3,4,5,6,7,8,9],
L3 = [_,_,_,_],
k_permutation(L3, L, L12),
listToNumber(L3, P),
call((
( L1=[_] ; L1=[_,_] ),
k_permutation(L1, L12, L2),
listToNumber(L1, M1),
permutation(L2_, L2),
listToNumber(L2_, M2),
P =:= M1 * M2,
!
)).
test5 :- time(findall(P, isEqual_v5(_=P), L)), sumlist(L,N), writeln((L->N)).
|
