Euler枚举

1.E22：Name score

在文本文件names.txt 中包含了五千多个名字，

首先将它们按照字母序排列，然后计算出每个名字的字母价值，乘以它在按字母顺序排列后的位置，就算出了这个名字的得分。

例如，按照字母序排列后，位于第938位的名字是COLIN，它的字母价值是3 + 15 + 12 + 9 + 14 = 53

因此，COLIN这个名字的得分是 938 × 53 = 49714.

上述文本文件中，所有名字的得分之和是多少？

1.暴力枚举

  1. 将name.txt文件下载下来，进行初步处理%s/","/ /g（将连接符替换为空格分隔）、%s/"/ /g（处理开头结尾的单引号）
  2. 将名字输入保存到name[6005]数组中
  3. 首先使用sort算法对name数组进行排序
  4. 外循环遍历name数字中的每一个名字，内循环遍历name的每一个字母计算每个名字的价值value
  5. 输出最后累加的score分数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

string name[6005];
int n;

int main(){
    while(cin >> name[n]){
        n++;
    }
    sort(name, name + n);
    long long score = 0;
    for(int i = 0; i < n; ++i){
        int value = 0;//name的价值
        for(int j = 0; j < name[i].size(); ++j){
            value += name[i][j] - 'A' + 1;
        }
        score += value * (i + 1);
    }
    cout << score << endl;
    return 0;
}

image-20220414122455987

补充：txt.name文件重定向输入操作./a.out < input22

2.E32：Pandigital products

如果一个n位数包含了1至n的所有数字恰好一次，我们称它为全数字的；例如，五位数15234就是1至5全数字的。

7254是一个特殊的乘积，因为在等式39 × 186 = 7254中，被乘数、乘数和乘积恰好是1至9全数字的。

找出所有被乘数、乘数和乘积恰好是1至9全数字的乘法等式，并求出这些等式中乘积的和。

注意：有些乘积可能从多个乘法等式中得到，但在求和的时候只计算一次。（需要对乘积去重）

1.暴力枚举

两层for循环不断尝试乘数与被乘数（乘积确定），动态判定结果是否符合全数字要求、乘积是否重复出现，符合则计入ans

  1. 枚举的范围：

    外层for循环范围，至少应从2开始（若为1乘数与成积重复必不为全数字），至多到98结束（3位数乘积将达到6位数必不符合）

    内层for循环范围，应该从j=i+1开始（乘数与被乘数重复），可暂时设置为死循环（在循环体中当i、j、i*j位数和大于9结束）

  2. 对于全数字的判断

    开辟一个mark[10]标记数组，将被判断的数字拆分存入标记数组中，查看当遍历结束时标记数组中是否全为1（如果满足则+=ans）

  3. 对于乘积相同的等式重复判断

    开辟一个check[10005]标记数组，如果乘积第1次出现则计入累加，否则乘积重复不记入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<iostream>
#include<cmath>
using namespace std;

//1.求数字位数
int digit(int x){
    return floor(log10(x)) + 1;
}

//2.检验每一位数字是否重复
int work(int *mark, int num){
    while(num){
        int temp = num % 10;//取num的最后一位
        if(mark[temp] == 1){
            return 0;//如果数字曾经出现过则直接return 0
        }
        mark[temp] = 1;//数字没有出现过将其标记值设为1
        num /= 10;
    }
    return 1;
}

//3.检查数字是否为全数字
int func(int x, int y, int z){
    int mark[10] = {0};//mark为标记数组，用于检查数字是否重复
    if(work(mark, x) && work(mark, y) && work(mark, z) && mark[0] == 0){
        return 1;//如果3个数字都不冲突,且数字当中没有0则返回1
    }
    return 0;
}

