ProjectEuler Problem 413

回頭玩ProjectEuler,先選413題 ( http://projecteuler.net/problem=413 ) 開始:但不知為何他們說 F(1000) = 389 而我 :- f(1000, N). 得到 N = 407 。

印出的 one child number 如下。再下方附Prolog程式。

[1,2,3,4,5,6,7,8,9,21,23,25,27,29,41,43,45,47,49,61,63,65,67,69,81,83,85,87,89,101,104,107 ,110,111,112,113,114,115,116,117,118,119,122,125,128,131,134,137,140,141,142,143,144,145 ,146,147,148,149,152,155,158,161,164,167,170,171,172,173,174,175,176,177,178,179,182,185 ,188,191,194,197,202,205,208,211,214,217,220,221,222,223,224,225,226,227,228,229,232, 235,238,241,244,247,250,251,252,253,254,255,256,257,258,259,262,265,268,271,274,277, 280,281,282,283,284,285,286,287,288,289,292,295,298,311,313,314,317,322,323,325,328, 341,343,344,347,352,353,355,358,371,373,374,377,382,383,385,388,401,404,407,410,411, 412,413,414,415,416,417,418,419,422,425,428,431,434,437,440,441,442,443,444,445,446, 447,448,449,452,455,458,461,464,467,470,471,472,473,474,475,476,477,478,479,482,485, 488,491,494,497,502,505,508,511,514,517,520,521,522,523,524,525,526,527,528,529,532, 535,538,541,544,547,550,551,552,553,554,555,556,557,558,559,562,565,568,571,574,577, 580,581,582,583,584,585,586,587,588,589,592,595,598,611,614,616,617,622,625,626,628, 641,644,646,647,652,655,656,658,671,674,676,677,682,685,686,688,701,704,707,710,711, 712,713,714,715,716,717,718,719,722,725,728,731,734,737,740,741,742,743,744,745,746,747, 748,749,752,755,758,761,764,767,770,771,772,773,774,775,776,777,778,779,782,785,788,791, 794,797,802,805,808,811,814,817,820,821,822,823,824,825,826,827,828,829,832,835,838, 841,844,847,850,851,852,853,854,855,856,857,858,859,862,865,868,871,874,877,880,881, 882,883,884,885,886,887,888,889,892,895,898,911,914,917,919,922,925,928,929,941,944, 947,949,952,955,958,959,971,974,977,979,982,985,988,989]

Prolog程式如下: f/2 是函數F, g/1 為驗算。

f(N, Number) :-
N1 is N – 1,
bagof(N2, between(1,N1,N2), Ns),
findall(N3, (member(N3,Ns),is_1_child_number(N3)), L),
write(L), nl,
length(L, Number).

g(N) :-
N1 is N – 1,
bagof(N2, between(1,N1,N2), Ns),
forall(member(N3,Ns), (to_string(N3,S),all_substrings(S,Ss),
setof(S1,member(S1,Ss),Ss1),length(Ss1,L1),length(Ss,L2),L1=:=L2)).

is_1_child_number(0).
is_1_child_number(N) :-
to_string(N, L),
length(L, L1),
is_1_child_number(N, L1).
is_1_child_number(0, _).
is_1_child_number(N, D) :-
to_string(N, L),
all_substrings(L, Ps),
findall(N1, (member(P,Ps),to_number(P,N1),mod(N1,D)=:=0), Ds),
[_] = Ds.

to_string(N, Result) :- to_string(N, “", Result).
to_string(N, Result, Result) :- N =< 0, !.
to_string(N, Acct, Result) :-
N1 is div(N, 10),
H is mod(N, 10),
to_string(N1, [H|Acct], Result).

all_substrings(“", []).
all_substrings([H|T], Substrings) :-
all_heads([H|T], Heads),
findall(Ts, (member(H1,Heads),all_tails(H1,Ts)), Tails),
lists:append(Tails, Tohs1),
setof(T1, member(T1,Tohs1), Tohs),
all_substrings(T, S1),
bagof(T2,(member(T2,Tohs),not(member(T2,S1))), S2),
append(S2, S1, Substrings).

all_heads(“", []).
all_heads(String, Substrings) :-
lists:reverse(String, R),
all_tails(R, Tails),
findall(Rt, (member(T,Tails),lists:reverse(T,Rt)), Substrings).

all_tails(“", []).
all_tails([H|T], [[H|T]|Substrings]) :-
all_tails(T, Substrings).

to_number(String, Number) :- to_number(String, 0, Number).
to_number(“", Result, Result).
to_number([H|T], Accu, Result) :-
Accu1 is Accu*10+H,
to_number(T, Accu1, Result).

廣告

About 黃耀賢 (Yau-Hsien Huang)

熱愛 Erlang ,並且有相關工作經驗。喜歡程式語言。喜歡邏輯。目前用 Python 工作。
本篇發表於 Prolog。將永久鏈結加入書籤。