La serie tribonacci es una generalización de la secuencia de Fibonacci donde cada término es la suma de los tres términos precedentes.
La secuencia Tribonacci:
0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415, 223317, 410744, 755476, 1389537, 2555757, 47007770, 8646064, 15902591, 29249425, 53798080, 98950096, 181997601, 334745777,
615693444444444442442222224452222222244522224452224452224452244522445222445222445224452244524
a(n) = a(n-1) + a(n-2) + a(n-3) with a(0) = a(1) = 0, a(2) = 1.
Dado un valor N, la tarea es imprimir los primeros N números Tribonacci.
Ejemplos:
Input : 5
Output : 0, 0, 1, 1, 2
Input : 10
Output : 0, 0, 1, 1, 2, 4, 7, 13, 24, 44
Input : 20
Output : 0, 0, 1, 1, 2, 4, 7, 13, 24, 44,
81, 149, 274, 504, 927, 1705, 3136,
5768, 10609, 19513
Una solución simple es simplemente seguir la fórmula recursiva y escribir código recursivo para ella,
C++
// A simple recursive CPP program to print
// first n Tribonacci numbers.
#include <iostream>
using namespace std;
int printTribRec(int n)
{
if (n == 0 || n == 1 || n == 2)
return 0;
if (n == 3)
return 1;
else
return printTribRec(n - 1) +
printTribRec(n - 2) +
printTribRec(n - 3);
}
void printTrib(int n)
{
for (int i = 1; i < n; i++)
cout << printTribRec(i) << " ";
}
// Driver code
int main()
{
int n = 10;
printTrib(n);
return 0;
}
Java
// A simple recursive CPP program
// first n Tribonacci numbers.
import java.io.*;
class GFG {
// Recursion Function
static int printTribRec(int n)
{
if (n == 0 || n == 1 || n == 2)
return 0;
if (n == 3)
return 1;
else
return printTribRec(n - 1) +
printTribRec(n - 2) +
printTribRec(n - 3);
}
static void printTrib(int n)
{
for (int i = 1; i < n; i++)
System.out.print(printTribRec(i)
+" ");
}
// Driver code
public static void main(String args[])
{
int n = 10;
printTrib(n);
}
}
// This code is contributed by Nikita tiwari.
Python
# A simple recursive CPP program to print # first n Tribonacci numbers. def printTribRec(n) : if (n == 0 or n == 1 or n == 2) : return 0 elif (n == 3) : return 1 else : return (printTribRec(n - 1) + printTribRec(n - 2) + printTribRec(n - 3)) def printTrib(n) : for i in range(1, n) : print( printTribRec(i) , " ", end = "") # Driver code n = 10 printTrib(n) # This code is contributed by Nikita Tiwari.
C#
// A simple recursive C# program
// first n Tribinocci numbers.
using System;
class GFG {
// Recursion Function
static int printTribRec(int n)
{
if (n == 0 || n == 1 || n == 2)
return 0;
if (n == 3)
return 1;
else
return printTribRec(n - 1) +
printTribRec(n - 2) +
printTribRec(n - 3);
}
static void printTrib(int n)
{
for (int i = 1; i < n; i++)
Console.Write(printTribRec(i)
+" ");
}
// Driver code
public static void Main()
{
int n = 10;
printTrib(n);
}
}
// This code is contributed by vt_m.
PHP
<?php
// A simple recursive PHP program to
// print first n Tribinocci numbers.
function printTribRec($n)
{
if ($n == 0 || $n == 1 || $n == 2)
return 0;
if ($n == 3)
return 1;
else
return printTribRec($n - 1) +
printTribRec($n - 2) +
printTribRec($n - 3);
}
function printTrib($n)
{
for ($i = 1; $i <= $n; $i++)
echo printTribRec($i), " ";
}
// Driver Code
$n = 10;
printTrib($n);
// This code is contributed by ajit
?>
Javascript
<script>
// A simple recursive Javascript program to
// print first n Tribinocci numbers.
function printTribRec(n)
{
if (n == 0 || n == 1 || n == 2)
return 0;
if (n == 3)
return 1;
else
return printTribRec(n - 1) +
printTribRec(n - 2) +
printTribRec(n - 3);
}
function printTrib(n)
{
for (let i = 1; i <= n; i++)
document.write(printTribRec(i) + " ");
}
// Driver Code
let n = 10;
printTrib(n);
// This code is contributed by _saurabh_jaiswal
</script>
Producción
0 0 1 1 2 4 7 13 24
La complejidad temporal de la solución anterior es exponencial.
Una mejor solución es usar Programación Dinámica .
1) Memoización de Dp de arriba hacia abajo:
C++
// A simple recursive CPP program to print
// first n Tribonacci numbers.
#include <bits/stdc++.h>
using namespace std;
int printTribRec(int n, vector<int> &dp)
{
if (n == 0 || n == 1 || n == 2)
return 0;
if(dp[n] != -1){
return dp[n] ;
}
if (n == 3)
return 1;
else
return dp[n] = printTribRec(n - 1, dp) +
printTribRec(n - 2, dp) +
printTribRec(n - 3, dp);
}
void printTrib(int n)
{
// dp vector to store subproblems
vector<int> dp(n+1, -1) ;
for (int i = 1; i < n; i++)
cout << printTribRec(i, dp) << " ";
}
// Driver code
int main()
{
int n = 10;
printTrib(n);
return 0;
}
Python3
def tribonacci(n):
h={} #creating the dictionary to store the results
def tribo(n):
if n in h:
return h[n]
if n==0:
return 0
elif n==1 or n==2:
return 1
else:
res=tribo(n-3)+tribo(n-2)+tribo(n-1)
h[n]=res #storing the results so that we can reuse it again
return res
return tribo(n)
n=10
for i in range(n):
print(tribonacci(i),end=' ')
Javascript
// A simple recursive JS program to print
// first n Tribonacci numbers.
function printTribRec(n, dp)
{
if (n == 0 || n == 1 || n == 2)
return 0;
if(dp[n] != -1){
return dp[n] ;
}
if (n == 3)
return 1;
else
return dp[n] = printTribRec(n - 1, dp) +
printTribRec(n - 2, dp) +
printTribRec(n - 3, dp);
}
function printTrib(n)
{
// dp vector to store subproblems
let dp = new Array(n+1).fill(-1) ;
for (var i = 1; i < n; i++)
process.stdout.write(printTribRec(i, dp) + " ");
}
// Driver code
let n = 10;
printTrib(n);
// This code is contributed by phasing17
C#
// A simple recursive C# program to print
// first n Tribonacci numbers.
using System;
using System.Collections.Generic;
class GFG {
static int printTribRec(int n, List<int> dp)
{
if (n == 0 || n == 1 || n == 2)
return 0;
if (dp[n] != -1) {
return dp[n];
}
if (n == 3)
return 1;
else
return dp[n] = printTribRec(n - 1, dp)
+ printTribRec(n - 2, dp)
+ printTribRec(n - 3, dp);
}
static void printTrib(int n)
{
// dp vector to store subproblems
List<int> dp = new List<int>();
for (var i = 0; i <= n; i++)
dp.Add(-1);
for (int i = 1; i < n; i++)
Console.Write(printTribRec(i, dp) + " ");
}
// Driver code
public static void Main(string[] args)
{
int n = 10;
printTrib(n);
}
}
// This code is contributed by phasing17
Java
// A simple recursive Java program to print
// first n Tribonacci numbers.
import java.util.*;
class GFG {
static int printTribRec(int n, int[] dp)
{
if (n == 0 || n == 1 || n == 2)
return 0;
if (dp[n] != -1) {
return dp[n];
}
if (n == 3)
return 1;
else
return dp[n] = printTribRec(n - 1, dp)
+ printTribRec(n - 2, dp)
+ printTribRec(n - 3, dp);
}
static void printTrib(int n)
{
// dp vector to store subproblems
int[] dp = new int[n + 1];
for (var i = 0; i <= n; i++)
dp[i] = -1;
for (int i = 1; i < n; i++)
System.out.print(printTribRec(i, dp) + " ");
}
// Driver code
public static void main(String[] args)
{
int n = 10;
printTrib(n);
}
}
// This code is contributed by phasing17
Producción
0 0 1 1 2 4 7 13 24
2) Tabulación ascendente de DP:
C++
// A DP based CPP
// program to print
// first n Tribonacci
// numbers.
#include <iostream>
using namespace std;
int printTrib(int n)
{
int dp[n];
dp[0] = dp[1] = 0;
dp[2] = 1;
for (int i = 3; i < n; i++)
dp[i] = dp[i - 1] +
dp[i - 2] +
dp[i - 3];
for (int i = 0; i < n; i++)
cout << dp[i] << " ";
}
// Driver code
int main()
{
int n = 10;
printTrib(n);
return 0;
}
Java
// A DP based Java program
// to print first n
// Tribonacci numbers.
import java.io.*;
class GFG {
static void printTrib(int n)
{
int dp[]=new int[n];
dp[0] = dp[1] = 0;
dp[2] = 1;
for (int i = 3; i < n; i++)
dp[i] = dp[i - 1] +
dp[i - 2] +
dp[i - 3];
for (int i = 0; i < n; i++)
System.out.print(dp[i] + " ");
}
// Driver code
public static void main(String args[])
{
int n = 10;
printTrib(n);
}
}
/* This code is contributed by Nikita Tiwari.*/
Python3
# A DP based # Python 3 # program to print # first n Tribonacci # numbers. def printTrib(n) : dp = [0] * n dp[0] = dp[1] = 0; dp[2] = 1; for i in range(3,n) : dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; for i in range(0,n) : print(dp[i] , " ", end="") # Driver code n = 10 printTrib(n) # This code is contributed by Nikita Tiwari.
C#
// A DP based C# program
// to print first n
// Tribonacci numbers.
using System;
class GFG {
static void printTrib(int n)
{
int []dp = new int[n];
dp[0] = dp[1] = 0;
dp[2] = 1;
for (int i = 3; i < n; i++)
dp[i] = dp[i - 1] +
dp[i - 2] +
dp[i - 3];
for (int i = 0; i < n; i++)
Console.Write(dp[i] + " ");
}
// Driver code
public static void Main()
{
int n = 10;
printTrib(n);
}
}
/* This code is contributed by vt_m.*/
PHP
<?php
// A DP based PHP program
// to print first n
// Tribonacci numbers.
function printTrib($n)
{
$dp[0] = $dp[1] = 0;
$dp[2] = 1;
for ($i = 3; $i < $n; $i++)
$dp[$i] = $dp[$i - 1] +
$dp[$i - 2] +
$dp[$i - 3];
for ($i = 0; $i < $n; $i++)
echo $dp[$i] ," ";
}
// Driver code
$n = 10;
printTrib($n);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program
// to print first n
// Tribonacci numbers.
function printTrib(n)
{
let dp = Array.from({length: n}, (_, i) => 0);
dp[0] = dp[1] = 0;
dp[2] = 1;
for (let i = 3; i < n; i++)
dp[i] = dp[i - 1] +
dp[i - 2] +
dp[i - 3];
for (let i = 0; i < n; i++)
document.write(dp[i] + " ");
}
// driver function
let n = 10;
printTrib(n);
// This code is contributed by code_hunt.
</script>
Producción
0 0 1 1 2 4 7 13 24 44
La complejidad del tiempo de arriba es lineal, pero requiere espacio adicional. Podemos optimizar el espacio utilizado en la solución anterior utilizando tres variables para realizar un seguimiento de los tres números anteriores.
C++
// A space optimized
// based CPP program to
// print first n
// Tribonacci numbers.
#include <iostream>
using namespace std;
void printTrib(int n)
{
if (n < 1)
return;
// Initialize first
// three numbers
int first = 0, second = 0;
int third = 1;
cout << first << " ";
if (n > 1)
cout << second << " ";
if (n > 2)
cout << second << " ";
// Loop to add previous
// three numbers for
// each number starting
// from 3 and then assign
// first, second, third
// to second, third, and
// curr to third respectively
for (int i = 3; i < n; i++)
{
int curr = first + second + third;
first = second;
second = third;
third = curr;
cout << curr << " ";
}
}
// Driver code
int main()
{
int n = 10;
printTrib(n);
return 0;
}
Java
// A space optimized
// based Java program
// to print first n
// Tribinocci numbers.
import java.io.*;
class GFG {
static void printTrib(int n)
{
if (n < 1)
return;
// Initialize first
// three numbers
int first = 0, second = 0;
int third = 1;
System.out.print(first + " ");
if (n > 1)
System.out.print(second + " ");
if (n > 2)
System.out.print(second + " ");
// Loop to add previous
// three numbers for
// each number starting
// from 3 and then assign
// first, second, third
// to second, third, and curr
// to third respectively
for (int i = 3; i < n; i++)
{
int curr = first + second + third;
first = second;
second = third;
third = curr;
System.out.print(curr +" ");
}
}
// Driver code
public static void main(String args[])
{
int n = 10;
printTrib(n);
}
}
// This code is contributed by Nikita Tiwari.
Python3
# A space optimized # based Python 3 # program to print # first n Tribinocci # numbers. def printTrib(n) : if (n < 1) : return # Initialize first # three numbers first = 0 second = 0 third = 1 print( first , " ", end="") if (n > 1) : print(second, " ",end="") if (n > 2) : print(second, " ", end="") # Loop to add previous # three numbers for # each number starting # from 3 and then assign # first, second, third # to second, third, and curr # to third respectively for i in range(3, n) : curr = first + second + third first = second second = third third = curr print(curr , " ", end="") # Driver code n = 10 printTrib(n) # This code is contributed by Nikita Tiwari.
C#
// A space optimized
// based C# program
// to print first n
// Tribinocci numbers.
using System;
class GFG {
static void printTrib(int n)
{
if (n < 1)
return;
// Initialize first
// three numbers
int first = 0, second = 0;
int third = 1;
Console.Write(first + " ");
if (n > 1)
Console.Write(second + " ");
if (n > 2)
Console.Write(second + " ");
// Loop to add previous
// three numbers for
// each number starting
// from 3 and then assign
// first, second, third
// to second, third, and curr
// to third respectively
for (int i = 3; i < n; i++)
{
int curr = first + second + third;
first = second;
second = third;
third = curr;
Console.Write(curr +" ");
}
}
// Driver code
public static void Main()
{
int n = 10;
printTrib(n);
}
}
// This code is contributed by vt_m.
PHP
<?php
// A space optimized
// based PHP program to
// print first n
// Tribinocci numbers.|
function printTrib($n)
{
if ($n < 1)
return;
// Initialize first
// three numbers
$first = 0; $second = 0;
$third = 1;
echo $first, " ";
if ($n > 1)
echo $second , " ";
if ($n > 2)
echo $second , " ";
// Loop to add previous
// three numbers for
// each number starting
// from 3 and then assign
// first, second, third
// to second, third, and
// curr to third respectively
for ($i = 3; $i < $n; $i++)
{
$curr = $first + $second + $third;
$first = $second;
$second = $third;
$third = $curr;
echo $curr , " ";
}
}
// Driver code
$n = 10;
printTrib($n);
// This code is contributed by m_kit
?>
Javascript
<script>
// A space optimized
// based Javascript program
// to print first n
// Tribonacci numbers.
function printTrib(n)
{
if (n < 1)
return;
// Initialize first
// three numbers
let first = 0, second = 0;
let third = 1;
document.write(first + " ");
if (n > 1)
document.write(second + " ");
if (n > 2)
document.write(second + " ");
// Loop to add previous
// three numbers for
// each number starting
// from 3 and then assign
// first, second, third
// to second, third, and curr
// to third respectively
for (let i = 3; i < n; i++)
{
let curr = first + second + third;
first = second;
second = third;
third = curr;
document.write(curr +" ");
}
}
// Driver code
let n = 10;
printTrib(n);
// This code is contributed by rag2127
</script>
Producción
0 0 0 1 2 4 7 13 24 44
A continuación se muestra una solución más eficiente utilizando exponenciación matricial .
C++
#include <iostream>
using namespace std;
// Program to print first n
// tribonacci numbers Matrix
// Multiplication function
// for 3*3 matrix
void multiply(int T[3][3], int M[3][3])
{
int a, b, c, d, e, f, g, h, i;
a = T[0][0] * M[0][0] +
T[0][1] * M[1][0] +
T[0][2] * M[2][0];
b = T[0][0] * M[0][1] +
T[0][1] * M[1][1] +
T[0][2] * M[2][1];
c = T[0][0] * M[0][2] +
T[0][1] * M[1][2] +
T[0][2] * M[2][2];
d = T[1][0] * M[0][0] +
T[1][1] * M[1][0] +
T[1][2] * M[2][0];
e = T[1][0] * M[0][1] +
T[1][1] * M[1][1] +
T[1][2] * M[2][1];
f = T[1][0] * M[0][2] +
T[1][1] * M[1][2] +
T[1][2] * M[2][2];
g = T[2][0] * M[0][0] +
T[2][1] * M[1][0] +
T[2][2] * M[2][0];
h = T[2][0] * M[0][1] +
T[2][1] * M[1][1] +
T[2][2] * M[2][1];
i = T[2][0] * M[0][2] +
T[2][1] * M[1][2] +
T[2][2] * M[2][2];
T[0][0] = a;
T[0][1] = b;
T[0][2] = c;
T[1][0] = d;
T[1][1] = e;
T[1][2] = f;
T[2][0] = g;
T[2][1] = h;
T[2][2] = i;
}
// Recursive function to raise
// the matrix T to the power n
void power(int T[3][3], int n)
{
// base condition.
if (n == 0 || n == 1)
return;
int M[3][3] = {{ 1, 1, 1 },
{ 1, 0, 0 },
{ 0, 1, 0 }};
// recursively call to
// square the matrix
power(T, n / 2);
// calculating square
// of the matrix T
multiply(T, T);
// if n is odd multiply
// it one time with M
if (n % 2)
multiply(T, M);
}
int tribonacci(int n)
{
int T[3][3] = {{ 1, 1, 1 },
{ 1, 0, 0 },
{ 0, 1, 0 }};
// base condition
if (n == 0 || n == 1)
return 0;
else
power(T, n - 2);
// T[0][0] contains the
// tribonacci number so
// return it
return T[0][0];
}
// Driver Code
int main()
{
int n = 10;
for (int i = 0; i < n; i++)
cout << tribonacci(i) << " ";
cout << endl;
return 0;
}
Java
// Java Program to print
// first n tribonacci numbers
// Matrix Multiplication
// function for 3*3 matrix
import java.io.*;
class GFG
{
static void multiply(int T[][], int M[][])
{
int a, b, c, d, e, f, g, h, i;
a = T[0][0] * M[0][0] +
T[0][1] * M[1][0] +
T[0][2] * M[2][0];
b = T[0][0] * M[0][1] +
T[0][1] * M[1][1] +
T[0][2] * M[2][1];
c = T[0][0] * M[0][2] +
T[0][1] * M[1][2] +
T[0][2] * M[2][2];
d = T[1][0] * M[0][0] +
T[1][1] * M[1][0] +
T[1][2] * M[2][0];
e = T[1][0] * M[0][1] +
T[1][1] * M[1][1] +
T[1][2] * M[2][1];
f = T[1][0] * M[0][2] +
T[1][1] * M[1][2] +
T[1][2] * M[2][2];
g = T[2][0] * M[0][0] +
T[2][1] * M[1][0] +
T[2][2] * M[2][0];
h = T[2][0] * M[0][1] +
T[2][1] * M[1][1] +
T[2][2] * M[2][1];
i = T[2][0] * M[0][2] +
T[2][1] * M[1][2] +
T[2][2] * M[2][2];
T[0][0] = a;
T[0][1] = b;
T[0][2] = c;
T[1][0] = d;
T[1][1] = e;
T[1][2] = f;
T[2][0] = g;
T[2][1] = h;
T[2][2] = i;
}
// Recursive function to raise
// the matrix T to the power n
static void power(int T[][], int n)
{
// base condition.
if (n == 0 || n == 1)
return;
int M[][] = {{ 1, 1, 1 },
{ 1, 0, 0 },
{ 0, 1, 0 }};
// recursively call to
// square the matrix
power(T, n / 2);
// calculating square
// of the matrix T
multiply(T, T);
// if n is odd multiply
// it one time with M
if (n % 2 != 0)
multiply(T, M);
}
static int tribonacci(int n)
{
int T[][] = {{ 1, 1, 1 },
{ 1, 0, 0 },
{ 0, 1, 0 }};
// base condition
if (n == 0 || n == 1)
return 0;
else
power(T, n - 2);
// T[0][0] contains the
// tribonacci number so
// return it
return T[0][0];
}
// Driver Code
public static void main(String args[])
{
int n = 10;
for (int i = 0; i < n; i++)
System.out.print(tribonacci(i) + " ");
System.out.println();
}
}
// This code is contributed by Nikita Tiwari.
Python 3
# Program to print first n tribonacci # numbers Matrix Multiplication # function for 3*3 matrix def multiply(T, M): a = (T[0][0] * M[0][0] + T[0][1] * M[1][0] + T[0][2] * M[2][0]) b = (T[0][0] * M[0][1] + T[0][1] * M[1][1] + T[0][2] * M[2][1]) c = (T[0][0] * M[0][2] + T[0][1] * M[1][2] + T[0][2] * M[2][2]) d = (T[1][0] * M[0][0] + T[1][1] * M[1][0] + T[1][2] * M[2][0]) e = (T[1][0] * M[0][1] + T[1][1] * M[1][1] + T[1][2] * M[2][1]) f = (T[1][0] * M[0][2] + T[1][1] * M[1][2] + T[1][2] * M[2][2]) g = (T[2][0] * M[0][0] + T[2][1] * M[1][0] + T[2][2] * M[2][0]) h = (T[2][0] * M[0][1] + T[2][1] * M[1][1] + T[2][2] * M[2][1]) i = (T[2][0] * M[0][2] + T[2][1] * M[1][2] + T[2][2] * M[2][2]) T[0][0] = a T[0][1] = b T[0][2] = c T[1][0] = d T[1][1] = e T[1][2] = f T[2][0] = g T[2][1] = h T[2][2] = i # Recursive function to raise # the matrix T to the power n def power(T, n): # base condition. if (n == 0 or n == 1): return; M = [[ 1, 1, 1 ], [ 1, 0, 0 ], [ 0, 1, 0 ]] # recursively call to # square the matrix power(T, n // 2) # calculating square # of the matrix T multiply(T, T) # if n is odd multiply # it one time with M if (n % 2): multiply(T, M) def tribonacci(n): T = [[ 1, 1, 1 ], [1, 0, 0 ], [0, 1, 0 ]] # base condition if (n == 0 or n == 1): return 0 else: power(T, n - 2) # T[0][0] contains the # tribonacci number so # return it return T[0][0] # Driver Code if __name__ == "__main__": n = 10 for i in range(n): print(tribonacci(i),end=" ") print() # This code is contributed by ChitraNayal
C#
// C# Program to print
// first n tribonacci numbers
// Matrix Multiplication
// function for 3*3 matrix
using System;
class GFG
{
static void multiply(int [,]T,
int [,]M)
{
int a, b, c, d, e, f, g, h, i;
a = T[0,0] * M[0,0] +
T[0,1] * M[1,0] +
T[0,2] * M[2,0];
b = T[0,0] * M[0,1] +
T[0,1] * M[1,1] +
T[0,2] * M[2,1];
c = T[0,0] * M[0,2] +
T[0,1] * M[1,2] +
T[0,2] * M[2,2];
d = T[1,0] * M[0,0] +
T[1,1] * M[1,0] +
T[1,2] * M[2,0];
e = T[1,0] * M[0,1] +
T[1,1] * M[1,1] +
T[1,2] * M[2,1];
f = T[1,0] * M[0,2] +
T[1,1] * M[1,2] +
T[1,2] * M[2,2];
g = T[2,0] * M[0,0] +
T[2,1] * M[1,0] +
T[2,2] * M[2,0];
h = T[2,0] * M[0,1] +
T[2,1] * M[1,1] +
T[2,2] * M[2,1];
i = T[2,0] * M[0,2] +
T[2,1] * M[1,2] +
T[2,2] * M[2,2];
T[0,0] = a;
T[0,1] = b;
T[0,2] = c;
T[1,0] = d;
T[1,1] = e;
T[1,2] = f;
T[2,0] = g;
T[2,1] = h;
T[2,2] = i;
}
// Recursive function to raise
// the matrix T to the power n
static void power(int [,]T, int n)
{
// base condition.
if (n == 0 || n == 1)
return;
int [,]M = {{ 1, 1, 1 },
{ 1, 0, 0 },
{ 0, 1, 0 }};
// recursively call to
// square the matrix
power(T, n / 2);
// calculating square
// of the matrix T
multiply(T, T);
// if n is odd multiply
// it one time with M
if (n % 2 != 0)
multiply(T, M);
}
static int tribonacci(int n)
{
int [,]T = {{ 1, 1, 1 },
{ 1, 0, 0 },
{ 0, 1, 0 }};
// base condition
if (n == 0 || n == 1)
return 0;
else
power(T, n - 2);
// T[0][0] contains the
// tribonacci number so
// return it
return T[0,0];
}
// Driver Code
public static void Main()
{
int n = 10;
for (int i = 0; i < n; i++)
Console.Write(tribonacci(i) + " ");
Console.WriteLine();
}
}
// This code is contributed by vt_m.
PHP
<?php
// Program to print first n tribonacci numbers
// Matrix Multiplication function for 3*3 matrix
function multiply(&$T, $M)
{
$a = $T[0][0] * $M[0][0] +
$T[0][1] * $M[1][0] +
$T[0][2] * $M[2][0];
$b = $T[0][0] * $M[0][1] +
$T[0][1] * $M[1][1] +
$T[0][2] * $M[2][1];
$c = $T[0][0] * $M[0][2] +
$T[0][1] * $M[1][2] +
$T[0][2] * $M[2][2];
$d = $T[1][0] * $M[0][0] +
$T[1][1] * $M[1][0] +
$T[1][2] * $M[2][0];
$e = $T[1][0] * $M[0][1] +
$T[1][1] * $M[1][1] +
$T[1][2] * $M[2][1];
$f = $T[1][0] * $M[0][2] +
$T[1][1] * $M[1][2] +
$T[1][2] * $M[2][2];
$g = $T[2][0] * $M[0][0] +
$T[2][1] * $M[1][0] +
$T[2][2] * $M[2][0];
$h = $T[2][0] * $M[0][1] +
$T[2][1] * $M[1][1] +
$T[2][2] * $M[2][1];
$i = $T[2][0] * $M[0][2] +
$T[2][1] * $M[1][2] +
$T[2][2] * $M[2][2];
$T[0][0] = $a;
$T[0][1] = $b;
$T[0][2] = $c;
$T[1][0] = $d;
$T[1][1] = $e;
$T[1][2] = $f;
$T[2][0] = $g;
$T[2][1] = $h;
$T[2][2] = $i;
}
// Recursive function to raise
// the matrix T to the power n
function power(&$T,$n)
{
// base condition.
if ($n == 0 || $n == 1)
return;
$M = array(array( 1, 1, 1 ),
array( 1, 0, 0 ),
array( 0, 1, 0 ));
// recursively call to
// square the matrix
power($T, (int)($n / 2));
// calculating square
// of the matrix T
multiply($T, $T);
// if n is odd multiply
// it one time with M
if ($n % 2)
multiply($T, $M);
}
function tribonacci($n)
{
$T = array(array( 1, 1, 1 ),
array( 1, 0, 0 ),
array( 0, 1, 0 ));
// base condition
if ($n == 0 || $n == 1)
return 0;
else
power($T, $n - 2);
// $T[0][0] contains the tribonacci
// number so return it
return $T[0][0];
}
// Driver Code
$n = 10;
for ($i = 0; $i < $n; $i++)
echo tribonacci($i) . " ";
echo "\n";
// This code is contributed by mits
?>
Javascript
<script>
// javascript Program to print
// first n tribonacci numbers
// Matrix Multiplication
// function for 3*3 matrix
function multiply(T , M)
{
var a, b, c, d, e, f, g, h, i;
a = T[0][0] * M[0][0] +
T[0][1] * M[1][0] +
T[0][2] * M[2][0];
b = T[0][0] * M[0][1] +
T[0][1] * M[1][1] +
T[0][2] * M[2][1];
c = T[0][0] * M[0][2] +
T[0][1] * M[1][2] +
T[0][2] * M[2][2];
d = T[1][0] * M[0][0] +
T[1][1] * M[1][0] +
T[1][2] * M[2][0];
e = T[1][0] * M[0][1] +
T[1][1] * M[1][1] +
T[1][2] * M[2][1];
f = T[1][0] * M[0][2] +
T[1][1] * M[1][2] +
T[1][2] * M[2][2];
g = T[2][0] * M[0][0] +
T[2][1] * M[1][0] +
T[2][2] * M[2][0];
h = T[2][0] * M[0][1] +
T[2][1] * M[1][1] +
T[2][2] * M[2][1];
i = T[2][0] * M[0][2] +
T[2][1] * M[1][2] +
T[2][2] * M[2][2];
T[0][0] = a;
T[0][1] = b;
T[0][2] = c;
T[1][0] = d;
T[1][1] = e;
T[1][2] = f;
T[2][0] = g;
T[2][1] = h;
T[2][2] = i;
}
// Recursive function to raise
// the matrix T to the power n
function power(T , n)
{
// base condition.
if (n == 0 || n == 1)
return;
var M = [[ 1, 1, 1 ],
[ 1, 0, 0 ],
[ 0, 1, 0 ]];
// recursively call to
// square the matrix
power(T, parseInt(n / 2));
// calculating square
// of the matrix T
multiply(T, T);
// if n is odd multiply
// it one time with M
if (n % 2 != 0)
multiply(T, M);
}
function tribonacci(n)
{
var T = [[ 1, 1, 1 ],
[ 1, 0, 0 ],
[ 0, 1, 0 ]];
// base condition
if (n == 0 || n == 1)
return 0;
else
power(T, n - 2);
// T[0][0] contains the
// tribonacci number so
// return it
return T[0][0];
}
// Driver Code
var n = 10;
for (var i = 0; i < n; i++)
document.write(tribonacci(i) + " ");
document.write('<br>');
// This code contributed by shikhasingrajput
</script>
Producción
0 0 1 1 2 4 7 13 24 44
Este artículo es una contribución de Sahil Rajput . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA