小编xan*_*xan的帖子

我想知道是否存在任何继续证明算法正确性的规则/方案？例如,我们在自然数上定义了一个函数$ F $,定义如下:

function F(n,k)
begin
  if k=0 then return 1
  else if (n mod 2 = 0) and (k mod 2 = 1) then return 0
  else return F(n div 2, k div 2);
end;

其中$ n\\ text {div}\2 =\left\lfloor\frac {n} {2}\right\rfloor $

任务是证明$ F(n,k)=\begin {cases} 1\Leftrightarrow {n\choose k}\\ text {mod}\2 = 1\0\text {otherwise}\end {cases} $

它看起来并不复杂(我错了吗？),但我不知道这种证据应该如何构建.我非常感谢你的帮助.

我必须在额外的作业下设计算法.该算法必须通过删除重复子树并将所有这些连接重定向到一个左原始子树来将二进制树转换为DAG来压缩二进制树.例如,我有一棵树(我给节点预订):

1 2 1 3 2 1 3

该算法必须删除1(根)的右连接(右子树,意思是2 1 3)并将其重定向到左连接(因为这些子节是相同的,左边是先预订,所以我们只留下左边)

我看待它的方式:我正在通过树预订.对于当前节点'w',我开始递归,必须检测(如果存在)原始子树等于具有根'w'的子树.如果我找到相同的子树(并且我做了必须做的事情),或者当我在找到相同的子树递归时得到"w"时,我正在削减递归.当然,我预测一些小的改进,例如只比较具有相同节点数的子树.

如果我没有错,它会给出复杂度O(n ^ 2),其中n是给定二叉树的节点数.有没有机会更快地完成它(我认为是).线性算法是否可行？

可惜我的算法最终有复杂度O(n ^ 3).一段时间后,你对散列的回答对我来说可能会非常有用,届时我会知道更多...现在对我来说太难了..

最后一个问题.有没有机会使用基本技术(不是散列)在O(n ^ 2)中做到这一点？

当我发现无法处理的问题时,我正在学习测试:

设计一个处理(关闭)间隔的数据结构,它将提供三种操作:

插入(x,y) - 添加区间[x,y]

删除(x,y) - 删除区间[x,y]

Count(x,y) - 计算区间[x,y]内纯粹包含的区间数

x,y是从1到n的整数.所有操作最多可以占用O((log n)²)

有人可以帮忙吗？

