？？

二分查找pro

#include<iostream>
using namespace std;
int n,x,a[1005],l,r,m;
int main(){
    cin>>n;
    for(int i=1;i<n-1;i++){
        cin>>a[i];
    }
    cin>>x;
    l=0;
    r=n-1;
    while(l<=r){
        m=(l+r)/2;
        if(a[m]==x){
            cout<<m<<"\n";
            return 0;
        }
        if(a[m]<x){
            l=m+1;
        }
        else{
            r=m-1;
        }
    }
    cout<<"-1\n";
} 

sort排序

#include<bits/stdc++.h>
using namespace std;
/*sort排序*/
int main(){
    int n,a[1005];
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    for(int i=n-1;i>=0;i--){
        cout<<a[i]<<" ";
    }
} 

最长连续子序列

#include<iostream>
using namespace std;
/*
最长连续子序列
功能：找出数组中最长的连续递增子序列的长度
原理：遍历数组，记录当前连续递增的长度，更新最大长度
例如：[1,3,5,4,7,8,9]中最长连续递增子序列为[4,7,8,9]
输出：4（长度为4）
*/
int main(){
    int n,a[1005],m=1,c=1;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        if(a[i]>a[i-1]){
            c++;
            if(c>m){
                m=c;
            }
        }
        else{
            c=1;
        }
    }
    cout<<m<<"\n";
} 

最大子数组和

#include<iostream>
using namespace std;
/*
最大子数组和
功能：找出数组中和最大的连续子数组的和
原理：遍历数组，维护当前和，如果当前和小于0则重新开始
例如：[-2,1,-3,4,-1,2,1,-5,4]的最大子数组和为6
过程：连续子数组[4,-1,2,1]的和为6，是最大的
*/
int main(){
    int n,a[1005],s=0,m=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        if(s>0){
            s+=a[i];
        }
        else{
            s=a[i];
        }
        if(s>m){
            m=s;
        }
    }
    cout<<m<<"\n";
} 

数字统计

#include<iostream>
using namespace std;
/*
数字统计
功能：统计一个数的所有数位中指定数字出现的次数
原理：不断取出个位数，与目标数字比较，计数
例如：统计12345中数字3出现的次数
过程：12345 -> 5不是3 -> 4不是3 -> 3是 -> 2不是3 -> 1不是3
输出：1（出现1次）
*/
int main(){
    int n,x,c=0;
    cin>>n>>x;
    while(n>0){
        if(n%10==x){
            c++;
        }
        n=n/10;
    }
    cout<<c<<"\n";
} 

二分查找

#include<iostream>
using namespace std;
/*
二分查找
功能：在有序数组中查找目标值的位置
原理：每次将区间分成两半，比较中间值与目标值的大小来缩小查找范围
时间复杂度：O(logn)
例如：在[1,2,3,4,5]中查找4
过程：中间值3<4，往右半部分[4,5]找，中间值4=4，找到
*/
int main(){
    int n,x,a[1005],l,r,m;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    cin>>x;
    l=0;
    r=n-1;
    while(l<=r){
        m=(l+r)/2;
        if(a[m]==x){
            cout<<m<<"\n";
            return 0;
        }
        if(a[m]<x){
            l=m+1;
        }
        else{
            r=m-1;
        }
    }
    cout<<"-1\n";
} 

最小公倍数(LCM)

#include<iostream>
using namespace std;
/*
最小公倍数(LCM)
功能：求两个数的最小公倍数
原理：两数乘积除以最大公约数即为最小公倍数
例如：lcm(12,18) = 12*18/gcd(12,18) = 216/6 = 36
*/
int main(){
    int a,b,c,m;
    cin>>a>>b;
    m=a*b;
    while(b>0){
        c=a%b;
        a=b;
        b=c;
    }
    cout<<m/a<<"\n";
} 

最大公约数（辗转相除法/欧几里得算法）

#include<iostream>
using namespace std;
/*
最大公约数（辗转相除法/欧几里得算法）
功能：求两个数的最大公约数(GCD)
原理：gcd(a,b) = gcd(b,a%b)，当b=0时，a即为最大公约数
例如：gcd(12,18) = 6
*/
int main(){
    int a,b,c;
    cin>>a>>b;
    while(b>0){
        c=a%b;
        a=b;
        b=c;
    }
    cout<<a<<"\n";
} 

组合数计算 C(n,m)

#include<iostream>
using namespace std;
/*
组合数计算 C(n,m)
功能：计算从n个不同元素中取m个元素的组合数
原理：C(n,m) = A(n,m)/A(m,m) = n!/(m!*(n-m)!)
例如：C(5,3) = 5!/(3!*2!) = (5*4*3)/(3*2*1) = 10
注意：结果可能很大，注意数据范围
*/
int main(){
    int n,m,a=1,b=1;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        a=a*(n-i+1);
        b=b*i;
    }
    cout<<a/b<<"\n";
} 

