Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Ruby: Общие вопросы > Разложение числа на слагаемые

Автор: PavAks 23.1.2008, 00:13

Всем привет! Помогите, плз, с идеей. Я для изучения ruby накачал в нете разных заданий, и пытаюсь их выполнить. Изучаю его недолго smile

. Поэтому извинете за глупый вопрос, но я с ним уже неделю бьюсь smile

. Вот текст задачи:

Написать метод partitions_p(n), которые получают целое положительное число n и возвращают все разложения числа n на сумму натуральных слагаемых (т.е. возвращают массивы слагаемых). В разложениях слагаемые идут по убыванию.
Пример: [[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]

з.ы. подскажите, пожалуйста, с какого боку к этому подходить. Или, может, есть какая функция, которая делает такое разложение? Или делать все циклами?

Автор: setq 23.1.2008, 18:16

Если такая функция уже есть, то задача становится немного бессмысленной. Циклы - хорошая идея, почему нет?)

Автор: PavAks 23.1.2008, 22:07

Просто я не могу себе представить как это делать циклами smile

Автор: PavAks 3.2.2008, 01:46

Что-то начало получаться, хотя не все разложения выдает smile

[[5], [4, 1], [3, 2, 1], [3, 2], [3, 1, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]
-----------------------------------------------------------------------
[[10], [9, 1], [8, 2], [7, 3], [6, 4], [5, 5], [5, 4, 1], [5, 3, 2], [5, 2, 2, 1], [5, 1, 1, 1, 1, 1], [4, 4, 2], [4, 4, 1, 1], [4, 3, 3], [4, 2, 2, 2], [4, 1, 1, 1, 1, 1, 1], [3, 3, 3, 1], [3, 3, 2, 2], [3, 2, 2, 2, 1], [3, 1, 1, 1, 1, 1, 1, 1], [2, 2, 2, 2, 2], [2, 2, 2, 2, 1, 1], [2, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]

Код


number = gets.chomp.to_i
i = number
j = 0
count = 0
arr1 = []
arr2 = []
arr3 = []
while i != number/2
i -= 1
j += 1
arr2.push(i, j)
arr2 = arr2.sort{|x, y| y<=>x}
arr1.push(arr2)
tmp = arr2[0]
arr2 = Array.new
while count != number/2
count += 1
tmp1 = tmp % count
tmp2 = tmp/count
tmp2.times do arr3.push(count) end
arr3.push(j)
if tmp1 != 0
arr3.push(tmp1)
end
arr3 = arr3.sort{|x, y| y<=>x }
arr1.push(arr3)
arr3 = Array.new
end

count = 0
end

p arr1.sort{|x, y| y<=>x }.uniq

На числах больше 10 не очень хорошо работает :(

Автор: fixxer 5.2.2008, 23:14

как то сложно у Вас получилось. У меня так

Код


def items(b)
    result = [[b]]
    (1..(b - 1)).each do |i|
        items(b - i).each do |j| 
            result.push(([i] + j).sort) 
        end
    end
    return result.sort
end

p items(5).uniq.reverse

Изучаю ruby совсем недавно. Уверен, что можно сделать еще короче.

Автор: fixxer 6.2.2008, 13:26

удалось сократить до

Код


def items(b)
  return (1..(b - 1)).inject([[b]]) {|s, i| s + items(b - i).collect{|j| ([i] + j).sort}}.sort
end

p items(5).uniq.reverse

ЗЫ. Админы, а когда будет подсветка для ruby?

Автор: PavAks 9.2.2008, 15:04

ну ты даешь... класс... smile

Автор: source777 9.2.2008, 16:47

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

Код


def items(b)
  return (1..b/2).inject([[b]]) {|s, i| s + items(b - i).collect{|j| ([i] + j).sort.reverse}}.uniq.sort.reverse
end

p items(5) # => [[5], [4, 1], [3, 2], [3, 1, 1], [2, 2, 1], [2, 1, 1, 1], [1, 1, 1, 1, 1]]