Если заданы два натуральных числа p и q , ваша задача - вернуть массив A, созданный с помощью следующего алгоритма:

1. Начните с A = [p, q] и d = 2
2. Для каждой пары (x, y) смежных чисел в A , сумма которых делится на d , вставьте (x + y) / d между x и y .
3. Если была найдена хотя бы одна подходящая пара, увеличьте d и перейдите к шагу № 2. В противном случае, остановка и возвращение .

пример

Ниже подробно описан процесс для 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

Отсюда и ожидаемый результат: [1, 1, 4, 3, 11, 8, 21]

Разъяснения и правила

• Ввод и вывод могут быть обработаны в любом разумном формате. Целые числа p и q гарантированно будут больше 0. Если это поможет, вы можете предположить, q ≥ p .
• 2-й шаг алгоритма не должен применяться рекурсивно к элементам, которые только что были вставлены на одной и той же итерации. Например, A = [1, 1] и d = 2 должны привести к [1, 1, 1] (не бесконечный список из 1).
• Это код-гольф , поэтому выигрывает самый короткий ответ в байтах!

Контрольные примеры

  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]

Если вы хотите протестировать свой код на чуть большем тестовом примере, вот ожидаемый результат для:

• р = 12096 (2 ⁶ * 3) ³ * 7)
• q = 24192 (2 ⁷ * 3 ³ * 7)

05AB1E , 28 19 18 байт

[Ðü+NÌ/‚ζ˜ʒ.ï}DŠQ#

Попробуйте онлайн!

да, безусловно, можно улучшить хардкор. все еще работает над рефакторингом.

Наверное, так хорошо, как я понимаю.

-1 спасибо, кто еще кроме Эминьи! Для указания swap работал лучше, чем регистры.

[                   // Infinite loop.
 Ð                  // Triplicate [p, ..., q]
  U                 // Pop 1 of 3 copies into register X.
   ü+               // Pairwise addition.
     NÌ/            // Divide by current iteration + 2 (which is d).
        ‚           // Group original [p, ..., q] with pairwise additives.
         ζ˜         // Transpose together and flatten.
           ʒ.ï}     // Filter out non-integer entities (includes the space added by zip).
               DXQ  // Dupe result, see if equal to original.
                  # // If new array is original array, nothing happened, quit & return.

Отладочный дамп для [p,q] = [1,3]:

