Die Teilsummen einer Liste von ganzen Zahlen [a ₁ , a ₂ , a ₃ , ..., a _n ] sind

s ₁ = a ₁
s ₂ = a ₁ + a ₂
s ₃ = a ₁ + a ₂ + a ₃
...
s _n = a ₁ + a ₂ + ... + a _n

Wir können dann die Liste der Teilsummen [s ₁ , s ₂ , s ₃ , ..., s _n ] nehmen und ihre Teilsummen erneut berechnen, um eine neue Liste zu erzeugen, und so weiter.

Verwandte: Iterierte Forward-Differenzen

Eingang:

• Eine nicht leere Liste von ganzen Zahlen
• Eine positive Anzahl von Iterationen,

Ausgabe: Gibt die Liste der Ganzzahlen aus, die sich aus der mehrfachen Verwendung der Teilsummen ergibt, oder gibt sie zurück.

Wenigste Bytes gewinnt. Built-Ins sind in Ordnung, auch wenn sie das Problem direkt lösen.

Testfälle:

f([-3, 4, 7, -1, 15], 1) == [-3, 1, 8, 7, 22]
f([-3, 4, 7, -1, 15], 3) == [-3, -5, 1, 14, 49]

Bestenliste:

var QUESTION_ID=59192,OVERRIDE_USER=20260;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/61321/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;

body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}

<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

J, 5 Bytes

+/\^:

Versuchen Sie es online auf J.js .

Wie es funktioniert

• /\ ist ein Adverb (Funktion, die ein linkes Argument annimmt), das sich kumulativ um sein Argument verringert.

• Also +/\ist das kumulative Summenverb .

• ^:ist die Machtverbindung ; (f ^: n) ytrifft finsgesamt nmal zu auf y.

• Der Verb-Konjunktionszug +/\^:bildet ein Adverb, das +/\so oft wiederholt wird, wie im (linken) Argument angegeben.

  x (+/\^:) ywird analysiert als (x (+/\^:)) y, was der Ausführung entspricht (+/\^:x) y.

Vielen Dank an @Zgarb für seine Hilfe bei der Erklärung.

Mathematica, 19 Bytes

Gut wenn Einbauten okay sind ...

Accumulate~Nest~##&

Definiert eine Funktion mit derselben Signatur wie die Beispiele in der Challenge. Ich bin mir ziemlich sicher, dank des langen Namens, Accumulatedass dies von den Golfsprachen und der APL-Familie leicht zu übertreffen sein wird. :)

Um den Kommentar von LegionMammal978 für diejenigen zu erläutern, die Mathematica nicht verwenden:

##Stellt eine Folge von Funktionsparametern dar (ähnlich einer Liste, die automatisch "splattet", wo immer sie eingefügt wird, wenn Sie mit diesem Begriff aus einer Sprache Ihrer Wahl vertraut sind). Das ~sind syntaktischer Zucker für Infix Funktionsaufruf, so dass , wenn wir die Funktion mit Parametern aufrufen listund nund alles erweitern, erhalten wir:

