最短加算チェーン

加算チェーンは、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.

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です