我对理解动态编程有困难,所以我决定解决一些问题.我知道基本的动态算法,如最长的常见子序列,背包问题,但我知道它们因为我读过它们,但我不能自己想出一些东西:-(

例如,我们有自然数的子序列.我们可以使用加号或减号的每个数字.最后,我们取这个总和的绝对值.对于每个子序列,找到尽可能低的结果.

in1:10 3 5 4; out1:2

in2:4 11 5 5 5; out2:0

in3:10 50 60 65 90 100; out3:5

第3次解释:5 = | 10 + 50 + 60 + 65-90-100 |

更糟糕的是我的朋友告诉我这是简单的背包问题,但我在这里看不到任何背包.动态编程有些困难,还是只有我有很大问题？

我有一个不寻常的(我认为)问题.对于给定数量F_n(我不知道n的值),我必须找到数字F_0,F_1,使得F_ {n} = F_ {n-1} + F_ {n-2}.另外的困难是这个序列应该尽可能长(F_n的值n应该是最高的),如果存在多个解决方案,我必须用最小的F_0.总之,我必须生成我自己的"斐波那契"序列.一些例子:

in:F_n = 10; out:F_0 = 0; F_1 = 2;

in:F_n = 17; out:F_0 = 1; F_1 = 5;

in:F_n = 4181; out:F_0 = 0; F_1 = 1;

我观察到的每个序列("Fibonacci规则")F_n有:

F_n = Fib_n*F_1 + Fib_ {n-1}*F_0

其中Fib_n是第n个斐波那契数.特别是斐波纳契数列确实如此.但我不知道这种观察是否值得.我们不知道n,我们的任务是找到F_1,F_0因此我认为我们什么也没有获得.有任何想法吗？

对于给定数n(我们知道n = p ^ a*q ^ b,对于一些素数p,q和一些整数a,b)和给定数量φ(n)(http://en.wikipedia. org/wiki/Euler%27s_totient_function)找到p,q,a和b.

捕获的是n,并且φ(n)具有大约200个数字,因此算法必须非常快.这似乎是非常难的问题,我完全不知道如何使用φ(n).

怎么解决这个问题？

我有一个布尔公式:(x_ {1}或x_ {2})和(x_ {3}或x_ {4})和.....和(x_ {2r-1}或x_ {2r}),其中x_ {i}属于集合:{p_ {1},p_ {2},... p_ {99},~p_ {1},~p_ {2},... ~p_ {99}}我必须确定给定公式的x_ {i}的某些值是否为真.

我知道这一般在计算上很困难.但是,有什么特别快的方法可以解决这个特殊问题吗？到目前为止,我已经尝试了回溯 - 这是在递归中我对每个可能的值(0或1所以不是很多)代入每个可能的变量,并且每个尚未获得值的变量都是非常正确的.在我深入了解递归之前,我会查看公式(即使并非所有变量都有值),如果它是假的,我也不会更深入.但它太慢了.有任何想法吗？我非常感谢你的帮助.

我正在从算法和数据结构(我在一个月内完成)中学习考试,而我无法找到解决此问题的有效算法:

我们在线上得到1 <= n <= 5000点.每个点具有不同的自然坐标0 <= d <= 10 ^ 6并且(不一定不同)自然点时间 0 <= t <= 10 ^ 9秒.我们可以从任何一点开始,每一秒都将当前坐标改变+/- 1.问题是以这样的顺序访问所有点,以便在经过他的点时间之前访问每个点.找到这次旅行的最短总时间(以秒为单位),或者说这是不可能的.

例如,给出5个点(坐标,点时间):

(1,3),(3,1),(5,6),(8,19),(10,15),有可能,当我们去旅行时访问坐标:3 - > 1 - > 5 - > 8 - > 10,我们得到最小总时间,等于:11.

我的第一个想法是按字典顺序对所有点进行排序:(点 - 时,坐标),然后按此顺序访问它们.当然,当在第i个点和第(i + 1)个点之间存在点时,我们可以在访问(第i + 1)点之前访问它们.但遗憾的是,尽管实施起来很困难,但为什么这种贪婪的方法应该有效仍然没有争论.也许我想要解决得太快？n很小,所以,O(n ^ 2)应该没问题,我想.

我找到了其他输入的例子,想想也许它会帮助我找到解决方案.但现在我只看到我必须找到所有可能的$ n!$排列的一个排列.

输入示例:

点(也分别由坐标,点时间给出):( 0,4),(1,2),(4,5):令人惊讶的是(我认为)我们必须访问它们:0 - > 1 - > 4,因为任何不同的顺序都不满足问题文本中最后一句之前的条件.

要点:(0,7),(1,2),(2,1),(3,4),(4,11),唯一有趣的方法是:2 - > 1 - > 3 - > 0 - > 4,这需要我们10秒.

有人可以帮忙吗？

我发现了一个有趣的算法问题.我们给出了一个二叉树,它在叶子之外的每个顶点都有0值.在叶子中我们有两个选择:

1. 值未知,但我们知道它是一个自然数> = 1

2. 值已知,它是一个自然数> = 1

问题是决定是否可以在叶子中设置每个未知值,使得给定树的每个子树在其左右子树中的顶点中具有相同的值总和.

例如:

树1:

      0
     / \
    0   ?
   / \
  0   5
 / \
?   ?

答案是否定的 - 考虑到每个问号都必须是自然数,这当然是不可能的

tree2:

        0
     /     \
    0      0
   / \    / \
  0   10 ?   ?
 / \
5   ?

答案是肯定的 - 我们在每个问号中分别设置:5,10,10.

到目前为止,我只提出了一个明显的算法 - 我们创建了线性方程组,并检查它是否有自然数的解.但我认为对于大树来说它可能会非常缓慢,它应该是解决它的更好方法.有人可以帮忙吗？我会很感激.

我正在学习测试,我无法解决这个问题:

我们给出一组n <1000个点和一个整数d.任务是创建两个不相交的点集A_1和A_2(该集合给出n个点的集合),使得来自A_i(对于i = 1或2)的每对点之间的距离(欧几里得)较小或者等于d.如果不可能,请打印-1.

例如,输入:

d = 3,分:

(5,3),(1,1),(4,2),(1,3),(5,2),(2,3),(5,1)

我们可以创建:

A_1 = {(2,3),(1,3),(1,1)}

A_2 = {(5,3),(4,2),(5,2),(5,1)}

因为来自A_i的每对点(对于i = 1或2)足够接近.

我真的想知道如何解决它,但不知道.由于n很小,算法甚至可以是O(n ^ 2 log n),但我不知道如何启动.我在想,也许从计算每对点之间的距离开始,然后取两个最大距离点并将它们放入不同的点(如果它们的距离大于d).然后对剩下的对重复此步骤,但问题是如何决定合法地放置下一个点的位置.任何人都可以帮助这个算法吗？