daniel 匆匆过客

IT博客 首页 新随笔 联系 聚合 管理
  3 Posts :: 0 Stories :: 7 Comments :: 0 Trackbacks

2006年8月3日 #

在一个集合S中寻找最大的C使A+B=C且A,B,C均在集合当中
解答(原创)
1,将集合S中的数排序X1<=X2<=X3.............Xn;
2,for(i=n;i>0;i--)
{
for(j=0,k=i-1;k>j;)
{
if(Xj+Xk>Xi)
{
      k--;
      cotinue;
}
if(Xj+Xk<Xi)
{
      j++;
      contiue;
}
A=Xj;
B=Xk;
C=Xi;
break;
}
例子:
1,4,7,10,11,13,15,18,34
34:1-18,4-18........15-18
18:1-15,4-15,4-13,7-13,7-11
结果:
A=7;B=11,C=18;
posted @ 2006-08-03 14:33 danielcheng 阅读(1924) | 评论 (7)编辑 收藏

题目:N个人排成一圈,指定第一个人,去除他,然后跳着一人去除第3人,以次类推,最后
的那一人获胜。给定这N个人和第一个人的位置,你该如何选取位置才会获胜。
解答(见concrete math):
m=3N;
while(m>N)
{
m=m-N+(m-N-1)/2;
}
result=m;
例子:1   2   3   4   5   6   7   8
            9   10      11   12    13 14
                  15      16           17 18
                              19          20                
                              21           22
                                             23
                                             24
posted @ 2006-08-03 14:16 danielcheng 阅读(717) | 评论 (0)编辑 收藏

解答:(参考introduction to algrithms)
1,从任意节点s出发用深度优先遍历(或宽度优先遍历)遍历该图,若生成多棵树,则不是连通的。
2,反向图中所有的边。
3,   从节点s出发用深度优先遍历(或宽度优先遍历)遍历该图,若生成多棵树,则不是连通的,否则是强连通图。
理由:1保证了从s可以到达所有的节点。2,3说明从任意节点都可以到达s。任意节点i,j都是连通的因为
i~s,s~j。

posted @ 2006-08-03 14:05 danielcheng 阅读(1300) | 评论 (0)编辑 收藏

仅列出标题