|
|
問題
S={1,5,11,13,17,29}として、{a[n]}は次の条件(1),(2),(3)を満たす数列とする。
条件
(1) a[1]∈S
(2) 個々の正整数nに対して(a[n+1]-1)/(a[n]+1)∈S
(3) 10以下のある正整数nに対してa[n]=2015
このような条件を満たす数列{a[n]}において、それまでの和
a[1]+a[2]+a[3]+ … +a[n] （n≦10,a[n]=2015）
はいくつになることができるか。
答え
バックトラック法で検索する。
DIM A(10),S(6)
DATA 1,5,11,13,17,29
MAT READ S
FOR N=10 TO 2 STEP -1 !逆からたどる
LET A(N)=2015 !条件3
CALL try(N-1,N,A,6,S)
NEXT N
END
EXTERNAL SUB try(P,N,A(),M,S())
FOR K=1 TO M !条件2
LET T=(A(P+1)-1)/S(K)-1
IF T>0 AND T=INT(T) THEN !これより、a[n]は正の整数
IF P=1 THEN
FOR i=1 TO M !条件1
IF T=S(i) THEN EXIT FOR
NEXT i
IF i<=M THEN !結果を表示する
PRINT STR$(T);
FOR J=2 TO N
LET T=T+A(J)
PRINT "+";STR$(A(J));
NEXT J
PRINT "=";STR$(T)
END IF
ELSE
LET A(P)=T
CALL try(P-1,N,A,M,S) !次へ
END IF
END IF
NEXT K
END SUB
実行結果
1+35+181+2003+2005+2007+2009+2011+2013+2015=14280
29+151+153+2003+2005+2007+2009+2011+2013+2015=14396
29+391+393+395+397+399+401+2011+2013+2015=8444
29+31+33+35+397+399+401+2011+2013+2015=7364
5+31+33+35+397+399+401+2011+2013+2015=7340
13+71+73+75+77+79+401+2011+2013+2015=6828
1+3+117+2007+2009+2011+2013+2015=10176
1+35+397+399+401+2011+2013+2015=7272
1+3+5+79+401+2011+2013+2015=6528
5+79+401+2011+2013+2015=6524
|
|