考验各位数学和算法水平的问题(各位高手,帮帮忙啊) (100分)

想了一下，好像还有很多地方可以改善，例如用上最小值
如果某颗子树包含的乘机个数>k，那么它的最小值也可以
用于截支，截掉最大值比它小的子树。

上面写错了点，a0m应该是a(0,m-1)才对

Puma Wang,
看了你的答案，看不懂。不过我知道从数学上解决问题往往是最方便的，可惜我
数学不行。以后有什么数学的难题能不能想你请教？
Sincerely,
James Jin

高手高手高高手！
特别感谢JJams_King，刚刚看了你的算法，也想到最小值也可以用来截肢。然后上网来，
就看到你的补充信息。以后有问题还请JJams_King老兄多照顾一下哟。
不过我暂时不结束这个帖子，看看还有没有更好的算法。

很有意思：
在我上面的第一种估值方法下，我并没有是用矩阵的具体数值，而且
也没有规定各行的顺序。这就是说如果第i行可以截掉最小的k个数据
的话，那么换任意行到i，它也可以截掉t个最小的数据。那么实际上
每一行都可以截掉max(t)个数据，变成一个小一点矩阵。这个max(t)
只是随n,m,k变化。谁数学好的可以帮忙求一下max(t)和n,m,k的关系。

JJams_King ：
不敢不敢，我数学也很差的。:-D 。
回头我好好研究研究你的算法 。
上面我说的情况是这样的思想 ：
最简单的数组 ：
17 15
3 2
P1 := 17 *3 =51 。 51 开方得到 =~ 7.2 , 现在次大的数 ， 15 和 2。
是把17 换到 15 Or 3 换成 2 ？ 看 3*(17-15) =6 而 17 *(3-2) =17 .
所以换 17 。推想一个计算公式 ：Max( | 17 + 15 -7.2 | ,|3 + 2 -7.2|) 中的数
是 17 。当然这个 公式可能不够严密，可能更复杂一点。
要是 数组的行数是 N 那么这个7.2 的求法就是 ： 51 开 N 次方根 。
根据这个依据来搜索，应该能求出的。

经JJams_King和Puma Wang两位高人一讨论,我决定把标题都改了

to Puma Wang:
你只举了一个例子,能讲讲理论依据吗?

各位高人在说什么，我看不懂，（从小到大，数学没及过格）
我有一个想法，每行都从大到小排序，第一列的乘积值为最大p0，然后每行
都除以本行第一个数，这样可以在第二列Mx行找到一个最大的数
m(x,1)=(m(x,1)/m(x,0)),这样p0*m(x,1)为第二大，但是问题也来了，
按这种想法，同行中后面的数总小于前面的数，但不同行中的其它数就不一定了，
这就要把除去第一列的新矩阵进行排序。麻烦还在后头，到达某个值时就小于
第二列数的乘积了？重复以前？
我的脑袋要炸啦，高手们帮我看看，是不是我又短路了，会不会丢数？

谢谢

to x_home
所以这种办法不怎么可行，比较可行的是JJams_King的算法

这是图论中的最短路径问题拓展，有经典的解决办法。

没有理论依据的 是我自己瞎想的。
可能不行，好象没有办法证明。太复杂了，只有用穷举法。
也不想讨论这个问题了。
研究 JJams_King 的算法还是比较实用 。

>来自：szHans, 时间：2001-12-19 22:03:00, ID：798977
>这是图论中的最短路径问题拓展，有经典的解决办法。

能说来听听么？

哎，我真蠢
因为 (n-1)^m>=k (???)
得到
m=[ln(k)/ln(n-1)]

就相关内容推荐几本书
我去看看
谢谢[]

>来自：szHans, 时间：2001-12-19 22:03:00, ID：798977
>这是图论中的最短路径问题拓展，有经典的解决办法。
>能说来听听么？
我把算法课的笔记(咱们复印的老师的)打了上来，
不知道这个对你们有没有用，下个星期就要算法考试了，
我什么都没有看懂，5555555555555
好心的叔叔阿姨姐姐妹妹哥哥弟弟们，求你们也帮忙帮忙看一下http://www.delphibbs.com/delphibbs/dispq.asp?LID=797586
是个排序的算法题.......

求图的所有顶点对之间的最短路径
1.思想
V={V1,V2,...Vn}, Floyd算法用一个n*n的矩阵A来计算最短路径的长度
开始时， /C[i,j] i!=j且Vi列到Vj有弧
A[i,j]= 无穷 i!=j且Vi列到Vj无弧
/0 i=j
对A做n次循环， A1[i.j]=min{A[i,j],A[i,1]+A[1+j]}
Ak[i.j]=min{A(k-1)[i,j],A(k-1)[i,k]+A(k-1)[k+j]}
k=1,2,3,........n.
最后An[i,j]是Vi到Vj的最短路径的长。
2.正确性证明（小弟打字速度慢，所以免了，可惜考试要考:（）
3.算法
begin
/ 对A置初值； {O(n的平方)}
| 对路径矩阵P置初值；{无边相连，置无穷大，其余置0} O
| for k:=1 to ndo
| for i:=1 to ndo
O(n的| for j:=1 to ndo
三次| if A[i,k]+A[k,j]+A[k,j]
方) | then
begin
| A[i,j]:=A[i,k]+A[k,j];
| P[i,j]:=k
| end
/ end
4.例子：(下面是个有向图,方向是1->2,有9的那条弧；2->1,中间的弧
1->3左下的那条弧，3->2，右下的弧)
9
___________________
| 4 |
(1)----------------(2)
| |
-------(3)---------
5 3
0 9 5
所以 A0= 4 0 无穷 (注：以下都是矩阵，打不出长大括号)
无穷 3 0
0 0 0
P0= 0 0 无穷
无穷 0 0
0 9 5 0 0 0
A1= 4 0 9 P1= 0 0 1
无穷 3 0 无穷 0 0

0 9 5 0 0 0
A2= 4 0 9 P2= 0 0 1
7 3 0 2 0 0
0 8 5 0 3 0
A3= 4 0 9 P3= 0 0 1
7 3 0 2 0 0

程序已经做好了，谢谢各位