加算チェーンは、1から始まる整数のシーケンスであり、最初の1以外のすべての整数は、2つの以前の整数の合計です。
たとえば、次のような加算チェーンがあります。
[1, 2, 3, 4, 7, 8, 16, 32, 39, 71]
それは加算鎖になる合計です：
1 + 1 = 2
1 + 2 = 3
1 + 3 = 4
3 + 4 = 7
1 + 7 = 8
8 + 8 = 16
16 + 16 = 32
7 + 32 = 39
32 + 39 = 71
このチャレンジでは、正の整数 n が与えられ、 n
で終わる最短加算チェーンの1つを出力する必要があります。
例 – 多くの可能な出力があることに注意してください。必要なのは、それほど短い追加チェーンだけです。
1: [1]
2: [1, 2]
3: [1, 2, 3]
4: [1, 2, 4]
5: [1, 2, 3, 5]
6: [1, 2, 3, 6]
7: [1, 2, 3, 4, 7]
11: [1, 2, 3, 4, 7, 11]
15: [1, 2, 3, 5, 10, 15]
19: [1, 2, 3, 4, 8, 11, 19]
29: [1, 2, 3, 4, 7, 11, 18, 29]
47: [1, 2, 3, 4, 7, 10, 20, 27, 47]
71: [1, 2, 3, 4, 7, 8, 16, 32, 39, 71]
標準I/Oルールなど標準的な抜け穴は禁止されています。コードゴルフ：最低のバイトが勝ちます。
ベストアンサー
Haskell, 57 bytes
c=[1]:[x++[a+b]|x<-c,a<-x,b<-x]
f n=[x|x<-c,last x==n]!!0
A brute force solution. Try it
online!
説明
無限リスト c には、すべての加算チェーンが長さ順に並べられています。 これは、
c のリストと x の2つの要素から x
リストを取り出し、その合計を > x 関数 f は、
c の目的の番号で終わる最初のリストを見つけます。
c= -- c is the list of lists
[1]: -- containing [1] and
[x -- each list x
++[a+b] -- extended with a+b
|x<-c, -- where x is drawn from c,
a<-x, -- a is drawn from x and
b<-x] -- b is drawn from x.
f n= -- f on input n is:
[x -- take list of those lists x
|x<-c, -- where x is drawn from c and
last x==n] -- x ends with n,
!!0 -- return its first element.