Diberi dua bilangan bulat positif p dan q , tugas Anda adalah mengembalikan array A yang dibuat dengan menerapkan algoritma berikut:

1. Mulai dengan A = [p, q] dan d = 2
2. Untuk setiap pasangan (x, y) dari angka-angka yang berdekatan dalam A yang jumlahnya dapat dibagi dengan d , masukkan (x + y) / d antara x dan y .
3. Jika setidaknya satu pasangan yang cocok ditemukan, naikkan d dan lanjutkan dengan langkah # 2. Jika tidak, berhenti dan kembali A .

Contoh

Di bawah ini adalah detail proses untuk p = 1 dan 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

Maka output yang diharapkan: [1, 1, 4, 3, 11, 8, 21]

Klarifikasi dan aturan

• Input dan output dapat ditangani dalam format apa pun yang wajar. Bilangan bulat p dan q dijamin lebih besar dari 0. Jika itu membantu, Anda dapat mengasumsikan q ≥ p .
• Langkah kedua dari algoritma seharusnya tidak diterapkan secara rekursif ke elemen yang baru saja dimasukkan pada iterasi yang sama. Misalnya, A = [1, 1] dan d = 2 harus mengarah ke [1, 1, 1] (bukan daftar 1 yang tak terbatas).
• Ini kode-golf , jadi jawaban tersingkat dalam byte menang!

Uji kasus

  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]

Jika Anda ingin menguji kode Anda pada test case yang sedikit lebih besar, inilah output yang diharapkan untuk:

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

05AB1E , 28 19 18 byte

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

Cobalah online!

eh, pasti bisa ditingkatkan hardcore. masih bekerja untuk refactor.

Mungkin sebaik yang saya dapatkan.

Terima kasih, kepada siapa lagi selain, Emigna! Untuk menunjukkan swap bekerja lebih baik daripada register.

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

Debug dump untuk [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]]

Cobalah online dengan debug!

Mathematica, 72 64 59 58 byte

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

Cobalah online!

Bagaimana itu bekerja

Kami mengambil input sebagai daftar {p,q}. Langkah iterasi dirumuskan kembali sebagai:

