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

B

beyondeast

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-12-18

• #1

有一个m行n列的矩阵，从每行中取一个数，将这m个数相乘，得到P
如何取得从最大的P到第k大的P这k个序列？
注意：不能将每个P都算出来，然后再排序。

 

P

Puma Wang

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-12-18

• #2

现在开始想。
回家再来答 。

 

Y

yexiaofeng

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-12-18

• #3

先对每行的数排序，第一列的乘积即为最大的P
然后将第一列中最小的数换成第二列中最大的数（如果两数不相等的话），将第一列最小数
置0。然后执行上一句话的操作就得到Pk-1，依此类推。

 

B

beyondeast

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-12-18

• #4

to Puma Wang:
多谢关照
to yexiaofeng:
请注意：不同行的数字不能互相交换，也就是说，第i行的数字不能拿到第j行去用。

 

蒋

蒋劲刚

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-12-18

• #5

对一行中的数是否可以多次取出？
9 8 7
6 5 4
3 2 1
最大是 9*6*3 ，当取第二次时，第一行的9 是否还可以取出？

 

B

beyondeast

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-12-18

• #6

to 蒋劲刚
可以.
因此一共有n^m个序列

 

Z

zyy04

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-12-18

• #7

注：假设均为正数！！！
1。先排序使得每行第一个数最大，第一列的乘积即为最大的P
2。排序使得每行第二个数为次大
3。计算每行第一个数/第二个数的值，假设i行的该值最小
4。将i行左移一个，此时第一列的乘积即为目前最大的P'
5。排序使得第i行的第二个数为i行次大
6。goto 3

 

蒋

蒋劲刚

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-12-18

• #8

数值是整数吗？

 

B

beyondeast

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-12-18

• #9

to 蒋劲刚
都是正数，但不一定是整数

 

B

beyondeast

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-12-18

• #10

to zyy04:
请注意，矩阵中的数可以重复取出，一共有n^m个序列。
实际上就是要求这n^m个序列的连乘积中由最大到第k大的序列。

 

蒋

蒋劲刚

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-12-18

• #11

这好象是一个np困难问题，我再想想

 

B

beyondeast

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-12-18

• #12

to 蒋劲刚
多谢多谢! 费神了..

 

L

lnboy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-12-18

• #13

好象以前看见过这个题，可惜没有认真听老师讲课
等下个星期算法考试过了再说吧。：）[]
翻翻笔记，或许有办法。

 

J

JJams_King

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-12-18

• #14

请把问题翻过来想，求最小的n^m-k个数组成的序列
然后用生成树，估值，剪支
不难

 

P

Puma Wang

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-12-18

• #15

我来说说 ：
假设 第 K 行的最大值表示为 ：r(K,1) 次大为 :r(K,2).... (k 为 1......N) .
诚然 ：r(1,1) * r(2,1) *.... * r(n,1) =P1 . 第一组。
现在求第二组 ：替换 ： r(1,1) 到 r(n,1) 中的其中一个的 r(k,1) 为 r(k,2) .
设 ： sqrtN 为 P1 的 N 次方根。
依据是 ：Max (r(k,1) + r(k,2) - SqrtN ) (K 为 1..N )
第二个到 n 个基本上能找到 。
这里也有不太严密。可能需要完善的地方就是这个 找 r(k,1)+r(k,2) -SqrtN .
但是有一点是肯定的是 和这个 sqrtN 是离不开的 。
根据 待求的次大值集合里的元素和它的差 是找 P2,P3,P4 .. 的关键。
这里只是从数学方面提出来，不知道我想的对不对，希望大家斧正。

 

B

beyondeast

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-12-18

• #16

to JJams_King,
能讲讲详细过程吗?多谢了, 就怕m和n足够大时，最小的几个值也求不到

 

M

MrMengyi

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-12-18

• #17

listen
比较复杂

 

Z

zyy04

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-12-18

• #18

to beyondeast:
sorry,我理解错了

 

J

JJams_King

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-12-18

• #19

1。对于n*m的矩阵，把每行都按小到大（安大到小也可以）排列,
的到新的矩阵
+- -+
| a00 a01 ... a0m |
A0 = | a10 a11 ... a1m |
| ... ... ... ... |
| an0 an1 ... anm |
+- -+
2。生成树的原则是根为A0，从第一行开始，生成树：
(1,A0)
----------+----------
| | ... |
(a00,A1) (a01,A1) ... (a0m,A1)
----------+------------------
| | ... |
(a00*a10,A1) (a01*a11,A1) ... (a0m*a1m,A1)
其中
+- -+
| ai0 ai1 ... aim |
Ai = | ... ... ... ... |
| an0 an1 ... anm |
+- -+
3。估值
比较(a00,A1) (a01,A1)
因为a00<a01，假设max=MAX(A1)表示矩阵A1中选出每行最大的数的乘积，
那么以a00为根的子树里包含的乘积都将比a00*max小。
又有a00*max<a01*max，这表明a00子树的所有乘积，至少有
a01*max,a02*max,...,a0m*max这(m-1)个数比它们大。把这个
数作为子树的估计值。
4。截支
按照这种方法，我们可以给每个子树估值，如果比某颗子树大的
乘积数大于k，则该子树可以被截去。

 

J

JJams_King

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2001-12-18

• #20

其实更好的估值方法是行从大到小排列
对A0到An-1求最大值。其中，
Ai=[a(k,j)] k=0,1,...,i;
j=0,1,...,m-1
MAX(Ai)定义为Ai中每行最大值的乘积

[哎，打字真累，希望能看懂]