Biorąc pod uwagę dwie dodatnie liczby całkowite p i q , Twoim zadaniem jest zwrócić tablicę A utworzoną przez zastosowanie następującego algorytmu:

1. Początek z A = [s, q], i D = 2
2. Dla każdej pary (x, y) ciągłych liczb w A, których suma jest podzielna przez d , wstaw (x + y) / d między x i y .
3. Jeśli znaleziono co najmniej jedną pasującą parę, zwiększ d i przejdź do kroku # 2. W przeciwnym razie zatrzymania i powrót .

Przykład

Poniżej znajduje się szczegółowość procesu dla p = 1 i 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

Stąd oczekiwany wynik: [1, 1, 4, 3, 11, 8, 21]

Wyjaśnienia i zasady

• Dane wejściowe i wyjściowe mogą być obsługiwane w dowolnym rozsądnym formacie. Liczby całkowite p i q są z pewnością większe niż 0. Jeśli to pomoże, możesz założyć, że q ≥ p .
• Drugi krok algorytmu nie powinien być rekurencyjnie stosowany do elementów, które właśnie zostały wstawione w tej samej iteracji. Na przykład, A = [1, 1], i D = 2 powinna prowadzić do [1, 1, 1] (nie nieskończonym Lista 1'S).
• To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach!

Przypadki testowe

  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]

Jeśli chcesz przetestować kod na nieco większym przypadku testowym, oto oczekiwane dane wyjściowe dla:

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

05AB1E , 28 19 18 bajtów

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

Wypróbuj online!

eh, zdecydowanie można poprawić hardcore. wciąż pracuje nad refaktoryzacją.

Prawdopodobnie tak dobrze, jak to rozumiem.

-1 dzięki, kto jeszcze oprócz, Emigna! Za wskazanie zamiany działało lepiej niż rejestry.

[                   // 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.

Zrzut debugowania dla [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]]

Wypróbuj online z debugowaniem!

Mathematica, 72 64 59 58 bajtów

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

Wypróbuj online!

Jak to działa

Traktujemy dane wejściowe jako listę {p,q}. Krok iteracji przeformułowano w następujący sposób:

