是否有内置函数或标准库函数大致相当于
def recur_until(start, step_fu, stop_predicate=lambda _: False):
current = start
while not stop_predicate(current):
yield current
current = step_fu(current)
要么
def recur_while(start, step_fu, predicate=lambda _: True):
current = start
while predicate(current):
yield current
current = step_fu(current)
甚至只是
def recur(start, step_fu):
current = start
while True:
yield current
current = step_fu(current)
在任何版本的Python？(当与之结合时,后者与其他两个一样好itertools.takewhile.)
像这样的生成器函数将允许迭代地计算某些递归定义的序列,即一阶递归关系.
虽然这些在需要时不太难实现,但我觉得像他们这样的东西应该是itertools或者可能的functools一部分,但如果是的话,我还没有在文档中发现它.
list(recur_until(2, lambda x: x**2 - 1, lambda x: x > 1e4))
# [2, 3, 8, 63, 3968]
还应该使用非数字元素:
list(recur_until('', lambda x: …最近我一直在研究递归; 如何写它,分析它等等我曾经想过复发和递归是一回事,但是最近的家庭作业和测验中的一些问题让我觉得有一些细微的差别,"复发"是通往描述递归程序或函数.
直到最近,当我意识到有一些叫做"主要定理"的东西用来为问题或程序写出"重现"时,这对我来说都是非常希腊的.我一直在阅读维基百科页面,但是,像往常一样,事情的措辞是这样的,我并不真正理解它在谈论什么.我通过实例了解得更多.
所以,有几个问题:让我们说你再次发生这种情况:
r(n)= 2*r(n-2)+ r(n-1);
r(1)= r(2)= 1
事实上,这是主定理的形式吗？如果是这样,用语言来说,它是什么意思？如果你试图根据这种重复尝试编写一个小程序或一个递归树,那会是什么样子？我是否应该尝试替换数字,查看模式,然后编写可以递归创建该模式的伪代码,或者,因为这可能是主定理的形式,是否有更简单的数学方法？
现在,假设有人要求您查找由上一次重复创建的程序执行的添加次数的重复次数T(n).我可以看到基本情况可能是T(1)= T(2)= 0,但我不知道从那里去哪里.
基本上,我问的是如何从给定的重复发生到代码,反之亦然.由于这看起来像主要定理,我想知道是否有一种直截了当的数学方法.
编辑:好的,我已经查看了我过去的一些作业,找到了另一个我被问到的例子,"找到复发",这是这个问题的一部分,我遇到了麻烦.
以最佳方式描述以下程序片段中的添加操作数的重复(当使用l == 1和r == n调用时)
int example(A, int l, int r) {
if (l == r)
return 2;
return (A[l] + example(A, l+1, r);
}
我有一个递归来解决.
f(m,n)=Sum[f[m - 1, n - 1 - i] + f[m - 3, n - 5 - i], {i, 2, n - 2*m + 2}] + f[m - 1, n - 3] + f[m - 3, n - 7]
f(0,n)=1, f(1,n)=n
但是,以下mma代码效率非常低
f[m_, n_] := Module[{},
If[m < 0, Return[0];];
If[m == 0, Return[1];];
If[m == 1, Return[n];];
Return[Sum[f[m - 1, n - 1 - i] + f[m - 3, n - 5 - i], {i, 2, n - 2*m …我知道如何对只调用一次的算法进行递归关系,但我不确定如何在一次出现时多次调用自身.
例如:
T(n) = T(n/2) + T(n/4) + T(n/8) + (n)
我有以下问题:
使用Big'O'表示法解决递归关系,简化答案:
f(0) = 2
f(n) = 6f(n-1)-5, n>0
我知道这是一阶非均匀递归关系并且已经解决了问题,但我似乎无法得到基本情况的正确输出(f(0)= 2).
问题必须在证明中使用几何级数论坛的总和.
这是我的答案 - 注意和(x = y,z)是大写西格玛符号的替代,其中x是初始化为y的求和的下界,z是求和的上界:
1. *change forumla:*
2. f(n) = 6^n.g(n)
3. => 6^n.g(n) = 6.6^(n-1) .g(n-1) -5
4. => g(n) = g(n-1)-5/6^n
5. => g(n) = sum(i=1, n)-5/6^i
6. => f(n) = 6^n.sum(i=1, n)-5/6^i
7. => *Evaluate the sum using geometric series forumla*
8. => sum(i = 1, n)-5/6^i = [sum(i = 1, n)a^i] -------> (a = -5/6)
9. => *sub a = -5/6 into geometric …我正在设计一个日历应用程序,其重现无,每日,每周,每月和每年.我的一个要求是"没有两个事件应该重叠" 我存储数据的表的名称
活动
领域
dtstart - 事件StartTime
dtend - 活动结束时间
考虑以下两种情况,
Event1 15th Aug 3:00 PM - 4:00 PM复发 - 无
Event2 15th Aug 2:00 PM - 5-00 PM复发 - 无
在上面的例子中,以下SQL Query的工作方式类似于charm
String sqlQuery ="SELECT*FROM Events WHERE dtstart AND dtend BETWEEN%d AND%d";
sqlQuery = String.format(sqlQuery,dtstart,dtend);
现在,考虑案例二.
事件1 8月15日下午3:00 - 下午4:00复发 - 每日至8月20日
Event2 18th Aug 2:00 PM - 5-00 PM复发 - 无
如果两个我的sqlQuery失败,因为它检查同一日期(8月18日)的事件开始和结束时间.就我而言,我的查询应显示8月15日的冲突时间.
请帮我查询SQL查询,以便检查重复的事件.
在事件表中,我存储开始时间,结束时间,上次出现日期和出现类型.
数据库方案如下
表名:事件
标题 | dtstart | dtend | 重复类型 | 最后一次出现
我正在寻找这个java方法的递推公式
void printInorder(Node<T> v) {
if(v != null) {
printInorder(v.getLeft());
System.out.println(v.getData());
printInorder(v.getRight());
}
}
一些标准:
我必须找到与depth h树的相关的递推公式n knots,并且作为额外的奖励,我需要从那里推断出导致O(n)的显式公式.
现在,这就是我得到的:
d = depth of the tree
c = constant runtime for execution of the method itself
d = 1: T(n) = c
d = 3: T(n) = T(d=1) + T(d=2) + T(d=3) + c
我用例子d = 3来为自己澄清事情,我很难进一步打破这个问题.我的假设是否正确？
编辑:下一次尝试的事情
[x] = { x in real numbers : max([x]) <= x }, [x] rounded down to next …我试图找到重现的时间复杂性:
T(n)= 2T(n 1/2)+ log n
我非常接近解决方案,但是,我遇到了障碍.我需要解决:
n (1/2 k) = 1
为了简化我的替换模式.我不是在寻找复发的答案,只是一个解决方案k.
我想了解如何达到下面递归关系的复杂性.
T(n) = T(n-1) + T(n-2) + C
鉴于T(1) = C和T(2) = 2C;
通常对于像T(n) = 2T(n/2) + C(给定T(1)= C)的方程式,我使用以下方法.
T(n) = 2T(n/2) + C
=> T(n) = 4T(n/4) + 3C
=> T(n) = 8T(n/8) + 7C
=> ...
=> T(n) = 2^k T (n/2^k) + (2^k - 1) c
现在什么时候n/2^k = 1 => K = log (n)(到基地2)
T(n) = n T(1) + (n-1)C
= (2n -1) C
= O(n)
但是,我无法针对我所遇到的问题提出类似的方法.如果我的方法不正确,请纠正我.
algorithm complexity-theory recurrence time-complexity asymptotic-complexity
我正在实施用于抄书问题的动态编程解决方案。解决方案的想法来自here和here。
问题陈述：
在书籍印刷发明之前，复印一本书非常困难。所有的内容都必须由所谓的抄写员手工重写。抄写员得到了一本书，几个月后他完成了副本。最著名的抄写员之一生活在 15 世纪，他的名字是 Xaverius Endricus Remius Ontius Xendrianus（施乐）。总之，工作很烦很无聊。而加快速度的唯一方法就是雇佣更多的抄写员。
曾几何时，有一个剧团想演著名的古董悲剧。这些剧本的剧本被分成了很多书，演员当然需要更多的副本。因此，他们聘请了许多抄写员来复印这些书。假设您有 m 本书（编号为 1、2、....、m），它们的页数可能不同（p_1、p_2、...、p_m），并且您想为每本书制作一份副本。你的任务是将这些书分给 k 个抄写员，k <= m。每本书只能分配给一个抄写员，并且每个抄写员都必须获得连续的书籍序列。这意味着，存在一个递增的数字序列 0 = b_0 < b_1 < b_2, ... < b_{k-1} <= b_k = m$ 使得第 i 个抄写员得到一个数字介于 bi- 1+1 和双。复印所有书籍所需的时间由分配最多工作的抄写员决定。因此，我们的目标是尽量减少分配给单个抄写员的最大页面数。您的任务是找到最佳分配。
我能够获得迭代描述的问题的最佳解决方案，但无法使用它来找到问题所需的解决方案，即：
Sample input:
2
9 3
100 200 300 400 500 600 700 800 900
5 4
100 100 100 100 100
Sample Output
100 200 300 400 500 / 600 700 / 800 900
100 / 100 …