偶数N 马蹄集

 偶数N
难度：白银
时间限制：1秒
巴占用内存：64M
输入偶数N(偶数N大于2)，返回两个素数，其和等于偶数N。可能有几种的组
合，仅输出最小值所在的组合，按从小到大输出。
格式
输入格式：输入偶数N
输出格式：输出整型，空格分隔。

//
// Created by abner on 2022/11/11.
//
#include 
using namespace std;
bool prime(int n){
    if(n ==2)return true;
    for(int i=2;i<=sqrt(n);++i) {
        if (n % i == 0) {
            return false;
        }
    }
        return true;
    }
    int main(){
        int n;
        scanf("%d",&n);
 
        for(int i=2;i<=n/2.0;++i) {
            if (prime(i) && prime(n - i)) {
                printf("%d %d\n", i, n - i);
                break;
            }
        }
            return 0;
        }

若运算的优先级和结合性做下述约定:
    1. 三种运算均具有左结合性质；
    2. 优先级从高到低顺序排列为:闭包运算、连接运算、或运算。
则正规式中不必要的括号可以被省略。

若正规式P和Q表示了同一个正规集，则称P和Q是等价的，记为P=Q

正在上传…重新上传取消

(3) 简化正规式描述(主要是简化书写上的复杂)

(a) 正闭包 若r是表示L(r)的正规式，则r+是表示(L(r))+的正规式，且下述等式成立:r+ = rr* = rr，r = r+|ε;
          +与*具有相同的运算结合性和优先级
(b) 可缺省  若r是正规式，则r?是表示L(r)∪{ε}的正规式，且下述等式成立:r? = r|ε
           ? 与 * 具有相同的运算结合性和优先级
(c) 串    若r是若干字符进行连接运算构成的正规式，则:串“r” =  r ，且: ε= “”，   a = “a”（a是Σ的任一字符）
(d) 字符组 若r是若干字符进行|运算构成的正规式，则可改写为  [r’]，其中r’可以有如下两种书写形式：
             枚举:      如  a|b|e|h，可写为 [abeh]：
             分段:   如0|1|2|3|4|5|6|7|8|9|a|b|c|d|e , 可写为： [0-9a-e]
(e) 非字符组 若[r]是一个字符组形式的正规式，则[^r]是表示∑- L([r])的正规式。 

3. 记号的识别——有限自动机

(1) 不确定的有限自动机（NondeterministicFinite Automaton, NFA）

NFA是一个五元组（5-tuple）：M =（S，∑，move，s0，F），其中
（1） S是有限个状态（state）的集合；
（2） ∑是有限个输入字符（包括ε）的集合；
（3） move是一个状态转移函数，move(si，ch)=sj表示，当前状态si下若遇到输入字符ch，则转移到状态sj；
（4） s0是唯一的初态（也称开始状态）；
（5） F是终态集（也称接受状态集），它是S的子集，包含了所有的终态。

<1> 直观的表示方式

① 状态转换图：用一个有向图来直观表示NFA
② 状态转换矩阵：用一个矩阵来直观表示NFA (矩阵中，状态对应行，字符对应列)

<2> NFA(识别记号)的特点
NFA识别记号的最大特点是它的不确定性，即在当前状态下对同一字符有多于一个的下一状态转移。

具体体现：
定义： move函数是1对多的；
状态转换图：从同一状态出发，可通过多于一条标记相同字符的边转移到不同的状态；
状态转换矩阵： M[si,a]是一个状态的集合

<3> NFA识别记号存在的问题

1.只有尝试了全部可能的路径,才能确定一个输入序列不被接受,而这些路径的条数随着路径长度的增长成指数增长
2.识别过程中需要进行大量回朔，时间复杂度升高且算法复杂

(2) 确定的有限自动机（Deterministic Finite Automaton, DFA）

定义: DFA是NFA的一个特例，其中： 
  （1）没有状态具有ε状态转移(ε-transition)，即状态转换图中没有标记ε的边；
  （2）对每个状态s和每个字符a，最多有一个下一状态。
  
特点：与NFA相比，DFA的特征：确定性
    定义：move（si, a)函数都是 1对1 的；
    转换图 从一个状态出发的任2条边上的标记均不同；
    转换矩阵：M[si,a]是一个状态   且字母表不包括ε。
提示：正规式和有限自动机从两个侧面表示正规式。正规式是描述，自动机是识别。

4. 从正规式到词法分析器

构造词法分析器的一般方法和步骤：
1. 用正规式描述模式（为记号设计正规式）；
2. 为每个正规式构造一个NFA，它识别正规式所表示的正规集；
3. 将构造的NFA转换成等价的DFA，这一过程也被称为确定化；
4. 优化DFA，使其状态数最少，这一过程也被称为最小化；
5. 根据优化后的DFA构造词法分析器。

(1) 从正规式到NFA

Thompson 算法

正在上传…重新上传取消

(2) 从NFA到DFA

- smove(S, a)：从状态集S出发，标记为a的下一状态全体。与move(s, a)的唯一区别：用状态集取代状态
- ε-闭包(T)：从状态集T出发，不经任何字符达到的状态全体
- “子集法”构造DFA

(3) 最小化DFA

​ ① 对于任何两个状态t和s，若从一状态出发接受输入字符串ω，而从另一状态出发不接受ω.

或者，② 从t出发和从s出发到达不同的接受状态，则称ω对状态t和s是可区分的.

​ 不可区分的状态位于一个组内，可以合并成一个状态.