int main(){
    int ans = 0, check[10005] = {0};
    for(int i = 2; i < 99; ++i){
        for(int j = i + 1; 1; ++j){
            int a = digit(i), b = digit(j), c = digit(i * j);
            if(a + b + c > 9){
                //1.a+b+c>9不可能是答案直接退出循环
                break;
            }
            if(a + b + c == 9){
                //2.a+b+c==9对数字进行进一步验证
                if(func(i, j, i * j)){
                    //利用func检查是否符合全数字
                    cout << i << " " << j << " = " << i * j << endl;
                    if(check[i * j] == 0){
                        //利用check进行重复检查
                        check[i * j] = 1;
                        ans += i * j;
                    }
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

image-20220414190537912

总结感悟：对于枚举法最重要的是确定枚举的范围，以及符合条件的结果判断

3.E33：Digit cancelling fractions

49/98是一个有趣的分数，缺乏经验的数学家可能在约简时错误地认为等式49/98 = 4/8

之所以成立是因为在分数线上下同时抹除了9的缘故。

我们也会想到，存在诸如30/50 = 3/5这样的平凡解。

这类有趣的分数恰好有四个非平凡的例子，它们的分数值小于1，且分子和分母都是两位数。

将这四个分数的乘积写成最简分数，求此时分母的值。

1.暴力枚举

  1. 枚举范围：外层for循环范围11~99，内层for循环范围i+1-99
  2. 对于非凡解的判定：将约去同一数字后的分数与约去前的分数交叉相乘，若相等则为非凡解（对于平凡解的去除，任一数字不为0）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
using namespace std;

//1.判断分数是否为不平凡解
int func(int x, int y){
    int x1 = x / 10, x2 = x % 10, y1 = y / 10, y2 = y % 10;//将两位数进行拆解
    if(!x1 || !x2 || !y1 || !y2){
        return 0;//如果数字中含有0则一定为平凡解return 0
    }
    if(x1 == y1 && x * y2 == y * x2) return 1;
    if(x1 == y2 && x * y1 == y * x2) return 1;
    if(x2 == y1 && x * y2 == y * x1) return 1;
    if(x2 == y2 && x * y1 == y * x1) return 1;
    return 0;
}

//2.辗转相除求a与b的最大公约数
int gcd(int a, int b){
    if(b == 0){
        return a;
    }
    return gcd(b, a % b);
}

int main(){
    int a = 1, b = 1;
    for(int i = 11; i < 100; ++i){
        for(int j = i + 1; j < 100; ++j){
            if(func(i, j)){
                //如果j\i为不平凡的解，则打印例子
                cout << i << " / " << j << endl;
                a *= i;
                b *= j;
            }
        }
    }
    int temp = gcd(a, b);//temp为a与b的最大公约数
    a /= temp;
    b /= temp;
    cout << a << " / " << b << endl;
    return 0;
}

image-20220414201406574

注意：熟练辗转相除法求最大公因数

4.E36：Double-base palindromes

十进制数585 = 10010010012（二进制表示），因此它在这两种进制下都是回文数。

找出所有小于一百万，且在十进制和二进制下均为回文的数，并求它们的和。

（请注意无论在哪种进制下，回文数均不考虑前导零。）

1.暴力枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
using namespace std;

//判断是否为回文数
int func(int num, int x){
    int raw = num;
    int temp = 0;//最后的temp值为回文数
    while(num){
        temp = temp * x + num % x;
        num /= x;
    }
    return temp == raw;
}

int main(){
    int ans = 0;
    for(int i = 1; i < 1000000; ++i){
        if(func(i, 10) && func(i, 2)){
            cout << i << endl;
            ans += i;
        }
    }
    cout << ans << endl;
    return 0;
}

image-20220416185523357

5.E30：Digit fifth powers

令人惊讶的是，只有三个数可以写成其各位数字的四次幂之和：

1634 = 1^4 + 6^4 + 3^4 + 4^4
8208 = 8^4 + 2^4 + 0^4 + 8^4
9474 = 9^4 + 4^4 + 7^4 + 4^4

由于1 = 1^4 并不是求和，所以这里不计入内。

上面这三个数的和是1634 + 8208 + 9474 = 19316

找出所有可以写成其各位数字的五次幂之和的数，并求这些数的和。

1.暴力枚举

  1. 枚举范围如何确定？

    首先考虑时间效率优化，对于1-9的五次幂可以先计算存储到一个数组中（避免每次重复计算，提升时间效率）

    利用关系（该数字 = 其各位数字的五次幂之和）确定枚举范围，

    假设该数字的位数为n，则有该数字取值为[1-10n)，五次幂之和的取值范围为[n * 05, n * 9n]

    故另10n = n * 9n则可以解出该数字位数n的最大值，从而确定枚举范围（n的取值大致为5~6之间，==枚举范围取6==）

  2. 符合要求答案的条件：各位数字的五次幂之和等于该数字，则符合题目条件进行累加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
using namespace std;

int penta[15];

void init(){
    for(int i = 1; i < 10; ++i){
        int temp = 1;
        for(int j = 0; j < 5; ++j){
            temp *= i;
        }
        penta[i] = temp;
        cout << i << ":" << penta[i] << " " << endl;
    }
}

int func(int num){
    int raw = num;
    int temp = 0;
    while(num){
        temp += penta[num % 10];
        num /= 10;
    }
    return temp == raw;
}

int main(){
    init();
    int ans = 0;
    for(int i = 2; i < 1000000; ++i){
        if(func(i)){
            ans += i;
            cout << i << endl;
        }
    }
    cout << ans << endl;
    return 0;
}

image-20220416214233422

相似题：E34-Digit factorials

2.总结：

刷题总结：对于数字num进行==各位5次幂求和==的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int penta[15];
void init(){
    for(int i = 1; i < 10; ++i){
        int temp = 1;
        for(int j = 0; j < 5; ++j){
            temp *= i;
        }
        penta[i] = temp;
        cout << i << ":" << penta[i] << " " << endl;
    }
}
//与回文数字判断代码相似
int func(int num){
    int raw = num;
    int temp = 0;
    while(num){
        temp += penta[num % 10];
        num /= 10;
    }
    return temp == raw;
}