Это второй день моего участия в августовском испытании обновлений.Подробности о событии смотрите:Испытание августовского обновления
Разработка алгоритма и анализ Тема 1:
Выберите 5 букв (a, b, c, d, e) из строки str, чтобы сформировать пароль
Удовлетворить, a - b * b + c * c * c - d * d * d * d + e * e * e * e * e == n
входить:
(1) Целое число n
(2) строка, состоящая из разных заглавных букв, 5≤длина≤12
вывод:
Пароль str, который соответствует правилам, в противном случае решения нет.
Основной код и комментарии:
/* 5层循环暴力破解 */
int flag = 1;
for (int i = 0; i < s.size() && flag; i++) {
int a = s[i] - 'A' + 1;//临时存放字母的序数
int A = a;//1次方
for (int j = 0; j < s.size() && flag; j++) {
if (i == j) continue;
int b = s[j] - 'A' + 1;
int B = b * b;//2次方
for (int k = 0; k < s.size() && flag; k++) {
if (i == k || j == k) continue;
int c = s[k] - 'A' + 1;
int C = c * c * c;//3次方
for (int l = 0; l < s.size() && flag; l++) {
if (i == l || j == l || k == l) continue;
int d = s[l] - 'A' + 1;
int D = d * d * d * d;//4次方
for (int m = 0; m < s.size() && flag; m++) {
if (i == m || j == m || k == m || l == m) continue;
int e = s[m] - 'A' + 1;
int E = e * e * e * e * e;//5次方
int sum = A - B + C - D + E;
if (sum == n) {
flag = 0;
cout << (char)(a + 'A' - 1);
cout << (char)(b + 'A' - 1);
cout << (char)(c + 'A' - 1);
cout << (char)(d + 'A' - 1);
cout << (char)(e + 'A' - 1);
cout << endl;
}
}//m
}//l
}//k
}//j
}//i
Результаты теста: /* введите 1 */
int n = 1;
s = "ABCDEFGHIJKL";
/* ввод 2 */
int n = 11700519;
s = "ZAYEXIWOVU";
/* ввод 3 */
int n = 3072997;
s = "SOUGHT";
/* ввод 4 */
int n = 1234567;
s = "THEQUICKFROG";
Выходной результат:
Разработка алгоритма и анализ Тема 2:Максимальная клика: полный подграф с наибольшим количеством вершин в неориентированном графе G.
Полный граф: между любыми двумя вершинами существует ребро.
входить:
(1) n вершин, пронумерованных 1...n
(2) m ненаправленных ребер
вывод:
Количество вершин в наибольшей клике
Входной образец:
5 6 //Первая строка n m: n вершин, m ребер
1 2 //Строка m ниже (s, t): есть ребро между вершиной s и вершиной t
2 3
2 4
3 4
3 5
4 5
Основной код и комментарии:
int max = 1;
for (int i = 1; i <= n; i++) {//依次遍历n个顶点
/* 遍历n个点 */
queue * q = new queue();
for (int j = i + 1; j <= n; j++) {
if (G[i][j]) {//若从顶点i到顶点j有边，顶点j入队
q->in(j);
}
}
/* 初始cur_max=1，因为[当前顶点]与[最近准备出队顶点]之间，必存在边 */
int cur_max = 1;
while (!q->isEmpty()) {
int val = q->out();//依次出队与当前顶点相邻的顶点
int flag = 1;//==1时，表示还没破坏完全图的规则
for (int j = 0; j < q->getSize(); j++) {//遍历[队列剩余顶点]
if (!G[val][q->get()]) {//如果[当前出队顶点]与[队列中剩余的所有顶点]之间无边，就不能保证完全图，退出当前循环
flag = 0;
break;
}
}
if (flag) cur_max++;//累计当前最大团的顶点个数
}
max = cur_max > max ? cur_max : max;
delete(q);
}
входить: 5 6
1 2
2 3
2 4
3 4
3 5
4 5
вывод: результат правильный