这题要求输出的是与当前分形三角形相邻的三角形编号。不难判断,在确定了分形阶数之后,与自己相邻的三角形至多有三个。
假设当前谢尔宾斯基三角形被分了 $n$ 阶(也就是T后面的字符串长度),那么我们可以分类讨论进行分析:
1.如果最后一位是 $4$ ,也就是处在最后这一层的正中央,那么很显然与其相邻的三个三角形就是与自己同一个分形内的其他三个三角形。那么我们把最后一位分别改成 $1,2,3$ ,分别输出一下就可以了。
2.如果最后一位不是 $4$ ,那么看图以及样例判断,就从最后往前看一下,$1,2,3$ 最后一次出现分别是在分形的哪一层。这三个数每出现一个,就这个数最后一次出现的那一层,与其在同一分形且处在正中央的那个三角形与其相连,对应三角形的编号就是把这一层后面的所有字符都去掉,这一层的字符改成 $4$ 就行了。
然后输出是字典序从小到大,考虑到正中央的编号是 $4$ ,所以阶数越大的应该更优先输出。那么我们的思路就是先判断,$1,2,3$ 是否都出现过,每出现一种就说明会多一个与自己相邻的三角形。然后看 $1,2,3$ 最后出现的位置,谁的位置更靠后就先输出其对应相邻的三角形,那就需要把当前位改成 $4$ 后面改成 '\0'
输出就行了。
#include <stdio.h>
#include <string.h>
char s[55];
int n;
int last_pos[4], order[4], cnt;
int main()
{
scanf("%s", s), n = strlen(s + 1);
if (s[n] == '4') // 最后一位是 4
for (int i = 1; i <= 3; ++i)
s[n] = i ^ '0', puts(s); // 把最后一位分别改成 1,2,3 然后输出
else // 最后一位不是4
{
for (int j = n; j; --j) // 从后往前判断,找 1,2,3 最后一次出现是在哪一层
for (int i = 1; i <= 3; ++i)
if ((!last_pos[i]) && ((s[j] ^ '0') == i))
order[++cnt] = i, last_pos[i] = j; // 最后出现位置靠后的要优先输出,所以这里记一下输出顺序
for (int i = 1; i <= 3; ++i) // 记录过顺序的有多少个就输出多少个
if (order[i])
{
// 每次输出将对应层的位数改成4,后面改成0然后printf或者puts的时候就会到 '\0' 处停止
int tmp1 = s[last_pos[order[i]]] ^ '0', tmp2 = s[last_pos[order[i]] + 1] ^ '0';
s[last_pos[order[i]]] = '4', s[last_pos[order[i]] + 1] = '\0';
puts(s);
// 直接在原数组修改,所以要记得备份原始信息并且恢复
s[last_pos[order[i]]] = tmp1 ^ '0', s[last_pos[order[i]] + 1] = tmp2 ^ '0';
}
}
}