拡張アレイ

2つの正の整数 pq
を指定すると、次のアルゴリズムを適用して作成した配列 A

  1. Start with A = [p, q] and d =
    2
  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.
  3. 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 ,
    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} として受け取ります。反復ステップは次のように再定義されます。

  1. Insert (a+b)/d between every two elements
    a and b: (x+{##2,}&@@x)
    computes the sequence of a+b‘s, with an
    a+Null at the end. We divide by d, and
    Riffle inserts each (a+b)/d between
    a and b. Increment d.
  2. Pick out the Integer elements of the resulting
    list. (This gets rid of the Null introduced by
    {##2,}, too.)

これは、結果が変更されなくなるまで繰り返されます(これは、新しい要素をすべて削除したためです。

FixedPoint の代わりに@MartinEnderが
//。を使って(そして入力としてリストを取ることで) -8バイト

ListConvolve は実際にそれほど大きくないので -6以上

返信を残す

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