选择排序

#include<iostream>
using namespace std;
/*
选择排序
功能：将n个数从小到大排序
原理：每次从未排序部分找到最小值，放到已排序部分的末尾
时间复杂度：O(n^2)
例如：[5,3,4,1,2] -> [1,3,4,5,2] -> [1,2,4,5,3] -> [1,2,3,5,4] -> [1,2,3,4,5]
*/
int main(){
    int n,a[1005],c,m;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n-1;i++){
        m=i;
        for(int j=i+1;j<n;j++){
            if(a[j]<a[m]){
                m=j;
            }
        }
        c=a[i];
        a[i]=a[m];
        a[m]=c;
    }
    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }
    cout<<"\n";
} 

完数判断

#include<iostream>
using namespace std;
/*
完数判断
功能：判断一个数是否是完数
原理：一个数等于它所有真因子（不包括自身的因子）之和
例如：6的真因子有1,2,3，1+2+3=6，所以6是完数
输出：是完数输出1，否则输出0
*/
int main(){
    int n,s=0;
    cin>>n;
    for(int i=1;i<n;i++){
        if(n%i==0){
            s=s+i;
        }
    }
    if(s==n){
        cout<<"1\n";
    }
    else{
        cout<<"0\n";
    }
} 

桶排序

#include<iostream>
using namespace std;
/*
桶排序
功能：将n个数从小到大排序
原理：统计每个数出现的次数，按顺序输出对应次数的数
时间复杂度：O(n+m)，m为数据范围
例如：[2,3,2,1,3] -> [1出现1次,2出现2次,3出现2次] -> [1,2,2,3,3]
*/
int main(){
    int n,a[1005],b[1005]={0},c;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>c;
        b[c]++;
    }
    for(int i=0;i<1005;i++){
        while(b[i]>0){
            cout<<i<<" ";
            b[i]--;
        }
    }
    cout<<"\n";
} 

水仙花数判断

#include<iostream>
using namespace std;
/*
水仙花数判断
功能：判断一个数是否是水仙花数
原理：一个n位数等于其各位数字的n次方之和
例如：153 = 1^3 + 5^3 + 3^3 = 1 + 125 + 27 = 153
输出：是水仙花数输出1，否则输出0
*/
int main(){
    int n,t,m,s;
    cin>>n;
    t=n;
    s=0;
    while(t>0){
        m=t%10;
        s=s+m*m*m;
        t=t/10;
    }
    if(s==n){
        cout<<"1\n";
    }
    else{
        cout<<"0\n";
    }
} 

排列数计算 A(n,m)

#include<iostream>
using namespace std;
/*
排列数计算 A(n,m)
功能：计算从n个不同元素中取m个元素的排列数
原理：A(n,m) = n*(n-1)*(n-2)*...*(n-m+1)
例如：A(5,3) = 5*4*3 = 60
注意：结果可能很大，注意数据范围
*/
int main(){
    int n,m,a=1;
    cin>>n>>m;
    for(int i=n;i>n-m;i--){
        a=a*i;
    }
    cout<<a<<"\n";
} 

冒泡排序

#include<iostream>
using namespace std;
/*
冒泡排序
功能：将n个数从小到大排序
原理：相邻元素比较，每轮将最大值移到末尾，像冒泡一样上浮
时间复杂度：O(n^2)
例如：[5,3,4,1,2] -> [3,4,1,2,5] -> [3,1,2,4,5] -> [1,2,3,4,5]
*/
int main(){
    int n,a[1005],c;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n-1-i;j++){
            if(a[j]>a[j+1]){
                c=a[j];
                a[j]=a[j+1];
                a[j+1]=c;
            }
        }
    }
    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }
    cout<<"\n";
} 

快速排序（非递归实现）

#include<iostream>
using namespace std;
/*
快速排序（非递归实现）
功能：将n个数从小到大排序
原理：选择基准值将数组分成两部分，小于基准值的放左边，大于的放右边
时间复杂度：O(nlogn)
例如：[5,3,4,1,2] -> 以5为基准 -> [3,4,1,2,5] -> 以3为基准 -> [1,2,3,4,5]
*/
int main(){
    int n,a[1005],l,r,c,i,j;
    cin>>n;
    for(i=0;i<n;i++){
        cin>>a[i];
    }
    l=0;
    r=n-1;
    int p[1005],t=0;
    p[t++]=l;
    p[t++]=r;
    while(t>0){
        r=p[--t];
        l=p[--t];
        i=l;
        j=r;
        c=a[l];
        while(i<j){
            while(i<j && a[j]>=c) j--;
            if(i<j) a[i++]=a[j];
            while(i<j && a[i]<=c) i++;
            if(i<j) a[j--]=a[i];
        }
        a[i]=c;
        if(l<i-1){
            p[t++]=l;
            p[t++]=i-1;
        }
        if(i+1<r){
            p[t++]=i+1;
            p[t++]=r;
        }
    }
    for(i=0;i<n;i++){
        cout<<a[i]<<" ";
    }
    cout<<"\n";
} 

