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