Fibonacci-artige Matrixerweiterung

25

Für jede Zeile und Spalte einer Matrix können wir einen zusätzlichen Eintrag mit der Summe der letzten beiden Einträge in dieser Zeile oder Spalte hinzufügen. Zum Beispiel mit der folgenden Eingabematrix:

[ 1 1 1 ]
[ 2 3 4 ]

Die resultierende Matrix wäre:

[ 1 1 1 2 ]
[ 2 3 4 7 ]
[ 3 4 5 9 ]

Führen Sie bei einer Eingabe einer Ganzzahl N und einer Matrix [X, Y] mit einer Größe von mindestens 2x2 die obige Erweiterung N-mal durch und geben Sie das Ergebnis aus. Die resultierende Matrix hat immer die Größe [X + N, Y + N].

Beispiele:

Input:                     Output:

2, [ 0 0 ]                 [ 0 0 0 0 ]
   [ 0 0 ]                 [ 0 0 0 0 ]
                           [ 0 0 0 0 ]
                           [ 0 0 0 0 ]


3, [ 1 1 1 ]               [ 1  1  1  2  3  5 ]
   [ 2 3 4 ]               [ 2  3  4  7 11 18 ]
                           [ 3  4  5  9 14 23 ]
                           [ 5  7  9 16 25 41 ]
                           [ 8 11 14 25 39 64 ]
Digitales Trauma
quelle

Antworten:

8

MATL , 13 14 15 16 20 21 Bytes

2*:"!tP2:Y)sv

Danke @Zgarb für das Entfernen von 1 Byte!

Probieren Sie es online!

2*         % implicitly input number N and multiply by 2
:          % create vector [1,2,...,2*N]
"          % for loop: do this 2*N times
  !        %   transpose. Implicitly input matrix in the first iteration
  tP       %   duplicate and flip vertically
  2:       %   vector [1,2]
  Y)       %   pick submatrix formed by the first two rows
  s        %   sum of each column
  v        %   append as a new row
           % end for
           % implicit display
Luis Mendo
quelle
1
Ich kenne MATL nicht, aber wäre es nicht kürzer, die 2NZeiten zu wiederholen, als zweimal zu wiederholen N?
Zgarb
@Zgarb Natürlich! Wie habe ich das vermisst? Vielen Dank!!
Luis Mendo
Verfügt MATL über eine integrierte Funktion zum Verdoppeln einer Zahl?
Zgarb
@Zgarb Nein. Du brauchst 2*(Postfix-Notation). Vielleicht sollte es einen eingebauten Ein-Zeichen-Code haben, der häufig verwendet wird. Auch 2^(quadratisch). Aber mir geht der Code aus :-)
Luis Mendo
6

J, 19 Bytes

