编程能力提升

男娘i 2022-12-24 14:50 182阅读 0赞

参考:[https://doublelll3.ml/mbss\_1\_%E7%BC%96%E7%A8%8B%E8%83%BD%E5%8A%9B%E6%8F%90%E5%8D%87/][https_doublelll3.ml_mbss_1_E7_BC_96_E7_A8_8B_E8_83_BD_E5_8A_9B_E6_8F_90_E5_8D_87]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0MjM0MDg3_size_16_color_FFFFFF_t_70][]

# Project Euler:Problem 1 3或5的倍数 #

在小于10的自然数中，3或5的倍数有3、5、6和9，这些数之和是23。

求小于1000的自然数中所有3或5的倍数之和。

## 解法1： ##

遍历1-1000，判断能不能被3或5整除，可以就加入sum  
时间复杂度：O(N)

#include <iostream>
    using namespace std;
    
    int main() {
        int sum;
        for (int i = 1; i < 1000; i++) {
            if(i % 3 == 0 || i % 5 == 0) {
                sum += i;
            }
        }
    
        cout << sum << endl;
        return 0;
    }

##  解法2： ##

直接计算3或5倍数的和  
利用等差数列，要注意有重复计算  
公式：（首项 + 末项） \* 项数 / 2  
3~999的3的倍数和 + 5~1000的5的倍数和 - 15~985的15的倍数和  
时间复杂度：O(1)

#include <iostream>
    using namespace std;
    
    int main() {
    
        int sum;
        int sum3 = (3 + 999) * 333 / 2;
        int sum5 = (5 + 995) * 199 / 2;
        int sum15 = (15 + 990) * 66 / 2;
        sum = sum3 + sum5 - sum15;
    
        cout << sum << endl;
        return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0MjM0MDg3_size_16_color_FFFFFF_t_70 1][]

# Project Euler:Problem 2 偶斐波那契数 #

斐波那契数列中的每一项都是前两项的和。由1和2开始生成的斐波那契数列的前10项为：

1,2,3,5,8,13,21,34,55,89,…

考虑该斐波那契数列中不超过四百万的项，求其中为偶数的项之和。

普通解法：用一个数组存储前面的值，递推，当是偶数时加入sum  
空间复杂度：O(N)，需要大量的额外空间  
更优解：用两个变量来回倒  
a、b：每次迭代，b = b + a; a = b - a;  
空间复杂度：O(1)

#include <iostream>
    using namespace std;
    
    int main() {
    
        int a = 1, b = 2, sum = 0;
        while(b <= 4000000){
            if(b % 2 ==0){
                sum += b;
            }
            b = b + a;
            a = b - a;
        }
        cout << sum << endl;
        return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0MjM0MDg3_size_16_color_FFFFFF_t_70 2][]

# **Project Euler:Problem 4 最大回文乘积** #

回文数就是从前往后读和从后往前读都一样的数。由两个2位数相乘得到的最大的回文数是 9009=91×99。

求由两个3位数相乘得到的最大的回文数。

判断回文数的思路  
两个指针分别从头尾对应判等  
更方便：把数字反过来，再做判等  
枚举所有的3位数相乘，判断回文数，找最大

#include<iostream>
    using namespace std;
    
    int func(int x) {
        int t = 0, raw = x;
        while(x) {
            t = t * 10 + x % 10;
            x /= 10;
        }
        return t == raw;
    }
    
    int main() {
        int ans = 0;
        for (int i = 100; i < 1000; i++) {
            for (int j =i; j < 1000; j++) {
                int t = i * j;
                if (func(t)) {
                    ans = max(ans, t);
                }
            }
        }
        cout << ans << endl;
        return 0;
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0MjM0MDg3_size_16_color_FFFFFF_t_70 3][]

# Project Euler:Problem 6 平方的和与和的平方之差 #

前十个自然数的平方的和是

![1^2+2^2+\\ldots +10^2=385][1_2_2_2_ldots _10_2_385]

前十个自然数的和的平方是

![(1+2+\\ldots+10)^2 = 55^2 = 3025][1_2_ldots_10_2 _ 55_2 _ 3025]

因此，前十个数的平方的和与和的平方之差是3025−385=2640。

求前一百个数的平方的和与和的平方之差。

分别计算1~100的平方和、和，再用和的平方 - 平方和即可

#include<iostream>
    using namespace std;
    
    int main() {
        int sum = 0, psum = 0;
        for (int i = 1; i <= 100; i++) {
            sum += i;
            psum += i * i;
        }
        cout << sum * sum - psum << endl;
        return 0;
    }

![图片][6d672faa0b744b5f13704c41f61f7e86.png]

# Project Euler:Problem 8 连续数字最大乘积 #

在如下的1000位数中，连续四个数字的最大乘积是![9 \\times 9 \\times 8 \\times 9 = 5832][9 _times 9 _times 8 _times 9 _ 5832]

73167176531330624919225119674426574742355349194934

96983520312774506326239578318016984801869478851843

85861560789112949495459501737958331952853208805511

12540698747158523863050715693290963295227443043557

66896648950445244523161731856403098711121722383113

62229893423380308135336276614282806444486645238749

30358907296290491560440772390713810515859307960866

70172427121883998797908792274921901699720888093776

65727333001053367881220235421809751254540594752243

52584907711670556013604839586446706324415722155397

53697817977846174064955149290862569321978468622482

83972241375657056057490261407972968652414535100474

82166370484403199890008895243450658541227588666881

16427171479924442928230863465674813919123162824586

17866458359124566529476545682848912883142607690042

24219022671055626321111109370544217506941658960408

07198403850962455444362981230987879927244284909188

84580156166097919133875499200524063689912560717606

05886116467109405077541002256983155200055935729725

71636269561882670428252483600823257530420752963450

下方数据已经去掉格式

7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450

求这个1000位数中连续十三个数字的最大乘积。

思路  
首先将数据复制，保存在本地为字符串  
检查复制后的格式：删掉空格、换行  
读入时用数组存储，读取每位时需转换为数字即- '0'  
滑动窗口法  
静态窗口：固定窗口大小  
动态窗口：一般称为双指针  
解法：使用滑动窗口法——静态窗口  
只需考虑窗口进的数和出的数，可以减少运算次数  
出：除以  
进：乘以  
注意值是否为0

#include<iostream>
    using namespace std;
    
    char num[1005];
    long long ans, zero_cnt, now = 1;    //此处必须使用long long，使用int时数据会超出int上届
    
    int main() {
        cin >>  num;
        for (int i = 0; i < 1000; i++) {
            if (i < 13) {    //观察数据，前13位不存在0；
                now *= num[i] - '0';    //-'0'的作用：将字符转化为数字
            } else {
                if (num[i] == '0') {    //入口，为0时zero_cnt++
                    zero_cnt++;
                } else {
                    now *= num[i] - '0';    //入口，不为0时将数据乘进now
                }
                if (num[i - 13] == '0') {    //出口,为0时zero_cnt--
                    zero_cnt--;
                } else {
                    now /= num[i - 13] - '0';    //出口，不为0时将数据踢出now
                }
    
            }
            if (zero_cnt == 0){    //只有在窗口中没有0时才会更新答案
                ans = max(ans, now);
            }
        }
        cout << ans << endl;
        return 0;
    }

*  前13位不含0，可以直接计算now
 *  注意窗口内0的情况
    
     *  ❗定义一个0的计数器
     *  ❌是否可以碰见0就将乘积变为1？
        
         *  不行，需**要存**除除0以外数的乘积
     *  ❌是否可以将0直接变为1？可以减少判断次数，只需要对进来的值判断0
        
         *  但这样是不可以的，因为有可能不满13位的两个0之间的数很大
         *  比如11022340111111111111111111
 *  执行时报错：floating point exception
    
     *  除以0了可能会导致该错误
 *  错误地估计了上界，9^13肯定超过了int类型的上界，所以使用long long

# Problem 11 #

# #

## ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0MjM0MDg3_size_16_color_FFFFFF_t_70 4][] ##

## **方阵中的最大乘积** ##

在如下的20×20方阵中，有四个呈对角线排列的数被标红了。

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08  
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00  
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65  
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91  
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80  
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50  
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70  
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21  
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72  
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95  
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92  
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57  
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58  
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40  
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66  
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69  
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36  
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16  
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54  
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

这四个数的乘积是26 × 63 × 78 × 14 = 1788696。

在这个20×20方阵中，四个在同一方向（从下至上、从上至下、从右至左、从左至右或者对角线）上相邻的数的乘积最大是多少？

[https_doublelll3.ml_mbss_1_E7_BC_96_E7_A8_8B_E8_83_BD_E5_8A_9B_E6_8F_90_E5_8D_87]: https://doublelll3.ml/mbss_1_%E7%BC%96%E7%A8%8B%E8%83%BD%E5%8A%9B%E6%8F%90%E5%8D%87/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0MjM0MDg3_size_16_color_FFFFFF_t_70]: /images/20221120/2d6e1ba93de442bfb459cdd068f8f8e8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0MjM0MDg3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201129214402179.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0MjM0MDg3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0MjM0MDg3_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201129214724800.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0MjM0MDg3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0MjM0MDg3_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201129222326572.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0MjM0MDg3,size_16,color_FFFFFF,t_70
[1_2_2_2_ldots _10_2_385]: https://private.codecogs.com/gif.latex?1%5E2&plus;2%5E2&plus;%5Cldots%20&plus;10%5E2%3D385
[1_2_ldots_10_2 _ 55_2 _ 3025]: https://private.codecogs.com/gif.latex?%281&plus;2&plus;%5Cldots&plus;10%29%5E2%20%3D%2055%5E2%20%3D%203025
[6d672faa0b744b5f13704c41f61f7e86.png]: https://img-blog.csdnimg.cn/img_convert/6d672faa0b744b5f13704c41f61f7e86.png
[9 _times 9 _times 8 _times 9 _ 5832]: https://private.codecogs.com/gif.latex?9%20%5Ctimes%209%20%5Ctimes%208%20%5Ctimes%209%20%3D%205832
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0MjM0MDg3_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201129231848787.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0MjM0MDg3,size_16,color_FFFFFF,t_70