Full program: [ÐUü+NÌ/‚ζ˜ʒ.ï}DXQ#
current >> [  ||  stack: []
ÐUü+NÌ/‚ζ˜ʒ.ï}DXQ#
Full program: ÐUü+NÌ/‚ζ˜ʒ.ï}DXQ#
current >> Ð  ||  stack: []
current >> U  ||  stack: [[1, 3], [1, 3], [1, 3]]
current >> ü  ||  stack: [[1, 3], [1, 3]]
Full program: +
current >> +  ||  stack: [1, 3]
stack > [4]
current >> N  ||  stack: [[1, 3], [4]]
current >> Ì  ||  stack: [[1, 3], [4], 0]
current >> /  ||  stack: [[1, 3], [4], 2]
current >> ‚  ||  stack: [[1, 3], [2.0]]
current >> ζ  ||  stack: [[[1, 3], [2.0]]]
current >> ˜  ||  stack: [[[1, 2.0], [3, ' ']]]
current >> ʒ  ||  stack: [[1, 2.0, 3, ' ']]
Filter: .ï
Full program: .ï
current >> .  ||  stack: [1]
stack > [1]
Full program: .ï
current >> .  ||  stack: [2.0]
stack > [1]
Full program: .ï
current >> .  ||  stack: [3]
stack > [1]
Full program: .ï
current >> .  ||  stack: [' ']
invalid literal for int() with base 10: ' '
stack > []
current >> D  ||  stack: [[1, 2.0, 3]]
current >> X  ||  stack: [[1, 2.0, 3], [1, 2.0, 3]]
current >> Q  ||  stack: [[1, 2.0, 3], [1, 2.0, 3], [1, 3]]
current >> #  ||  stack: [[1, 2.0, 3], 0]
stack > [[1, 2.0, 3]]
Full program: ÐUü+NÌ/‚ζ˜ʒ.ï}DXQ#
current >> Ð  ||  stack: [[1, 2.0, 3]]
current >> U  ||  stack: [[1, 2.0, 3], [1, 2.0, 3], [1, 2.0, 3]]
current >> ü  ||  stack: [[1, 2.0, 3], [1, 2.0, 3]]
Full program: +
current >> +  ||  stack: [1, 2.0]
stack > [3.0]
Full program: +
current >> +  ||  stack: [3.0, 2.0, 3]
stack > [3.0, 5.0]
current >> N  ||  stack: [[1, 2.0, 3], [3.0, 5.0]]
current >> Ì  ||  stack: [[1, 2.0, 3], [3.0, 5.0], 1]
current >> /  ||  stack: [[1, 2.0, 3], [3.0, 5.0], 3]
current >> ‚  ||  stack: [[1, 2.0, 3], [1.0, 1.6666666666666667]]
current >> ζ  ||  stack: [[[1, 2.0, 3], [1.0, 1.6666666666666667]]]
current >> ˜  ||  stack: [[[1, 1.0], [2.0, 1.6666666666666667], [3, ' ']]]
current >> ʒ  ||  stack: [[1, 1.0, 2.0, 1.6666666666666667, 3, ' ']]
Filter: .ï
Full program: .ï
current >> .  ||  stack: [1]
stack > [1]
Full program: .ï
current >> .  ||  stack: [1.0]
stack > [1]
Full program: .ï
current >> .  ||  stack: [2.0]
stack > [1]
Full program: .ï
current >> .  ||  stack: [1.6666666666666667]
stack > [0]
Full program: .ï
current >> .  ||  stack: [3]
stack > [1]
Full program: .ï
current >> .  ||  stack: [' ']
invalid literal for int() with base 10: ' '
stack > []
current >> D  ||  stack: [[1, 1.0, 2.0, 3]]
current >> X  ||  stack: [[1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3]]
current >> Q  ||  stack: [[1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3], [1, 2.0, 3]]
current >> #  ||  stack: [[1, 1.0, 2.0, 3], 0]
stack > [[1, 1.0, 2.0, 3]]
Full program: ÐUü+NÌ/‚ζ˜ʒ.ï}DXQ#
current >> Ð  ||  stack: [[1, 1.0, 2.0, 3]]
current >> U  ||  stack: [[1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3]]
current >> ü  ||  stack: [[1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3]]
Full program: +
current >> +  ||  stack: [1, 1.0]
stack > [2.0]
Full program: +
current >> +  ||  stack: [2.0, 1.0, 2.0]
stack > [2.0, 3.0]
Full program: +
current >> +  ||  stack: [2.0, 3.0, 2.0, 3]
stack > [2.0, 3.0, 5.0]
current >> N  ||  stack: [[1, 1.0, 2.0, 3], [2.0, 3.0, 5.0]]
current >> Ì  ||  stack: [[1, 1.0, 2.0, 3], [2.0, 3.0, 5.0], 2]
current >> /  ||  stack: [[1, 1.0, 2.0, 3], [2.0, 3.0, 5.0], 4]
current >> ‚  ||  stack: [[1, 1.0, 2.0, 3], [0.5, 0.75, 1.25]]
current >> ζ  ||  stack: [[[1, 1.0, 2.0, 3], [0.5, 0.75, 1.25]]]
current >> ˜  ||  stack: [[[1, 0.5], [1.0, 0.75], [2.0, 1.25], [3, ' ']]]
current >> ʒ  ||  stack: [[1, 0.5, 1.0, 0.75, 2.0, 1.25, 3, ' ']]
Filter: .ï
Full program: .ï
current >> .  ||  stack: [1]
stack > [1]
Full program: .ï
current >> .  ||  stack: [0.5]
stack > [0]
Full program: .ï
current >> .  ||  stack: [1.0]
stack > [1]
Full program: .ï
current >> .  ||  stack: [0.75]
stack > [0]
Full program: .ï
current >> .  ||  stack: [2.0]
stack > [1]
Full program: .ï
current >> .  ||  stack: [1.25]
stack > [0]
Full program: .ï
current >> .  ||  stack: [3]
stack > [1]
Full program: .ï
current >> .  ||  stack: [' ']
invalid literal for int() with base 10: ' '
stack > []
current >> D  ||  stack: [[1, 1.0, 2.0, 3]]
current >> X  ||  stack: [[1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3]]
current >> Q  ||  stack: [[1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3]]
current >> #  ||  stack: [[1, 1.0, 2.0, 3], 1]
[1, 1.0, 2.0, 3]
stack > [[1, 1.0, 2.0, 3]]

