本文主要是介绍算法笔记，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

算法笔记

一些的小的注意事项

#include<bits/stdc++.h>//万能头文件

比赛时用double 别用float

ios::sync_with_stdio(false);//加速

int 大概到2*10^9；
long long 到9*10^18

读入一行
string s;
getline(cin,s);

10^6数组要设为全局变量

判断闰年
能被4整除，但不能被100整除，能被400整除
year%4==0&&year%100!=0||year%400==0;

#include<string.h>
memest(数组名，值，sizeof(数组名))；
 
const double PI=acos(-1.0);

算法初步

递归

//求斐波那契数列
//递归求斐波那契数列
//f(0)=1,f(1)=1,f(n)=f(n-1)+f(n-2);
#include<iostream>
using namespace std;
int f(int n)
{
    if(n==0||n==1)
        return 1;
    else
        return f(n-1)+f(n-2);
}
int main()
{
    int n;
    cin>>n;
    cout<<f(n)<<endl;
    return 0;
}

//n皇后问题
//n*n的国际象棋棋盘中放置n个皇后，两两均不在同一行、同一列，同一条对角线上，求合法的方案数
#include<iostream>
using namespace std;
const int maxn=11;
//数组P来存放当前的排列，hashTable记录整数x是否已经在P中
int n,P[maxn],hashTable[maxn]={false};
//当前处理排列的第index号位
int count=0;
void generateP(int index)
{
    if(index==n+1)//递归边界，已经处理完排列的1~n位,到达了这一定是合法的
    {
        count++;
        return;
    }
    for(int x=1;x<=n;x++)//枚举1~n,试图将x填入P[index]
    {
        if(hashTable[x]==false)//如果x不在p[0]~p[index-1]中  ，第x行还没有皇后
        {
            bool flag=true;
            for(int pre=1;pre<index;pre++)  //遍历之前的皇后
            {
                //第index列皇后的行号是x，第pre列皇后的行号是p[pre]
                if(abs(index-pre)==abs(x-P[pre]))
                {
                    flag=false;//与之前的皇后在一条对角线上了
                    break;
                }
            }
            if(flag)//可以放在第x行
            {
                P[index]=x;//放进去
                hashTable[x]=true;//第x行已被占用
                generateP(index+1);//再去处理第index+1行皇后
                hashTable[x]=false;//还原
            }
        }
    }


}
int main()
{
    cin>>n;
    generateP(1);//从第一行开始填
    cout<<count<<endl;
    return 0;
}

二分查找

//二分查找，在有序序列中查找元素
#include<iostream>
using namespace std;
int binarySearch(int a[],int left,int right,int x)
{
    int mid;
    while(left<=right)
    {
        mid=(left+right)/2;
        if(a[mid]==x)
            return mid;
        else if(a[mid]>x)
            right=mid-1;
        else
            left=mid+1;
    }
    return -1;
}
int main()
{
    int n;
    cin>>n;
    int a[100];
    for(int i=0;i<n;i++)
        cin>>a[i];
    int t=binarySearch(a,0,n-1,1);
    if(t!=-1)
        cout<<"查找位置下标为："<<t<<endl;
    else
        cout<<"没有找到"<<endl;
    return 0;
}

二分答案

//二分答案
//计算根号2
#include<iostream>
using namespace std;
const double eps=1e-5;
double f(double x)//计算一个函数
{
    return x*x;
}
double calSqrt()//二分查找
{
    double left=1,right=2,mid;
    while(right-left>eps)
    {
        mid=(left+right)/2;
        if(f(mid)>2)  
            right=mid;
        else
            left=mid;
    }
    return mid;
}
int main()
{
    printf("%.5f",calSqrt());
    return 0;
}

//木棒切割,n个木棒希望得到至少k段最长相同的木棍，求最大长度
#include<iostream>
#include<algorithm>
using namespace std;
int n,k;
int a[1000];
bool judge(int x)
{
    int cnt=0;
    for(int i=0;i<n;i++)
        cnt+=a[i]/x;//每个木棒可以分的段数
    return cnt>=k;
}
int main()
{
    cin>>n>>k;
    int r=1;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        r=max(r,a[i]);
    }
    int l=1;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(judge(mid))
            l=mid+1;
        else
            r=mid-1;
    }
    cout<<r<<endl;
}

快速幂

//快速幂，求a^b%m
#include<iostream>
using namespace std;
typedef long long ll;
ll binaryPow(ll a,ll b,ll m)
{
    ll ans=1;
    while(b>0)
    {
        if(b&1)
            ans=ans*a%m;
        a=a*a%m;
        b>>=1;
    }
    return ans;
}
int main()
{
    ll a,b,m;
    cin>>a>>b>>m;
    cout<<binaryPow(a,b,m)<<endl;
}

