Ruby'de recrusion kullanılarak fibonacci dizisi nasıl yazılır?

Ruby'de sayı fibonacci dizisi içeriyorsa true, değilse false döndüren bir yöntem oluşturmaya çalıştım.

Doğru ya da yanlış döndüğümde bir sorunum olduğunu düşünüyorum.

Birisi bana neden ilk kodun işe yaramadığını söyleyebilir mi?

def is_fibonacci?(num, array=[0,1])

  n = array.length - 1

  if array[n] > num
    array.include?(num) ? true : false
  end

  array << array[n] + array[n-1]
  is_fibonacci?(num, array)

end

Bu kodu çalıştırdığımda, bu hata mesajını aldım.

=>filename.rb:36:in `include?': Interrupt

def is_fibonacci?(num, array=[0,1])
  n = array.length - 1

  if array[n] > num
    if array.include?(num)
        return true
    else
        return false
    end
  end

  array << array[n] + array[n-1]
  is_fibonacci?(num, array)

end

İkinci kod çalıştı.

Neden kullanamıyorum

array.include?(num) ? true : false 

Kodda?

Yardım ettiğiniz için teşekkür ederim.

2
def fibonacci (n), eğer n <= 1 fibonacci (n - 1) + fibonacci (n - 2) sonunda fibonacci (10) # => 55 verir
katma yazar Santhucool, kaynak
Conding stili hakkında kısa bir not: array.include? (Num) zaten true veya false değerini döndürür. if ... else ... end bloğunun tamamını yalnızca return array.include? (Num) ile değiştirebilirsiniz
katma yazar spickermann, kaynak

6 cevap

Shivam zaten ilk versiyonun çalışmadığı sorusuna iyi bir cevap verdi.

Hesaplanan tüm fibonacci sayılarını dizide tutmak için hiçbir neden olmadığını belirtmek istiyorum Bu bir alan kaybı ve muhtemelen biraz verimsiz. Bu nedenle, yönteminizi şu şekilde basitleştirebilirsiniz:

def fibonacci?(number)
  fibos = [0, 1]
  fibos << (fibos.shift + fibos.last) while fibos.last < number
  fibos.include?(number)
end
2
katma
@SergioTulentsev: Haklısın. Bunu daha çok beğendin mi?
katma yazar spickermann, kaynak
Pastören örneğini beğendim. Özyineleme konusunda emin değilim. Çünkü bu resüzyon için gerçekten kötü bir örnek, çünkü problemi her tekrarlamada küçülmek yerine daha büyük yapıyor. Bu nedenle özyineleme sorunu çözmek için kötü bir seçimdir. Özyineleme bir ev ödevi alıştırması olduğu için şartsa, umrumda değil ...
katma yazar spickermann, kaynak
Merge veya Quicksort gibi bazı sıralama algoritmaları harika örneklerdir.
katma yazar spickermann, kaynak
çok fazla geçici dizi oluşturmak da süper verimli değildir :)
katma yazar Sergio Tulentsev, kaynak
evet, bu daha iyi, ama: 1) tekrarlamıyorsunuz (ki bu şart, sanırım) 2) çünkü imzada diziye ihtiyacınız yok (veya hatta ona ihtiyacınız yok) herşey). Böyle bir şey daha da iyidir: pastebin.com/1ew7Tktp
katma yazar Sergio Tulentsev, kaynak
BTW, özyinelemenin burada kullanılmaması gerektiğine katılıyorum (pratik yapıyorsak). Hatta bu konuda bile döngü. Nth fibonacci terimini hesaplamak için bir O (1) formülü vardır. Sanırım bunu ve ikili aramayı kullanabiliriz.
katma yazar Sergio Tulentsev, kaynak
Özyinelemeyi öğretmek için pek iyi örnek yoktur. Kafamın üstünden bir tane düşünemiyorum.
katma yazar Sergio Tulentsev, kaynak
Fakat sıralama fibonacci'den çok daha karmaşık :)
katma yazar Sergio Tulentsev, kaynak
Belki bazı ağaç yürüyüş örnekleri. AST'yi bytecode ya da her neyse dönüştürmek gibi :)
katma yazar Sergio Tulentsev, kaynak
Pjs: Anladım. Ancak öğrenciler her zaman, özyinelemenin burada kullanılmasının kötü bir fikir olduğunu anlamamaktadır.
katma yazar Sergio Tulentsev, kaynak
@SergioTulentsev Daha gerçekçi örneklerin karmaşıklığı, profesörlerin Fibonacci, faktörler, tamsayı üsteli ve Hanoi kuleleri gibi oyuncak örnekleri ile başlamasının nedenidir.
katma yazar pjs, kaynak

array.include? (Num)? Nedeni true: false çalışmıyor çünkü return deyiminiz yok. return array.include? (Num)? Olarak değiştirin true: false . Ancak, sadece özyineleme algoritmasının başka bir seviyesini arayacak ve sonunda yığının içine çok derinlemesine girecektir.

Ve sadece bir bonus olarak, işte hash kullanan meşhur tek gömlek:

fibonacci = Hash.new{ |h,k| h[k] = k < 2 ? k : h[k-1] + h[k-2] }

p fibonacci[2]  # => 1
p fibonacci[23] # => 28657
1
katma
Bilgilendirme kullanmadan algoritma karmaşıklığınız katlanır, buna gerçekten ihtiyacınız var mı?
katma yazar Anatoly, kaynak
Hiçbir zaman boolean desenini kullanmamalısınız? true: false , Boole kendisi için konuşabilir.
katma yazar vgoff, kaynak

İlk versiyonunda, blok

if array[n] > num
  array.include?(num) ? true : false
end

sözdizimsel olarak doğru (kötü olmasına rağmen), ancak sonucu döndürmediğiniz için programınız için anlamsal olarak yanlış. Bu ifadeye açık bir return ekleyebilir veya programınızın geri kalanını bir else deyimi yapabilirsiniz. Aşağıdaki sürüm çalışır çünkü varsayılan olarak Ruby, çalıştırılan son ifadedeki sonucu döndürür ve if/else öğesinin yalnızca bir dalı değerlendirilir:

def is_fibonacci?(num, array=[0,1])
  n = array.length - 1
  if array[n] > num
    array.include?(num)
  else
    array << array[n] + array[n-1]
    is_fibonacci?(num, array)
  end
end
1
katma

Neden array.include? (num) kullanamıyorum? true: false

Sözdizimsel olarak, bu ifadede yanlış bir şey yoktur ve iyi çalışması gerekir. ( SystemStackError: yığın düzeyi çok derin olabilir ancak herhangi bir değer döndürmediğiniz için kodunuz bağlamında döndürülebilir).

İşte bir örnek:

array = [0,1]
num = 1
array.include?(num) ? true : false
# => true
num = 3
array.include?(num) ? true : false
# => false

Ancak bu korkunç bir koddur. .include? için resmi belgeler açıkça belirtir:

Verilen nesne kendi içinde mevcutsa true değerini döndürür (varsa   object == anObject), aksi takdirde yanlıştır.

Bunun anlamı:

num = 1
array.include?(num)
# => true
num = 3
array.include?(num)
# => false

Yine aynı hatayı aşağıdaki kodda tekrarlıyorsunuz:

 if array.include?(num)
    return true
 else
    return false
 end

Yukarıdaki kodun tümü tek bir satırla değiştirilebilir:

return array.include?(num)
1
katma

Fibonacci sayıları algoritması iki şekilde yapılabilir: özyineleme ile/olmadan. Özyinelemeli sürüm algoritmanın katlanarak karmaşıklaşmasını önlemek için uygulanan bir not tutmaya sahip olmalıdır.

Değişken 1:

class Fibonacci
  def initialize(num)
    @num = num
    @array = [0,1]
  end

  def process
    return @num if [0,1].include?(@num)
    2.upto(@num).each do |i|
      @array[i] = @array[i-1] + @array[i-2]
    end
    @array[@num]
  end
end

Değişken 2:

class FibonacciMemoizedRecursion
  def initialize(num)
    @num = num
    @memo = {0 => 0, 1 => 1, 2 => 1}
  end

  def process
    recursion(@num)
  end

  private

  def recursion(a)
    return @memo[a] if @memo.include?(a)
    @memo[a] = recursion(a-1) + recursion(a-2)
  end
end

Test etmek için MiniTest kütüphanesini kullanabiliriz:

require 'minitest/autorun'

class FibonacciTest < Minitest::Unit::TestCase
  def test_process_1
    assert_equal 0, Fibonacci.new(0).process
  end

  def test_process_2
    assert_equal 1, Fibonacci.new(1).process
  end

  def test_process_3
    assert_equal 1, Fibonacci.new(2).process
  end

  def test_process_4
    assert_equal 2, Fibonacci.new(3).process
  end

  def test_process_5
    assert_equal 3, Fibonacci.new(4).process
  end

  def test_process_6
    assert_equal 5, Fibonacci.new(5).process
  end

  def test_process_7
    assert_equal 8, Fibonacci.new(6).process
  end

  def test_process_8
    assert_equal 13, Fibonacci.new(7).process
  end
end
0
katma

Hashtag'i @hirolau kullanarak iki satırda yapabiliriz.

def fib?(n)
  @fibonacci ||= Hash.new{ |h,k| h[k] = k < 2 ? k : h[k-1] + h[k-2] }
  (0..n+1).any? { |x| @fibonacci[x] == n }
end
0
katma