(v"1@v=.,[+&{:}:)^:

Dies definiert ein Adverb, das die Zahl links nimmt und ein Verb erzeugt, das die Matrix rechts nimmt. Für das zweite Beispiel gibt es

  3 ((v"1@v=.,[+&{:}:)^:) 2 3 $ 1 1 1 2 3 4
1  1  1  2  3  5
2  3  4  7 11 18
3  4  5  9 14 23
5  7  9 16 25 41
8 11 14 25 39 64

Erläuterung

(v"1@v=.,[+&{:}:)^:  Left argument x, right argument y
(               )^:  Repeat x times:
     v=.               Bind the following verb to v, and apply to y:
         [    }:         y and y-without-last-item
          +&{:           Sum of their last items
        ,                Append that to y
                       (v automatically threads to rows)
 v"1@                  then apply v to columns
Zgarb
quelle
3

K, 23 Bytes

{x(2({x,+/-2#x}'+)/)/y}

In Aktion:

  {x(2({x,+/-2#x}'+)/)/y}[3;(1 1 1;2 3 4)]
(1 1 1 2 3 5
 2 3 4 7 11 18
 3 4 5 9 14 23
 5 7 9 16 25 41
 8 11 14 25 39 64)

Probieren Sie es hier aus .

JohnE
quelle
es funktioniert immer noch, wenn Sie das führende {xund das y}
nachfolgende
3

Jelly, 15 13 12 Bytes

-1 Byte von @Dennis

ṫ-S;@"Z
ÇḤ}¡

Wie bei der MATL-Antwort von @ LuisMendo wird das Array transponiert, bevor die Transformation entlang einer Achse ausgeführt wird. Daher müssen wir die Funktion 2 * n mal aufrufen.

ṫ-S;@"Z       Helper link. Input: x (2D array)
 -              Numeric literal: -1
ṫ               Get x[-1:], i.e. last two rows in x
  S             Sum
   ;@"          Append each to x. " is 'zipWith'; @ switches argument order.
      Z         Transpose the array.
ÇḤ}¡          Main link. Input: a, n
Ç               Call the last link on a
 Ḥ}             2n
   ¡            times.

Probieren Sie es hier aus .

Lirtosiast
quelle
2

ES6, 134 Bytes

(n,a)=>[...a.map(b=>[...b,...Array(n)].map(c=>(c<1/0?0:c=a+d,d=a,a=c))),...Array(n)].map(b=>(b?0:b=[...a].map((c,j)=>c+d[j]),d=a,a=b))

Erläuterung:

(n,a)=> // arguments n is number to expand, a is original array
    [...
        a.map(b=> // for each row in a
            [...b,...Array(n)] // append n elements to the row
            .map(c=>(c<1/0?0:c=a+d,d=a,a=c))) // scan the elements and fill the new ones by summing the previous two
        ,...Array(n)] // append n rows
    .map(b=>(b?0:b=[...a].map((c,j)=>c+d[j]),d=a,a=b)) // scan the rows and fill the new rows by summing the previous two rows
Neil
quelle
2

Haskell, 67 Bytes

o%m=m++[o(+)(last m)$last$init m]
(!!).iterate(map(id%).(zipWith%))

Anwendungsbeispiel:

*Main> ( (!!).iterate(map(id%).(zipWith%)) ) [[1,1,1],[2,3,4]] 3
[[1,1,1,2,3,5],[2,3,4,7,11,18],[3,4,5,9,14,23],[5,7,9,16,25,41],[8,11,14,25,39,64]]

Wie es funktioniert:

(!!).iterate(    ...         )  -- repeatedly apply ... to the first agrument and
                                -- pick the iteration defined by the second arg
                   (zipWith%)   -- for one iteration add a new row and
          map(id%)              -- then a new element at the end of each each row

o%m                             -- add row or element at the end of a row resp.
                                -- argument o is a "modify function"
                                --          m the whole matrix or a row
 m++[    (last m)(last$init m)] -- take m and append the result of combining the
                                -- last and 2nd last element of m
     o(+)                       -- with a modified version of (+)
                                -- modification is none (aka. id) when adding an
                                -- element to the end of a row and
                                -- zipping elementwise (zipWith) when adding a row
nimi
quelle
Ich bin ein Haskell-Anfänger. Ich bin so weit gekommen sudo apt-get install haskell-platformund ghciführe die REPL aus, die mir eine Prelude> Aufforderung gibt. Wenn ich einfüge, o%m=m++[o(+)(last m)$last$init m]bekomme ich <interactive>:2:4: parse error on input '='. Können Sie mir eine kleine Einführung geben, die entweder aus einer Quelldatei oder in der REPL ausgeführt wird?
Digital Trauma
@DigitalTrauma: Setzen Sie entweder die o%m=...Zeile (und nur diese Zeile) in eine Datei mit dem Namen, sagen wir mal fib-matrix.hs. Dann können Sie den :l fib-matrix.hsBefehl in verwenden ghci, um die Definitionen zu laden und die Hauptfunktion aufzurufen, wie in meinem Verwendungsbeispiel beschrieben. - Oder benutzen let o%m=... in ( (!!). ... ) [[1,1,1]...] 3.
nimi
1
@DigitalTrauma: oh, es gibt einen dritten Weg: gib der Hauptfunktion einen Namen, z. B. füge einen f=vor der zweiten Zeile hinzu: f=(!!).iterate...speichere beide Zeilen in einer Datei und lade sie über l: <filename.hs>. Dann können Sie anrufen f [[1,1,1],[2,3,4]] 3, etc.
nimi
Ich bin mir nicht sicher, ob ich dies als gültiges Hash akzeptieren würde. Die oberste Zeile ist eine Funktionsdefinition und muss für die Verwendung in der REPL geändert werden. Die zweite Zeile kann jedoch nur in der REPL verwendet werden.
Daniel Hill
@DanielHill: Es gibt ein Thema zu Meta, das unbenannte Funktionen zulässt, die von globalen Hilfsfunktionen abhängen.
nimi
2

CJam, 17 16 Bytes

q~2*{~_2$.+]z}*p

Das Eingabeformat ist zuerst die Matrix (als 2D-Array im CJam-Stil) und danach die Anzahl der Iterationen.

Teste es hier.

Erläuterung

Es stellt sich heraus, dass dies die gleiche Lösung ist wie die aller anderen:

q~      e# Read and evaluate input.
2*      e# Double the iteration count.
{       e# Run this block that many times...
  ~     e#   Dump all rows on the stack.
  _     e#   Copy the last row.
  2$    e#   Copy the penultimate row.
  .+    e#   Vectorised addition.
  ]     e#   Wrap all rows in a new array.
  z     e#   Transpose such that the next iteration processes the other dimension.
}*
p       e#   Pretty-print.
Martin Ender
quelle
1

Im Ernst, 20 Bytes

,,τ"┬`;d@d@X+@q`M"£n

Übernimmt dann die Eingabe der Matrix (als 2D-Liste) N. Gibt eine 2D-Liste aus.

Diese Version funktioniert aus irgendeinem Grund nicht mit dem Online-Interpreter, funktioniert jedoch mit diesem Pre-Challenge-Commit .

Eine online funktionierende Version für 23 Bytes:

,τ",┬`;d@d@X+@q`M"nkΣ£ƒ

Nimmt die Eingabe in umgekehrter Reihenfolge vor ( Ndann Matrix).

Probieren Sie es online!

Ich werde eine Erklärung hinzufügen, nachdem ich eine Weile geschlafen habe. Das Umgehen von Interpreter-Fehlern macht niemals Spaß.

Mego
quelle
1

Pyth, 13 12 Bytes

u+Rs>2dCGyEQ

Probieren Sie es online aus. Testsuite.

Verwendet den gleichen Algorithmus für die meisten Antworten. Nimmt als Eingabe die Matrix als 2D-Array in der ersten Zeile und nin der zweiten Zeile.

Erläuterung

u        yEQ     do 2*N times, starting with input matrix:
       CG          transpose
 +R                append to each row:
   s                 sum of
    >2d              last 2 elements of row
PurkkaKoodari
quelle
1

Matlab, 60 Bytes

Ich habe zuerst mit Matlabs ausgefallenen Indizierungsmethoden rumgespielt, A(end+1,:)=sum...bevor ich herausgefunden habe, dass in diesem seltenen Fall eine einfache Verkettung in Matlab tatsächlich günstiger ist. Schade, dass ich dies in eine tatsächliche Funktion umwandeln musste. Sollte auch mit Octave funktionieren.

function A=f(A,n)
for i=1:2*n
A=[A;sum(A(end-1:end,:))]';end

Ich nehme an, dies ist ein hervorragendes Beispiel dafür, wie man keine Algorithmen erstellt. Für A = 2x2, n = 1000 dauert dieser Algorithmus auf meinem Laptop bereits 5 Sekunden, n = 2000 sind es fast 50 Sekunden! (oder ungefähr 30s, wenn A ein gpuArrayDank an meinen vertrauenswürdigen Quadro 1000M ist)

Sanchises
quelle
Ich habe keine Kopie von Matlab. Kann ich das unter GNU Octave ausführen? Wenn ja, können Sie Anweisungen geben?
Digitales Trauma
1
Ja, ich habe es Matlab genannt, weil es keine Octave-spezifischen Funktionen verwendet. f([0,1;2,3],1000)
Legen Sie
Aha. 1) speichern unter f.m. 2) Starten Sie octave. 3) Einfügen load f.m; f([1,1,1;2,3,4],3)in die REPL-Eingabeaufforderung - funktioniert bei mir.
Digital Trauma
Wenn du es sagst! Ich benutze nur die Octave-Online-Website, also keine Ahnung, wie es sonst funktionieren soll. Ich werde sehen, ob ich von dort aus einen Permalink
erstellen
1

Java, 2179 Bytes

Es ist einfach geklappt: - Dieser Code ist in Java-Sprache.

import java.util.Scanner;

public class FebonnaciMatrix {
        static Scanner scan=new Scanner(System.in);

        public static void main(String[] args) {

        int x,y;
        System.out.println("For the Array to Work Upon:- ");

        System.out.println("Enter the Row:- ");
        int row=scan.nextInt();
        System.out.println("Enter the Column:- ");
        int col=scan.nextInt();

        int inpArr[][]=new int[row][col];

        System.out.println("Enter the values");
        inpArr=inpValues(row,col);

        System.out.println("The Input Array is:- ");
        display(inpArr,row,col);

        System.out.println("Input the Array size of Febonacci Array ");

        System.out.println("Enter the Row");
        int frow=scan.nextInt();
        System.out.println("Enter the Column");
        int fcol=scan.nextInt();

        int febArr[][]=new int[frow][fcol];
        febArr=copyValue(inpArr,febArr,row,col);

        for(x=0;x<row;x++)
        {
            for(y=col;y<fcol;y++)
                febArr[x][y]=febArr[x][y-2]+febArr[x][y-1];
        }

        for(x=row;x<frow;x++)
        {
            for(y=0;y<fcol;y++)
                febArr[x][y]=febArr[x-2][y]+febArr[x-1][y];
        }

        System.out.println();
        System.out.println("The Febonacci Array:-");
        display(febArr,frow,fcol);
    }

    static void display(int[][] arr,int row,int col)
    {
        int x,y;
        for(x=0;x<row;x++)
        {
            for(y=0;y<col;y++)
                System.out.print(arr[x][y]+"\t");
            System.out.println();
        }
    }

    static int[][] inpValues(int row,int col)
    {
        int arr[][]=new int[row][col];
        int x,y;
        for(x=0;x<row;x++)
        {
            for(y=0;y<col;y++)
            {
                System.out.print("Enter the value:- ");
                arr[x][y]=scan.nextInt();
            }
        }
        return arr;
    }

    static int[][] copyValue(int[][] old, int[][] ne, int row,int col)
    {
        int x,y;    
        for(x=0;x<row;x++)
        {
            for(y=0;y<col;y++)
                ne[x][y]=old[x][y];

        }
        return ne;
    }

}
Dhruv Govila
quelle
1
Willkommen bei Programming Puzzles und Code Golf! Die Frage ist mit Code-Golf gekennzeichnet, was bedeutet, dass die Antworten konkurrieren, um in der kürzest möglichen Menge an Code (in Bytes) geschrieben zu werden. Ihre Antwort mag das Problem lösen, aber ich sehe kaum einen Versuch, den Code zu "golfen" (dh ihn so kurz wie möglich zu machen). Es gibt viele einfache Möglichkeiten, dies mit Ihrem Code zu tun, z. B. Variablen mit 1-Zeichen-Namen und das Entfernen unnötiger Leerzeichen. Darüber hinaus können Sie diese Tipps speziell für Java
Digital Trauma
... Schauen Sie sich das Tag-Wiki für Code-Golf an , insbesondere das Wie soll ich auf einen Code-Golf antworten? Irgendwelche Hinweise? Sektion. Beachten Sie auch, dass Java im Vergleich zu vielen anderen Sprachen notorisch schwer zu golfen ist. Dies sollte Sie jedoch nicht davon abhalten - wenn Sie eine gut golfene Java-Antwort haben, ist diese wahrscheinlich recht beliebt, auch wenn sie länger ist als alle anderen Antworten. Lassen Sie sich nicht von all den verblüffenden kurzen Esolang-Antworten abschrecken - diese Community ist in der Regel gut darin, Sprachbehinderungen zu berücksichtigen.
Digital Trauma
@ DigitalTrauma- Danke ... für die Unterstützung als Neuling ... Ich werde sicher die Links durchgehen und mir einen neuen Code
einfallen lassen
Da Sie ein neuer Benutzer sind, habe ich mir die Freiheit genommen, Ihre Antwort zur besseren Formatierung zu bearbeiten. Insbesondere a) ein klarer Titel, der Sprache und Anzahl der Bytes angibt, b) die Code-Formatierung Ihres Codes. Auf allen Stack-Exchange-Sites ist die Code-Formatierung einfach - stellen Sie einfach allen Codezeilen vier Leerzeichen voran. Noch einfacher: Wählen Sie im Bearbeitungsfeld Ihren Code aus und klicken Sie {}oben im Bearbeitungsfeld auf. Dadurch wird das Präfix automatisch eingefügt.
Digital Trauma
Okay ... Ich werde es einfach überprüfen ...
Dhruv Govila
1

Python, 103 105 Bytes

f=lambda n,L:f(n-1,[l+[sum(l[-2:])]for l in L])if n else L
lambda n,L:zip(*f(n,map(list,zip(*f(n,L)))))

Die anonyme Funktion übernimmt die Liste der Listen und übergibt sie an die rekursive Funktion f. Die Ausgabe wird transponiert und dann an übergebenf erneut weitergeleitet. Anschließend wird die Ausgabe des zweiten Durchgangs erneut transponiert. Die Ausgabe ist eine Liste von Tupeln

Zwei Bytes dank Bakuriu gespeichert

wnnmaw
quelle
1
n>0könnte einfach sein n, da man mit einem positiven anfängt nund wenn man 0seinen wert erreicht falsch ist.
Bakuriu
0

Perl 6 ,  87 73  71 Bytes

->\c,\m{for ^c {.[+*]=[+] .[*X-1,2]for m;m.push: [map {[+] m[*X-1,2;$_]},m[0].keys]};m}
->\c,\m{for ^c {.[+*]=[+] .[*X-1,2]for m;m[+*]=[m[*-2;*] »+«m[*-1]]};m}
->\c,\m{for ^c {.[+*]=[+] .[*X-1,2]for m;m[+*]=[m[*-2;*]Z+m[*-1;*]]};m}
-> \c, \m {
  for ^c { # 0 ..^ c

    # each row
    .[+*]                            # new column at the end of row ($_)
          = [+] .[ * X- 1,2 ]        # add up the last two entries in row ($_)
                              for m; # for every row

    # too bad this was longer than the above code
    # m[*;+*]=map *+*,m[*;*-2,*-1]

    # each column
    m[ +* ]                 # add new row
            = [             # make it an Array rather than a List
                m[ *-2; * ] # the second to last row
                »+«         # added columnwise with
                m[ *-1 ]    # the last row
              ]
  };

  m # return the result
}

Verwendung:

use v6.c;
# give it a lexical name
my &code = ->\c,\m{  }

my @return = code 3,[[1,1,1],[2,3,4]];

put '[ ', $_».fmt('%2d'), ' ]' for @return;

put '';

put @return.perl ~~ {S:g/' '//};
[  1  1  1  2  3  5 ]
[  2  3  4  7 11 18 ]
[  3  4  5  9 14 23 ]
[  5  7  9 16 25 41 ]
[  8 11 14 25 39 64 ]

[[1,1,1,2,3,5],[2,3,4,7,11,18],[3,4,5,9,14,23],[5,7,9,16,25,41],[8,11,14,25,39,64]]
Brad Gilbert b2gills
quelle
Das Einfügen in perl6 gibt mir einige Fehler . Ich bin ein Perl-Anfänger - was mache ich falsch?
Digital Trauma
@DigitalTrauma Es tut mir leid, ich hätte die Verwendung so schreiben sollen my &code = ->\c,\m{ … }, dass deutlich wird, dass ->\c,\m{ … }der Code durch den obigen Code ersetzt werden muss. Normalerweise verwende ich implizite $_oder @_explizite Platzhalterparameter, $^ada diese in der Regel kürzer sind. Ich habe nur nicht darüber nachgedacht. $*PERL.compiler.version !before 2015.12
Stellen
@DigitalTrauma Sie können auch den # perl6- Kanal auf freenode.net aufrufen und camelia (wie folgt ) verwenden , um den Code auszuführen (Zeilen mit m: und ein Leerzeichen voranstellen ). Sie können
camelia