123456789组成的3×3的矩阵的行列式最大的值是多少?

浅涛吖_3675

浅涛吖_3675

2016-06-06

10223人浏览

原创

123456789怎样运算等于1? - abccsss 的回答
假定每个数字只能出现一次。

回复内容:

Mathematica代码

较简洁

Det/@N@Range@9~Permutations~{9}~ArrayReshape~{9!,3,3}//Max
egin{Large}
det
egin{vmatrix}
9 & 2 & 4 \
5 & 7 & 1 \
3 & 6 & 8 \
end{vmatrix}
= 412
end{Large}

以上用Matlab暴力破解(枚举9! = 362880种情形),暂未输出行列式相同的其他情形,貌似基本秒出。
<span class="n">max_det</span> <span class="p">=</span> <span class="mi">0</span><span class="p">;</span>
<span class="n">init_perm</span> <span class="p">=</span> <span class="nb">reshape</span><span class="p">(</span><span class="mi">1</span><span class="p">:</span><span class="mi">9</span><span class="p">,</span> <span class="p">[</span><span class="mi">3</span><span class="p">,</span> <span class="mi">3</span><span class="p">]);</span>
<span class="n">all_perms</span> <span class="p">=</span> <span class="nb">perms</span><span class="p">(</span><span class="mi">1</span><span class="p">:</span><span class="mi">9</span><span class="p">);</span>

<span class="k">for</span> <span class="nb">i</span> <span class="p">=</span> <span class="mi">1</span><span class="p">:</span><span class="nb">size</span><span class="p">(</span><span class="n">all_perms</span><span class="p">,</span> <span class="mi">1</span><span class="p">)</span>
    <span class="n">matrix</span> <span class="p">=</span> <span class="n">all_perms</span><span class="p">(</span><span class="nb">i</span><span class="p">,</span> <span class="p">:);</span>
    <span class="n">matrix</span> <span class="p">=</span> <span class="nb">reshape</span><span class="p">(</span><span class="n">matrix</span><span class="p">,</span> <span class="p">[</span><span class="mi">3</span><span class="p">,</span> <span class="mi">3</span><span class="p">]);</span>
    <span class="n">det_value</span> <span class="p">=</span> <span class="n">det</span><span class="p">(</span><span class="n">matrix</span><span class="p">);</span>
    
    <span class="k">if</span> <span class="n">det_value</span> <span class="o">></span> <span class="n">max_det</span>
        <span class="n">max_det</span> <span class="p">=</span> <span class="n">det_value</span><span class="p">;</span>
        <span class="n">init_perm</span> <span class="p">=</span> <span class="n">matrix</span><span class="p">;</span>
    <span class="k">end</span>
    
