[数据结构与算法]写给大一小白的算法练习一

大一的小伙伴进入大学也已经有2个多月，C/C++语言能力肯定增强了不少了，然而遇到一些需要思考的题目就可能力不从心了，以下几道题选自我校部分期中卷，有优化也有思考，给你展现不一样的C/C++语言。

[声明]：本人用C++习惯了，所以部分语法可能对小白来说优点困难。就这样说吧，cout<<相当于printf，cin>>相当于scanf，因为不需要格式化所以还是很方便的。

你的三连就是我创作的最大动力，后期还会有我校去年期末卷的讲解代码与蓝桥杯选拔赛题目嗷，敬请关注。

开灯问题（优化算法）

题目描述
有n盏灯，编号为1~n，第一个人把所有灯打开，第二个人按下所有编号为2的倍数开关(这些灯将被关掉)，第三个人按下所有编号为3的倍数的开关(其中关掉的灯将被打开，开着的灯将被关闭)，一次类推，一共有k个人，问最后哪些灯开着？

输入：
7 3

输出：
1 5 6 7

先上暴力法，时间复杂度为O(n*k),很好理解，就是先让灯状态为0，然后遇到公倍数就取反,核心算法就是a[i]=!a[i]

#include <iostream>
#include <cstring>

using namespace std;

int main(){
    int a[1005];
    int n,k;
    cin>>n>>k;
    memset(a,0,sizeof(a));
    for(int i=1;i<=k;i++){
        for(int j=1;j<=n;j++){
            if(j%i==0) a[j]=!a[j];
        }
    }
    for(int i=1;i<=n;i++){
        if(a[i]) cout<<i<<" ";
    }
    cout<<endl;
    return 0;
}

但是学习过数据结构了，对于时间复杂度是比较敏感的，所以又对此进行优化。怎么优化呢？
观察发现，将n个数从k开始划分2半，首先思考第一半：每盏灯都会被“1”操作一次，也会被自身的值操作一次，这两次相互抵消。对于灯i，如果存在一个i的约数j，那么一定存在另外一个约数k，如果j != k ，那么这两次相互抵消，如果j == k，那么只有一个这样的值，不会被抵消，这样只有存在完全约数（比如:4 = 22 , 9 = 33类的）的灯才不会被抵消，所以我们要求的就是具有完全约数的值。所以我们在k之前的数字只要判断值的开方是不是整数就可以了，然后输出是整数的数就可以了，在k之后的数字我们只需要判断被开方数不是整数就输出就好了。
时间复杂度仅为k(或者n-k)

#include <iostream>
#include <cmath>

using namespace std;

bool IntNext(int x){
    int m=(int)sqrt(x);
    return m*m==x?true:false;
}

int main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=k;i++){
        if(IntNext(i)) cout<<i<<" ";
    }
    for(int i=k+1;i<=n;i++){
        if(!IntNext(i)) cout<<i<<" ";
    }
    cout<<endl;
    return 0;
}

公因数公倍数问题

这个大一小白肯定是训练了不少，暴力法啊，或者辗转相除啊，等等。这里就给出一行代码求公因数，可以学习，也比较简单。
这里给出了欧几里得算法和更相减损法，比较容易理解。
关于欧几里得与更相减损法的证明如下：此次

#include <iostream>

using namespace std;

//辗转相除法
int gcd(int n,int m){
    return n%m==0?m:gcd(m,n%m);
}

//更相减损法
int gcd2(int n,int m){
    if(n==m) return n;
    else if(n<m) return gcd2(m-n,n);
    else return gcd2(n-m,m);
}

int main(){
    int n,m,N,M;
    cin>>n>>m;//n大
    cout<<gcd(n,m)<<endl;
    cout<<gcd2(n,m)<<endl;
    return 0;
}

素数

关于素数的知识还是比较重要的，这次考试也是有涉及，这里不多废话，给出我以前写的blog，大家可以学习。
就是分解质因数的题目。

点击此次有详细解析嗷
后期还有更多干货哦！