计算机科学与技术

C++算法1

一维前缀和

1
2
3
4
5
6
7
8
9
//现有数组
a={a[0],a[1],a[2]....a[n]};

s[0]=a[0];
s[1]=a[0]+a[1];
s[2]=a[0]+a[1]+a[2]
.........
//s[]为a[]的前缀和数组

程序示例

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>
using namespace std;
int main(){
	
	int a[10];
	int s[10];
	
	//输入数组 
	for(int i=0;i<10;i++){
		cin>>a[i];
	}
	
	//求一维前缀和 
	s[0]=a[0];
	for(int j=0;j<10;j++){
		s[j]=s[j-1]+a[j];
	}
	
	//输出一维前缀和 
	for(int k=0;k<10;k++){
		cout<<s[k]<<" "; 
	}	
	return 0;
}

二维前缀和

  • 使用s[i,j]来代表a[i,j]左上方的所有元素的和，那么它可以表示为s[i,j]=s[i,j-1]+s[i-1,j]-s[i-1,j-1]+a[i,j]
    代码展示
    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
    //二维前缀和
    #include<iostream>
    using namespace std;

    #define N 500
    #define M 500

    int main(){
    	int a[N][M];
    	int i,j;
    	int s[N][M];
    	//输入数组 
    	for(i=1;i<=3;i++){
    		for(j=1;j<=4;j++){
    			cin>>a[i][j];
    		}
    	}
    	
    	//求二维前缀和 
    	for(i=1;i<=3;i++){
    		for(j=1;j<=4;j++){
    			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
    			cout<<s[i][j]<<" ";
    	}
    		cout<<endl;
    	}
    	return 0;
    }

求最大公约数及最小公倍数

  1. 辗转相除法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int zhanzhuanchugcd(int a, int b)
    {
    	if(a%b==0){
    		return b;
    	}
    	else{
    		return zhanzhuangcd(b,a%b);
    	}
    }
    //保证a>b
    //判断a%b=0

  2. 辗转相减法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int zhanzhuanjiangcd(int a,int b)
    {
    	while(a!=b){
    		if(a>b){
    			a=a-b;
    		}
    		else{
    			b=b-a;
    		}
    	}
    	return b;
    }
    //判断 a==b

  3. 穷举法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int qiongju(int a,int b)
    {
    	int temp =0;
    	temp = a>b?b:a;
    	for(;;temp--){
    		if(a%temp==0&&b%temp==0)
    			break;
    	}
    	return temp;	
     }

  4. 最小公倍数 = a*b/gcd(a,b)