「prolog勉強プロジェクトオイラー181～190」の編集履歴（バックアップ）一覧に戻る
*problem 188 Problem 188 「ある数のハイパーべき乗」 †
数 a の正整数 b による ハイパーべき乗 (hyperexponentiation) または テトレーション (tetration) を a↑↑b と書き, 以下のように再帰的に定義する.
a↑↑1 = a,
a↑↑(k+1) = a(a↑↑k).
定義によれば 3↑↑2 = 33 = 27であり, 3↑↑3 = 327 = 7625597484987となる. また, 3↑↑4は大体103.6383346400240996*10^12となる.
1777↑↑1855の最後の8桁を求めよ.
解法
単純にMod演算の
1777のｎ上の末尾8桁は1777＾ｒでｒの値によりループします。
1250001でループするので累乗をループサイズで割った余りをとっても計算は同じです。
あとはmod演算をしながら定義通りハイパーべき乗の一段階の計算をしていけば答えです。
ループサイズを求める計算は手抜き実装です。
mod_pow(_,0,1):-!.
mod_pow(A,R,Result):-
R mod 2 =:=1,
!,
R1 is R//2,
A1 is (A*A) mod 10^8,
mod_pow(A1,R1,Re),
Result is (Re*A) mod 10^8.
mod_pow(A,R,Result):-
R1 is R//2,
A1 is (A*A) mod 10^8,
mod_pow(A1,R1,Result).
loop_size(1777,R,R):-
R>1,
!.
loop_size(N,R,Result):-
!,
N1 is (N*1777) mod 10^8,
R1 is R+1,
loop_size(N1,R1,Result).
calc(A,Ans,1,_):-
!,
mod_pow(A,Ans,Ans1),
Ans2 is Ans1 mod 10^8,
write(Ans2).
calc(A,Ans,R,Size):-
!,
mod_pow(A,Ans,Ans1),
Ans2 is Ans1 mod Size,
R1 is R-1,
calc(A,Ans2,R1,Size).
main188:-
loop_size(1777,1,Size),
Size1 is Size-1,
calc(1777,1,1855,Size1).
*Problem 189 「三角形格子の三色塗り分け」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20189
三角形格子を３色に塗り分けるときの塗り分け方をこたえる問題。
解法
三角形のサイズが小さいので何も考えない動的計画法でもそれなりの計算時間で答えが出ます。
ただ私の解放は普通に答えが出るだけで高速ではありません。
数学掲示板の常連、らすかるさん というかたならたぶん数式ひとつに収めるでしょう。
私なりに高速化の道を考えてみたりはします。
ok_ki(Up,Result):-
!,
member(Result,[r,g,b]),
Up\==Result.
ok_gu(L,R,Result):-
member(Result,[r,g,b]),
L\==Result,
R\==Result.
ki_search([],[]):-!.
ki_search([Up|Rest],[NextColor|Result]):-
ok_ki(Up,NextColor),
ki_search(Rest,Result).
gu_search(0,[X|Rest],[NextColor|Result]):-
!,
ok_ki(X,NextColor),
gu_search(1,[X|Rest],Result).
gu_search(1,[X],[NextColor]):-
!,
ok_ki(X,NextColor).
gu_search(1,[L,R|Rest],[NextColor|Result]):-
ok_gu(L,R,NextColor),
gu_search(1,[R|Rest],Result).
ki_calc(Memo,[RePerm,Count]):-
member([Perm,Count],Memo),
ki_search(Perm,RePerm).
gu_calc(Memo,[RePerm,Count]):-
member([Perm,Count],Memo),
gu_search(0,Perm,RePerm).
union_sum([],Y,[Y]):-!.
union_sum([[X,Count]|Rest],[X,Count1],Result):-
!,
Count2 is Count1+Count,
union_sum(Rest,[X,Count2],Result).
union_sum([[X,Count]|Rest],Y,[Y|Result]):-
!,
union_sum(Rest,[X,Count],Result).
sum([],0):-!.
sum([[_,Count]|Rest],Result):-
sum(Rest,Re),Result is Re+Count.
calc(Memo,15):-!,sum(Memo,Ans),write(Ans).
calc(Memo,N):-
!,
(N mod 2=:=1 ->
findall(M,ki_calc(Memo,M),Memo1);
findall(M,gu_calc(Memo,M),Memo1)),
N1 is N+1,
msort(Memo1,Memo2),
[Top|Memo3]=Memo2,
union_sum(Memo3,Top,Memo4),
calc(Memo4,N1).
main189:-
calc([[[g],3]],1).