Accumulate~Nest~##
Nest[Accumulate, ##]
Nest[Accumulate, list, n]

Das ist genau die Argumentreihenfolge, die von erwartet wird Nest.

Haskell, 26 23 Bytes

(!!).iterate(scanl1(+))

Dies definiert eine anonyme Funktion, die wie folgt aufgerufen wird:

> let f = (!!).iterate(scanl1(+)) in f [-3,4,7,-1,15] 3
[-3,-5,1,14,49]

Vielen Dank an @nimi für das Speichern von 3 Bytes.

Erläuterung

(!!).                    -- Index by second argument from
     iterate(         )  -- the infinite list obtained by iterating
             scanl1(+)   -- the partial sums function (left scan by +) to first argument

APL, 9 8 Bytes

{+\⍣⍺⊢⍵}

Dies definiert eine dyadische Funktion, die die Iterationen und Listen als linkes und rechtes Argument akzeptiert.

Vielen Dank an @NBZ für das Golfen ab 1 Byte!

Probieren Sie es online auf TryAPL aus .

Wie es funktioniert

• ⍺und ⍵sind die linken und rechten Argumente für die Funktion.

• +\ ist kumulativ um die Summe zu reduzieren.

• ⍣⍺wiederholt die vorhergehenden Operatorzeiten ⍺.

• ⊢⍵Wendet die Identitätsfunktion auf an ⍵.

  Dies ist eine kürzere Methode zum Parsen des Codes als (+\⍣⍺)⍵anstelle von +\⍣(⍺⍵).

Zusammen bewerben wir uns +\insgesamt ⍺mal um⍵

Matlab, 41 Bytes

function f(l,n);for i=1:n;l=cumsum(l);end

Recht einfach. Ich finde es immer noch ziemlich ärgerlich, keine eingebaute Methode zur Erstellung stückweise definierter anonymer Funktionen oder Anker in Rekursionen zu haben.

Ungolfed:

function f(l,n);
for i=1:n;
    l=cumsum(l);
end

JavaScript (ES6) 38

Überraschend klein, wenn .map rekursiv verwendet wird

f=(l,n,t=0)=>n?f(l.map(x=>t+=x),n-1):l

function test()
{
  var n, v, i = I.value
  v = i.match(/\-?\d+/g).map(x=>+x)
  n = v.pop()
  console.log(v,n)
  O.innerHTML = I.value + ' -> ' + f(v,n) + '\n' + O.innerHTML;
}

test()

<input id=I value='[-3, 4, 7, -1, 15], 3'><button onclick="test()">-></button>
<pre id=O></pre>

K, 7 3 Bytes

{y+\/x}

Sehr ähnlich der J-Lösung. +\Führt präzise eine Teilsumme aus und /iteriert , wenn ein monadisches Verb und ein ganzzahliges linkes Argument angegeben sind, eine festgelegte Anzahl von Malen, wie bei einer "for" -Schleife. Der Rest packt es einfach so zusammen, dass es der Reihenfolge der Argumente entspricht.

  {y+\/x}[-3 4 7 -1 15;1]
-3 1 8 7 22
  {y+\/x}[-3 4 7 -1 15;3]
-3 -5 1 14 49

Getestet in Kona und OK .

Bearbeiten:

Wenn ich die Argumente umkehren darf, wie @ kirbyfan64sos festgestellt hat, kann ich ganz auf die Funktionsumhüllung verzichten:

+\/

Aufgerufen wie:

+\/[3;-3 4 7 -1 15]

Dies funktioniert sowohl in k2.8 als auch in k5 einwandfrei. In oK funktioniert es nicht, da dieser Interpreter noch keine Curry-Adverbien (auch als "projizierte Adverbien" bezeichnet) unterstützt und aus weniger eindeutigen Gründen in Kona nicht ordnungsgemäß zu funktionieren scheint.

edit : Seit ein paar Tagen +\/funktioniert die Formulierung auch in OK.

Pyth, 9 Bytes

usM._GvwQ

Probieren Sie es online aus: Demo oder Test Suite

Erläuterung

usM._GvwQ  implicit: Q = input list
      vw   input number
u       Q  repeat the following instruction ^ times to G = Q
   ._G        sequence of prefixes of G
 sM           sum them up

Julia, 29 Bytes

f(x,y)=y>0?f(cumsum(x),y-1):x

Das braucht wirklich nicht viel Erklärung. Es ist eine rekursive Funktion, wenn y==0dann nur x ausgegeben wird. Ansonsten dekrementiere y, führe ein Cumsum durch und rekursiere. Wahrscheinlich nicht die bestmögliche Julia-Lösung, ich arbeite noch daran.

Labyrinth , 73 Bytes

;?
,"
;
#
#;}=
;  #
"#;(
_  ;={()"
#;; ( { "
  ; { !\(@
+=( =
" " "
":{:"

Es ist schon eine Weile her, dass ich im Labyrinth etwas beantwortet habe, und das schien machbar. :)

Das Eingabeformat ist eine flache Liste mit der Anzahl der Iterationen zuerst (und dann der Liste, auf die die Teilsummen angewendet werden sollen). Trennzeichen spielen keine Rolle, solange nach der letzten Ganzzahl kein Zeichen steht. Daher können Sie Folgendes verwenden:

3 | -3, 4, 7, -1, 15

Die Ausgabe ist durch Zeilenumbrüche getrennt:

-3
-5
1
14
49

R, 75 Bytes

Es ist lang, aber eine andere Einstellung ... die Berechnung der gewünschten Sequenz direkt anstelle von kumulierten Summen:

function(x,n)sapply(1:length(x),function(i)sum(x[1:i]*choose(i:1+n-2,n-1)))

Man beachte, dass die Koeffizienten der Terme von xi für cumsum ^ n (x) Diagonalen des Pascalschen Dreiecks sind. dh

cumsum^3(x) = choose(2,2) * x1, choose(3,2) * x1 + choose(2,2) *x2, choose(4,2) * x1 + choose(3,2) * x2 + choose(2,2) * x3, ....

edit: um eine funktion zu machen

Python 2, 67

Dies verwendet dieselbe Summe wie Anthony Roitman und dieselbe Rekursion wie Morgan Thrapp .

f=lambda l,n:f([sum(l[:i+1])for i in range(len(l))],n-1)if n else l

Ich habe diese Lösung entwickelt, bevor ich ihre gesehen habe, und dann schien es einfacher, sie als Antwort zu veröffentlichen, anstatt sie einem oder beiden zu kommentieren.

Python, 113 93 89 76 Bytes

def f(l,n):
 for i in[0]*n:l=[sum(l[:j+1])for j in range(len(l))];
 print(l)

Es funktioniert für beide Testfälle. Dank an Status, Morgan Thrapp und Ruth Franklin, die mir geholfen haben, das Programm auf 93, 89 bzw. 76 Bytes herunterzuspielen.

Gol> <> 0,3,10 , 22 Bytes

SI
C>rFlMF:}+
NRl<C}<;

Die erste Ganzzahl ist die Iterationsnummer und der Rest bildet die Liste. Die endgültige Liste wird zeilenweise getrennt ausgegeben.

Die Sprache ist noch recht jung und instabil, aber da ich ziemlich auf diese Operatoren eingestellt bin, dachte ich, es wäre okay.

Erläuterung

SI            Read integer, moving down on EOF (first line runs as loop)
r             Reverse stack, putting iteration number on top

[outer loop]
F             Do #(iterations) times

[inner loop]
lMF           Do #(length of stack - 1) times
:             Duplicate top of stack
}             Rotate stack rightward (top goes to bottom)
+             Add the top two elements of the stack
C             Continue inner loop, moving down from F when loop is over

}             Rotate once more
C             Continue outer loop, moving down from F when loop is over

