Application pratique de l'algorithme pour la représentation de Zeckendorff

Comme dans le passé

J'ai écrit un article sur l'algorithme récursif de Zeckendorff: post

Exemple de code

def le_fib(limit, fib)
  theoretical = fib[fib.count - 1] + fib[fib.count - 2]
  return fib.last if theoretical > limit

  fib << theoretical
  le_fib(limit, fib)
end

def main(target,result)
  temporary = le_fib(target, [1,1])
  result << temporary
  return result if target - temporary <= 0

  main(target - temporary, result)
end
pp main(gets.to_i,[])

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Fonction  Le_fib  - recherche récursivement une série de Fibonacci avec une limite, de sorte que le nombre suivant ne soit pas supérieur au nombre cible d' entrée  . Il est important ici que nous ne nous intéressions pas à l'ensemble de la série Fibonacci, seule sa fin nous importe.

La fonction  principale  - recherche récursivement un tableau dont les nombres sont des nombres de Fibonacci, et qui ensemble nous donneraient un nombre d'entrée.

Bien qu'en vérité, les commentaires suggèrent une solution plus élégante:

Un cycle et une entreprise

n, F = 100, [1, 2]
while F[-1] < n do
  F << F[-2] + F[-1]
end
F.reverse.each do |f|
  if f <= n
    n -= f
    print f
    print '+' if n > 0
  end
end
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

En pratique, j'utiliserai le deuxième algorithme car il est moins surchargé d'actions inutiles.

Énoncé du problème où nous allons "pousser cet algorithme"

Il existe un certain ensemble de produits, relativement parlant:

[Poulet, tomates, lavash, champignons].

Ces produits ont à la fois un coût et une valeur pour l'utilisateur final.

Par exemple, la gradation peut être effectuée comme suit

[poulet> tomates> champignons> lavash] .

, 1 "Low cost", 1 "High cost" .

().

( Ruby) , .

, .

x y .

1. 

   

2. Y - .
   
   
   
   - , .
   
   
   
   . Y

   
   
   
   
   

   

3. 1 89. , "Middle cost" .
   
   
   
   3 x = 1 y = 143.

   
   
   
   
   

, :

• - ( )

  
  
  
  
  

• Collector, Hash ( -> , -> )

  
  
  
  
  

, autoloader , .

, Telegram , .

, ,

@fib = [1,2,3,5,8,13,21,34,55,89]
    def collect_the_items
      food_hash = Hash.new
      (0..9).each do |iterator|
        food_hash[@fib[iterator]] = FOOD.first[iterator]
      end
      puts food_hash.map{|key,value| "#{key} - #{value}"}
    end
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

, :

def get_sequence(limit)  
  result = []  n, fib = limit, [1, 2]  
  while fib[-1] < n do
    fib << fib[-2] + fib[-1]  end
  fib.reverse.each do |f|    if f <= n
      n -= f
      result << f
    end
  end
  result
end
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

- .

def generate_food
          food_array = Collector.collect_the_items
          food = []
          rarity = rand(1..143)
          get_sequence(rarity).each do |key|
            food << food_array[key]
          end
          food
end
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

, 6 , .

. - .

:

Low cost : ?

Mid cost : ?

High cost : ?

L'application de l'algorithme de représentation de Zeckendorff me satisfait complètement. Autrement dit, il exécute la tâche qui lui est assignée.

L'un des premiers commentaires sous l'article sur lequel cette application pratique est basée, m'a juste posé la question: "mais vraiment, où cela peut-il s'appliquer?" Comme vous pouvez le voir, cet algorithme peut être utilisé pour de telles tâches.

Et je ne dis pas que c'est la seule option correcte pour compiler une liste de produits pour mon bot, mais cela fonctionne vraiment très bien.