第 9 集 · A2 · 5 分钟
数学趣题 · 第9集 · Динамическое программирование
适合听读练习的俄语真实语料。片段原文开头：ну в смысле программа действий для путешественника. И другого способа попасть в Вуконда у него нет.
中俄字幕
ну в смысле программа действий для путешественника.
嗯，意思是旅行者的行动方案。
И другого способа попасть в Вуконда у него нет.
而且他没有其他办法进入武孔达。
а дальше всё ровно по вот этой формуле, но с некоторым обобщением, что если у меня
接下来都按这个公式计算，但稍作推广：如果我只有一条入路，
дорога входящая одна, то я просто по сути это число копирую.
那么我就直接复制这个数字。
То есть других способов всё равно нет.
也就是说，没有其他办法了。
Поэтому здесь у меня в этот город попасть один способ из города А.
因此，从A市到这个城市只有一种方式。
В этот одна входящая стрелка из города, в который один способ, один, да?
这里只有一条来自某个城市的入边，而到达那个城市也只有一种方式，对吧？
Сюда две входящие стрелки из городов, в каждый из которых по одной траектории.
这里有两条入边，分别来自两个城市，而到达每个城市都只有一条路径。
Значит, у меня сюда два способа попасть, да?
所以，到达这里共有两种方式，对吧？
Сюда две входящие стрелки, да?
这里也有两条入边，对吧？
Два плюс один, две траектории в этот, одна в этот, значит сюда три способа попасть.
2加1，两条路径到这个城市，一条路径到这个城市，因此共有三条路径到达这里。
сюда одна входящая стрелка из города, в который три траектории, значит здесь три.
这里有一条来自城市的入边，而该城市有三条路径，因此这里是三条。
Далее, у меня вот в этот город 1 плюс 2, сюда 3 способа попасть, сюда 3 способа
接下来，到这个城市的路径数是1加2，即有三条路径到达这里，也有三条路径到达这里。
попасть. смотрим сюда
到达这里。我们来看这里。
3 плюс 2 плюс 3 это получается.
3加2加3，结果是……
это получается 8 способов попасть вот в этот город.
结果是8种方式到达这个城市。
И сюда в итоге 8 плюс 3
最后，到这里是8加3……
это. 11 и еще плюс 3 это 14.
等于11，再加3等于14。
Значит я насчитал всего 14 способов.
所以我总共算出了14种方式。
ну отсюда вот можно заметить да что я очень старался посчитать да и вот этот вроде
嗯，从这里可以看出，我确实非常努力地进行了计算，而这个……
граф не очень большой а все- таки я обсчитался потому что количество траекторий
这个图不是很大，但我还是算错了，因为路径的数量
оказалось неверным минус балл на егэ да ну либо плюс балл если мы будем действовать
结果是错误的——高考扣一分；当然，如果我们这样操作，也可能加一分。
вот таким вот образом
就用这种方式。
давайте теперь сотрем этот граф дорог и посмотрим на.
现在，让我们擦掉这张道路图，来看一下。
нашего кузнечика.
我们的蚱蜢。
посмотрим на нашего кузнечика.
看看我们的蚱蜢。
Он, исполнитель Кузнечик, умеет перемещаться по числовой прямой.
它是一个名为“蚱蜢”的执行器，能在数轴上移动。
допустим у него есть только два возможных прыжка.
假设它只有两种可能的跳跃方式。
Это прыжок на единичку вперёд и прыжок на два вперёд.
即向前跳一个单位，或向前跳两个单位。
то есть вот такой и вот такой.
也就是这样的跳跃和这样的跳跃。
Меня интересует вопрос, сколько существует различных способов.
我感兴趣的问题是，有多少种不同的方式。
достичь точки n.
到达第n个点。
Задача на самом деле сводится к вот этой задачке про карту с городами, но её проще
这个问题实际上等价于之前那个关于城市地图的问题，但这个更容易
программировать.
编程实现。
На линии каждый город, который посещает кузнечик, а я буду в принципе называть
在直线上，蚱蜢访问的每个城市——我姑且把这些点称为城市，对吧？
городами эти точечки, да?
对吧？
Вот каждый город, в который он прыгает,
蚱蜢跳到的每个城市，
он обозначается просто числом.
仅用一个数字表示。
Мы сможем хранить все эти числа в массиве, вот эти k n-
我们可以将所有这些数字存储在一个数组中，也就是这k个n值，
ты, мы сможем хранить в массиве.
我们可以将它们存储在数组中。
Давайте посмотрим, вот в этот город я могу попасть только с такими прыжками, только
让我们看看，我只能通过这样的跳跃到达这个城市，只能
из предыдущего и из предпредыдущего.
从上一个城市和上上一个城市出发。
И отсюда я заключаю, что количество траекторий попадания в город n, kn,
由此我得出结论：到达第n个城市的路径数量kn
оно равно kn минус 1 плюс kn минус 2.
等于kn−1加kn−2。
рассмотрим крайний случай
考虑边界情况：
сколько способов попасть из города 1 в город 1 ну
从第1个城市到第1个城市有多少种方式？
Единственный способ не прыгать.
唯一的方式是不跳跃。
Соответственно k1 равно 1.
因此k1等于1。
Но очевидно, что нам этого не хватит для рекурсии, потому что нам нужно n минус 2, и
但显然，仅此不足以支持递归，因为我们需要kn−2，而
k2 нам некуда вычислить.
我们无法计算k2。
На самом деле есть два способа.
实际上有两种方法。
Можно отдельно руками сказать, что k2
可以手动单独说明k2
равно 1, а можно подойти иначе.
等于1，也可以换一种方式。
У меня есть город, на числовой прямой есть город 0.
我有一个城市，在数轴上，城市0位于此处。
Почему бы нет?
为什么不行呢？
И в этот город попасть кузнечик не может никак.
而蚱蜢根本无法到达这个城市。
Правда? У него ноль способов попасть.
真的吗？它到达这里的方法数为零。
в этот город. Поэтому я могу написать k0 равно нулю, и проверить, что эта формула
到达这个城市。因此我可以写k0等于零，并验证该公式
для k равного 2 как раз даст мне единичку.
当k等于2时，恰好给出结果1。
То есть в принципе можно в массиве я никак не смогу избавиться от нулевого члена.
也就是说，原则上我在数组中根本无法去掉第零项。
У меня же там k будет массив, я создам его.
我的 k 将是一个数组，我会创建它。
У меня там будет для n чисел обязательно число с индексом 0.
对于 n 个数，我那里必然包含索引为 0 的数。
И вот я просто туда 0 положу.
我就直接把 0 放进去。
Все, а начиная с двух я буду вычислять.
好了，从 2 开始我就进行计算。
Итак, давайте двигаться дальше.
那么，我们继续往下进行。
Давайте двигаться дальше.
我们继续往下进行。
Давайте запрограммируем что ли это дело.
我们来把这个程序编写出来吧。
Значит, вот моя.
这就是我的。
программа заготовка в которой я создал функцию number of trajectories и
程序框架，其中我创建了函数 number_of_trajectories，以及
grasshopper has соответствующее количество траекторий от единички до ну вот некой
grasshopper_has 对应从 1 到 n 的轨迹数量。
заданной с клавиатуры давайте сейчас она
从键盘输入的，现在就它
来源：Тимофей Хирьянов · CC BY 3.0