2つの正の整数 p と q
を指定すると、次のアルゴリズムを適用して作成した配列 A
- Start with A = [p, q] and d =
2 - For each pair (x, y) of contiguous numbers in
A whose sum is divisible by d,
insert (x + y)/d between x and
y. - If at least one matching pair was found, increment
d and go on with step #2. Otherwise, stop and
return A.
例
以下は、 p = 1 および q = 21
のプロセスの詳細です。
1 21 | Iteration #1: we start with d = 2 and A = [1, 21]
/ | 1 + 21 is divisible by 2 -> we insert 11
22/2=11 |
|
1 11 21 | Iteration #2: d = 3, A = [1, 11, 21]
/ | 1 + 11 is divisible by 3 -> we insert 4
12/3=4 |
|
1 4 11 21 | Iteration #3: d = 4, A = [1, 4, 11, 21]
/ | 11 + 21 is divisible by 4 -> we insert 8
32/4=8 |
|
1 4 11 8 21 | Iteration #4: d = 5, A = [1, 4, 11, 8, 21]
/ / | 1 + 4 is divisible by 5 -> we insert 1
5/5=1 15/5=3 | 4 + 11 is divisible by 5 -> we insert 3
|
1 1 4 3 11 8 21 | Iteration #5: d = 6, A = [1, 1, 4, 3, 11, 8, 21]
| no sum of two contiguous numbers is divisible by 6
| -> we stop here
Hence the expected output: [1, 1, 4, 3, 11, 8,
21]
説明とルール
- Input and output can be handled in any reasonable format. The
integers p and q are guaranteed
to be greater than 0. If that helps, you may assume q ≥
p. - The 2nd step of the algorithm should
not be recursively applied to elements
that have just been inserted at the same iteration. For instance,
A = [1, 1] and d = 2 should lead
to [1, 1, 1] (not an infinite list of 1’s). - This is code-golf,
so the shortest answer in bytes wins!
テストケース
p | q | Output
----+-----+-------------------------------------------------------------------------------
1 | 1 | [1,1,1]
1 | 2 | [1,2]
1 | 3 | [1,1,2,3]
2 | 6 | [2,1,2,1,4,1,2,6]
3 | 13 | [3,1,8,1,3,1,7,1,2,1,5,1,3,2,13]
9 | 9 | [9,6,9,6,9]
60 | 68 | [60,13,1,4,31,2,3,5,2,19,64,7,13,1,2,5,2,27,44,3,4,8,2,1,12,1,5,3,28,2,4,16,1,
| | 2,12,1,2,1,10,1,6,68]
144 | 336 | [144,68,3,4,8,1,12,1,4,2,28,13,128,44,17,92,240,58,108,5,17,1,2,5,3,28,3,1,11,
| | 60,3,6,2,42,2,4,26,192,54,132,7,1,15,1,3,1,18,1,4,2,30,3,1,12,1,9,78,46,336]
少し大きめのテストケースでコードをテストする場合は、 ここ 期待される出力は次のとおりです。
- p = 12096 (26*33*7)
- q = 24192 (27*33*7)
ベストアンサー
Mathematica、 72 64 59 58バイト
(d=2;#//.x_:>Riffle[x,(x+{##2,}&@@x)/d++]~Cases~_Integer)&
使い方
入力はリスト {p、q}
として受け取ります。反復ステップは次のように再定義されます。
- Insert
(a+b)/d
between every two elements
a
andb
:(x+{##2,}&@@x)
computes the sequence ofa+b
‘s, with an
a+Null
at the end. We divide byd
, and
Riffle
inserts each(a+b)/d
between
a
andb
. Incrementd
. - Pick out the
Integer
elements of the resulting
list. (This gets rid of theNull
introduced by
{##2,}
, too.)
これは、結果が変更されなくなるまで繰り返されます(これは、新しい要素をすべて削除したためです。
FixedPoint
の代わりに@MartinEnderが
//。
を使って(そして入力としてリストを取ることで) -8バイト
ListConvolve
は実際にそれほど大きくないので -6以上