lRN           Print stack as (num + newline)
;             Halt

Um zu sehen, warum dies funktioniert, versuchen wir ein kleines Beispiel [5 2 1]:

[5 2 1] -- : --> [5 2 1 1] -- } -->  [1 5 2 1]  -- + --> [1 5 3]
[1 5 3] -- : --> [1 5 3 3] -- } -->  [3 1 5 3]  -- + --> [3 1 8]

-- } --> [8 3 1]

Python, 52 Bytes

f=lambda l,n:n*l and f(f(l[:-1],1)+[sum(l)],n-1)or l

Eine rekursive Funktion, die sowohl in der Liste lals auch in der Anzahl der Iterationen rekursiv ist n. Lassen Sie es uns aufschlüsseln.

Betrachten wir zunächst eine rekursive Funktion g, bei der die Teilsumme nur einmal durchlaufen wurde.

g=lambda l:l and g(l[:-1])+[sum(l)]

Bei einer leeren Liste lgibt dies sich lselbst zurück, die leere Liste. Ansonsten ist der letzte Eintrag der Teilsummen von ldie Gesamtsumme von l, die an das rekursive Ergebnis für alle bis auf das letzte Element von angehängt wirdl .

Betrachten wir nun eine Funktion f, die gfür nIterationen gilt.

