Aplicação prática do algoritmo para representação de Zeckendorff

Como no passado

Escrevi um artigo sobre Algoritmo Zeckendorff Recursivo: post

Código de amostra

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,[])

      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Função  Le_fib  - procura recursivamente por uma série de Fibonacci com um limite, de forma que o próximo número não seja maior que o número de destino de entrada  . É importante aqui que não estamos interessados ​​em toda a série Fibonacci, apenas seu final é importante para nós.

A função  principal  - procura recursivamente por um array cujos números são números de Fibonacci, e que nos daria um número de entrada no total.

Embora, na verdade, os comentários sugerissem uma solução mais elegante:

Um ciclo e negócios

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
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
    

Na prática, usarei o segundo algoritmo, pois é menos sobrecarregado com ações desnecessárias.

Declaração do problema onde iremos "empurrar este algoritmo"

Existe um certo conjunto de produtos, relativamente falando:

[Frango, tomate, lavash, cogumelos].

Esses produtos têm custo e valor para o usuário final.

Por exemplo, a gradação pode ser feita da seguinte forma

[frango> tomate> cogumelos> 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 : ?

A aplicação do algoritmo de representação Zeckendorff me satisfaz completamente. Ou seja, ele executa a tarefa atribuída a ele.

Um dos primeiros comentários no artigo em que esta aplicação prática se baseia, apenas me fez a pergunta: "mas realmente, onde isso pode ser aplicado?" Como você pode ver, esse algoritmo pode ser usado para tais tarefas.

E não estou dizendo que essa seja a única opção correta para compilar uma lista de produtos para o meu bot, mas realmente é muito capaz e funciona.