Powinieneś napisać program lub funkcję, która podając listę dodatnich liczb całkowitych zwielokrotnia każdy element przez najmniejszą dodatnią liczbę całkowitą możliwą do utworzenia ściśle rosnącej listy.

Na przykład, jeśli dane wejściowe to

5 4 12 1 3

mnożenia będą

5*1=5 4*2=8 12*1=12 1*13=13 3*5=15

a wynikiem będzie rosnąca lista

5 8 12 13 15

Wkład

• Lista dodatnich liczb całkowitych zawierających co najmniej 1 element

Wydajność

• Lista liczb całkowitych dodatnich

Przykłady

9 => 9
1 2 => 1 2
2 1 => 2 3
7 3 => 7 9
1 1 1 1 => 1 2 3 4
5 4 12 1 3 => 5 8 12 13 15
3 3 3 8 16 => 3 6 9 16 32
6 5 4 3 2 1 => 6 10 12 15 16 17
9 4 6 6 5 78 12 88 => 9 12 18 24 25 78 84 88
8 9 41 5 12 3 5 6 => 8 9 41 45 48 51 55 60
15 8 12 47 22 15 4 66 72 15 3 4 => 15 16 24 47 66 75 76 132 144 150 153 156

To jest kod golfowy, więc wygrywa najkrótszy program lub funkcja.

Ciekawostka: ostatnim elementem danych wejściowych N, N-1, ... ,1wydaje się być (N+1)thelement sekwencji A007952 . Jeśli znajdziesz dowód, możesz dołączyć go do odpowiedzi na golfa lub opublikować jako komentarz.

Galaretka , 6 5 bajtów

:‘×µ\

Pierwsza odpowiedź Jelly, zanim @Dennis budzi się i bije mnie. Wypróbuj online!

Wyjaśnienie

:          Integer division, m//n
 ‘         Increment, (m//n+1)
  ×        Multiply, (m//n+1)*n
   µ       Turn the previous links into a new monadic chain
    \      Accumulate on the array

Dzięki @Dennis za -1 bajtów.

JavaScript (ES6), 28

Edytuj Zgodnie z sugestią @Patrick Roberts, pmoże być niezainicjowanym parametrem. Ta sama liczba bajtów, ale unikaj używania zmiennej globalnej

(a,p)=>a.map(n=>p=n*-~(p/n))

TEST

f=(a,p)=>a.map(n=>p=n*-~(p/n))

console.log=x=>O.textContent+=x+'\n'

;[
[[9], [ 9]],
[[1, 2], [ 1, 2]],
[[2, 1], [ 2, 3]],
[[7, 3], [ 7, 9]],
[[1, 1, 1, 1], [ 1, 2, 3, 4]],
[[5, 4, 12, 1, 3], [ 5, 8, 12, 13, 15]],
[[3, 3, 3, 8, 16], [ 3, 6, 9, 16, 32]],
[[6, 5, 4, 3, 2, 1], [ 6, 10, 12, 15, 16, 17]],
[[9, 4, 6, 6, 5, 78, 12, 88], [ 9, 12, 18, 24, 25, 78, 84, 88]],
[[8, 9, 41, 5, 12, 3, 5, 6], [ 8, 9, 41, 45, 48, 51, 55, 60]],
[[15, 8, 12, 47, 22, 15, 4, 66, 72, 15, 3, 4], [ 15, 16, 24, 47, 66, 75, 76, 132, 144, 150, 153, 156]]
].forEach(t=>{
  var i=t[0],k=t[1],r=f(i),ok=(k+'')==(r+'')
  console.log(i + ' => ' + r + (ok?' OK':'FAIL expecting '+x))
})

<pre id=O></pre>

Python 2, 67 64 bajtów

Najpierw spróbuj golfa, więc wskazówki są mile widziane.

def m(l):
 for x in range(1,len(l)):l[x]*=l[x-1]/l[x]+1
 print l

PHP, 55 46 42 41 bajtów

Wykorzystuje kodowanie ISO 8859-1.

for(;$a=$argv[++$i];)echo$l+=$a-$l%$a,~ß;

Działaj w ten sposób ( -ddodano tylko dla estetyki):

php -d error_reporting=30709 -r 'for(;$a=$argv[++$i];)echo$l+=$a-$l%$a,~ß;' 10 10 8

• Zapisano 1 bajt dzięki Ismael Miguel.
• Zaoszczędzono 8 bajtów, używając modulo zamiast floor
• Zapisano 4 bajty dzięki Ismael Miguel (zamiast zamiast foreach)
• Zapisano bajt, używając ~ßdo uzyskania spacji.

Haskell (30 28 25 bajtów)

scanl1(\x y->y*div x y+y)

Wersja rozszerzona

f :: Integral n => [n] -> [n]
f xs = scanl1 increaseOnDemand xs
 where
   increaseOnDemand :: Integral n => n -> n -> n
   increaseOnDemand acc next = next * (1 + acc `div` next)

Wyjaśnienie

scanl1umożliwia złożenie listy i zgromadzenie wszystkich wartości pośrednich na innej liście. Jest to specjalizacja scanl, która ma następujący typ:

scanl  :: (acc  -> elem -> acc)  -> acc -> [elem] -> [acc]
scanl1 :: (elem -> elem -> elem) ->        [elem] -> [elem]

scanl1 f (x:xs) = scanl f x xs

Dlatego wszystko, czego potrzebujemy, to odpowiednia funkcja, która bierze dwa ostatni element naszej listy ( accw wersji rozszerzonej) i ten, który chcemy przetworzyć ( nextw wersji rozszerzonej) i zwrócić odpowiednią liczbę.

Możemy łatwo wyliczyć tę liczbę, dzieląc akumulator przez następny i wylewając wynik. divdba o to. Następnie musimy po prostu dodać, 1aby upewnić się, że lista faktycznie się powiększa (i że tak się nie stanie 0).

C ++, 63 60 57 bajtów

void s(int*f,int*e){for(int c=*f;++f!=e;c=*f+=c/ *f**f);}

Działa w miejscu, biorąc pod uwagę zakres [first, last). Pierwotnie napisany jako wariant szablonu, ale był dłuższy:

template<class T>void s(T f,T e){for(auto c=*f;++f!=e;c=*f+=c/ *f**f);}

Rozszerzona wersja

template <class ForwardIterator>
void sort(ForwardIterator first, ForwardIterator last){
    auto previous = *first;

    for(++first; first != last; ++first){
        auto & current = *first;
        current += current * (current / previous);
        previous = current;
    }
}

CJam, 13 bajtów

q~{\_p1$/)*}*

Wprowadź jako listę w stylu CJam. Wyjście jest oddzielone od linii.

Sprawdź to tutaj.

Wyjaśnienie

q~    e# Read and evaluate input.
{     e# Fold this block over the list (i.e. "foreach except first")...
  \   e#   Swap with previous value.
  _p  e#   Duplicate and print previous value.
  1$  e#   Copy current value.
  /   e#   Integer division.
  )*  e#   Increment and multiply current value by the result.
}*