<span class="k">end</span>
list = Permutations[Range[9], {9}];
matrix = Partition[#, 3] & /@ list;
answer = Det /@ matrix;
m = Max[answer];
pos = Flatten[Position[answer, m]];
matrix[[#]] & /@ pos 贴个毫无技术含量暴力程度max的python版。。。

import itertools
import time

def max_matrix():
	begin = time.time()
	elements = [1, 2, 3, 4, 5, 6, 7, 8, 9]
	maxdet = 0
	maxmat = []
	for i in itertools.permutations(elements, 9):
		det = i[0] * i[4] * i[8] + i[1] * i[5] * i[6] + i[2] * i[3] * i[7] - i[2] * i[4] * i[6] - i[1] * i[3] * i[8] - i[0] * i[5] * i[7]
		if(det > maxdet):
			maxdet = det
			maxmat = []
			for j in range(0, 9):
				maxmat.append(i[j])
	print "|" + str(maxmat[0]) + " " + str(maxmat[1]) + " " + str(maxmat[2]) + "|"
	print "|" + str(maxmat[3]) + " " + str(maxmat[4]) + " " + str(maxmat[5]) + "| = " + str(maxdet)
	print "|" + str(maxmat[6]) + " " + str(maxmat[7]) + " " + str(maxmat[8]) + "|"
	end = time.time()
	print str(end - begin) + 's used.'

if __name__ == '__main__':
	max_matrix()
题目应该改成1 2 3 ...n^2组成n阶行列式的最大值。并求最优解的时间复杂度才有意思。 C++:
<span class="cp">#include <cstdio></cstdio></span>
<span class="cp">#include <algorithm></algorithm></span>
<span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>
<span class="kt">int</span> <span class="n">ans</span><span class="p">,</span> <span class="n">a</span><span class="p">[]</span> <span class="o">=</span> <span class="p">{</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="mi">4</span><span class="p">,</span> <span class="mi">5</span><span class="p">,</span> <span class="mi">6</span><span class="p">,</span> <span class="mi">7</span><span class="p">,</span> <span class="mi">8</span><span class="p">,</span> <span class="mi">9</span><span class="p">};</span>
<span class="kt">int</span> <span class="nf">main</span><span class="p">()</span> <span class="p">{</span>
  <span class="k">do</span>
    <span class="n">ans</span> <span class="o">=</span> <span class="n">max</span><span class="p">(</span><span class="n">ans</span><span class="p">,</span> <span class="n">a</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="o">*</span> <span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="mi">4</span><span class="p">]</span> <span class="o">*</span> <span class="n">a</span><span class="p">[</span><span class="mi">8</span><span class="p">]</span> <span class="o">-</span> <span class="n">a</span><span class="p">[</span><span class="mi">5</span><span class="p">]</span> <span class="o">*</span> <span class="n">a</span><span class="p">[</span><span class="mi">7</span><span class="p">])</span> <span class="o">+</span>
                   <span class="n">a</span><span class="p">[</span><span class="mi">1</span><span class="p">]</span> <span class="o">*</span> <span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="mi">5</span><span class="p">]</span> <span class="o">*</span> <span class="n">a</span><span class="p">[</span><span class="mi">6</span><span class="p">]</span> <span class="o">-</span> <span class="n">a</span><span class="p">[</span><span class="mi">3</span><span class="p">]</span> <span class="o">*</span> <span class="n">a</span><span class="p">[</span><span class="mi">8</span><span class="p">])</span> <span class="o">+</span>
                   <span class="n">a</span><span class="p">[</span><span class="mi">2</span><span class="p">]</span> <span class="o">*</span> <span class="p">(</span><span class="n">a</span><span class="p">[</span><span class="mi">3</span><span class="p">]</span> <span class="o">*</span> <span class="n">a</span><span class="p">[</span><span class="mi">7</span><span class="p">]</span> <span class="o">-</span> <span class="n">a</span><span class="p">[</span><span class="mi">4</span><span class="p">]</span> <span class="o">*</span> <span class="n">a</span><span class="p">[</span><span class="mi">6</span><span class="p">]));</span>
  <span class="k">while</span> <span class="p">(</span><span class="n">next_permutation</span><span class="p">(</span><span class="n">a</span><span class="p">,</span> <span class="n">a</span> <span class="o">+</span> <span class="mi">9</span><span class="p">));</span>
  <span class="n">printf</span><span class="p">(</span><span class="s">"%d</span><span class="se">
</span><span class="s">"</span><span class="p">,</span> <span class="n">ans</span><span class="p">);</span>
<span class="p">}</span>
把yellow的答案重排一下可得
9 4 2
3 8 6
5 1 7

很容易看出思路了。
1.所有数按大小在斜率为-1的对角线上依次排开。(即:987在一条对角线,654在一条,321在一条)很容易看出这是让正向数值最大的方法。
2.对于反向的对角线,排除主对角线之外的任意两个数之和相等,且乘积越大的,相应的主对角线元素越小。(也就是让三个乘积的最大值最小,然后最大的结果再和最小的数相配这样)

