La array de Wythoff es una array infinita de números enteros derivados de la secuencia de Fibonacci . Cada número entero positivo en la array ocurre solo una vez.
array de Wythoff:
1 2 3 5 8 13 ...
4 7 11 18 29 47 ...
6 10 16 26 42 68 ...
9 15 24 39 63 102 ...
12 20 32 52 84 136 ...
14 23 37 60 97 157 ...
. . . . . .
. . . . . .
Si A m, n denota el elemento en la m -ésima fila y la n-ésima columna, entonces
- Un metro , 1 = [[mφ]φ]
- UN metro , 2 = [[mφ]φ 2 ]
- UN metro, n = UN metro, n-2 + UN metro, n-1 para n > 2
- φ = (1 + √5) / 2
Si atravesamos la array de forma antidiagonal comenzando desde el elemento superior izquierdo, entonces
la secuencia de Wythoff:
1, 2, 4, 3, 7, 6, 5, 11, 10, 9….
Para un N dado , la tarea de imprimir los primeros N números de la secuencia.
Ejemplos:
Entrada: N = 10
Salida: 1, 2, 4, 3, 7, 6, 5, 11, 10, 9
Entrada: N = 15
Salida: 1, 2, 4, 3, 7, 6, 5, 11, 10 , 9, 8, 18, 16, 15, 12
Enfoque:
Las recursiones anteriores se pueden modificar como
- T(n, -1) = n-1, si k = -1
- T(n, 0) = [n*φ], si k = 0
- T(n, k) = T(n, k-1) + T(n, k-2), si k > 0
- φ = (1 + √5) / 2
Entonces, podemos encontrar recursivamente el valor de T(n, k) con dos casos base para t = 0 y para t = – 1. Almacenaremos los valores en un mapa y lo usaremos cuando sea necesario para reducir el cálculo. Después de obtener la array, tenemos que atravesarla en forma antidiagonal, por lo que establecemos i=0 y j= 0 y disminuimos j y aumentamos i cuando j < 0 inicializamos j = i e i = 0 .
también mantenemos un conteo que aumenta cuando se muestra un número. Rompemos la array cuando el conteo alcanza el valor requerido.
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ program to find Wythoff array
#include <bits/stdc++.h>
using namespace std;
// Function to find the n, k term of Wythoff array
int Wythoff(map<int, map<int, int> >& mp, int n, int k)
{
// tau = (sqrt(5)+1)/2
double tau = (sqrt(5) + 1) / 2.0, t_n_k;
// Already_stored
if (mp[n][k] != 0)
return mp[n][k];
// T(n, -1) = n-1.
if (k == -1) {
return n - 1;
}
// T(n, 0) = floor(n*tau).
else if (k == 0) {
t_n_k = floor(n * tau);
}
// T(n, k) = T(n, k-1) + T(n, k-2) for k>=1.
else
{
t_n_k = Wythoff(mp, n, k - 1) +
Wythoff(mp, n, k - 2);
}
// Store
mp[n][k] = t_n_k;
// Return the ans
return (int)t_n_k;
}
// Function to find first n terms of Wythoff
// array by traversing in anti-diagonal
void Wythoff_Array(int n)
{
int i = 0, j = 0, count = 0;
// Map to store the Wythoff array
map<int, map<int, int> > mp;
while (count < n) {
cout << Wythoff(mp, i + 1, j + 1);
count++;
if(count != n)
cout << ", ";
// Anti diagonal
i++;
j--;
if (j < 0) {
j = i;
i = 0;
}
}
}
// Driver code
int main()
{
int n = 15;
// Function call
Wythoff_Array(n);
return 0;
}
Java
// Java program to find Wythoff array
import java.util.*;
public class GFG
{
// Function to find the n, k term of Wythoff array
static int Wythoff(HashMap<Integer,
HashMap<Integer, Integer>> mp,
int n, int k)
{
// tau = (sqrt(5)+1)/2
double tau = (Math.sqrt(5) + 1) / 2.0, t_n_k;
// Already_stored
if (mp.containsKey(n) &&
mp.get(n).containsKey(k) &&
mp.get(n).get(k) != 0)
return mp.get(n).get(k);
// T(n, -1) = n-1.
if (k == -1)
{
return n - 1;
}
// T(n, 0) = floor(n*tau).
else if (k == 0)
{
t_n_k = Math.floor(n * tau);
}
// T(n, k) = T(n, k-1) + T(n, k-2) for k>=1.
else
{
t_n_k = Wythoff(mp, n, k - 1) +
Wythoff(mp, n, k - 2);
}
// Store
mp.put(n, new HashMap<Integer, Integer>(k,(int)t_n_k));
// Return the ans
return (int)t_n_k;
}
// Function to find first n terms of Wythoff
// array by traversing in anti-diagonal
static void Wythoff_Array(int n)
{
int i = 0, j = 0, count = 0;
// Map to store the Wythoff array
HashMap<Integer, HashMap<Integer,Integer>> mp =
new HashMap<Integer, HashMap<Integer,Integer>>();
while (count < n)
{
System.out.print(Wythoff(mp, i + 1, j + 1));
count++;
if(count != n)
System.out.print(", ");
// Anti diagonal
i++;
j--;
if (j < 0)
{
j = i;
i = 0;
}
}
}
// Driver code
public static void main(String[] args)
{
int n = 15;
// Function call
Wythoff_Array(n);
}
}
// This code is contributed by divyeshrabadiya07.
Python3
# Python3 program to find Wythoff array
import math
# Function to find the n, k term of Wythoff array
def Wythoff(mp, n, k):
# tau = (sqrt(5)+1)/2
tau = (math.sqrt(5) + 1) / 2
t_n_k = 0
# Already_stored
if ((n in mp) and (k in mp[n])):
return mp[n][k];
# T(n, -1) = n-1.
if (k == -1):
return n - 1;
# T(n, 0) = floor(n*tau).
elif (k == 0):
t_n_k = math.floor(n * tau);
# T(n, k) = T(n, k-1) + T(n, k-2) for k>=1.
else:
t_n_k = Wythoff(mp, n, k - 1) + Wythoff(mp, n, k - 2)
# Store
if n not in mp:
mp[n] = dict()
mp[n][k] = t_n_k;
# Return the ans
return int(t_n_k)
# Function to find first n terms of Wythoff
# array by traversing in anti-diagonal
def Wythoff_Array(n):
i = 0
j = 0
count = 0;
# Map to store the Wythoff array
mp = dict()
while (count < n):
print(Wythoff(mp, i + 1, j + 1), end = '')
count += 1
if(count != n):
print(", ", end = '')
# Anti diagonal
i += 1
j -= 1
if (j < 0):
j = i;
i = 0;
# Driver code
if __name__=='__main__':
n = 15;
# Function call
Wythoff_Array(n);
# This code is contributed by rutvik_56
C#
// C# program to find Wythoff array
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the n, k term of Wythoff array
static int Wythoff(Dictionary<int, Dictionary<int, int>> mp, int n, int k)
{
// tau = (sqrt(5)+1)/2
double tau = (Math.Sqrt(5) + 1) / 2.0, t_n_k;
// Already_stored
if (mp.ContainsKey(n) && mp[n].ContainsKey(k) && mp[n][k] != 0)
return mp[n][k];
// T(n, -1) = n-1.
if (k == -1) {
return n - 1;
}
// T(n, 0) = floor(n*tau).
else if (k == 0)
{
t_n_k = Math.Floor(n * tau);
}
// T(n, k) = T(n, k-1) + T(n, k-2) for k>=1.
else
{
t_n_k = Wythoff(mp, n, k - 1) + Wythoff(mp, n, k - 2);
}
// Store
if(!mp.ContainsKey(n))
{
mp[n] = new Dictionary<int,int>();
}
mp[n][k] = (int)t_n_k;
// Return the ans
return (int)t_n_k;
}
// Function to find first n terms of Wythoff
// array by traversing in anti-diagonal
static void Wythoff_Array(int n)
{
int i = 0, j = 0, count = 0;
// Map to store the Wythoff array
Dictionary<int, Dictionary<int,int>> mp = new Dictionary<int, Dictionary<int,int>>();
while (count < n)
{
Console.Write(Wythoff(mp, i + 1, j + 1));
count++;
if(count != n)
Console.Write(", ");
// Anti diagonal
i++;
j--;
if (j < 0) {
j = i;
i = 0;
}
}
}
// Driver code
static void Main()
{
int n = 15;
// Function call
Wythoff_Array(n);
}
}
// This code is contributed by divyesh072019.
Producción:
1, 2, 4, 3, 7, 6, 5, 11, 10, 9, 8, 18, 16, 15, 12,
Referencia: https://oeis.org/A035513
Publicación traducida automáticamente
Artículo escrito por andrew1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA