This is the second day of my participation in the August More text Challenge. For details, see: August More Text Challenge

Algorithm Design and Analysis

Select five letters from STR (a, b, C, d, e) to form a password

A – b * b + c * c * c-d * d * d * d * d * d * d + e * e * e * e * e == n

Input:

(1) Integer n

(2) STR, composed of different uppercase letters, 5≤ length ≤12

Output:

The password of STR that meets the rules is no solution

Core code and comments:

/* int flag = 1; for (int i = 0; i < s.size() && flag; i++) { int a = s[i] - 'A' + 1; Int A = A; // for (int j = 0; j < s.size() && flag; j++) { if (i == j) continue; int b = s[j] - 'A' + 1; int B = b * b; // 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; // 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; // 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; 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 }//iCopy the code

Test result: /* Enter 1 */

int n = 1;

s = “ABCDEFGHIJKL”;

/* Enter 2 */

int n = 11700519;

s = “ZAYEXIWOVU”;

/* Enter 3 */

int n = 3072997;

s = “SOUGHT”;

/* Enter 4 */

int n = 1234567;

s = “THEQUICKFROG”;

Output results:

Problem 2: Maximum clique: the complete subgraph with the largest number of vertices in an undirected graph G

Complete graph: There are edges between any two vertices

 

Input:

(1) n vertices, number 1… n

(2) M undirected edges

Output:

The number of vertices of the maximum clique

Input sample:

5 6 // The first row n m: n vertices, m edges

1 2 // Next m row (s, t) : there is an edge between vertex s and vertex t

2, 3,

2, 4

3, 4,

3 5

4, 5

Core code and comments:


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);

}
Copy the code

Enter 5, 6

1 2

2, 3,

2, 4

3, 4,

3 5

4, 5

Output: the result is correct