论坛 › 编程擂台 › 三重内积的最小值

王守恩 发表于 2025-9-20 12:56:59

northwolves 发表于 2025-9-19 21:04
01        2        3        4        5        6        7        8        09        10
10        6        4        8        5        3        7        2        01        09
09        7        8        3        4        5        2        6        10        01

鹦鹉学舌,没学好。 离正确答案总是差1。

a(11)=1305,1*11*10 + 2*7*9 + 3*5*8 + 4*6*5 + 5*9*3 + 6*3*6 + 7*4*4 + 8*8*2 + 9*2*7 + 10*1*11 + 11*10*1=1305, 正确答案=1304。
01,2,3,4,5,6,7,8,9,10,11,
11,7,5,6,9,3,4,8,2,01,10,
10,9,8,5,3,6,4,2,7,11,01,

a(12)=1782,1*12*11 + 2*8*10 + 3*6*9 + 4*7*5 + 5*10*3 + 6*4*7 + 7*5*4 + 8*9*2 + 9*3*6 + 10*2*8 + 11*1*12 + 12*11*1=1782, 正确答案=1781。
01,02,3,4,05,6,7,8,9,10,11,12,
12,08,6,7,10,4,5,9,3,02,01,11,
11,10,9,5,03,7,4,2,6,08,12,01,

a(13)=2378,1*13*12 + 2*8*11 + 3*7*10 + 4*11*4 + 5*5*8 + 6*6*5 + 7*9*3 + 8*4*6 + 9*3*7 + 10*10*2 + 11*2*9 + 12*1*13 + 13*12*1=2378, 正确答案=2377。
01,02,03,04,5,6,7,8,9,10,11,12,13,
13,08,07,11,5,6,9,4,3,10,02,01,12,
12,11,10,04,8,5,3,6,7,02,09,13,01,

a(14)=3112,1*14*13 + 2*9*12 + 3*7*11 + 4*8*7 + 5*12*4 + 6*5*8 + 7*6*5 + 8*10*3 + 9*3*9 + 10*4*6 + 11*11*2 + 12*2*10 + 13*1*14 + 14*13*1] =3112, 正确答案=3111。
01,02,03,4,05,6,7,08,9,10,11,12,13,14,
14,09,07,8,12,5,6,10,3,04,11,02,01,13,
13,12,11,7,04,8,5,03,9,06,02,10,14,01,

王守恩 发表于 2025-9-20 14:16:12

有个"更狠"的"角色",可以冲到a(10000)。——A070893。——可惜答案不太"准"。—— 还不如 mathe —— 6#的公式。

1, 6, 19, 46, 94, 172, 290, 460, 695, 1010, 1421, 1946, 2604, 3416, 4404, 5592, 7005, 8670, 10615, 12870, 15466, 18436, 21814, 25636, 29939, 34762, 40145, 46130, 52760, 60080, 68136, 76976, 86649, 97206, ——A070893。

1, 6, 18, 44, 89, 162, 271, 428, 642, 0930, 1304, 1781, 2377, 3111, 4002, 5073, 6344, 7842, 09587, 11610, 13933, 16591, 19612, 23028, 26871, 31177, 35976, 41314, 47221, 53736, 60907, 68773, 77373, 86759, ——A070735—标准答案。

1, 6, 18, 44, 89, 161, 271, 427, 642, 0929, 1302, 1776, 2367, 3094, 3976, 5032, 6285, 7757, 09472, 11454, 13731, 16330, 19280, 22610, 26353, 30539, 35204, 40381, 46107, 52419, 59356, 66957, 75263, 84316, ——OEIS没有—mathe—6#公式。

Table], {n, 40}]

northwolves 发表于 2025-9-20 17:14:06

s={{01,2,3,4,5,6,7,8,9,10,11,12},{12,10,6,7,5,9,3,2,4,8,01,11}, {11,8,9,5,6,3,7,10,4,2,12,01}};Times@@s//Total

王守恩 发表于 2025-9-20 18:55:47

第1行 = r = 1, 2, 3, 4, 5, ... 。第2行 = s 。

第3行 = t:r*s 的最大值 = 1,r*s 的次大值 = 2,r*s 的三大值 = 3, ... 。

给出第2行 = s 。——还是没找到规律。

1,
2, 1,
3, 1, 2,
4, 2, 1, 3,
5, 2, 3, 1, 4,
6, 3, 4, 2, 1, 5,
7, 3, 4, 5, 2, 1, 6,
8, 5, 3, 4, 6, 2, 1, 7,
9, 5, 4, 6, 7, 3, 2, 1, 8,
10,7, 4, 5, 6, 8, 3, 2, 1, 9,
11,7, 5, 8, 4, 6, 9, 3, 2, 1, 10,
12,8, 6, 7,10,4, 5, 9, 3, 2, 1, 11,

大海捞针——越来越难！后面尽可能用 ..., 3, 2, 1。

王守恩 发表于 2025-9-21 10:05:06

五重内积 A260356：1, 12, 60, 214, 600, 1443, 3089, ——a(7)。——冰火两重天。

a(1)=1,1×1×1×1×1=1,
1,
1,
1,
1,
1,

a(2)=12,1×1×2×2×1+2×2×1×1×2=12,
1, 2,
1, 2,
2, 1,
2, 1,
1, 2,

a(3)=60,1×2×2×3×2+2×3×3×1×1+3×1×1×2×3=60,
1, 2, 3,
2, 3, 1,
2, 3, 1,
3, 1, 2,
2, 1, 3,