Ostateczna wartość pozostawia się na stosie i drukuje automatycznie na końcu.

Matematyka, 36 32 bajty

 #2(Floor[#1/#2]+1)&~FoldList~#&

Test

#2(Floor[#1/#2]+1)&~FoldList~#& /@ {{5, 4, 12, 1, 3}, 
   {15, 8, 12, 47, 22, 15, 4, 66, 72, 15, 3, 4}}
(* {{5, 8, 12, 13, 15}, {15, 16, 24, 47, 66, 75, 76, 132, 144, 
  150, 153, 156}} *)

Perl, 17 + 3 = 20 bajtów

$p=$_*=$==1+$p/$_

Wymaga -pi oznacza -l:

$ perl -ple'$p=$_*=$==1+$p/$_' <<< $'15\n8\n12\n47\n22\n15\n4\n66\n72\n15\n3\n4'
15
16
24
47
66
75
76
132
144
150
153
156

Wyjaśnienie:

# '-p' reads each line into $_ and auto print
# '-l' chomp off newline on input and also inserts a new line when printing
# When assigning a number to `$=` it will automatic be truncated to an integer
# * Added newlines for each assignment 
$p=
  $_*=
    $==
      1+$p/$_

Python (3.5), 63 62 bajty

def f(a):
 r=[0]
 for i in a:r+=i*(r[-1]//i+1),
 return r[1:]

Test

>>> print('\n'.join([str(i)+' => '+str(f(i)) for i in [[9],[1,2],[2,1],[7,3],[1,1,1,1],[5,4,12,1,3],[3,3,3,8,16],[6,5,4,3,2,1],[9,4,6,6,5,78,12,88],[8,9,41,5,12,3,5,6],[15,8,12,47,22,15,4,66,72,15,3,4]]]))
[9] => [9]
[1, 2] => [1, 2]
[2, 1] => [2, 3]
[7, 3] => [7, 9]
[1, 1, 1, 1] => [1, 2, 3, 4]
[5, 4, 12, 1, 3] => [5, 8, 12, 13, 15]
[3, 3, 3, 8, 16] => [3, 6, 9, 16, 32]
[6, 5, 4, 3, 2, 1] => [6, 10, 12, 15, 16, 17]
[9, 4, 6, 6, 5, 78, 12, 88] => [9, 12, 18, 24, 25, 78, 84, 88]
[8, 9, 41, 5, 12, 3, 5, 6] => [8, 9, 41, 45, 48, 51, 55, 60]
[15, 8, 12, 47, 22, 15, 4, 66, 72, 15, 3, 4] => [15, 16, 24, 47, 66, 75, 76, 132, 144, 150, 153, 156]

Poprzednie rozwiązanie

niektóre rozwiązania rekurencyjne, ale większe

(68 bytes) f=lambda a,i=0:[i,*f(a[1:],a[0]*(i//a[0]+1))][i==0:]if a!=[]else[i]
(64 bytes) f=lambda a,i=0:a>[]and[i,*f(a[1:],a[0]*(i//a[0]+1))][i<1:]or[i]

Brachylog , 12 bajtów

{≤.;?%0∧}ᵐ<₁

Na tyle dziwne, że pomnożenie każdej zmiennej przez liczbę zacznie się od pomnożenia przez 2, a nie 0 lub 1. To wydaje się jednak działać i pokonuje obie inne implementacje Brachylog

Wyjaśnienie

{       }ᵐ          --  Map each number
 ≤.                 --      to a number greater or equal to the original
  .;?%0             --      and a multiple of the original
       ∧            --      no more constraints
          <₁        --  so that the list is strictly increasing

Wypróbuj online!

Brachylog , 54 bajty

:_{h_.|[L:T],LhH,(T_,IH;0:$Ie*H=:T>I),Lb:I:1&:[I]rc.}.

Wyjaśnienie

:_{...}.                § Call sub-predicate 1 with [Input, []] as input. Unify its output
                        § with the output of the main predicate


§ Sub-predicate 1

h_.                     § If the first element of the input is an empty list, unify the
                        § output with the empty list
|                       § Else
[L:T],LhH,              § Input = [L,T], first element of L is H
    (T_,IH              §     If T is the empty list, I = H
    ;                   §     Else
    0:$Ie*H=:T>I),      §     Enumerate integers between 0 and +inf, stop and unify the
                        §     enumerated integer with I only if I*H > T
Lb:I:1&                 § Call sub-predicate 1 with input [L minus its first element, I]
:[I]rc.                 § Unify the output of the sub-predicate with
                        § [I|Output of the recursive call]

Pyth, 11

t.u*Yh/NYQ0

Pakiet testowy

Czy skumulowane zmniejszenie, zmniejszenie, które zwraca wszystkie wartości pośrednie, zaczynając od 0. Ponieważ wejście na pewno zawiera tylko dodatnie liczby całkowite, jest to w porządku. Na każdym etapie bierzemy starą wartość, dzielimy ją przez nową wartość i dodajemy 1, a następnie mnożymy przez nową wartość.

C, 79 bajtów

p;main(x,v)char**v;{for(;*++v;printf("%d ",p=((x+p-1)/x+!(p%x))*x))x=atoi(*v);}

Bez golfa

p; /* previous value */

main(x,v) char**v;
{
    /* While arguments, print out x such that x[i] > x[i-1] */
    for(;*++v; printf("%d ", p = ((x+p-1)/x + !(p%x)) * x))
        x = atoi(*v);
}

PowerShell, 26 bajtów

$args[0]|%{($l+=$_-$l%$_)}

Pobiera dane wejściowe jako jawną tablicę, np . > .\sort-by-multiplying.ps1 @(6,5,4,3,2,1)Przez $args[0].

Następnie omijamy to za pomocą |%{...}i każda iteracja wykonuje magię . Nie, żartuję, używamy tej samej sztuczki modulo, co inne odpowiedzi (rekwizyty dla @aross, ponieważ zauważyłem ją tam wcześniej).

Hermetyzujące pareny (...)zapewniają, że wynik operacji matematycznej jest umieszczany na rurociągu, a tym samym generowany. Gdybyśmy to pominęli, nic nie byłoby wypisywane, ponieważ $lzmienna jest zbierana w śmieci po zakończeniu wykonywania.

Przykład

PS C:\Tools\Scripts\golfing> .\sort-by-multiplying.ps1 @(8,9,1,5,4)
8
9
10
15
16

Japt, 11 bajtów

Uå@Y*-~(X/Y

Przetestuj online!

Jak to działa

          // Implicit: U = input array of integers
Uå@       // Cumulative reduce: map each previous value X and current value Y to:
-~(X/Y    //  floor(X/Y+1).
          // Implicit: output last expression

05AB1E , 11 bajtów

Kod:

R`[=sŽDŠ/ò*

Wypróbuj online!

Wyjaśnienie:

R            # Reverse input
 `           # Flatten the list
  [          # While loop
   =         # Print the last item
    s        # Swap the last two items
     Ž       # If the stack is empty, break
      D      # Duplicate top of the stack
       Š     # Pop a,b,c and push c,a,b
        /    # Divide a / b
         ò   # Inclusive round up
          *  # Multiply the last two items

Wykorzystuje kodowanie CP-1252.

Minkolang 0,15 , 17 bajtów

nd1+?.z0c:1+*d$zN

Wypróbuj tutaj!

Wyjaśnienie

nd                   Take number from input and duplicate it
  1+                 Add 1
    ?.               Stop if top of stack is 0 (i.e., when n => -1 because input is empty).
      z              Push value from register
       0c            Copy first item on stack
         :           Pop b,a and push a//b
          1+         Add 1
            *        Multiply
             d$z     Duplicate and store in register
                N    Output as number

Zasadniczo rejestr przechowuje najnowszego członka rosnącej listy, który jest dzielony przez dane wejściowe i zwiększany, aby uzyskać mnożnik dla następnego członka. Toroidalna właściwość pola kodu Minkolanga oznacza, że ​​pętla ta odbywa się poziomo bez potrzeby ()lub []pętli.

Brachylog , 21 bajtów

l~lCℕ₁ᵐ≤ᵛ~+?&;Cz≜×ᵐ<₁

Wypróbuj online!

Wykorzystuje sumę wartości wejściowych jako górną granicę dla współczynników C. Dość wolno, przekroczenie limitu czasu dla TIO dla list wejściowych dłuższych niż 5 lub 6 (również w zależności od sumy wartości). Ale nie tak wolno, jak moja oryginalna wersja, która wymaga niewielkich list składających się z maksymalnie 3 elementów z małymi wartościami, aby nie przekroczyć limitu czasu:

21 bajtów

l~l.&+^₂⟦₁⊇.;?z/ᵐℕ₁ᵐ∧

Wypróbuj online!

C (gcc) , 37 bajtów

o(int*_){for(;*++_;)*_*=_[~0]/ *_+1;}

Wypróbuj online!

Python 2 , 53 bajty

lambda a:reduce(lambda b,v:b+[b[-1]/v*v+v],a,[0])[1:]

Wypróbuj online!

k*x>yimplikuje k>y/x; więc najmniejszy kmoże być k=floor(y/x)+1. Ponieważ w Pythonie 2.7 dzielenie liczb całkowitych jest już przyjmowane jako floor, chcemy k=y/x+1i k*x = (y/x+1)*x = y/x*x+x.

Oracle SQL 11.2, 210 bajtów

WITH v AS(SELECT TO_NUMBER(COLUMN_VALUE)a,rownum i FROM XMLTABLE(('"'||REPLACE(:1,' ','","')||'"'))),c(p,n)AS(SELECT a,2 FROM v WHERE i=1UNION ALL SELECT a*CEIL((p+.1)/a),n+1 FROM c,v WHERE i=n)SELECT p FROM c;

Bez golfa

WITH v AS                                           
(
  SELECT TO_NUMBER(COLUMN_VALUE)a, rownum i            -- Convert the input string into rows 
  FROM   XMLTABLE(('"'||REPLACE(:1,' ','","')||'"'))   -- using space as the separator between elements
)
, c(p,n) AS                        
(
  SELECT a, 2 FROM v WHERE i=1                         -- Initialize the recursive view
  UNION ALL 
  SELECT a*CEIL((p+.1)/a),n+1 FROM c,v WHERE i=n       -- Compute the value for the nth element
)
SELECT p FROM c;

Program Cheza (140 bajtów)

Wersja do gry w golfa:

(define(f l)(define(g l p m)(cond((null? l)l)((<(*(car l)m)(+ p 1))(g l p(+ m 1)))(else(cons(*(car l)m)(g(cdr l)(* m(car l))1)))))(g l 0 1))

Wersja bez golfa:

(define(f l)
  (define(g l p m)
    (cond
      ((null? l) l)
      ((< (* (car l) m) (+ p 1)) (g l p (+ m 1)))
      (else (cons (* (car l) m) (g (cdr l) (* m (car l)) 1)))
    )
  )
  (g l 0 1)
)

Wypróbuj online!

K (oK) , 11 bajtów

{y*1+_x%y}\

Wypróbuj online!