但是以上方法仅限于1~9的3x3矩阵,对于其它的矩阵不一定适用。
因为显然这种方法要求正向和负向都只有对角线(或平行于对角线),但是4x4的行列式就开始有拐弯了。。。

然后,我感觉还有三个漏洞,一是贪心法不一定保证正向最大,也不一定保证反向最小,更不一定保证正反向之差最大。(不一定都是漏洞,可能有的是恒成立的)
但是我感觉对3x3的非负矩阵来说,贪心在多数情况下是可以拿到最大值的。

PS:试了很多组数,都是这个解,然后又试了一组[1 2 3 4 5 6 7 8 100],显然答案发生了变化,因为100的权值比8和7大太多,所以负向的时候直接就把2和1给了100。那么这也就证明了贪心法确实有时候得不到最大值。 前面已经有了python,c和MMA的代码了,我来一发matlab的吧
<span class="n">p</span><span class="p">=</span><span class="nb">perms</span><span class="p">(</span><span class="mi">1</span><span class="p">:</span><span class="mi">9</span><span class="p">);</span>
<span class="p">[</span><span class="n">n</span><span class="p">,</span><span class="o">~</span><span class="p">]=</span><span class="nb">size</span><span class="p">(</span><span class="n">p</span><span class="p">);</span>
<span class="n">z</span><span class="p">=</span><span class="nb">zeros</span><span class="p">(</span><span class="n">n</span><span class="p">,</span><span class="mi">1</span><span class="p">);</span>
<span class="k">for</span> <span class="nb">i</span><span class="p">=</span><span class="mi">1</span><span class="p">:</span><span class="n">n</span>
    <span class="n">z</span><span class="p">(</span><span class="nb">i</span><span class="p">)=</span><span class="n">det</span><span class="p">(</span><span class="nb">reshape</span><span class="p">(</span><span class="n">p</span><span class="p">(</span><span class="nb">i</span><span class="p">,:),</span><span class="mi">3</span><span class="p">,</span><span class="mi">3</span><span class="p">));</span>
<span class="k">end</span>
<span class="n">max</span><span class="p">(</span><span class="n">z</span><span class="p">)</span>
<span class="n">id</span><span class="p">=</span><span class="nb">find</span><span class="p">(</span><span class="n">z</span><span class="o">==</span><span class="n">max</span><span class="p">(</span><span class="n">z</span><span class="p">));</span>
<span class="k">for</span> <span class="nb">i</span><span class="p">=</span><span class="mi">1</span><span class="p">:</span><span class="nb">length</span><span class="p">(</span><span class="n">id</span><span class="p">)</span>
    <span class="nb">disp</span><span class="p">(</span><span class="nb">reshape</span><span class="p">(</span><span class="n">p</span><span class="p">(</span><span class="n">id</span><span class="p">(</span><span class="nb">i</span><span class="p">),:),</span><span class="mi">3</span><span class="p">,</span><span class="mi">3</span><span class="p">));</span>
