When using the exhaustive method to solve a problem, the range of the exhaustive can be determined most of the time, that is, the problem to be solved has a clear interval limit, and the solution that meets the constraint conditions can be searched in a loop within the specified range.

[Example 2] Digital grid

There are 3 squares, and each square has an integer a1, a2, a3. It is known that 0 <= a1, a2, a3 <= n, and a1 + a2 is a multiple of 2, a2 + a3 is a multiple of 3, and a1 + a2 + a3 is a multiple of 5. Write a program, enter n (0 <= n <= 100), find a group of a1, a2, a3, so that a1 + a2 + a3 is the largest.

(1) Programming ideas.

Use a 3-fold loop to directly exhaust the a1, a2, and a3 in the range of 0 ~ n. In the inner loop, check whether the constraints ((a1 + a2)% 2 == 0) && ((a2 + a3)% 3 == 0) && ((a1 + a2 + a3)% 5 == 0) are satisfied, If yes, then see if you need to update the value of max (the initial value of max can be set to 0).

(2) Source program and operation result.

#include <iostream>

using namespace std;

int main ()

{

int a1, a2, a3, n, max, x, y, z;

max = 0;

cin >> n;

for (a1 = 0; a1 <= n; a1 ++)

for (a2 = 0; a2 <= n; a2 ++)

for (a3 = 0; a3 <= n; a3 ++)

{

if (((a1 + a2)% 2 == 0) && ((a2 + a3)% 3 == 0) && ((a1 + a2 + a3)% 5 == 0))

{

if ((a1 + a2 + a3)> max)

{

max = a1 + a2 + a3;

x = a1; y = a2; z = a3;

}

}

}

cout << "Max =" << max << endl;

cout << "a1 =" << x << ", a2 =" << y << ", a3 =" << z << endl;

return 0;

}

(3) Problem expansion.

The above program can find the maximum value of a1 + a2 + a3, and the value of a1, a2, and a3 when the maximum value is reached. But in fact, for a given n, when a1 + a2 + a3 reaches the maximum value, there may be multiple value combinations of a1, a2, and a3. For example, when n = 5, the maximum value of a1 + a2 + a3 is 10, and when the maximum value is reached, the value combinations of a1, a2, and a3 that meet the requirements are (1, 5, 4), (4, 2, 4) ) And (4, 4, 2). Can you expand the program and export all the combinations?

To save all combinations, a two-dimensional array can be defined in the program. When max is updated, the array is updated.

(4) Expand the source program and operation results of the problem.

#include <iostream>

using namespace std;

int main ()

{

int a1, a2, a3, n, i, max, cnt;

int a [100] [3];

max = 0; cnt = 0;

cin >> n;

for (a1 = 0; a1 <= n; a1 ++)

for (a2 = 0; a2 <= n; a2 ++)

for (a3 = 0; a3 <= n; a3 ++)

{

if (((a1 + a2)% 2 == 0) && ((a2 + a3)% 3 == 0) && ((a1 + a2 + a3)% 5 == 0))

{

if ((a1 + a2 + a3)> max)

{

cnt = 0; max = a1 + a2 + a3;

a [cnt] [0] = a1; a [cnt] [1] = a2; a [cnt] [2] = a3;

}

else if ((a1 + a2 + a3) == max)

{

cnt ++;

a [cnt] [0] = a1; a [cnt] [1] = a2; a [cnt] [2] = a3;

}

}

}

cout << "Max =" << max << endl;

for (i = 0; i <= cnt; i ++)

cout << "(" << a [i] [0] << "," << a [i] [1] << "," << a [i] [2] << ")" << endl;

return 0;

}

[Example 3] Guess the age

American mathematician N. Wiener was precocious and went to college at the age of 11. Once, he attended an important meeting, and his young face was striking. So someone asked his age and he replied: "The cube of my age is a 4-digit number. The fourth power of my age is a 6-digit number. These 10 numbers contain exactly 10 numbers from 0 to 9, They happen to happen once. "

