README.md
skill_tree_algorithm
算法(algorithm)技能树 是技能森林的一部分。
初始化
pip install -r requirement.txt目录结构说明
- 技能树
骨架文件：- 位置：
data/tree.json - 说明：该文件是执行
python main.py生成的，请勿人工编辑
- 位置：
- 技能树
根节点配置文件：- 位置：
data/config.json - 说明：可编辑配置关键词等字段，其中
node_id字段是生成的，请勿编辑
- 位置：
- 技能树
难度节点：- 位置：
data/xxx，例如:data/1.算法初阶 - 说明：
- 每个技能树有 3 个等级，目录前的序号是必要的，用来保持文件夹目录的顺序
- 每个目录下有一个
config.json可配置关键词信息，其中node_id字段是生成的，请勿编辑
- 位置：
- 技能树
章节点：- 位置：
data/xxx/xxx，例如：data/1.算法初阶/1.蓝桥杯 - 说明：
- 每个技能树的每个难度等级有 n 个章节，目录前的序号是必要的，用来保持文件夹目录的顺序
- 每个目录下有一个
config.json可配置关键词信息，其中node_id字段是生成的，请勿编辑
- 位置：
- 技能树
知识节点：- 位置：
data/xxx/xxx/xxx，例如：data/1.算法初阶/1.蓝桥杯/7段码 - 说明：
- 每个技能树的每章有
n个知识节点 - 每个目录下有一个
config.json- 其中
node_id字段是生成的，请勿编辑 - 其中
keywords可配置关键字字段 - 其中
children可配置该知识节点下的子树结构信息，参考后面描述 - 其中
export可配置该知识节点下的导出习题信息，参考后面描述
- 其中
- 每个技能树的每章有
- 位置：
知识节点 子树信息结构
例如 data/1.算法初阶/1.蓝桥杯/7段码/config.json 里配置对该知识节点子树信息结构：
{
// ...
"children": [],
}
知识节点 的导出习题编辑
例如 data/1.算法初阶/1.蓝桥杯/7段码/config.json 里配置对该知识节点导出的习题
{
// ...
"export": ["solution.json"]
}格式说明：
-
file: 指定该目录下的习题源文件 -
variants： 指定习题同名的json选项配置文件，参考下一节 -
depends: 如果习题依赖同目录下的其他习题源代码，则在此字段里配置依赖的其他习题源文件名
知识节点 的导出习题选项配置编辑
首先，我们根据前文，在 data/1.算法初阶/1.蓝桥杯/7段码 目录增加一个solution.json文件：
{
"type": "code_options",
"author": "卢昕",
"source": "solution.md"
}然后在 data/1.算法初阶/1.蓝桥杯/7段码 下增加一个solution.md文件：
# 7段码
#### 题目描述
小蓝要用七段码数码管来表示一种特殊的文字。
上图给出了七段码数码管的一个图示，数码管中一共有 7 段可以发光的二极管，分别标记为 a, b, c, d, e, f, g。
小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符的表达时，要求所有发光的二极管是连成一片的。
* 例如：b 发光，其他二极管不发光可以用来表达一种字符。
* 例如：c 发光，其他二极管不发光可以用来表达一种字符。
这种方案与上一行的方案可以用来表示不同的字符，尽管看上去比较相似。
* 例如：a, b, c, d, e 发光，f, g 不发光可以用来表达一种字符。
* 例如：b, f 发光，其他二极管不发光则不能用来表达一种字符，因为发光的二极管没有连成一片。
请问，小蓝可以用七段码数码管表达多少种不同的字符？
## aop
### before
```cpp
#include <iostream>
using namespace std;
int use[10];
int ans, e[10][10], father[10];
void init()
{
e[1][2] = e[1][6] = 1;
e[2][1] = e[2][7] = e[2][3] = 1;
e[3][2] = e[3][4] = e[3][7] = 1;
e[4][3] = e[4][5] = 1;
e[5][4] = e[5][6] = e[5][7] = 1;
e[6][1] = e[6][5] = e[6][7] = 1;
}
int find(int a)
{
if (father[a] == a)
return a;
father[a] = find(father[a]);
return father[a];
}
```
### after
```cpp
int main()
{
init();
dfs(1);
cout << ans;
return 0;
}
```
## 答案
```cpp
void dfs(int d)
{
if (d > 7)
{
for (int i = 1; i <= 7; i++)
{
father[i] = i;
}
for (int i = 1; i < 8; i++)
{
for (int j = 1; j < 8; j++)
{
if (e[i][j] == 1 && use[i] && use[j])
{
int fx = find(i);
int fy = find(j);
if (fx != fy)
{
father[fx] = fy;
}
}
}
}
int k = 0;
for (int i = 1; i < 8; i++)
{
if (use[i] && father[i] == i)
{
k++;
}
}
if (k == 1)
{
ans++;
}
return;
}
use[d] = 1;
dfs(d + 1);
use[d] = 0;
dfs(d + 1);
}
```
## 选项
### A
```cpp
void dfs(int d)
{
if (d > 7)
{
for (int i = 1; i <= 7; i++)
{
father[i] = i;
}
for (int i = 1; i < 8; i++)
{
for (int j = 1; j < 8; j++)
{
if (e[i][j] == 1 && use[i] && use[j])
{
int fx = find(i);
int fy = find(j);
if (fx != fy)
{
father[fx] = fy;
}
}
}
}
int k = 0;
for (int i = 1; i < 8; i++)
{
if (father[i] == i)
{
k++;
}
}
if (k == 1)
{
ans++;
}
return;
}
use[d] = 1;
dfs(d + 1);
use[d] = 0;
dfs(d + 1);
}
```
### B
```cpp
void dfs(int d)
{
if (d > 7)
{
for (int i = 1; i <= 7; i++)
{
father[i] = i;
}
for (int i = 1; i < 8; i++)
{
for (int j = 1; j < 8; j++)
{
if (e[i][j] == 1)
{
int fx = find(i);
int fy = find(j);
if (fx != fy)
{
father[fx] = fy;
}
}
}
}
int k = 0;
for (int i = 1; i < 8; i++)
{
if (use[i] && father[i] == i)
{
k++;
}
}
if (k == 1)
{
ans++;
}
return;
}
use[d] = 1;
dfs(d + 1);
use[d] = 0;
dfs(d + 1);
}
```
### C
```cpp
void dfs(int d)
{
if (d > 7)
{
for (int i = 1; i <= 7; i++)
{
father[i] = i;
}
int k = 0;
for (int i = 1; i < 8; i++)
{
if (use[i] && father[i] == i)
{
k++;
}
}
if (k == 1)
{
ans++;
}
return;
}
use[d] = 1;
dfs(d + 1);
use[d] = 0;
dfs(d + 1);
}
```后续的处理程序会根据“答案”、“选项”等标题查找内容，选项章节内部的三级标题不会进入题目，可以用来标注选项信息，例如 “语法错误”，“内存没有初始化”等等。
技能树合成
在根目录下执行 python main.py 会合成技能树文件，合成的技能树文件: data/tree.json
- 合成过程中，会自动检查每个目录下
config.json里的node_id是否存在，不存在则生成 - 合成过程中，会自动检查每个知识点目录下
config.json里的export里导出的习题配置，检查是否存在exercise_id字段，如果不存在则生成