Ruby递归算法问题

Question

研究该算法：

Given a rows x cols screen and a sentence represented by a list of non-empty words, find how many times the given sentence can be fitted on the screen.

Note:

A word cannot be split into two lines.
The order of words in the sentence must remain unchanged.
Two consecutive words in a line must be separated by a single space.
Total words in the sentence won't exceed 100.
Length of each word is greater than 0 and won't exceed 10.
1 ≤ rows, cols ≤ 20,000.
Example 1:

Input:
rows = 2, cols = 8, sentence = ["hello", "world"]

Output: 
1

Explanation:
hello---
world---

The character '-' signifies an empty space on the screen.
Example 2:

Input:
rows = 3, cols = 6, sentence = ["a", "bcd", "e"]

Output: 
2

Explanation:
a-bcd- 
e-a---
bcd-e-

The character '-' signifies an empty space on the screen.
Example 3:

Input:
rows = 4, cols = 5, sentence = ["I", "had", "apple", "pie"]

Output: 
1

Explanation:
I-had
apple
pie-I
had--

The character '-' signifies an empty space on the screen.

这是我的密码：

def words_typing(sentence, rows, cols)
   count_words(sentence, rows, cols, cols, 0, 0)
end

def count_words(sentence, rows, cols, remaining_space, row_num, word_idx)
    return 0 if row_num == rows #keep going until out of rows, ends the recursion
    word_idx = 0 if word_idx == sentence.length  #reset the word back to the first

    if remaining_space >= sentence[word_idx].length
        if remaining_space == sentence[word_idx].length
            return 1 + count_words(sentence, rows, cols, remaining_space - sentence[word_idx].length, row_num, word_idx + 1 )
        else #greater than 1
            return 1 + count_words(sentence, rows, cols, remaining_space - sentence[word_idx].length - 1, row_num, word_idx + 1 )
        end
    else #move to a new line, reset remaining space
        return count_words(sentence, rows, cols, cols, row_num+1, word_idx)
    end 
end

代码的工作原理如下。word_idx是句子数组中单词的索引。剩余空间最初是列的数量。只要有足够的空间放置一个单词，我就在同一行上返回1+函数调用，并保留下一个单词和剩余的空格。如果剩余的空格>= 1+字长，那么我将考虑在两个连续单词之间有一个空格(这就是为什么我有额外的条件)。

如果word_idx比句子数组长，它就会按照它应该的方式将其重置为零。递归函数将继续运行，直到row_num现在大于问题中提供给我们的行数。

然而，这段代码不起作用。我的输出通常比正确的答案要大，但从概念上看，一切似乎都是对的。有人看到我的方法有什么问题吗？

Answer 1

这是因为你在数单词而不是句子。

def words_typing(sentence, rows, cols)
   count_words(sentence, rows, cols, cols, 0, 0, 0)
end

def count_words(sentence, rows, cols, remaining_space, row_num, word_idx, number_of_sentences)
    nos = number_of_sentences
    return nos if row_num == rows #keep going until out of rows, ends the recursion

    if word_idx == sentence.length  #reset the word back to the first
    word_idx = 0 
    nos = number_of_sentences+1
    end
    if remaining_space >= sentence[word_idx].length

        if remaining_space == sentence[word_idx].length

            return count_words(sentence, rows, cols, remaining_space - sentence[word_idx].length, row_num, word_idx + 1, nos )
        else #greater than 1

            return count_words(sentence, rows, cols, remaining_space - sentence[word_idx].length - 1, row_num, word_idx + 1 , nos)
        end
    else #move to a new line, reset remaining space

        return count_words(sentence, rows, cols, cols, row_num+1, word_idx, nos)
    end 
end


rows = 3
 cols = 6
 sentence = ["a", "bcd", "e"]
words_typing(sentence, rows, cols)
rows = 4; cols = 5; sentence = ["I", "had", "apple", "pie"]
words_typing(sentence, rows, cols)

我引入了一个新的变量/参数(最后一个)，它包含了许多句子(从0开始)。当word_idx == sentence.length的意思是，新的句子适合在剩余的空间，因此nos = number_of_sentences+1。

最后我们返回nos (句数)。

Answer 2

由于您的问题已经确定，我想建议另一种方法来编写该方法。

def sentences_per_page(rows, cols, sentence)
  nbr_sentences = 0
  last_word_index = sentence.size-1
  loopy = sentence.each_with_index.cycle
  word, idx = loopy.next
  rows.times do
    cols_left = cols
    while cols_left >= word.size
      cols_left -= (word.size + 1)
      nbr_sentences += 1 if idx == last_word_index
      word, idx = loopy.next
    end
  end
  nbr_sentences
end

rows = 4
cols = 5
sentence = ["I", "had", "apple", "pie"]
puts                    "    rows      sentences"
(1..12).each { |n| puts "     %d           %d" %
  [n, sentences_per_page(n, cols, sentence)] }
rows      sentences
  1           0
  2           0
  3           1
  4           1
  5           1
  6           2
  7           2
  8           2
  9           3
 10           3
 11           3
 12           4

我使用了Array#cycle方法。对于上面定义的sentence，

loopy = sentence.each_with_index.cycle
  #=> #<Enumerator: #<Enumerator: ["I", "had", "apple", "pie"]:each_with_index>:cycle> 
loopy.first 10
  #=> [["I", 0], ["had", 1], ["apple", 2], ["pie", 3],
  #    ["I", 0], ["had", 1], ["apple", 2], ["pie", 3],
  #    ["I", 0], ["had", 1]]