Новичок в Ruby - нужна помощь в оптимизации этого кода

В настоящее время в процессе изучения Ruby/программирования в целом, и я столкнулся с этим вопросом:

Ваша задача построить здание, которое будет состоять из n кубиков. Куб внизу будет иметь объем n^3, куб выше будет иметь объем (n-1)^3 и так далее до вершины, которая будет иметь объем 1^3. Вам дан общий объем m здания. Получив m, сможете ли вы найти количество n кубиков, которое вам нужно построить? Параметром функции findNb(find_nb, find-nb) будет целое число m, и вы должны вернуть целое число n, например n^3 + (n-1)^3 + ... + 1^3 = m, если такое n существует, или -1, если такого n* нет.

и вот моя попытка решить это:

def find_nb(m)
  (1..Float::INFINITY).each do |n|
    if (1..n).inject(0) {|sum, value| sum + value**3} == m
      return p n 
    else
      next
    end
  end
end

Кажется, это работает нормально с входными данными, которые, как я знаю, будут работать, например:

find_nb(4183059834009)
find_nb(135440716410000)
find_nb(40539911473216)

Области, в которых мне нужна помощь:

  • Я не знаю, как мне заставить его понять, когда нет значения n, которое удовлетворяло бы уравнению и, следовательно, выводило -1 для ввода, такого как

    find_nb(24723578342962)

  • Мы будем очень признательны за любые советы о том, как улучшить существующий код.


ruby optimization algorithm enumerable
person hellothere1    schedule 29.11.2016    source источник
comment
Ответы охватили большинство важных моментов, но я думаю, стоит повторить, что важно искать оптимизации в самой проблеме. Поскольку вы знаете, что сумма n^3 + (n - 1)^3 + ... равна m, вы знаете, что n^3 не может быть больше, чем m (граница, очевидно, более строгая, чем эта, но это простая отправная точка ). Из-за этого вы знаете, что нет смысла искать значения n выше кубического корня из m.   -  person Linuxios    schedule 29.11.2016
comment
en.wikipedia.org/wiki/Squared_triangular_number   -  person steenslag    schedule 29.11.2016

Ответы (2)


arrow_upward
7
arrow_downward

Подсказка 1: Вам не нужно уходить в бесконечность: после определенного n сумма будет больше, чем m, и быстро уйдет дальше.

Подсказка 2: если n найдено, функция никогда не достигнет своей последней строки из-за return.

Подсказка 3: next выполняется автоматически, если вы достигаете конца блока each.

Подсказка 4: Сумму кубов не нужно каждый раз пересчитывать с нуля. Вы не строите совершенно новое здание, вы просто кладете под него куб большего размера.

So...

def find_nb(m)
  n = 1
  sum = 1
  while sum < m
    n += 1
    sum += n**3
  end
  return sum == m ? n : -1
end

Редактировать: вот функциональная версия, но я думаю, что простой while выше все еще намного понятнее (и, вероятно, быстрее):

def find_nb(m)
  sum = 0
  sizes = 1.upto(Float::INFINITY)
    .lazy
    .map { |n| sum += n ** 3 }
    .take_while { |x| x <= m }
    .to_a
  sizes.last == m ? sizes.length : -1
end
person Amadan    schedule 29.11.2016
comment
Ударь меня мне это! Отличное объяснение, я просто добавлю, что вы можете вернуть -1 в любом случае, когда ваш sum превышает m. Также возврат необязателен в ruby, но здесь он более явный. - person Anthony; 29.11.2016
comment
@Anthony: вы можете вернуть -1 в любом случае, когда ваш sum превышает m: если вы проверите логику, это именно то, что я делаю. Этого не произойдет, пока продолжается while. - person Amadan; 29.11.2016
comment
Да, мы на одной странице, я просто имел в виду ваше письменное объяснение (отдельно от вашего кода), чтобы помочь вам понять ваш ответ. - person Anthony; 29.11.2016

arrow_upward
1
arrow_downward

Исправление/улучшение вашего кода

Чтобы исправить свой код, создайте еще одну ветку в if-statement, сообщающую вашей итерации, когда возвращать -1. next не требуется в итерации each (благодаря @Amadan за указание на это).

Обратите внимание, что лучше ничего не печатать из определения метода. Печатать при вызове метода. Улучшены отступы и интервалы. Также обратите внимание, что я определяю сумму кубов в переменной total:

def find_nb m
  (1..Float::INFINITY).each do |n|
    total = (1..n).inject(0) { |sum, value| sum + value**3 }
    if total == m
      return n 
    elsif total > m
      return -1
    end
  end
end

find_nb 4183059834009   #=> 2022
find_nb 135440716410000 #=> 4824
find_nb 40539911473216  #=> 3568
find_nb 37              #=> -1

Дальнейшие улучшения

Если вы хотите использовать бесконечный цикл, в Ruby есть loop. Используйте это с with_index вот так:

def find_nb m
  loop.with_index(1) do |_,n|
    t = (1..n).inject { |sum,i| sum + i**3 }
    if t == m
      return n            
    elsif t > m
      return -1        
    end
  end
end

find_nb 4183059834009   #=> 2022
find_nb 135440716410000 #=> 4824
find_nb 40539911473216  #=> 3568
find_nb 37              #=> -1
person Sagar Pandya    schedule 29.11.2016