a(4)=214,1×1×3×4×4+2×2×2×2×3+3×3×1×3×2+4×4×4×1×1=214,
1, 2, 3, 4,
1, 2, 3, 4,
3, 2, 1, 4,
4, 2, 3, 1,
4, 3, 2, 1,

a(5)=600,1×2×3×4×5+2×1×4×5×3+3×4×5×2×1+4×5×1×3×2+5×3×2×1×4=600,
1, 2, 3, 4, 5,
2, 1, 4, 5, 3,
3, 4, 5, 1, 2,
4, 5, 2, 3, 1,
5, 3, 1, 2, 4,

a(6)=1443,1×1×6×6×6+2×2×4×4×4+3×3×3×3×3+4×6×1×2×5+5×5×2×5×1+6×4×5×1×2=1445,
1, 2, 3, 4, 5, 6,——第1行 = A1 = 1, 2, 3, 4, 5, ... 。
1, 2, 3, 6, 5, 4,——第2行 = A2——还没找到规律。
6, 4, 3, 1, 2, 5,——第3行 = A3——还没找到规律。
6, 4, 3, 2, 5, 1,——第4行 = A4——还没找到规律。
6, 4, 3, 5, 1, 2,——第5行 = A5——A1*A2*A3*A4的最大值 = 1,A1*A2*A3*A4的次大值 = 2,A1*A2*A3*A4的三大值 = 3, ... 。

a(7)=3089,1×3×7×7×3+2×6×1×6×6+3×7×5×1×4+4×2×3×4×5+5×5×6×3×1+6×1×2×5×7+7×4×4×2×2=3091,
1, 2, 3, 4, 5, 6, 7,
3, 6, 7, 2, 5, 1, 4,
7, 1, 5, 3, 6, 2, 4,
7, 6, 1, 4, 3, 5, 2,
3, 6, 4, 5, 1, 7, 2,

OEIS——A260356—是这样一串数——1, 12, 60, 214, 600, 1443, 3089, ——没有了。

mathe —— 6# ——是这样一串数——1, 12, 60, 213, 600, 1443, 3089, 6048, 11041, 19050, 31367, 49658, 76029, 113089, 164031, 232710, 323725, 442510, 595431, 789881, 1034385, 1338715,

Table], {n, 40}]

王守恩 发表于 3 天前

A070735——Let r, s, t be three permutations of the set {1, 2, 3, ..., n}; a(n) = minimal value of Sum_{i=1..n} r(i)*s(i)*t(i).
例如：
a(1)=1,1×1×1=1,
a(2)=6,1×2×2+2×1×1=6,
r={1, 2},
s={2, 1},
t={2, 1}.

a(3)=18,1×3×2+2×1×3+3×2×1=18,
r={1, 2, 3},
s={3, 1, 2},
t={2, 3, 1}.

a(4)=44,1×4×3+2×2×2+3×1×4+4×3×1=44,
r={1, 2, 3, 4},
s={4, 2, 1, 3},
t={3, 2, 4, 1}.

a(5)=89,1×5×3+2×2×4+3×3×2+4×1×5+5×4×1=89,
r={1, 2, 3, 4, 5},
s={5, 2, 3, 1, 4},
t={3, 4, 2, 5, 1}.

a(6)=162,1×6×5+2×4×3+3×2×4+4×3×2+5×1×6+6×5×1=162,
r={1, 2, 3, 4, 5, 6},
s={6, 4, 2, 3, 1, 5},
t={5, 3, 4, 2, 6, 1}.

a(7)=271,1×7×5+2×5×4+3×2×6+4×3×3+5×4×2+6×1×7+7×6×1=271,
r={1, 2, 3, 4, 5, 6, 7},
s={7, 5, 2, 3, 4, 1, 6},
t={5, 4, 6, 3, 2, 7, 1}.

a(8)=428,1×8×7+2×5×5+3×3×6+4×4×3+5×6×2+6×2×4+7×1×8+8×7×1=428,
r={1, 2, 3, 4, 5, 6, 7, 8},
s={8, 5, 3, 4, 6, 2, 1, 7},
t={7, 5, 6, 3, 2, 4, 8, 1}.

a(9)=642,——OEIS没有列出相应的 r, s, t。
......
前32项为 1, 6, 18, 44, 89, 162, 271, 428, 642, 930, 1304, 1781, 2377, 3111, 4002, 5073, 6344, 7842, 9587, 11610, 13933, 16591, 19612, 23028, 26871, 31177, 35976, 41314, 47221, 53736, 60907, 68773.

a(16)-a(19) from Hiroaki Yamanouchi, Aug 21 2015

a(20) onwards from Martin Fuller, Aug 06 2023

Martin Fuller, Table of n, a(n) for n = 1~204——记住Martin Fuller这个狠角色, 冲到a(204)。

想你了——Martin Fuller！

王守恩 发表于 前天 04:51

题目(1)——A070735——Let r, s, t be three permutations of the set {1, 2, 3, ..., n}; a(n) = minimal value of Sum_{i=1..n} r(i)*s(i)*t(i).

题目(2)——给定3*n个数 {1,1,1,2,2,2,3,3,3,4,4,4,...,n,n,n},分成 n 组,每组3个数,使得各组乘积的和最小。

题目(1),题目(2)——答案是一样的吗？

查看完整版本: 三重内积的最小值