当前位置:网站首页>Prime partner of Huawei machine test questions
Prime partner of Huawei machine test questions
2022-07-07 06:51:00 【Sunny day m rainy day】
Maximum matching of bipartite graph ( hungarian algorithm ): Prime mate
The top
Title Description
If sum of the two positive integers is prime , Then these two positive integers are called “ Prime mate ”, Such as 2 and 5、6 and 13, They can be applied to communication encryption . Now the password society asks you to design a program , From what already exists N(N For the even ) Select several pairs of positive integers to form “ Prime mate ”, There are many options , For example, there are 4 A positive integer :2,5,6,13, If you will 5 and 6 You can only get one group in a group “ Prime mate ”, And will be 2 and 5、6 and 13 Grouping will result in two groups “ Prime mate ”, Energy composition “ Prime mate ” The most common scheme is called “ Best solution ”, Of course, the password society wants you to find “ Best solution ”.
Input
There is a positive even number N(N≤100), Represents the number of natural numbers to be selected . Specific figures are given later , The scope is [2,30000].
Output
Output an integer K, It means what you get “ Best solution ” form “ Prime mate ” The logarithmic .
Input description
1、 Enter a positive even number n
2 、 Input n It's an integer
Output description
Obtained “ Best solution ” form “ Prime mate ” The logarithmic .
Input
4
2 5 6 13
Output
2
Ideas
Consider using graph theory to model this problem .100 The number is 100 A little bit , If the sum of these two numbers is prime , Connect an edge between these two numbers . after , We should choose as many edges as possible , Require these edges not to share endpoints . The value range of each number is [2,30000]. Prime except 2 It's even , Others are odd numbers —— And now it can't happen 2 了 , So we only consider odd primes .2 The sum of numbers is odd , Only an odd number + even numbers . therefore , We divide these numbers into 2 Pile up —— Odd and even , Get bipartite graph . Then among them , And are prime , Connect an edge , Then match . The maximum match of bipartite graph , There is a much simpler algorithm , hungarian algorithm .
Relevant concepts
Bipartite graph
A bipartite graph is actually a graph in which all points can be divided into two groups , There are no edges in the same group , All edges span two groups . Accurately speaking : Divide the vertex of a graph into two disjoint sets U and V , And make each side connected separately U 、V The summit of , If there is such a division , This graph is called a bipartite graph .
Another equivalent definition of bipartite graph is : It doesn't contain 「 Rings with odd edges 」 Graph .
matching
Bipartite graph matching is the set of edges, in which any two edges have no common vertices . We define :
Match side 、 Match points 、 Unmatched edges 、 Mismatches .
Pictured : if 1—2 Connected to a ,5—4 Connected to a ,7—6 Connected to a . Obviously 1—2 edge 、5—4 edge 、7—6 The edge is a matching edge ,1、2、4、5、6、7 For matching points . The rest are unmatched points and unmatched edges .
The biggest match
The matching with the largest number of edges in the matching of a graph is the maximum matching of this graph . As shown in the figure above, the maximum match is :
Obviously, there may be more than one maximum match .
Perfect match
If there is a match in a graph , All vertices are matching points , Then it's a perfect match . The above pictures are perfect matches . obviously , Perfect match must be the biggest match ( Any point of perfect match has been matched , Adding a new matching edge will conflict with the existing matching edge ). But not every graph has a perfect match .
Alternate paths
Starting from an unmatched point , Pass through the unmatched edges in turn 、 Match side 、 Unmatched edges …… The formed path is called alternate path . Pictured 2—>1—>8—>7 It is an alternate path .
Augmentation path
Starting from an unmatched point , Take alternate paths , If you reach another unmatched point , Then this alternate path is called augmented path (agumenting path). Pictured 1—>2—>3—>6—>7—>8 That is, an expansion path .
Code reference
import java.util.Scanner;
import java.util.ArrayList;
public class Main{
static int max=0;
public static void main(String[] args){
// The standard input
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
// Enter positive and even numbers
int n=sc.nextInt();
// Used to record input n It's an integer
int[] arr=new int[n];
// Used to store all odd numbers
ArrayList<Integer> odds=new ArrayList<>();
// Used to store all even numbers
ArrayList<Integer> evens=new ArrayList<>();
for(int i=0;i<n;i++){
arr[i]=sc.nextInt();
// Add odd numbers to odds
if(arr[i]%2==1){
odds.add(arr[i]);
}
// Add even numbers to evens
if(arr[i]%2==0){
evens.add(arr[i]);
}
}
// Subscripts correspond to even subscripts that have been matched , The value corresponds to this even number of partners
int[] matcheven=new int[evens.size()];
// Record the number of partners
int count=0;
for(int j=0;j<odds.size();j++){
// Used to mark whether the corresponding even number has been searched
boolean[] v=new boolean[evens.size()];
// If match up , Then count and add 1
if(find(odds.get(j),matcheven,evens,v)){
count++;
}
}
System.out.println(count);
}
}
// Judge the odd number x Can you find a partner
private static boolean find(int x,int[] matcheven,ArrayList<Integer> evens,boolean[] v){
for(int i=0;i<evens.size();i++){
// This location has not been visited even , And can communicate with x Form prime partners
if(isPrime(x+evens.get(i))&&v[i]==false){
v[i]=true;
/* If i Even number has no partner , Then with x Form a partner , If you already have a partner , And this partner can find a new partner , Then give your original partner to others , Oneself and x Form a partner */
if(matcheven[i]==0||find(matcheven[i],matcheven,evens,v)){
matcheven[i]=x;
return true;
}
}
}
return false;
}
// Judge x Is it a prime
private static boolean isPrime(int x){
if(x==1) return false;
// If it can be 2 Root number x to be divisible by , Then it must not be prime
for(int i=2;i<=(int)Math.sqrt(x);i++){
if(x%i==0){
return false;
}
}
return true;
}
}
边栏推荐
- 偏执的非合格公司
- JESD204B时钟网络
- 当前发布的SKU(销售规格)信息中包含疑似与宝贝无关的字
- AddressSanitizer 技术初体验
- oracle如何备份索引
- Force deduction 62 different paths (the number of all paths from the upper left to the lower right of the matrix) (dynamic planning)
- Google Chrome browser released patch 103.0.5060.114 to fix the 0-day vulnerability
- 常用函数detect_image/predict
- Programmers' daily | daily anecdotes
- Postgresql源码(59)分析事务ID分配、溢出判断方法
猜你喜欢
品牌电商如何逆势增长?在这里预见未来!
2022年全国所有A级景区数据(13604条)
[opencv] morphological filtering (2): open operation, morphological gradient, top hat, black hat
MOS tube parameters μ A method of Cox
软件测试到了35岁,真的就干不动了吗?
jdbc数据库连接池使用问题
SolidWorks GB Library (steel profile library, including aluminum profile, aluminum tube and other structures) installation and use tutorial (generating aluminum profile as an example)
Can't you really do it when you are 35 years old?
dolphinscheduler3. X local startup
场馆怎么做体育培训?
随机推荐
Stack and queue-p79-9
docker-compose启动redis集群
Google Chrome browser released patch 103.0.5060.114 to fix the 0-day vulnerability
impdp的transform参数的测试
AddressSanitizer 技术初体验
从零到一,教你搭建「CLIP 以文搜图」搜索服务(二):5 分钟实现原型
MySQL的主从复制原理
RuntimeError: CUDA error: CUBLAS_STATUS_ALLOC_FAILED when calling `cublasCreate(handle)`问题解决
企業如何進行數據治理?分享數據治理4個方面的經驗總結
Linear algebra (1)
MYSQL binlog相关命令
mobx 知识点集合案例(快速入门)
多个kubernetes集群如何实现共享同一个存储
偏执的非合格公司
Mysql---- import and export & View & Index & execution plan
循环肿瘤细胞——Abnova 解决方案来啦
2022 Android interview essential knowledge points, a comprehensive summary
MySQL SQL的完整处理流程
Force deduction 62 different paths (the number of all paths from the upper left to the lower right of the matrix) (dynamic planning)
Performance comparison between Ceres solver and g2o