f=lambda l,n:n and f(g(l),n-1)or l

Wenn dies der Fall nist 0, wird die Liste lunverändert zurückgegeben. Andernfalls wird sie geinmal angewendet und anschließend frekursiv mit einer verbleibenden Iteration weniger aufgerufen.

Betrachten wir nun noch einmal den eigentlichen Code, der die beiden Rekursionen zu einer einzigen Funktion kombiniert. Die Idee ist, g(l)als Sonderfall zu behandeln f(l,1).

f=lambda l,n:n*l and f(f(l[:-1],1)+[sum(l)],n-1)or l

Wir haben f(g(l),n-1)von der vorherigen Definition erweitert g(l)in g(l[:-1])+[sum(l)], und dann ersetzt g(_)mit f(_,1)auf , um die rekursive Anrufe beschränkt f.

Für den Basisfall möchten wir zurückkehren, lwann immer n==0oder l==[]. Wir kombinieren diese, indem wir feststellen, dass eine der beiden n*lListen die leere Liste ist, die Falsy ist. Wir greifen also immer dann zu, wenn n*les nicht leer ist, und kehren lansonsten zurück.

Obwohl es zwei rekursive Aufrufe gibt, fführt dies nicht zu einer exponentiellen Explosion der rekursiven Definition der Fibonacci-Zahlen, sondern bleibt quadratisch.

C ++ (61 + 17 = 78 Byte)

#include<numeric>
void f(int*a,int*e,int n){for(;n--;)std::partial_sum(a,e,a);}

Testfall:

#include <iostream>
#include <iterator>

int main() {
    int a[] { -3, 4, 7, -1, 15 };
    f(a, std::end(a), 3);
    for (auto i : a)
        std::cout << i << " ";
}

Dies lässt sich leicht mit der Spezifikation vereinbaren: Es wird ein Array im C-Stil verwendet, das Zeiger an den Anfang und das Ende des Arrays übergibt. Intern ist es, wie Sie sehen, nur eine extrem dünne Hüllestd::partial_sum in der Standardbibliothek. Anstatt den resultierenden Wert tatsächlich zurückzugeben, wird lediglich das übergebene Array geändert.

Wenn es uns nichts ausmacht, Definitionen von Dingen an ihre Grenzen zu treiben (und vielleicht sogar darüber hinaus), können wir eine "Funktion" in einem Lambda-Ausdruck definieren:

#include<numeric>
#include <iostream>
#include <iterator>

int main() {
    int a[] { -3, 4, 7, -1, 15 };
    int *e = std::end(a);
    int n=3;

    auto f=[&]{for(;n--;)std::partial_sum(a,e,a);};

    f();
    for (auto i : a)
        std::cout << i << " ";
}

Dies reduziert die Definition der Funktion (-ähnliches Objekt) auf dieses Stück:

[&]{for(;n--;)std::partial_sum(a,e,a);};

... für 40 Bytes (+17 für die #include).

CJam, 13 Bytes

q~{{1$+}*]}*p

Teste es hier.

Haskell, 52 47 Bytes

Der erste Code-Golf-Versuch, und ich bin ein absoluter Haskell-Anfänger. Kommentare sind daher sehr willkommen! Bei der Frage nach dem erforderlichen Format des Funktionsaufrufs oder ob es sich um ein Argument für das Programm handelt, war nicht klar, weshalb ich das Ausrufezeichen als Funktionskennung verwendete, um einige Leerzeichen zu speichern.

0!a=a
i!a=(i-1)![sum$take j a|j<-[1..length a]]

Verbrauch (GHCi):

$ ghci partialsums.hs
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( partialsums.hs, interpreted )
Ok, modules loaded: Main.
*Main> 1![-3, 4 ,7 ,-1 ,15]
[-3,1,8,7,22]
*Main> 3![-3, 4 ,7 ,-1 ,15]
[-3,-5,1,14,49]

R, 41 Bytes