阶乘计算

#include<iostream>
using namespace std;
/*
阶乘计算
功能：计算n的阶乘（n!）
原理：n个正整数的乘积，n!=n*(n-1)*(n-2)*...*2*1
例如：5! = 5*4*3*2*1 = 120
注意：n不能太大，否则会溢出
*/
int main(){
    int n,m=1;
    cin>>n;
    for(int i=1;i<=n;i++){
        m=m*i;
    }
    cout<<m<<"\n";
} 

回文素数判断

#include<iostream>
using namespace std;
/*
回文素数判断
功能：判断一个数是否是真正的回文素数
原理：这个数是素数，且它的回文数也是素数（不包括回文数本身）
例如：113的回文数是311，两个都是素数，所以113是真正的回文素数
输出：是真正的回文素数输出1，否则输出0
*/
int main(){
    int n,m,t,k,p;
    cin>>n;
    k=1;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            k=0;
            break;
        }
    }
    if(n==1){
        k=0;
    }
    if(k==1){
        t=n;
        m=0;
        while(t>0){
            m=m*10+t%10;
            t=t/10;
        }
        if(m==n){
            cout<<"0\n";
        }
        else{
            p=1;
            for(int i=2;i*i<=m;i++){
                if(m%i==0){
                    p=0;
                    break;
                }
            }
            if(m==1){
                p=0;
            }
            cout<<p<<"\n";
        }
    }
    else{
        cout<<"0\n";
    }
} 

回文数判断

#include<iostream>
using namespace std;
/*
回文数判断
功能：判断一个数是否是回文数
原理：将数字翻转后与原数相同
例如：12321翻转后还是12321，所以是回文数
输出：是回文数输出1，否则输出0
*/
int main(){
    int n,m,t;
    cin>>n;
    t=n;
    m=0;
    while(t>0){
        m=m*10+t%10;
        t=t/10;
    }
    if(m==n){
        cout<<"1\n";
    }
    else{
        cout<<"0\n";
    }
} 

分割排序

#include<iostream>
using namespace std;
/*
分割排序（选择排序的一种变体）
功能：将n个数从小到大排序
原理：每次将当前位置的数与后面所有数比较，找到更小的就交换
时间复杂度：O(n^2)
例如：[5,3,4,1,2] -> [1,2,3,4,5]
*/
int main(){
    int n,a[1005],b[1005],c;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            if(a[i]>a[j]){
                c=a[i];
                a[i]=a[j];
                a[j]=c;
            }
        }
    }
    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }
    cout<<"\n";
} 

斐波那契数列

#include<iostream>
using namespace std;
/*
斐波那契数列
功能：计算第n个斐波那契数
原理：每个数是前两个数的和，f(n)=f(n-1)+f(n-2)，f(1)=f(2)=1
例如：n=5
过程：1,1,2,3,5
结果：5
*/
int main(){
    int n,a=1,b=1,c;
    cin>>n;
    if(n<=2){
        cout<<"1\n";
    }
    else{
        for(int i=3;i<=n;i++){
            c=a+b;
            a=b;
            b=c;
        }
        cout<<c<<"\n";
    }
} 

翻转数字

#include<iostream>
using namespace std;
/*
翻转数字
功能：将一个整数的各位数字顺序翻转
原理：不断取出个位数(n%10)，原数去掉个位(n/10)，新数乘10加上个位
例如：1234 -> 4321
过程：1234 -> 4 -> 43 -> 432 -> 4321
注意：末尾是0的数字翻转后会丢掉0
*/
int main(){
    int n,m=0;
    cin>>n;
    while(n>0){
        m=m*10+n%10;
        n=n/10;
    }
    cout<<m<<"\n";
} 

插入排序

#include<iostream>
using namespace std;
/*
插入排序
功能：将n个数从小到大排序
原理：将每个数插入到已排序部分的合适位置，类似打牌时整理牌
时间复杂度：O(n^2)
例如：[5,3,4,1,2] -> [3,5,4,1,2] -> [3,4,5,1,2] -> [1,3,4,5,2] -> [1,2,3,4,5]
*/
int main(){
    int n,a[1005],c,j;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        c=a[i];
        j=i-1;
        while(j>=0 && a[j]>c){
            a[j+1]=a[j];
            j--;
        }
        a[j+1]=c;
    }
    for(int i=0;i<n;i++){
        cout<<a[i]<<" ";
    }
    cout<<"\n";
}