归并排序

//归并排序
#include<iostream>
using namespace std;
const int maxn=100;
void merge(int a[],int l1,int r1,int l2,int r2)
{
    int i=l1,j=l2;//左端点
    int temp[maxn],index=0;
    while(i<=r1&&j<=r2)
    {
        if(a[i]<a[j])
        {
            temp[index++]=a[i++];
        }
        else
            temp[index++]=a[j++];
    }
    while(i<=r1)
        temp[index++]=a[i++];
    while(j<=r2)
        temp[index++]=a[j++];
    for(i=0;i<index;i++)
        a[l1+i]=temp[i];
}
void mergeSort(int a[],int left,int right)
{
    if(left<right)
    {
        int mid=(left+right)/2;
        mergeSort(a,left,mid);
        mergeSort(a,mid+1,right);
        merge(a,left,mid,mid+1,right);
    }
}
int main()
{
    int n;
    cin>>n;
    int a[100];
    for(int i=0;i<n;i++)
        cin>>a[i];
    mergeSort(a,0,n-1);
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    return 0;
}

快速排序

//快排代码
#include<iostream>
using namespace std;
int Partition(int a[],int s,int t)//一趟排序，找到基准的位置
{
	int i=s,j=t;
	int tmp=a[s];//选择序列的第一个元素作为基准
	while(i!=j)//从两端交替向中间扫描，直到i=j
	{
		while(j>i&&a[j]>=tmp)//右边的数比基准大的话，右边的数就继续走，直到遇到一个元素比基准小
			j--;
		a[i]=a[j];//把这个比基准小的元素放在当前基准的位置上
		while(j>i&&a[i]<=tmp)//左边的数比基准小的话，左边的数就继续向右走，直到遇到一个元素比基准大
			i++;
		a[j]=a[i];//把这个比基准大的元素放在刚刚空出来的位置上
	}
	a[i]=tmp;//最后那个位置放原来的基准，左边的数都比基准小，右边的数都比基准大
	return i;
}
void QuickSort(int a[],int s,int t)
{
    if(s<t)
    {
        int i=Partition(a,s,t);
        QuickSort(a,s,i-1);//左子序列排序
        QuickSort(a,i+1,t);//右子序列排序

    }
}
int main()
{
    int n;
    cin>>n;
    int a[100];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    QuickSort(a,0,n-1);
    cout<<"排序结果为："<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<a[i]<<" ";
    }
    return 0;
}

/*求解一个整数数组划分为两个子数组的问题：分成两个数组个数相差最少，和相差最大
用快速排序的思想，一次排序找到基准点，左边的都比它小，右边的都比它大，分情况排序
*/
#include<iostream>
#include<cmath>
using namespace std;
int n;
int Partition(int a[],int s,int t)//一趟排序，找到基准的位置
{
	int i=s,j=t;
	int tmp=a[s];//选择序列的第一个元素作为基准
	while(i!=j)//从两端交替向中间扫描，直到i=j
	{
		while(j>i&&a[j]>=tmp)//右边的数比基准大的话，右边的数就继续走，直到遇到一个元素比基准小
			j--;
		a[i]=a[j];//把这个比基准小的元素放在当前基准的位置上
		while(j>i&&a[i]<=tmp)//左边的数比基准小的话，左边的数就继续向右走，直到遇到一个元素比基准大
			i++;
		a[j]=a[i];//把这个比基准大的元素放在刚刚空出来的位置上
	}
	a[i]=tmp;//最后那个位置放原来的基准，左边的数都比基准小，右边的数都比基准大
	return i;
}
int solve(int a[],int n)
{
	int low=0,high=n-1;
	int flag=1;
	while(flag)
	{
		int i=Partition(a,low,high);//基准的位置
		if(i==n/2-1)//如果基准的位置是中心位置，就跳出循环
			flag=false;
		else if(i<n/2-1)//如果当前基准的位置在中间位置的左边，就排右边的部分
			low=i+1;
		else
			high=i-1;//如果当前基准的位置在中间位置的右边，就排左边的部分
	}
	int s1=0,s2=0;
	for(int i=0;i<n/2;i++)//算左半部分的和
		s1+=a[i];
	for(int j=n/2;j<n;j++)//算右半部分的和
		s2+=a[j];
	return s2-s1;
 }
int main()
{
	cin>>n;
	int a[100];
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	cout<<"两个子数组相差最大为："<<endl;
	cout<<solve(a,n);
 }

