刷题小记

藏宝库编辑 · 2024-9-15 21:56:45

本日在刷牛客网华为机试的标题。
有个素数朋友的算法，就是在给定一组数字中，比方2，3，5，6，11，13，找出可以或许配对最多的素数对数（素数：不能被除了1和自己之外的数整除）。好比2+3就是一个素数，这俩就是一对素数朋友，剩下四个数以此类推找出最大配对数。
标题很好懂，假如给一个例子自己算也很好算，但就是自己的盘算也没有规律可言，都是肉眼找。
思来想去找不到盘算规律，查察题解才知道，原来有一个匈牙利算法，可以办理此类标题。这个算法的核心可以用八个字概括：先到先得，能让则让。
简朴来说我们的数字列表可以分为奇数和偶数两对，只有奇数+偶数的组合才大概是素数。
也就是说我们实在是在给奇数项和偶数项画毗连线。
先到先得意思是假如第一个奇数和第一个偶数加起来是素数，就可以作为一对朋友。
能让则让意思是，假如第二个奇数和第一个偶数也能配对，那么第一个奇数思量把原来配对的偶数让出去。假如能找到新的偶数朋友的话。
假设第一个奇数找到了第三个偶数配对乐成，那么第二个奇数就可以找第一个偶数，如许就有两对了。以此类推可以办理素数朋友的标题。

看完算法的分析我实在是蒙圈的，为什么先到先得能让则让就可以找到最优解？原理是什么呢？谁想到的这么解呢？
找了一些资料也没有发现普通地说法，只能表明为这背后有数学理论作为依据。
看来算法的本质是数学啊，还得学好数学，才气做好算法。

刷题小记

所属分类: 问答交流

新帖推荐: 30日

推荐作品