1. Sisipkan (a+b)/dantara setiap dua elemen adan b: (x+{##2,}&@@x)hitung urutan a+b's, dengan sebuah a+Nulldi akhir. Kami membagi dengan d, dan Rifflemenyisipkan masing (a+b)/d- masing antara adan b. Penambahan d.
2. Pilih Integerelemen dari daftar yang dihasilkan. (Ini menghilangkan Nulldiperkenalkan juga oleh {##2,}.)

Ini diulangi sampai hasilnya tidak berubah (yang hanya bisa terjadi karena kami menghapus semua elemen baru, karena tidak ada yang bilangan bulat).

-8 byte terima kasih kepada @MartinEnder dari menggunakan //.alih-alih FixedPoint(dan dari mengambil input sebagai daftar).

-6 lebih karena ListConvolvesebenarnya tidak terlalu bagus

Ruby , 80 byte

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

Cobalah online!

Fungsi rekursif fmengambil input sebagai array [p, q].

Haskell, 85 81 byte

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

Cobalah online!

Input diambil sebagai daftar, mis [1,2].

Edit: -4 byte terima kasih kepada @Laikoni.

Python 2 , 112 110 108 105 103 byte

^{-2 byte terima kasih kepada Jonathan Frech
-5 byte terima kasih kepada 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

Cobalah online!

Python 2 , 98 byte

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)

Diminta sebagai f([p,q]). Cobalah online!

Jonathan Allan menyimpan 12 byte. Terima kasih ~!

Penjelasan

fadalah fungsi rekursif: f(A, B, d)evalutes untuk f(next_A, A, d+1), kecuali A == B, dalam hal ini kembali A. (Ini ditangani oleh A*(A==B)or …: jika A ≠ B, A*(A==B)adalah daftar kosong, yang salah-y, maka …bagian tersebut dievaluasi; jika A = B maka A*(A==B)adalah A, yang tidak kosong dan dengan demikian benar, dan akan dikembalikan.)

next_A dihitung sebagai:

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

Ini paling baik dijelaskan dengan contoh. Kapan misalnya d = 5 dan 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 byte

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

Cobalah online!

-8 Terima kasih kepada Rod .
Terima kasih kepada Lynn .

Sekam , 22 byte

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

Mengambil daftar 2-elemen, mengembalikan daftar bilangan bulat dan mengapung. Cobalah online!

Penjelasan

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

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

Cobalah online!

Retina , 111 byte

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

1+@

1+
$.&
;

Cobalah online!

Mengambil input sebagai angka yang dipisahkan spasi. Cukup naif mengikuti algoritma yang diberikan, dengan satu-satunya teknik yang terkenal adalah menggunakan simbol penanda a,, untuk mencatat ketika salah satu nomor telah disimpan. Ini digunakan untuk bekerja dengan kemampuan pengulangan yang agak terbatas dari Retina, yang hanya memungkinkan Anda untuk mengulang sampai satu set tahapan tidak membuat perubahan keseluruhan pada input ke tahapan tersebut.

Penjelasan:

Ini akan menggunakan contoh yang sama seperti dalam pertanyaan.

\d+
$*1;

Kami mengubah larik input angka menjadi larik unary yang dipisahkan koma, jadi kami harus:

1; 111111111111111111111;

^
11@

Masukkan dkode kita di awal, beri kami:

11@1; 111111111111111111111;

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

Ini sedikit lebih rumit. {memulai sekelompok tahapan yang akan dieksekusi hingga mencapai titik tetap. Kemudian, +menunjukkan bahwa tahap ini sendiri harus dieksekusi sampai titik yang tetap. Tahap ini menambahkan setiap pasangan angka yang berdekatan tetapi menyisipkannya tanpa titik koma tambahan. Sekarang kita akan memiliki:

11@1; 1111111111111111111111 111111111111111111111;

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

Tahap rumit lainnya, yang satu ini mengakumulasikan pembagi kami di grup tangkapan pertama, dan mengganti angka apa pun di daftar kami tanpa tanda titik koma dengan angka yang dibagi dengan d. Kami juga menambahkan arahan ake angka-angka ini, untuk menunjukkan bahwa ada sesuatu yang disimpan, bersama dengan ;untuk menunjukkan itu harus secara permanen menjadi bagian dari array. Sekarang kita akan memiliki:

11@1; a11111111111; 111111111111111111111;

 1+ 

Ini menghapus angka-angka yang tidak dapat dibagi oleh datau dalam array sebelum babak ini. Ini tidak membuat perubahan dalam contoh kita.

.*a
1&$

Ini serakah cocok dari awal string ke huruf terakhir adalam input. Ini berarti paling tidak ada satu pertandingan. Jika kami melakukan perubahan, kami menambahkannya d, jika tidak biarkan sama sehingga kami dapat keluar dari loop.

111@1; a11111111111; 111111111111111111111;

)`a

Yang )menutup loop dimulai oleh {(jangan mempertanyakannya!) Dan jika tidak, tahap ini hanya menghapus penanda yang kita letakkan sebelumnya. Karena ini adalah akhir dari loop, kami akan mengulangi tahap-tahap di atas berkali-kali, namun saya hanya akan melanjutkan seolah-olah saya telah melupakan loop, karena itu membuat contoh lebih berkelanjutan.

111@1; 11111111111; 111111111111111111111;

1+@

Tahap ini menghapus dari output kami:

1; 11111111111; 111111111111111111111;

1+
$.&

Tahap ini menggantikan angka unary dengan angka desimal:

1; 11; 21;

;

Tahap terakhir menghilangkan titik koma:

1 11 21

Jelas, melewatkan loop membuat kami memiliki hasil yang salah di sini, tapi mudah-mudahan itu tidak terlalu membingungkan.

JavaScript (ES6), 89 87 82 byte

Terima kasih @Arnauld untuk -2 byte dan untuk membantu menghemat 5 byte lagi.

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

Mengambil input sebagai array: f([p,q]).

Uji Kasus

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 byte

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}

Cobalah online!

Java 8, 180 byte

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

Penjelasan:

Coba di sini.

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 byte

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

Upaya pertama pada kode golf, yang merupakan keseluruhan program. Menguji

Percobaan 2, 159 byte

Mengambil perancah, karena tugasnya adalah untuk menyediakan fungsi yang dapat mengambil sepasang angka (array berfungsi) dan mengembalikan array. Mengingat bahwa Func <int [], int []> F dapat digunakan untuk memenuhi persyaratan, cukup tentukan 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();};

Uji Program Lengkap Di Sini

Ini bisa lebih kecil jika Daftar generik dianggap sebagai output yang valid (jatuhkan .ToArray () untuk menghemat 10 byte).

Jika input juga dapat dimodifikasi, maka meneruskan Daftar <int> alih-alih sebuah array menghilangkan kebutuhan untuk menginisialisasi output (keluar pada 126 byte).

Mengambil langkah ini lebih jauh, tidak perlu benar-benar ada nilai balik dalam kasus ini. Menggunakan Aksi bukannya menghapus 9 byte yang digunakan oleh pernyataan kembali.

Jelly , 19 byte

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

Cobalah online!