数学问题

欧几里得算法

//欧几里得算法求解最大公约数
#include<iostream>
using namespace std;
int gcd(int a,int b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
int main()
{
    int m,n;
    while(cin>>m>>n)
    {
        cout<<gcd(m,n)<<endl;
    }
    return 0;
}

//求最小公倍数，最小公倍数是两个数的乘积除以最大公约数
#include<iostream>
using namespace std;
int gcd(int a,int b)
{
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
int main()
{
    int m,n;
    while(cin>>m>>n)
    {
        cout<<m/gcd(m,n)*n<<endl;//防止溢出
    }
    return 0;
}

判断素数

//判断素数
#include<iostream>
#include<cmath>
using namespace std;
bool isPrime(int n)
{
    if(n<=1)
        return false;
    int sqr=(int)sqrt(1.0*n);
    for(int i=2;i<=sqr;i++)
    {
        if(n%i==0)
            return false;
    }
    return true;
}
int main()
{
    int n;
    cin>>n;
    if(isPrime(n))
        cout<<"是素数"<<endl;
    else
        cout<<"不是素数"<<endl;
}

//筛法求素数
#include<iostream>
using namespace std;
const int maxn=101;
int prime[maxn],pNum=0;
bool p[maxn]={0};
void Find_Prime()
{
    for(int i=2;i<maxn;i++)//从i到100
    {
        if(p[i]==false)//i是素数，没有被筛去的话就计数，并且筛去他的倍数
          {
              prime[pNum++]=i;
              for(int j=i+i;j<maxn;j+=i)
              {
                  p[j]=true;
              }
          }
    }
}
int main()
{
    Find_Prime();
    for(int i=0;i<pNum;i++)
    {
        cout<<prime[i]<<" ";
    }
    return 0;
}

//分解质因数
#include<iostream>
#include<cmath>
using namespace std;
const int maxn=100010;
bool is_prime(int n)//判断素数
{
    if(n<=1)
        return false;
    int sqr=(int)sqrt(1.0*n);
    for(int i=2;i<=sqr;i++)
    {
        if(n%i==0)
            return false;
    }
    return true;
}
int prime[maxn],pNum=0;
void Find_Prime()//求素数表
{
    for(int i=2;i<maxn;i++)
    {
        if(is_prime(i)==true)
            prime[pNum++]=i;
    }
}
struct factor{
    int x,cnt;
}fac[10];
int main()
{
    Find_Prime();
    int n,num=0;
    cin>>n;
    if(n==1)
        cout<<"1=1"<<endl;
    else
    {
        cout<<n<<"=";
        int sqr=(int)sqrt(1.0*n);
        for(int i=0;i<pNum&&prime[i]<=sqr;i++)
        {
            if(n%prime[i]==0)
            {
                fac[num].x=prime[i];
                fac[num].cnt=0;
                while(n%prime[i]==0)
                {
                    fac[num].cnt++;
                    n/=prime[i];
                }
                num++;
            }
            if(n==1)
                break;
        }
        if(n!=1)
        {
            fac[num].x=n;
            fac[num++].cnt=1;
        }
         for(int i=0;i<num;i++)
         {
             if(i>0)
                cout<<"*";
            cout<<fac[i].x;
             if(fac[i].cnt>1)
             {
                 cout<<"^"<<fac[i].cnt;
             }
         }

    }
}

高精度加法

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
int a[510],b[510],c[510];
int main()
{
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));//都赋初值
    string str1,str2;
    cin>>str1>>str2;//读入数据
    int len1=str1.size();
    int len2=str2.size();//取长度
    reverse(str1.begin(),str1.end());//翻转一下,方便下面读入
    reverse(str2.begin(),str2.end());
    for(int i=0;i<len1;i++)//先算个位，所以低位放在低位
    {
        a[i]=str1[i]-'0';//注意要“-0”
    }
    for(int i=0;i<len2;i++)
    {
        b[i]=str2[i]-'0';
    }
    int d=0;//进位
    int maxlen=len1>len2? len1:len2;
    for(int i=0;i<maxlen;i++)
    {
        int t=a[i]+b[i]+d;
        c[i]=t%10;
        d=t/10;
    }
    if(d>0)
    {
        c[maxlen]=1;
        maxlen++;
    }
    for(int i=maxlen-1;i>=0;i--)
    {
        cout<<c[i];
    }
    return 0;
}

n!质因子的个数

//求解n!中有多少个质因子p
#include<iostream>
using namespace std;
int cal(int n,int p)
{
	if(n<p)
		return 0;
	return n/p+cal(n/p,p);
}
int main()
{
	int n,p;
	cin>>n>>p;
	cout<<cal(n,p);
    return 0;
 }

