Sie sollten ein Programm oder eine Funktion schreiben, die bei einer Liste positiver Ganzzahlen jedes Element mit der kleinstmöglichen positiven Ganzzahl multipliziert, um eine streng ansteigende Liste zu erstellen.

Zum Beispiel, wenn der Eingang ist

5 4 12 1 3

die Multiplikationen werden sein

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

und die Ausgabe wird die aufsteigende Liste sein

5 8 12 13 15

Eingang

• Eine Liste positiver Ganzzahlen mit mindestens einem Element

Ausgabe

• Eine Liste positiver Ganzzahlen

Beispiele

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

Dies ist Codegolf, also gewinnt das kürzeste Programm oder die kürzeste Funktion.

Unterhaltsame Tatsache: Das letzte Element der Ausgabe für die Eingabe N, N-1, ... ,1scheint das (N+1)thElement der Sequenz A007952 zu sein . Wenn Sie einen Beweis finden, können Sie ihn gerne in Ihre Golfantwort aufnehmen oder als Kommentar posten.

Gelee , 6 5 Bytes

:‘×µ\

Erste Gelee-Antwort, bevor @Dennis aufwacht und mich schlägt. Probieren Sie es online!

Erläuterung

:          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

Vielen Dank an @Dennis für -1 Byte.

JavaScript (ES6), 28

Bearbeiten Kann, wie von @Patrick Roberts vorgeschlagen, pein nicht initialisierter Parameter sein. Gleiche Byteanzahl, aber keine globale Variable verwenden

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

PRÜFUNG

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 Bytes

Versuchen Sie zuerst, Code-Golf zu spielen. Tipps sind also willkommen.

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 Bytes

Verwendet ISO 8859-1-Codierung.

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

Laufen Sie wie folgt ( -dnur aus ästhetischen Gründen hinzugefügt):

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

• 1 Byte Dank an Ismael Miguel gespeichert.
• 8 Bytes gespart, indem modulo anstelle von floor verwendet wurde
• 4 Bytes an Ismael Miguel gespart (für statt für jeden)
• Ein Byte mit gespeichert ~ß, um ein Leerzeichen zu ergeben.

Haskell (30 28 25 Bytes)

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

Erweiterte Version

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)

Erläuterung

scanl1Mit dieser Option können Sie eine Liste falten und alle Zwischenwerte in einer anderen Liste zusammenfassen. Es ist eine Spezialisierung von scanl, die den folgenden Typ hat:

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

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

Aus diesem Grund benötigen wir nur eine geeignete Funktion, die das letzte Element unserer Liste ( accin der erweiterten Version) und das zu verarbeitende Element ( nextin der erweiterten Version) enthält und eine geeignete Nummer zurückgibt.

Wir können diese Zahl leicht ableiten, indem wir den Akku durch den nächsten teilen und das Ergebnis auswerten. divkümmert sich darum. Danach müssen wir nur noch hinzufügen, 1um sicherzustellen, dass die Liste tatsächlich wächst (und dass wir nicht dazu kommen 0).

C ++, 63 60 57 Bytes

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

Funktioniert in einem bestimmten Bereich [first, last). Ursprünglich als Template-Variante geschrieben, aber das war länger:

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

Erweiterte Version

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 Bytes

q~{\_p1$/)*}*

Eingabe als CJam-Liste. Der Ausgang ist zeilenweise getrennt.

Teste es hier.

Erläuterung

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.
}*

Der Endwert bleibt auf dem Stapel und wird am Ende automatisch ausgedruckt.

Mathematica, 36 32 Bytes

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

Prüfung

#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 Bytes

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

Benötigt -pund -lFahnen:

$ 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

Erläuterung:

# '-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 Bytes

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

Prüfung

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

Vorherige Lösung

Einige rekursive Lösungen sind jedoch größer

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

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

Der seltsame Versuch, jede Variable mit einer Zahl zu multiplizieren, beginnt mit dem Versuch, mit 2 und nicht mit 0 oder 1 zu multiplizieren. Dies scheint jedoch zu funktionieren und schlägt beide anderen Brachylog-Implementierungen

Erläuterung

{       }ᵐ          --  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

Probieren Sie es online!

Brachylog , 54 Bytes

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

Erläuterung

:_{...}.                § 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

Test Suite

Führt eine kumulative Reduzierung durch, die alle Zwischenwerte zurückgibt, beginnend mit 0. Da die Eingabe garantiert nur positive Ganzzahlen enthält, ist dies in Ordnung. In jedem Schritt nehmen wir den alten Wert, dividieren ihn durch den neuen Wert und addieren ihn 1, dann multiplizieren wir ihn mit dem neuen Wert.

C 79 Bytes

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

Ungolfed

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 Byte

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

Übernimmt Eingaben als explizites Array, z . B. > .\sort-by-multiplying.ps1 @(6,5,4,3,2,1)über $args[0].

Wir durchlaufen dann die Schleife mit |%{...}und führen bei jeder Iteration eine Magie aus . Nein, nur ein Scherz, wir verwenden den gleichen Modulo-Trick wie andere Antworten (Requisiten für @aross, weil ich ihn dort zuerst entdeckt habe).

Die einkapselnden Parens stellen (...)sicher, dass das Ergebnis der mathematischen Operation in der Pipeline platziert und somit ausgegeben wird. Wenn wir diese auslassen, wird nichts ausgegeben, da die $lVariable nach Abschluss der Ausführung durch Garbage-Collection erfasst wird.

Beispiel

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

Japt, 11 Bytes

Uå@Y*-~(X/Y

Online testen!

Wie es funktioniert

          // 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 Bytes

Code:

R`[=sŽDŠ/ò*

Probieren Sie es online!

Erläuterung:

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

Verwendet die CP-1252-Codierung.

Minkolang 0,15 , 17 Bytes

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

Probieren Sie es hier aus!

Erläuterung

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

Im Wesentlichen behält das Register das neueste Mitglied der aufsteigenden Liste bei, und dieses wird durch die Eingabe geteilt und inkrementiert, um den Multiplikator für das nächste Mitglied zu erhalten. Das toroidale Merkmal von Minkolangs Codefeld bedeutet, dass es horizontal ohne die Notwendigkeit von ()oder []Schleifen geschleift wird .

Brachylog , 21 Bytes

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

Probieren Sie es online!

Verwendet die Summe der Eingabewerte als Obergrenze für die Koeffizienten C. Ziemlich langsam, Timeout bei TIO für Eingabelistenlängen über 5 oder 6 (auch abhängig von der Summe der Werte). Aber nicht so langsam wie meine ursprüngliche Version, die winzige Listen mit bis zu 3 Elementen mit winzigen Werten erfordert, um keine Zeitüberschreitung zu verursachen:

21 Bytes

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

Probieren Sie es online!

C (gcc) , 37 Bytes

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

Probieren Sie es online!

Python 2 , 53 Bytes

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

Probieren Sie es online!

k*x>yimpliziert k>y/x; so kann das kleinste ksein ist k=floor(y/x)+1. Da in Python 2.7 die Ganzzahldivision bereits als "wie floorgewünscht" k=y/x+1und " wie gewünscht" angenommen wird k*x = (y/x+1)*x = y/x*x+x.

Oracle SQL 11.2, 210 Byte

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;

Nicht golfen

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;

Chez-Schema (140 Bytes)

Golf Version:

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

Ungolfed Version:

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

Probieren Sie es online!

K (oK) , 11 Bytes

{y*1+_x%y}\

Probieren Sie es online!