Попробуйте онлайн с отладкой!

Mathematica, 72 64 59 58 байт

(d=2;#//.x_:>Riffle[x,(x+{##2,}&@@x)/d++]~Cases~_Integer)&

Попробуйте онлайн!

Как это устроено

Мы принимаем входные данные в виде списка {p,q}. Шаг итерации переформулирован так:

1. Вставить (a+b)/dмежду каждыми двумя элементами aи b: (x+{##2,}&@@x)вычисляет последовательность a+b's, с a+Nullв конце. Мы делим на d, и Riffleвставляем каждый (a+b)/dмежду aи b. инкрементd .
2. Выделите Integerэлементы результирующего списка. (Это избавляет от Nullвведенного {##2,}тоже.)

Это повторяется до тех пор, пока результат не изменится (что может произойти только потому, что мы удалили все новые элементы, потому что ни один из них не был целым числом).

-8 байт благодаря @MartinEnder за использование //.вместо FixedPoint(и за принятие ввода в виде списка).

-6 больше, потому что на ListConvolveсамом деле это не так здорово

Рубин , 80 байт

->a,d=2{*b=a[0];a.each_cons 2{|x,y|z=x+y;b+=z%d>0?[y]:[z/d,y]};b==a ?a:f[b,d+1]}

Попробуйте онлайн!

Рекурсивная функция, fпринимающая входные данные в качестве массива [p, q].

Haskell, 85 81 байт

(a:b:c)#d=a:[div(a+b)d|mod(a+b)d<1]++(b:c)#d
l#d=l
l%d|l==l#d=l|e<-d+1=l#d%e
(%2)

Попробуйте онлайн!

Ввод принимается в виде списка, например [1,2].

Изменить: -4 байта благодаря @Laikoni.

Python 2 , 112 110 108 105 103 байт

^{-2 байта благодаря Джонатану Фреху
-5 байтов благодаря Эрику Аутгольферу}

y=input()
x=d=1
while x!=y:
 d+=1;x=y;y=x[:1]
 for a,b in zip(x,x[1:]):c=a+b;y+=[c/d,b][c%d>0:]
print x

Попробуйте онлайн!

Python 2 , 98 байт

f=lambda A,B=0,d=2:A*(A==B)or f(sum([[(l+r)/d,r][(l+r)%d>0:]for l,r in zip(A,A[1:])],A[:1]),A,d+1)

Вызывать как f([p,q]). Попробуйте онлайн!

Джонатан Аллан спас 12 байтов. Спасибо ~!

объяснение

fявляется рекурсивной функцией: f(A, B, d)возвращает значение f(next_A, A, d+1), если только A == B, в этом случае оно возвращает A. (Это обрабатывается следующим образом A*(A==B)or …: если A ≠ B, A*(A==B)это пустой список, который имеет значение false-y, поэтому …часть оценивается; если A = B, то A*(A==B)есть A, что непусто и, следовательно, верно, и оно возвращается.)

next_A вычисляется как:

sum([[(l+r)/d,r][(l+r)%d>0:]for l,r in zip(A,A[1:])],A[:1])

Это лучше всего объяснить на примере. Когда например d = 5 и A = [1, 4, 11, 8, 21]:

  sum([[(l+r)/d,r][(l+r)%d>0:]for l,r in zip(A,A[1:])],A[:1])
= sum([[(1+4)/d, 4], [(4+11)/d, 11], [8], [21]], [1])
= [1] + [1, 4] + [3, 11] + [8] + [21]
= [1, 1, 4, 3, 11, 8, 21]

Python 2 , 111 байт

A=input()
m=d=1
while m:
 m=o=0;d+=1
 while A[o+1:]:
	o+=1;s=A[o-1]+A[o]
	if s%d<1:A[o:o]=s/d,;m=1;o+=1
print A

Попробуйте онлайн!

-8 спасибо Роду .
-2 спасибо Линн .

Шелуха , 22 байта

→UG`λf£NΣẊṠeo/⁰+:.)⁰tN

Принимает список из 2 элементов, возвращает список целых чисел и чисел с плавающей точкой. Попробуйте онлайн!

объяснение

→UG`λf£NΣẊṠeo/⁰+:.)⁰tN  Input is a list L.
  G                 tN  Cumulative reduce over the list [2,3,4..
                   ⁰    with initial value L
   `λ             )     using flipped version of this function:
     f£NΣẊṠeo/⁰+:.       Arguments are a list, say K=[1,3,3], and a number, say d=4.
                :.       Prepend 0.5: [0.5,1,2,3]
         Ẋ               For each adjacent pair,
               +         take their sum,
            o/⁰          divide by d,
          Ṡe             and pair it with the right number in the pair: [[0.375,1],[1.0,3],[1.5,3]]
        Σ                Concatenate: [0.375,1,1.0,3,1.5,3]
     f£N                 Remove non-integers: [1,1.0,3,3]
                        Now we have an infinite list of L threaded through 2,3,4.. using the expansion operation.
 U                      Take longest prefix of unique elements,
→                       then last element of that.

Perl 5 , 92 + 1 ( -a) = 93 байта

do{$c=0;@n=shift@F;$.++;push@n,($t=$_+$n[-1])%$.?$_:($c=$t/$.,$_)for@F;@F=@n}while$c;say"@F"

Попробуйте онлайн!

Сетчатка , 111 байт

\d+
$*1;
^
11@
{+`(1+); (1+);
$1; $1$2 $2;
(?<=(?=(1+)).*) (\1)+ 
 a$#2$*1; 
 1+ 
 
.*a
1$&
)`a

1+@

1+
$.&
;

Попробуйте онлайн!

Принимает ввод как разделенные пробелами числа. Весьма наивно следует заданному алгоритму, при этом единственная заметная техника заключается в использовании символа маркера,a , чтобы отмечать, когда любое из чисел было сохранено. Это используется для работы с несколько ограниченными возможностями зацикливания Retina, которые позволяют вам зацикливаться только до тех пор, пока набор этапов не изменит общих входных данных этих этапов.

Объяснение:

Это будет использовать тот же пример, что и в вопросе.

\d+
$*1;

Мы изменим входной массив чисел в унарный массив, разделенный точкой с запятой, поэтому у нас будет:

1; 111111111111111111111;

^
11@

Поместите dв наш код в начале, давая нам:

11@1; 111111111111111111111;

{+`(1+); (1+);
$1; $1$2 $2;

Это немного сложнее. {запускает группу этапов, которые будут выполняться, пока они не достигнут фиксированной точки. Затем +указывает, что сам этот этап должен выполняться до фиксированной точки. Эта стадия добавляет каждую пару соседних чисел, но вставляет их без дополнительной точки с запятой. Теперь у нас будет:

11@1; 1111111111111111111111 111111111111111111111;

(?<=(?=(1+)).*) (\1)+ 
 a$#2$*1;

Другая сложная стадия, эта накапливает наш делитель в первой группе захвата и заменяет любое число в нашем списке без конечной точки с запятой на это число, разделенное на d. Мы также добавляем ведущие aк этим числам, чтобы указать, что что-то было сохранено, вместе с тем, ;чтобы указать, что это должно быть постоянно частью массива. Теперь у нас будет:

11@1; a11111111111; 111111111111111111111;

 1+ 

Это удаляет числа, которые не делятся dни в массиве до этого раунда. Это не вносит изменений в нашем примере.

.*a
1&$

Это жадно совпадает с начала строки до последней буквы aво входных данных. Это означает, что может быть не более одного матча. Если мы внесли какие-либо изменения, мы добавляем их d, в противном случае оставляем их такими же, чтобы мы могли выйти из цикла.

111@1; a11111111111; 111111111111111111111;

)`a

)Закрывает цикл , начатый {(не ставят под сомнение его!) , И в противном случае этот этап просто удаляет маркеры мы кладем вниз ранее. Так как это конец цикла, мы повторяем вышеупомянутые этапы много раз, однако я просто продолжу, как если бы я забыл цикл, поскольку это делает пример более непрерывным.

111@1; 11111111111; 111111111111111111111;

1+@

Этот этап удаляет из нашего вывода:

1; 11111111111; 111111111111111111111;

1+
$.&

Этот этап заменяет одинарные числа десятичными числами:

1; 11; 21;

;

Завершающий этап избавляет от точек с запятой:

1 11 21

Очевидно, что пропуск цикла лишает нас результата, но, надеюсь, это не смущает.

JavaScript (ES6), 89 87 82 байта

Спасибо @Arnauld за -2 байта и за помощь в сохранении еще 5 байтов.

f=(a,d=2,r)=>a.map(v=>b.push(v,...(v+=a[++i])%d<1?[r=v/d]:[]),b=i=[])|r?f(b,d+1):a

Принимает ввод в виде массива: f([p,q]) .

Тестовые случаи

f=(a,d=2,r)=>a.map(v=>b.push(v,...(v+=a[++i])%d<1?[r=v/d]:[]),b=i=[])|r?f(b,d+1):a

;[[1,1],[1,2],[1,3],[2,6],[3,13],[9,9],[60,68],[144,336],[12096,24192]]
.forEach(test=>O.innerText+=JSON.stringify(test)+" -> "+JSON.stringify(f(test))+"\n")

<pre id=O></pre>

Röda , 90 байт

f a,d=2{A=[a()|slide 2|[_,(_1+_)/d]if[(_1+_2)%d=0]else[_1]]+a[-1]f A,d=d+1 if[a!=A]else A}

Попробуйте онлайн!

Java 8, 180 байт

import java.util.*;p->q->{List<Integer>r=new Stack();r.add(p);r.add(q);for(int d=1,f=d,i;f==d++;)for(i=1;i<r.size();i++)if((q=r.get(i)+r.get(i-1))%d<1)r.add(i++,q/(f=d));return r;}

Объяснение:

Попробуй это здесь.

import java.util.*;           // Required import for List and Stack

p->q->{                       // Method with two integer parameters and List return-type
  List<Integer>r=new Stack(); //  Result-list
  r.add(p);r.add(q);          //  Add the two input-integers to the List
  for(int d=1,                //  Divisible integer (starting at 1)
          f=d,                //  Temp integer (starting at `d` / also 1)
          i;                  //  Index-integer
      f==d++;)                //  Loop (1) as long as `f` and `d` are equal
                              //  (and raise `d` by 1 so it starts at 2 inside the loop)
    for(i=1;                  //   Reset index-integer to 1
        i<r.size();i++)       //   Inner loop (2) over the List
      if((q=r.get(i)+r.get(i-1)) 
                              //    If the current + previous items (stored in `q`)
         %d<1)                //    are divisible by `d`:
        r.add(i++,q/(f=d));   //     Insert `q` divided by `d` to the List at index `i`
                              //     (and raise `i` by 1 and set `f` to `d` in the process)
                              //   End of inner loop (2) (implicit / single-line body)
                              //  End of loop (1) (implicit / single-line body)
  return r;                   //  Return the result-List
}                             // End of method

C #, 280 байт

using System.Linq;class A{static void Main(string[] p){var l=new System.Collections.Generic.List<int>(p.Select(int.Parse));int r,d=2,c;do{c=0;for(int i=1;i<l.Count;++i){if((r=l[i-1]+l[i])%d==0){l.Insert(i++,r/d);++c;}}++d;}while(c>0);l.ForEach(v=>System.Console.Write((v+" ")));}}

Первая попытка кода гольф, который является целой программой. Проверь это

Попытка 2, 159 байт

Убираем леса, поскольку задача состоит в том, чтобы предоставить функцию, которая может взять пару чисел (работает массив) и вернуть массив. Учитывая, что Func <int [], int []> F может использоваться для удовлетворения требований, просто определите F :

F=v=>{var l=new List<int>(v);int i,r,d=2,c;do{c=0;for(i=1;i<l.Count;++i){if((r=l[i-1]+l[i])%d==0){l.Insert(i++,r/d);++c;}}++d;}while(c>0);return l.ToArray();};

Протестируйте полную программу здесь

Это может быть меньше, если универсальный List считается допустимым выводом (сбросьте .ToArray (), чтобы сохранить 10 байтов).

Если вход также может быть изменен, то передача List <int> вместо массива избавляет от необходимости инициализировать вывод (выводится в 126 байтах).

Если сделать еще один шаг вперед, в этом случае нет необходимости возвращать значение. Использование Action вместо этого удаляет 9 байтов, используемых оператором return.

Желе , 19 байт

®‘©‘÷@+2\⁸żFfṀR$µÐL

Попробуйте онлайн!