Please calculate, what's his age then?

(1) Programming ideas.

Because the cube of 10 is the smallest 4-digit number, and the cube of 23 is 12167, which is a 5-digit number, age can be exhausted between 10-22.

Define an array int a [10] to store the occurrence of the numbers 0-9, and assign an initial value of 0 each time it is exhausted. For each age i, calculate the cube num1 and fourth power num2 of i, and then decompose the numbers of num1 and num2, and set the array element a [k] = 1 accordingly. Set it multiple times, it does not meet the requirements.

(2) Source program and operation result.

#include <iostream>

using namespace std;

int main ()

{

int a [10], i, k, num1, num2;

for (i = 10; i <22; i ++)

{

num1 = i * i * i;

num2 = i * i * i * i;

for (k = 0; k <= 9; k ++) a [k] = 0;

while (num1! = 0)

{

if (a [num1% 10] == 0)

{

a [num1% 10] = 1;

num1 = num1 / 10;

}

else

break;

}

while (num2! = 0) {

if (a [num2% 10] == 0) {

a [num2% 10] = 1;

num2 = num2 / 10;

}

else

break;

}

if (num1 == 0 && num2 == 0)

cout << i << endl;

}

return 0;

}

[Example 4] Abacus Mental Arithmetic Test

Abacus and Mental Arithmetic is a computing technique that performs fast calculations by simulating abacus changes in the brain. Abacus mental arithmetic training can develop intelligence and bring a lot of convenience to daily life, so it is popular in many schools.

The abacus and mental arithmetic teacher of a school uses a test method to quickly check the abacus and mental arithmetic addition ability. He randomly generates a set of positive integers with no more than 100 elements. The number of numbers in the set does not exceed 1000, and they are different. Then he asks the students to answer: how many of them are exactly equal to the other two in the set ( Different) sum of numbers?

For example, for the set {1, 2, 3, 4, 5}, the output should be 3. Because 3 = 1 + 2, 4 = 2 + 2 = 1 + 3, 5 = 1 + 4 = 2 + 3, a total of 3 numbers.

(1) Programming ideas.

Define an array int flag [2001] to record the occurrence of sum. Element values are all 0 at the beginning.

Add and sum each two different numbers in the set, and mark the sum. For example, if the number a and the number b are equal to the number c, then flag = 1 is set.

After that, scan the number x in all the collections, and count the number of all marked numbers (that is, flag [x] == 1).

(2) Source program and operation result.

#include <iostream>

using namespace std;

int main ()

{

int n, i, j, x, a [101], flag [2001] = {0}, cnt;

cout << "Please enter the number of data elements in the set to be generated:";

cin >> n;

i = 0;

while (i <n)

{

x = rand ()% 1000 + 1;

if (flag [x] == 0)

{

a [i ++] = x;

flag [x] = 1;

}

}

cout << "The randomly generated" << n << "integers are as follows:" << endl;

for (i = 0; i <n; i ++)

cout << a [i] << "";

cout << endl;

for (i = 0; i <= 2000; i ++)

flag [i] = 0;

for (i = 0; i <n-1; i ++)

for (j = i + 1; j <n; j ++)

flag [a [i] + a [j]] = 1;

cnt = 0;

for (i = 0; i <n; i ++)

if (flag [a [i]] == 1) cnt ++;

cout << "Count =" << cnt << endl;

return 0;

}

[Example 5] Magical formula

A multiplication formula composed of 4 different numbers, and their product is still composed of these 4 numbers. For example: 210 × 6 = 1260, 8 × 473 = 3784, and 27 × 81 = 2187 all meet the requirements.

If the expressions satisfying the multiplication commutative law are counted as the same situation, how many expressions satisfy the requirements?

(1) Programming ideas.

Use exhaustive method to solve. The exhaustive objects are the product and the smaller multiplier. The product is a 4-digit number with a value ranging from 1023 to 9876 and the multiplier value ranges from 2 to 98.

