Рекурсивный множитель в рубине

Question

Я пытаюсь создать рекурсивный множитель в ruby.

@j = 0

def multiplier(x, y, z)
    count = 0
    if x > 0
        if z > 0
            @j += y
            z -= 1
            count += 1
            multiplier(x, y, z)
        else
            x -= 1
            z = count
            p z
            multiplier(x, y, z)
        end
    else
        return @j
    end
end


def main
    puts "Calculation is: " + multiplier(3, 10, 4).to_s
end

main

X - это сколько раз умножение происходит

Y - это число, которое мы хотим умножить

Z - это число, которое мы умножаем на

Код должен выводить 120 с переменными, которые там есть

У меня проблемы с получением Z, чтобы остаться таким, каким я должен быть.Кроме того, я бы предпочел сделать это без глобальной переменной

Так что-то вроде x * (y * z), но без символа времени

Answer 1

Это можно записать так:

def multiplier(*args)
  prod = recurse(*args.map(&:abs))
  args.count { |n| n < 0 }.even? ? prod : -prod
end

def recurse(first, *rest)
  first.zero? || rest.empty? ? first : ([recurse(*rest)]*first).sum
end

multiplier(3,  10,  4)        #=>  120
multiplier(3,  10,  4, 2, 3)  #=>  720
multiplier(3, -10,  4)        #=> -120
multiplier(3, -10, -4)        #=>  120
multiplier(3,   0,  4)        #=>    0
multiplier(3,   0, -4)        #=>    0

Предположим, мы хотим вычислить multiplier(3, -4).recurse(3, 4) называется, где

first = 3
rest = [4]
first.zero? #=> false
rest.empty? #=> false

, поэтому мы вычисляем

([recurse(4)]*3).sum

In recurse(4),

first = 4
rest = []

As rest.empty #=> true, recurseвозвращает first #=> 4, поэтому

([recurse(4)]*3).sum]
  #=> ([4]*3).sum => [4,4,4].sum => 12

возвращается к multiplier.Поскольку [3, -4] содержит нечетное число отрицательных значений, множитель возвращает -12.

Answer 2

Я бы начал с написания метода рекурсивного умножения двух чисел:

def multiply_2(a, b)
  return 0 if a.zero?
  b + multiply_2(a - 1, b)
end

multiply_2(3, 4)
#=> 12

и построения на этом методе умножения трех чисел:

def multiply_3(a, b, c)
  multiply_2(multiply_2(a, b), c)
end

multiply_3(3, 4, 10)
#=> 3

и в конечном итоге его расширения дообрабатывать n чисел:

def multiply_n(a, b, *more)
  result = multiply_2(a, b)
  return result if more.empty?
  multiply_n(result, *more)
end

multiply_n(3, 4, 10, 2)
#=> 240

Обратите внимание, что вы можете столкнуться с SystemStackError для больших чисел.Этого можно избежать, сделав multiply_2 хвост-рекурсивным (оставив это как упражнение, это не сложно) и включив Ruby's :tailcall_optimization.

Answer 3

Я бы сказал, что идиоматическим способом в ruby ​​является использование итераторов вместо рекурсии / циклов

def multiplier(x, y, z)
  x.times.map do
    y.times.map do
      z
    end.reduce(:+)
  end.reduce(:+)
end

или

def multiplier(x, y, z)
  x.times.map do
    y.times.map do
      z
    end
  end.flatten.reduce(:+)
end

Или, если единственной операцией является inc

def multiplier(x, y, z)
  j = 0
  x.times do
    y.times do
      z.times do
        j += 1
      end
    end
  end
  j
end

вывод такой же

multiplier(3, 10, 4)
# 120

Для произвольного числа аргументов мы должны использовать рекурсию

def multiplier(*xs, res: 0)
  return res if xs.empty?
  xs[0].times do
    res += 1 if xs.size == 1
    res = multiplier(*xs.drop(1), res: res)
  end
  res
end

или

def multiplier(*xs, res: 0)
  head, *tail = xs
  head.to_i.times do
    res += 1 if tail.empty?
    res = multiplier(*tail, res: res)
  end
  res
end

Answer 4

Основываясь на рекурсивном ответе выше , вот более общая функция, которая может взять произвольно длинный список натуральных чисел и умножить их на рекурсивное сложение:

def multiplier(*integers, accum: 0)
  if integers.size == 1
    # We are finished!
    integers[0]
  elsif integers[-1].positive?
    # "Multiply" the last two integers, by recursive addition
    integers[-1] -= 1
    multiplier(*integers, accum: accum + integers[-2])
  else
    # The above multiplication is complete; set the last integer to its result
    integers[-2] = accum
    multiplier(*integers[0..-2])
  end
end

Answer 5

Основная проблема с вашим кодом - count - локальная переменная, она не сохраняется между рекурсивными вызовами.Также, если вы хотите избежать глобальных переменных, передайте переменную в качестве дополнительного параметра при вызове функции.В FP мы называем это аккумулятор :

def multiplier(x, y, z, j = 0)
  if z > 0
    multiplier(x, y, z - 1, j + y)
  elsif z.zero? # done with z, jump to x × (y × z)
    # z = -1 to explicitly mark we are done with z
    multiplier(x, j, -1, 0)
  elsif y.zero? # yay, we are all set, reducing is done!
    j
  else
    # still doing x × result step
    multiplier(x, y - 1, -1, j + x)
  end
end

multiplier(3, 10, 4)
#⇒ 120

Выше, конечно, не хватает необходимых проверок на достоверность ввода, но я уверен, что вы поняли.