<span class="k">end</span>
对于三阶的穷举,可以不用det函数会比较简单:
<span class="n">p</span> <span class="p">=</span> <span class="nb">reshape</span><span class="p">(</span><span class="nb">perms</span><span class="p">(</span><span class="mi">1</span><span class="p">:</span><span class="mi">9</span><span class="p">),</span><span class="s">''</span><span class="p">,</span><span class="mi">3</span><span class="p">,</span><span class="mi">3</span><span class="p">);</span>
<span class="n">M</span> <span class="p">=</span> <span class="n">max</span><span class="p">(</span><span class="n">sum</span><span class="p">(</span><span class="n">prod</span><span class="p">(</span><span class="n">p</span><span class="p">,</span><span class="mi">2</span><span class="p">),</span><span class="mi">3</span><span class="p">)</span><span class="o">-</span><span class="n">sum</span><span class="p">(</span><span class="n">prod</span><span class="p">(</span><span class="n">p</span><span class="p">,</span><span class="mi">3</span><span class="p">),</span><span class="mi">2</span><span class="p">));</span>
话题的语言还少个Mathematica,就我来吧
直接9!个结果存下来刚正面,0优化
Det[Partition[#, 3]] & /@ Permutations[Range[9]] // Max

412
PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
Navicat创建数据库教程
Navicat创建数据库教程

本专题整理Navicat创建数据库相关教程,介绍新建前的准备、基础设置和创建后的检查方法。内容兼顾入门学习及实际使用需求,帮助用户了解不同数据库类型下的操作差异,为后续建表、保存数据和日常管理提供参考。

2026.11.20

20

7

Navicat入门教程大全
Navicat入门教程大全

本专题整理Navicat入门教程,从认识软件界面到开展数据库操作,介绍初次使用需要了解的知识和方法。内容兼顾连接配置、数据管理及日常使用中的疑问,方便用户按学习进度查阅,为后续实践和独立操作打好基础。

2026.11.20

20

17

Navicat数据库连接配置指南
Navicat数据库连接配置指南

从确认数据库信息到建立可用连接,本专题串联Navicat连接数据库的相关知识和操作方法。既有初次配置时需要了解的基础内容,也有连接后的检查思路,方便用户按实际需求查阅教程,逐步熟悉数据库连接的设置流程。

2026.11.20

0

10

PHP8.6数组与数据处理教程
PHP8.6数组与数据处理教程

本专题汇总PHP8.6数组与数据处理教程,涵盖CSV读取和导出、引用遍历删除、array_filter回调模式、配置键名冲突、pathinfo文件名校验、GMP大整数进制转换及UTF-8正则筛选,说明升级兼容变化、输入范围和失败处理方法。

2026.11.20

60

8

PHP8.6升级迁移教程
PHP8.6升级迁移教程

本专题汇总PHP8.6升级迁移与弃用接口改造教程,涵盖反射调用、对象属性赋值、标识符更名、构造函数与__debugInfo调整,以及插件类名检查、常量导出、ArrayIterator排序、SPL和DTO查询参数转换,帮助梳理弃用提示并完成代码兼容改造。

2026.11.20

0

10

PHP8.6安装配置与FPM运维教程
PHP8.6安装配置与FPM运维教程

本专题汇总PHP8.6正式版安装部署与FPM运维教程,涵盖Linux并存安装、独立ini配置、扩展重新编译、Nginx切换与回滚、FPM状态监控和慢日志排查,以及环境变量、请求超时、OPcache刷新和预加载配置。

2026.11.20

40

10

Nginx CVE-2026-123007排查与防护指南
Nginx CVE-2026-123007排查与防护指南

Nginx HTTP/2漏洞该怎么修复?本专题围绕CVE-2026-123007,介绍安全版本升级、模块兼容检查和配置恢复方法,以及日志排查、权限设置等后续加固操作,方便你按实际部署情况查找对应教程。

2026.11.20

40

8

GoFrame框架Web开发与路由中间件
GoFrame框架Web开发与路由中间件

本专题聚焦GoFrame框架的Web开发,拆解路由注册与匹配规则、请求参数获取、参数校验与中间件执行顺序,说明统一响应、JWT鉴权、文件上传与接口文档生成的落地方式,并补充优雅重启与测试实践。

2026.11.17

80

15

GoFrame框架安装与gf命令行工具
GoFrame框架安装与gf命令行工具

本专题围绕GoFrame框架的安装与工具链配置展开,讲清Go版本要求、gf命令行的安装方式、代理镜像与依赖准备,说明项目初始化、热编译、交叉编译打包的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.17

100

15

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
热门推荐
/
最新课程
phpStudy极速入门视频教程
phpStudy极速入门视频教程

共6课时 | 54.8万人学习

独孤九贱(4)_PHP视频教程
独孤九贱(4)_PHP视频教程

共89课时 | 134.5万人学习