1. Wstaw (a+b)/dpomiędzy co dwa elementy ai b: (x+{##2,}&@@x)oblicza sekwencję a+bz a+Nullna końcu. Dzielimy di Rifflewstawiamy każdy (a+b)/dmiędzy ai b. Przyrost d.
2. Wybierz Integerelementy z wynikowej listy. (Pozbywa się również Nullwprowadzonego przez {##2,}.)

Jest to powtarzane, dopóki wynik się nie zmieni (co może się zdarzyć tylko dlatego, że usunęliśmy wszystkie nowe elementy, ponieważ żaden z nich nie był liczbami całkowitymi).

-8 bajtów dzięki @MartinEnder od używania //.zamiast FixedPoint(i od pobierania danych wejściowych jako listy).

-6 więcej, bo ListConvolvetak naprawdę nie jest tak świetnie

Rubinowy , 80 bajtów

->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]}

Wypróbuj online!

Funkcja rekurencyjna fprzyjmująca dane wejściowe jako tablicę [p, q].

Haskell, 85 81 bajtów

(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)

Wypróbuj online!

Dane wejściowe są traktowane jako lista, np [1,2].

Edycja: -4 bajty dzięki @Laikoni.

Python 2 , 112 110 108 105 103 bajtów

^{-2 bajki dzięki Jonathan Frech
-5 bajtów dzięki Erik the Outgolfer}

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

Wypróbuj online!

Python 2 , 98 bajtów

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)

Wywołaj jako f([p,q]). Wypróbuj online!

Jonathan Allan zapisał 12 bajtów. Dzięki ~!

Wyjaśnienie

fjest funkcją rekurencyjną: f(A, B, d)ewaluuje do f(next_A, A, d+1), chyba że A == B, w którym to przypadku zwraca A. (Jest to obsługiwane przez A*(A==B)or …: jeśli A ≠ B, A*(A==B)to pusta lista, która jest fałszem-y, więc …część jest oceniana; jeśli A = B, to A*(A==B)jest A, która jest niepusta, a zatem zgodna z prawdą, i jest zwracana.)

next_A jest obliczany jako:

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

Można to najlepiej wyjaśnić przykładem. Kiedy np. d = 5 I 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 bajtów

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

Wypróbuj online!

-8 dzięki Rod .
-2 dzięki Lynn .

Łuska , 22 bajty

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

Pobiera 2-elementową listę, zwraca listę liczb całkowitych i liczb zmiennoprzecinkowych. Wypróbuj online!

Wyjaśnienie

→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 bajty

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

Wypróbuj online!

Siatkówka , 111 bajtów

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

1+@

1+
$.&
;

Wypróbuj online!

Pobiera dane wejściowe jako liczby oddzielone spacjami. Całkiem naiwnie podąża za danym algorytmem, a jedyną godną uwagi techniką jest użycie symbolu znacznika a, aby zauważyć, kiedy zachowana została dowolna liczba. Służy to do pracy z nieco ograniczonymi możliwościami zapętlania Retiny, które pozwalają tylko zapętlać, dopóki zestaw stopni nie wprowadzi ogólnej zmiany w danych wejściowych do tych stopni.

Wyjaśnienie:

Użyjemy tego samego przykładu, co w pytaniu.

\d+
$*1;

Zmieniamy tablicę liczb wejściowych na tablicę jedności oddzieloną średnikami, abyśmy mieli:

1; 111111111111111111111;

^
11@

Wstaw ddo naszego kodu na początku, dając nam:

11@1; 111111111111111111111;

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

To jest nieco bardziej skomplikowane. {rozpoczyna grupę etapów, które będą wykonywane, dopóki nie osiągną ustalonego punktu. Następnie +wskazuje, że sam ten etap powinien być wykonywany do stałego punktu. Ten etap dodaje każdą parę sąsiednich liczb, ale wstawia je bez dodatkowego średnika. Teraz mielibyśmy:

11@1; 1111111111111111111111 111111111111111111111;

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

Drugi trudny etap, ten gromadzi nasz dzielnik w pierwszej grupie przechwytywania i zastępuje dowolną liczbę na naszej liście bez średnika końcowego z tą liczbą podzieloną przez d. Dodajemy również wiodące ado tych liczb, aby wskazać, że coś zostało zachowane, wraz z ;oznaczeniem, że powinno to być na stałe częścią tablicy. Teraz mielibyśmy:

11@1; a11111111111; 111111111111111111111;

 1+ 

Spowoduje to usunięcie liczb, które nie były podzielne przez dani w tablicy przed tą rundą. Nie powoduje to zmian w naszym przykładzie.

.*a
1&$

To zachłannie dopasowuje od początku ciągu do ostatniej litery ana wejściu. Oznacza to, że może być maksymalnie jeden mecz. Jeśli wprowadziliśmy jakieś zmiany, dodajemy jedną d, w przeciwnym razie pozostawiamy to samo, abyśmy mogli wyjść z pętli.

111@1; a11111111111; 111111111111111111111;

)`a

)Zamyka pętlę zapoczątkowaną przez {(nie kwestionują to!), A poza tym na tym etapie po prostu usuwa znaczniki Włożyliśmy w dół wcześniej. Ponieważ jest to koniec pętli, powtarzalibyśmy powyższe etapy wiele razy, jednak zamierzam kontynuować, tak jakbym zapomniał pętli, ponieważ dzięki temu przykład jest bardziej ciągły.

111@1; 11111111111; 111111111111111111111;

1+@

Ten etap usuwa z naszej produkcji:

1; 11111111111; 111111111111111111111;

1+
$.&

Ten etap zastępuje liczby jednostkowe liczbami dziesiętnymi:

1; 11; 21;

;

Ostatni etap pozbywa się średników:

1 11 21

Oczywiście pomijanie pętli powoduje, że mamy tutaj niepoprawny wynik, ale mam nadzieję, że nie jest to zbyt mylące.

JavaScript (ES6), 89 87 82 bajtów

Dzięki @Arnauld za -2 bajty i za pomoc w oszczędzaniu 5 dodatkowych bajtów.

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

Staje wejściowy jako tablicy: f([p,q]).

Przypadki testowe

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 bajtów

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}

Wypróbuj online!

Java 8, 180 bajtów

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;}

Wyjaśnienie:

Wypróbuj tutaj.

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 bajtów

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+" ")));}}

Pierwsza próba kodowania golfa, czyli całego programu. Sprawdź to

Próba 2, 159 bajtów

Odebranie rusztowania, ponieważ zadaniem jest zapewnienie funkcji, która może przyjąć parę liczb (tablica działa) i zwraca tablicę. Biorąc pod uwagę, że Func <int [], int []> F może być użyty do spełnienia wymagań, wystarczy zdefiniować 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();};

Przetestuj pełny program tutaj

Może być mniejszy, jeśli ogólna lista jest uważana za prawidłowe wyjście (upuść .ToArray (), aby zapisać 10 bajtów).

Jeśli dane wejściowe można również zmodyfikować, to przekazanie List <int> zamiast tablicy eliminuje potrzebę inicjowania wyjścia (wychodzi na 126 bajtów).

Idąc o krok dalej, tak naprawdę nie ma potrzeby zwracania wartości w tym przypadku. Zamiast tego użycie akcji usuwa 9 bajtów używanych przez instrukcję return.

Galaretka , 19 bajtów

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

Wypróbuj online!