第四章四元组求log2n1
需积分: 0 112 浏览量
2022-08-08
18:19:51
上传
评论
收藏 15KB DOCX 举报
题目:四元组解[log
2
n]
思路：每次将待处理的 1 段平分，并将 y 值增加 1，当最后待处理字符串仅剩一个字符时，
即得到解。
算法：
1. 初始化：抹掉 1 段最右侧一个 1，并在其右侧初始 y，即 B11…1B1B
2. while(待处理段长度大于 1)
3. while(a 和 b 尚未相遇)
4. 将 1 段最左侧一个 1 改为 a，将 1 段最右侧一个 1 改为 b
5. 确定新的待处理 1 段：
将 a 段最右侧的 a 改为 B；
将所有 b 改为 1；
6. y<-y+1
字母表取Σ={1，B，a，b}，状态取 Q={q
1
, q
2
, q
3
, q
4
, q
5
, q
6
, q
7
, q
8
, q
9
, q
10
, q
11
, q
12
, q
13
, q
14
, q
15
,
q
16
, q
17
, q
18
, q
19
, q
20
}。
q
1
1Rq
1
//初始化
q
1
BLq
2
q
2
1Bq
3
q
3
BRq
4
q
4
B1q
5
q
5
1Lq
5
//指向待处理 1 段的最左侧
q
5
BLq
6
q
6
1Lq
6
q
6
BRq
7
q
7
1aq
8
//q
7
~q
15
将 1 段平分
q
7
BBq
20
//被除数为 0 的情况
q
8
aRq
9
q
9
BBq
20
//BaB 的情况，程序出口
q
9
bLq
15
//平分完重新确定 1 段
q
9
1Rq
10
//确定了一对 a,b
q
10
1Rq
10
q
10
BLq
11
q
10
bLq
11
q
11
1bq
12
q
12
bLq
13
q
13
aaq
15
//(a 与 b 个数相同)
q
13
1Lq
14
q
14
1Lq
14
q
14
aRq
7
q
15
aBq
16
//以下确定新的 1 段
q
16
BRq
17
q
17
b1q
18
q
17
BRq
19
q
18
1Rq
17
q
19
1Rq
19
q
19
B1q
5
//y 增加 1
q
1
将指针右移到 1 段尾
q
2
将 1 段最后一个 1 改写为 B
q
3
右移一位
q
4
初始化 y，即写一个“1”
q
5
跳过 y 段
q
6
移动至 1 段最左侧
q
7
将 1 个“1”改写为 a
q
8
复写 a 后的状态
q
9
移动到 a 段最右侧
q
10
右移到 1 段最右侧
q
11
将最右侧 1 改为 b
q
12
复写 b 后的状态
q
13
移动到 b 段的左侧字符
q
14
移动至 1 段最左侧
q
15
将 a 改写为 B
q
16
复写 B 后的状态
q
17
将 b 改写为 1
q
18
指针右移
q
19
跳过 y 段，将其后 B 改写为 1
q
20
指针右移
评论0