function(x,n){for(i in 1:n)x=cumsum(x);x}

C #, 52 + 85 = 148 137 Bytes

using E=System.Collections.Generic.IEnumerable<int>;

und

E I(E s,int i){int t=0;return i<1?s:I(System.Linq.Enumerable.Select(s,v=>t+=v),i-1);}

Es werden unorthodoxe Praktiken verwendet ( v=>t+=v), dies ist jedoch PPCG. Beachten Sie auch die Einschränkung der Stapeltiefe.

Python 3, 73

Könnte wohl etwas weiter unten golfen werden.

def f(n,i):
 p=0;c=[]
 for m in n:p+=m;c+=[p]
 f(c,i-1)if i else print(n)

Diese Version benutzt Numpy, was sich ein bisschen wie Schummeln anfühlt, aber hier ist es:

Python 3 (mit Zahl), 72

from numpy import*
def f(n,i):
 if i:c=cumsum(n);f(c,i-1)
 else:print(n)

C ++ 14, 102 103 94 + 17 (Einschluss) = 111 Bytes

#include<vector>
auto f(std::vector<int>a,int n){for(;n--;)for(int i=0;i<a.size()-1;++i)a[i+1]+=a[i];return a;}

Ungolfed, mit Testfall

#include <vector>
#include <iostream>

auto f(std::vector<int> a, int n)
{
    for (; n--;)
        for (int i = 0; i < a.size() - 1; ++i)
            a[i + 1] += a[i];
    return a;
}


int main()
{
    auto t = f({-3, 4, 7, -1, 15}, 3);
    for (int i : t)
        std::cout << i << " ";
}

Verlässt sich auf die Reihenfolge der Bewertung. Ich bin mir nicht sicher, ob es UB ist oder nicht, aber es funktioniert. Es ist vom Compiler abhängig, also habe ich es geändert.

Oktave, 24 Bytes

@(l,n)l*triu(0*l'*l+1)^n

Burlesque, 10 Bytes

{q++pa}jE!

Es ist im Allgemeinen nicht sehr effizient, aber es macht den Trick.

blsq ) {-3 4 7 -1 15} 1 {q++pa}jE!
{-3 1 8 7 22}
blsq ) {-3 4 7 -1 15} 3 {q++pa}jE!
{-3 -5 1 14 49}

C ++ 14, 67 Bytes

Als unbenanntes Lambda modifiziert es seine Eingabe und benötigt cso einen Random-Access-Container wie vector<int>.

[](auto&c,int n){while(n--)for(int i=0;i++<c.size();c[i]+=c[i-1]);}

05AB1E , 4 Bytes (wahrscheinlich nicht konkurrierend)

F.pO

F    # Implicitly take first input and loop n times.
 .p  # Generate prefixes of input.
   O # Sum all prefixes (implicitly vectorized).

Probieren Sie es online!

Gelee , 3 Bytes

SƤ¡

Probieren Sie es online!

Dies ist meine ( Mr Xcoders ) Methode.

Gelee , 3 Bytes

+\¡

Probieren Sie es online!

Dies ist die Lösung von caird coinheringaahing .

Methode 1

Vollständiges Programm, dyadisch.

  ¡- N-mal wiederholt anwenden.
 Ƥ - Ordnen Sie den vorhergehenden Link den Präfixen der Liste zu.
S - Summe.
     - Implizit ausgeben

Methode # 2

+ \ ¡- Volles Programm, dyadisch.

  ¡- N-mal wiederholt anwenden.
 \ - kumulativ reduziert um:
+ - Ergänzung.

Axiom 213 47 Bytes

m(a,b)==(for i in 1..b repeat a:=scan(+,a,0);a)

ungolf und ein beispiel

 (3) -> [m([-3,4,7,-1,15],1), m([-3,4,7,-1,15],3)]
    Compiling function l with type List Integer -> List Integer
    Compiling function m with type (List Integer,Integer) -> List
       Integer

    (3)  [[- 3,1,8,7,22],[- 3,- 5,1,14,49]]
                                                       Type: List List Integer