我不太明白如何"将多维数组初始化为等于 1",因为这里的初始 for 循环似乎暗示了这一点。我还没有学会正确阅读伪代码,也不完全理解这个程序是如何工作的。
function countRoutes(m,n)
grid ← array[m + 1][n + 1]
for i = 0 to m do
grid[i][0] ← 1
end for
for j = 0 to n do
grid[0][j] ← 1
end for
for i = 1 to m do
for j = 1 to n do
grid[i][j] ← grid[i − 1][j] + grid[i][j − 1]
end for
end for
return grid[m][n]
end function
感谢您的帮助!
这并不难翻译。Ruby 使用=
而不是左箭头进行赋值,并使用def
而不是function
来定义子例程(它调用方法而不是函数),但仅此而已。 让我们来看看它。
function countRoutes(m,n)
这就是函数定义的开始。在 Ruby 中,我们改用一种方法,定义这样的事情的关键字是def
.在 Ruby 中,使用 snake_case 表示多字名称而不是 camelCase 也是惯例:
def count_routes(m, n)
现在要创建网格:
grid ← array[m + 1][n + 1]
Ruby 数组是动态的,因此通常不需要在创建时指定大小。但这也意味着您不会免费获得初始化或二维。所以我们在这里要做的是创建一个 m+1 数组的数组,每个数组都可以是空的(我们不需要指定子数组需要容纳 n+1 个项目)。 Ruby的Array构造函数有一种方法可以做到这一点:
grid = Array.new(m+1) do [] end
现在是初始化。Ruby 在技术上具有for
循环,但没有人使用它们。相反,我们使用迭代器方法。 对于计数循环,有一种关于整数的方法称为times
。但是伪代码从0
到m
(含)计数;times
也从0
开始,但只比调用少计数一个(这样当你调用3.times
时,循环确实执行了"三次",而不是四次)。在这种情况下,这意味着要获取伪代码的行为,我们需要在m+1
上调用times
而不是m
:
(m+1).times do |i|
grid[i][0] = 1
end
顺便说一句,我们也可以在原始数组创建中完成初始化的那部分:
grid = Array.new(m+1) do [1] end
无论如何,第二个循环(合并到原始创作中会更尴尬)的工作方式与第一个循环相同。Ruby 会很乐意扩展一个数组来分配给尚不存在的元素,所以我们没有初始化子数组的事实不是问题:
(n+1).times do |j|
grid[0][j] = 1
end
对于嵌套循环,伪代码不再从 0 开始计数,而是从 1 开始计数。从 1 到 m 的计数与从 0 到 m-1 计数的循环迭代次数相同,因此最简单的方法是让times
使用其自然值,但调整循环内赋值语句中的索引。也就是说,伪代码从 1 开始计数i
并引用i-1
和i
,Ruby 代码从 0 开始计数i
并改为引用i
和i+1
。
m.times do |i|
n.times do |j|
grid[i+1][j+1] = grid[i][j+1] + grid[i+1][j]
end
end
return
语句的工作方式相同,尽管在 Ruby 中您可以将其关闭:
return grid[m][n]
end
综上所述,你会得到这个:
def count_routes(m, n)
grid = Array.new(m+1) do [1] end
(n+1).times do |j|
grid[0][j] = 1
end
m.times do |i|
n.times do |j|
grid[i+1][j+1] = grid[i][j+1] + grid[i+1][j]
end
end
return grid[m][n]
end
表示法grid[i][j] ← something
表示将something
分配给发生在第i
行j
-th 位置的grid
元素。因此,这里的前两个循环建议将网格的第一列和第一行(相应地,第一个和第二个循环)的所有值设置为 1。