求组合数

//求组合数c(n,m)
#include<iostream>
using namespace std;
long long C(long long n,long long m)
{
    long long ans=1;
    for(long long i=1;i<=m;i++)
    {
        ans=ans*(n-m+i)/i;
    }
    return ans;
}
int main()
{
    int n,m;
    cin>>n>>m;
    cout<<C(n,m);
    return 0;
}

搜索

dfs深度优先搜索

深度为第一关键词，当碰到岔道口的时候总是先选择其中一条岔路前进，不管其他岔路，直到遇到死胡同才返回岔道口，选择其他岔路。

/*01背包问题
从n件物品中选择若干件物品放入背包，使他们的价值和最大*/
#include<bits/stdc++.h>
using namespace std;
const int maxn=30;
int n,v,maxvalue=0;
int w[maxn],c[maxn];
void dfs(int index,int sumw,int sumc)
{
    if(index==n)
    {
        if(sumw<=v&&sumc>maxvalue)
        {
            maxvalue=sumc;
        }
        return;
    }
    dfs(index+1,sumw,sumc);
    dfs(index+1,sumw+w[index],sumc+c[index]);
}
int main()
{
    cin>>n>>v;//商品数和背包容量
    for(int i=0;i<n;i++)
    {
        cin>>w[i];//每件商品的价值
    }
    for(int i=0;i<n;i++)//每件商品的重量
    {
        cin>>c[i];
    }
    dfs(0,0,0);
    cout<<maxvalue<<endl;//最大的价值
    return 0;
}

//右剪枝
#include<bits/stdc++.h>
using namespace std;
const int maxn=30;
int n,v,ans=0;
int w[maxn],c[maxn];
void dfs(int index,int sumw,int sumc)
{
    if(index==n)
    {
        return;
    }
    dfs(index+1,sumw,sumc);//不选第index件物品
    if(sumw+w[index]<=v)
    {
        if(sumc+c[index]>ans)
            ans=sumc+c[index];
         dfs(index+1,sumw+w[index],sumc+c[index]);//选择第index件物品
    }

}
int main()
{
    cin>>n>>v;//商品数和背包容量
    for(int i=0;i<n;i++)
    {
        cin>>w[i];//每件商品的价值
    }
    for(int i=0;i<n;i++)//每件商品的重量
    {
        cin>>c[i];
    }
    dfs(0,0,0);
    cout<<ans<<endl;//最大的价值
    return 0;
}

bfs广度优先搜索

BFS模板
void BFS(int s)
{
    queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        取出队首元素top;
        访问队首元素top;
        将队首元素出队；
        将top的下一层结点中未曾入队的结点全部入队，并设置为已入队。
    }
}

/*
6 7
0 1 1 1 0 0 1
0 0 1 0 0 0 0
0 0 0 0 1 0 0
0 0 0 1 1 1 0
1 1 1 0 1 0 0
1 1 1 1 0 0 0
1的块数为4
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn=100;
struct node{
    int x,y;
}Node;
int n,m;
int matrix[maxn][maxn];
bool inq[maxn][maxn]={false};//记录位置x,y是否已经入过队
int X[4]={0,0,1,-1};
int Y[4]={1,-1,0,0};
bool judge(int x,int y)
{
    //是否越界
    if(x>=n||x<0||y>=m||y<0)
        return false;
    //当前位置为0,或者已经入过队了
    if(matrix[x][y]==0||inq[x][y]==true)
        return false;
    return true;
}
//访问（x,y)所在的块，将该块的inq置1，全部入队
void bfs(int x,int y)
{
    queue<node> Q;
    Node.x=x;
    Node.y=y;
    Q.push(Node);
    inq[x][y]=true;
    while(!Q.empty())
    {
        node top=Q.front();
        Q.pop();
        for(int i=0;i<4;i++)
        {
            int newX=top.x+X[i];
            int newY=top.y+Y[i];
            if(judge(newX,newY))
            {
                Node.x=newX;
                Node.y=newY;
                Q.push(Node);
                inq[newX][newY]=true;
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int x=0;x<n;x++)
    {
        for(int y=0;y<m;y++)
        {
            cin>>matrix[x][y];
        }
    }
    int ans=0;
    for(int x=0;x<n;x++)
    {
        for(int y=0;y<m;y++)
        {
            if(matrix[x][y]==1&&inq[x][y]==false)
            {
                ans++;
                bfs(x,y);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

这篇关于算法笔记的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！