There are two constraints that need to be detected in the loop body: 1) each of the four digits of the product must not be repeated; 2) these four digits appear and appear only twice. These constraints can be handled using a tag array used [10]. The initial value of the used array is all 0. When the number i is used, set used [i] = 1. If the number i is used again, at this time used [i] is equal to 1 again, it can be determined that the constraints are not satisfied.

(2) Source program and operation result.

#include <iostream>

using namespace std;

int check (int x, int y, int used [10])

{

int i, tmp [10] = {0};

do {

tmp [x% 10] ++;

} while (x / = 10);

do {

tmp [y% 10] ++;

} while (y / = 10);

for (i = 0; i <10; i ++)

if (tmp [i]! = used [i])

return 0;

return 1;

}

int check4 (int x, int used [10])

{

do {

if (used [x% 10]! = 0)

return 0;

used [x% 10] ++;

} while (x / = 10);

return 1;

}

int main ()

{

int a, b, c, i, cnt = 0, used [10];

for (c = 1023; c <= 9876; c ++)

{

for (i = 0; i <10; i ++)

used [i] = 0;

if (! check4 (c, used))

continue;

for (a = 2; a <= 98; a ++)

{

if (c% a! = 0)

continue;

b = c / a;

if (a> b)

continue;

if (! check (a, b, used))

continue;

cout << a << "*" << b << "=" << c << endl;

cnt ++;

}

}

cout << "Count =" << cnt << endl;

return 0;

}

[Example 6] Exclusive square number

Xiao Ming is looking at the number 203879 in a daze.

It turns out that 203879 * 203879 = 41566646641

What's so magical about this? Looking closely, 203879 is a 6-digit number, and the digits at each digit are different, and all the digits after its squaring do not appear to form its own number.

Please find all 6 digits with such characteristics.

(1) Programming ideas.

Exhaust 6 digits, the lower limit of the interval is 123456 and the upper limit is 987654.

Define the array used [10] to record the usage of the numbers 0-9, separate the exhaustive 6-digit bits x, and set used [x] ++. If each used [x] is greater than 2, the number x is repeated Appears, unsatisfactory, for the next exhaustive.

In addition, because the result of multiplying two 6-digit numbers is beyond the representation range of integer numbers, two array elements are used to store the product. When calculating the square of a 6-digit i, express i as a * 10000 + b, so that the square of i is equal to a * a * 100000000 + 2 * a * b * 10000 + b * b, and save it with the array element x [1] The lower 8 bits, use x [0] to save the upper 8 bits, the specific method is:

x [1] = x [1] + c% 10000 * 10000;

x [0] = x [0] + c / 10000;

x [0] = x [0] + x [1] / 100000000;

x [1] = x [1]% 100000000;

Then check whether the number k of each bit in x [0] and x [1] has appeared, that is, whether the corresponding used [k] is 1.

(2) Source program and operation result.

#include <iostream>

using namespace std;

int check (int x, int used [10])

{

do {

if (used [x% 10]> 0)

return 0;

else

used [x% 10] ++;

) while (x / = 10);

return 1;

}

int checkpower (int x [], int used [10])

{

do {

if (used [x [0]% 10]> 0) {

return 0;

}

} while (x [0] / = 10);

for (int i = 1; i <= 8; i ++)

{

if (used [x [1]% 10]> 0)

return 0;

x [1] = x [1] / 10;

}

return 1;

}

int main ()

{

int i, a, b, c, x [2];

int k, used [10];

for (i = 123456; i <= 987654; i ++)

{

for (k = 0; k <= 9; k ++)

used [k] = 0;

if (! check (i, used))

continue;

a = i / 10000; b = i% 10000;

x [0] = a * a; x [1] = b * b;

c = 2 * a * b;

x [1] = x [1] + c% 10000 * 10000;

x [0] = x [0] + c / 10000;

x [0] = x [0] + x [1] / 100000000;

x [1] = x [1]% 100000000;

if (! checkpower (x, used))

continue;

cout << i << endl;

}

return 0;

}