博客详情 - XJYOJ

pengsizhe's blog
课堂笔记
彭思哲 (pengsizhe) LV 6 @ 2023-8-19 9:10:30

一维数组的排序

#include <bits/stdc++.h>
using namespace std;
int main() {

    // 3、一维数组的排序
    
    int n;
    cin >> n;

    const int MAXSIZE = 100 + 1;
    int arr[MAXSIZE];
    memset(arr, 0, sizeof(arr));

    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    
    // (1) 冒泡排序
    
    for (int i = 1; i <= n; i++) {
        for (int j = n; j > i; j--) {
            if (arr[j] < arr[j - 1]) { // < 升序，> 降序 
                swap(arr[j], arr[j - 1]);
            }
        } 
    }

    // (2) 冒泡排序（优化，用于接近完成的序列） 
    
    bool exchange;
    for (int i = 1; i <= n; i++) {
        exchange = false;
        for (int j = n; j > i; j--) {
            if (arr[j] < arr[j - 1]) { // < 升序，> 降序 
                swap(arr[j], arr[j - 1]);
                cout << "swap : " << arr[j] << " <-> " << arr[j - 1] << endl;
                exchange = true;
            }
        } 
        if (!exchange) break;
    }  

    // (3) 选择排序
    
    for (int i = 1; i < n; i++) {
        for (int j = i; j <= n; j++) {
            if (arr[i] > arr[j]) { // 确定擂主 
                swap(arr[i], arr[j]);
            }
        }
    }

    // (3) 插入排序
    
    for (int i = 1; i <= n; i++) {
        for (int j = i; j > 1; j--) {
            if (arr[j] < arr[j - 1]) {
                swap(arr[j], arr[j - 1]);
            }
        }
    }  

    for (int i = 1; i <= n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    // (4) 计数排序
    
    int n;
    cin >> n;
    const int MAXSIZE = 100 + 1;
    int arr[MAXSIZE];
    memset(arr, 0, sizeof(arr));   
     
    int num; 
    for (int i = 1; i <= n; i++) {
        cin >> num;
        arr[num]++;
    }
    
    // 去重输出 
    for (int i = 1; i <= MAXSIZE; i++) {
        if (arr[i] > 0) {
            cout << i << " ";
        }
    }
    cout << endl;
    
    // 重复元素输出 
    for (int i = 1; i <= MAXSIZE; i++) {
        while (arr[i] > 0) {
            cout << i << " ";
            arr[i]--;
        }
    }     
    cout << endl;

    // (5) sort 排序 
     
    int n;
    cin >> n;
    const int MAXSIZE = 100 + 1;
    int arr[MAXSIZE];
    memset(arr, 0, sizeof(arr));
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
     
    sort(arr + 1, arr + 1 + n); // 升序排序 
    
    sort(arr + 1, arr + 1 + n, greater<int>()); // 降序排序 
    
    for (int i = 1; i <= n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;  
    
    int cnt = unique(arr + 1, arr + 1 + n) - (arr + 1); // 去重 , 并返回去重后的数量 

    for (int i = 1; i <= cnt; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;  
	
	return 0;
}

一维数组的查找

#include <bits/stdc++.h>
using namespace std;

int main() {
	
    // 2、一维数组的查找
    
    int n;
    cin >> n;

    int key = 108;

    int arr[100 + 1];
    memset(arr, 0, sizeof(arr)); 

    // 数组的批量读入
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    
    // (1) 顺序查找 
    
    bool found = false;
    for (int i = 1; i <= n; i++) {
        if (arr[i] == key) {
            found = true;
        }
    }
    if (found) {
        cout << "found" << endl;
    } else {
        cout << "not found" << endl;
    }
    
    // (2) 二分法查找
    
    bool found = false;
    int left = 1;
    int right = n;
    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        if (key == arr[mid]) {
            found = true;
            break;
        } else if (key < arr[mid]) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    if (found) {
        cout << "found" << endl;
    } else {
        cout << "not found" << endl;
    }   

	return 0;
}

一位数组的基本操作

#include <bits/stdc++.h>
using namespace std;

int main() {
	
	// (1) 一维数组的基本操作
	
	const int MAXSIZE = 1000; 	// 定义常量 
	int arr[MAXSIZE + 1]; 		// 定义数组 
//	int arr[1000 + 1]; 			// 也可以 
//	vector<int> vec; 			// 向量(变长数组) 

	memset(arr, 0, sizeof(arr)); // 数组置零 

	// 数组的引用 
	arr[0] = 102;  
	arr[1] = 105;
	arr[2] = 104;
	cout << arr[0] + arr[1] + arr[2] << endl;
	
	int n;
	cin >> n;
	
	// 从 1 号 下标 (索引 index) 使用数组
	
	// 批量读入 
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	
	// 批量处理（排序） 
	sort(arr + 1, arr + 1 + n);  // 对 1 ~ n 号 元素 进行排序 
	
	// 批量输出 
	for (int i = 1; i <= n; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
	
	// 从 0 号 下标 (索引 index) 使用数组
	
	// 批量读入 
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	 
	// 批量处理（排序）  
	sort(arr, arr + n);  // 对 0 ~ n - 1 号 元素 进行排序 
	
	// 批量输出 
	for (int i = 0; i < n; i++) {
		cout << arr[i] << " ";
	}
	cout << endl;
	
	return 0;
}

自定义函数

#include <bits/stdc++.h>
using namespace std;

void hello() {
	cout << "Hello,World!" << endl;	
}

int MAX(int x, int y) {
	if (x > y) {
		return x;
	} else {
		return y;
	}
}

bool prime(int n) {
	if (n < 2) {
		return false;
	} else {
		int nn = sqrt(n);
		for (int i = 2; i <= nn; i++) {
			if (n % i == 0) {
				return false;
			} 
		}
	}
	return true;
}

int main() {
	
	hello();
	
	int a, b;
	cin >> a >> b;
	cout << MAX(a, b) << endl;
	
	int n;
	cin >> n;
	
	cout << prime(n) << endl;
	
	if (prime(n)) {
		cout << "true" << endl; 
	} else {
		cout << "false" << endl; 
	}
	
	cout << (prime(n) ? "true" : "false" ) << endl;
	
	return 0;
}

哥德巴赫猜想

#include <bits/stdc++.h>
using namespace std;

bool prime(int n) {
	if (n < 2) {
		return false;
	} else {
		int nn = sqrt(n);
		for (int i = 2; i <= nn; i++) {
			if (n % i == 0) {
				return false;
			} 
		}
	}
	return true;
}

int main() {

	// 哥德巴赫猜想：任一大于2的偶数都可写成两个质数之和

	int cnt = 0;
	for (int n = 4; n <= 1000; n += 2) {
		for (int i = 2; i < n - 1; i++) {
			if (prime(i) && prime(n - i)) {
				cout << n << "=" << i << "+" << n - i << endl;
				cnt++;
				break;
			}
		}
	} 
	cout << "cnt = " << cnt << endl;
	 
	return 0;
}

打擂台算法

using namespace std;
int main() {
	int n, num, maxNum = INT_MIN, minNum = INT_MAX;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> num;
		if (maxNum < num) {
			maxNum = num;
		}
		if (minNum > num) {
			minNum = num;
		}
	}
	cout << maxNum - minNum << endl;
	return 0;
}

数学专题

#include <bits/stdc++.h>
using namespace std;

bool prime(int n) {
	if (n < 2) {
		return false;
	} else {
		int nn = sqrt(n);
		for (int i = 2; i <= nn; i++) {
			if (n % i == 0) {
				return false;
			} 
		}
	}
	return true;
}

int main() {
	
	// 数学专题
	
	// 穷举法 求所有公因数
	 
	int a, b;
	cin >> a >> b;
	if (a > b) swap(a, b);
	for (int i = 1; i <= a; i++) {
		if (a % i == 0 && b % i == 0) {
			cout << i << endl;
		}
	} 
	
	// 穷举法 求最大公因数
	
	for (int i = a; i >= 1; i--) {
		if (a % i == 0 && b % i == 0) {
			cout << i << endl;
			break;
		}		
	} 
	
	// 辗转相除法 求最大公因数
	
	int a, b, c;
	cin >> a >> b;
	if (a < b) swap(a, b); 
	c = a % b;
	while (c > 0) {
		a = b;
		b = c;
		c = a % b;
	}
	cout << b << endl;
	
	// 穷举法 求最小公倍数
	
	int a, b;
	cin >> a >> b;
	if (a > b) swap(a, b);
	for (int i = b; i <= a * b; i++) {
		if (i % a == 0 && i % b == 0) {
			cout << i << endl;
			break;
		}
	}
	
	// 穷举法优化 求最小公倍数 
	
	int a, b;
	cin >> a >> b;
	if (a > b) swap(a, b);
	for (int i = b; i <= a * b; i = i + b) {
		if (i % a == 0 && i % b == 0) {
			cout << i << endl;
			break;
		}
	}	 
	
	// 借助最大公约数的终极优化
	
	lcm(a, b) = (a * b) / gcd(a, b);
	
	
	// 判断质数(素数) （穷举大法） 
	
	int n;
	cin >> n;
	bool isPrime = true;
	if (n < 2) {
		isPrime = false;
	} else {
		for (int i = 2; i < n; i++) {
			if (n % i == 0) {
				isPrime = false;
				break;
			}
		} 	
	}
	if (isPrime) {
		cout << "Yes" << endl; 
	} else {
		cout << "No" << endl;
	}
	
	// 判断质数(素数) （优化） 
	
	int n;
	cin >> n;
	bool isPrime = true;
	if (n < 2) {
		isPrime = false;
	} else {
		int nn = sqrt(n); 
		for (int i = 2; i <= nn; i++) {
			if (n % i == 0) {
				isPrime = false;
				break;
			}
		} 	
	}
	if (isPrime) {
		cout << "Yes" << endl; 
	} else {
		cout << "No" << endl;
	}	
	
	// 哥德巴赫猜想：任一大于2的偶数都可写成两个质数之和
	int cnt = 0;
	for (int n = 4; n <= 1000; n += 2) {
		for (int i = 2; i < n - 1; i++) {
			if (prime(i) && prime(n - i)) {
				cout << n << "=" << i << "+" << n - i << endl;
				cnt++;
				break;
			}
		}
	} 
	cout << "cnt = " << cnt << endl;
	 
	return 0;
}

流程控制结构-循环结构嵌套

#include<bits/stdc++.h>
using namespace std;
int main() {
	// 4、循环结构嵌套
	
	//(1) 矩形星阵 
	
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cout << "*";
		}
		cout << endl;
	}
	
	// (2) 直角三角形星阵
	
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			cout << "*";
		}
		cout << endl;
	}	 
	
	// (3) 等腰三角形星阵
	
	int n;  
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int k = 1; k <= n - i; k++) {
			cout << " ";
		}
		for (int j = 1; j <= 2 * i - 1; j++) {
			cout << "*";
		}
		cout << endl;
	} 
		
	// (4) 倒置等腰三角形星阵
	
	int n;  
	cin >> n;
	for (int i = n; i >= 1; i--) {
		for (int k = 1; k <= n - i; k++) {
			cout << " ";
		}
		for (int j = 1; j <= 2 * i - 1; j++) {
			cout << "*";
		}
		cout << endl;
	} 
	
	// (5) 九九乘法表 
	
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			cout << j << "*" << i << "=" << i * j << " ";
		}
		cout << endl;
	}
	
	return 0;
}

流程控制结构-循环结构

#include<bits/stdc++.h>
using namespace std;
int main() {

	// 3、循环结构
	
	// (1) 前置条件循环 while () { } ; if () {} 
	
	int i = 1;
	// i = i + 1;
	while (i <= 9) {
		cout << "我要上天 " << i << " 重" << endl;
		i++;
	} 
	
	int j = 0;
	while (j < 18) {
		cout << "他要入地 " << j << " 层" << endl; 
		j++;
	}
	
	// 高斯求和： 1 + 2 + 3 + ... + 18

	// 1 = 0 + 1;
	// 3 = 1 + 2;
	// 6 = 3 + 3;
	// 10 = 6 + 4;
	
	int i = 1;   // 循环变量 初始化 
	int sum = 0;
	while (i <= 100) { // 循环条件 
		sum = sum + i;
		i++;     //  循环变量 渐变 
	}
	cout << sum << endl;
	
	
	// (2) 后置条件循环 do{ } while(); 
	
	int i = 1;
	do {
		cout << "我要上天 " << i << " 重" << endl;
		i++; 
	} while (i <= 9);
	
	int j = 0;
	do {
		cout << "他要入地 " << j << " 层" << endl;
		j++; 
	} while (j < 18);
	
	
	int i = 1;   // (1) 循环变量 初始化 
	int sum = 0;
	do {         // (2) 循环条件 
		sum = sum + i;
		i++;     // (3) 循环变量 渐变 
	} while (i <= 100);
	cout << sum << endl;
	
	// (3) 计数循环 for (循环变量初始化; 循环条件; 循环变量 渐变) { 代码块 }
		
	for (int i = 1; i <= 9; i++) {
		cout << "我要上天 " << i << " 重" << endl;
	}
	
	for (int j = 0; j < 18; j++) {
		cout << "他要入地 " << j << " 层" << endl;
	}
	
	
	int sum = 0;
	for (int i = 1; i <= 100; i++) {
		sum = sum + i;
	}
	cout << sum << endl;
	
	// (4) 无限循环 : while(true) {} , for (;;) {} 
	
	int num;
	int sum = 0;
	while (true) {
		cin >> num; 
		if (num == 0) {
			break;
		}
//		sum = sum + num;
		sum += num;
		
	}
	cout << sum << endl;
	// 无限循环 
	for (;;) {
		
	} 
	
	// (5) 循环语句 ： 
	
	// continue 跳过当前循环， 
	// break 停止后续所有循环 
	
	for (int i = 1; i <= 18; i++) {
		if (i == 4) continue;
		if (i == 14) continue;
		cout << "他要入地 " << i << " 层" << endl; 
	}
	
	// (6) 遍历循环 
	
	int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	for (auto num : arr) {
		cout << num << " ";
	} 
	cout << endl;
	
	string s = "Hello,World!";
	for (auto c : s) {
		cout << c << " ";
	}
	cout << endl;
	
	
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main() {
	
	// 1、顺序结构 
	int a, b, c;
	cin >> a >> b;
//	c = a; // c <- a
//	a = b; // a <- b
//	b = c; // b <- c
	swap(a, b);
	cout << a << " " << b << endl;	
	
	// 2、分支(选择)结构 
	
	// (1) 单分支结构：求整数的绝对值 
	int n;
	cin >> n;
	if (n < 0) { // true 成立 真 
		n = -n;
	}
	cout << n << endl; 

	// (2) 双分支结构：判断整数的奇偶性 
	int n;
	cin >> n;
	if (n % 2 == 0) {
		cout << "even" << endl;
	} else {
		cout << "odd" << endl;
	}
	
	if (n % 2) { // 0 : false 不成立, 非0 : true 成立 
		cout << "odd" << endl;
	} else {
		cout << "even" << endl;
	}
	
	// (3) 多分支 ：判断整数的正负性 
	int n;
	cin >> n;
	if (n > 0) {
		cout << "positive" << endl;
	} else if (n < 0) {
		cout << "negative" << endl;
	} else { 
		cout << "zero" << endl;
	}
	
//	 成绩等级判断
//	 A : 90 ~ 100
//	 B : 80 ~ 89
//	 C : 70 ~ 79
//	 D : 60 ~ 69
//	 E : 0 ~ 59 
	int n;
	cin >> n;
	if (n >= 90) {
		cout << "A" << endl;
	} else if (n >= 80) {
		cout << "B" << endl;
	} else if (n >= 70) {
		cout << "C" << endl;
	} else if (n >= 60) {
		cout << "D" << endl;
	} else {
		cout << "E" << endl;
	}
	
	// (4) 分支结构嵌套 ：三个整数比大小 
	int a, b, c;
	cin >> a >> b >> c;
	if (a > b) {
		if (a > c) {
			cout << a << endl;
		} else {
			cout << c << endl;
		}
	} else {
		if (b > c) {
			cout << b << endl;
		} else {
			cout << c << endl;
		}
	}
	// 使用 max 函数 
	cout << max(max(a, b), c) << endl;
	
	
	// (5) switch 开关分支结构: 星期判断 
	int n;
	cin >> n;
	switch(n) {
		case 1 :
			cout << "Monday" << endl;
			break;
		case 2 :
			cout << "Tuesday" << endl;
			break;
		case 3 :
			cout << "Wednesday" << endl;
			break;
		case 4 : 
			cout << "Thursday" << endl;
			break;
		case 5 :
			cout << "Friday" << endl;
			break;
		case 6 :
			cout << "Saturday" << endl;
			break;
		case 7 : 
			cout << "Sunday" << endl;
			break;
		default :
			cout << "Error" << endl;
			
	} 

	// (6) 三目运算符  ? :
	
	bool flag; // 1 : true, 0 : false
	cin >> flag;
	if (flag) {
		cout << "true" << endl;
	} else {
		cout << "false" << endl;
	}
	// 三目运算符 (简洁、省事) 
	cout << (flag ? "true" : "false") << endl;
	
	return 0;
}

常用缩写

// std : standard 标准 
	// ans : answer 答案
	// sum : summary 总和 
	// cnt : counter 计数器 
	// res : result 结果

编程四步骤

// (1) define 定义 
	// (2) input 输入 
	// (3) process 处理 
	// (4) output 输出

#include <bits/stdc++.h>
using namespace std;
int main() {
	
    // 1. 基本数据类型
    
    // (1) 整型数据类型

    // int 整型 (4个字节): -21亿 ~ 21亿 （10位数字）
    // long long 超长整型 (8个字节): -922亿亿 ~ 922亿亿 (19位数字) 
    long long a, b; 
    cin >> a >> b;
    cout << a + b << endl; 
    // char 字符型 (1个字节) ：-128 ~ 127 
    char c = 'A' + 15;
    cout << c << endl;
    cout << int(c) << endl; 
    // bool 逻辑型 (1个字节) ：-128 ~ 127 
    int n;
    cin >> n;
    bool flag = (n == 100); // true : 1, false : 0
    cout << flag << endl; 
	    
    // (2) 浮点数据类型
    
    // 123.456 : 0.123456 x 10的3次方 
    // float 单精度 (4个字节): 7位有效数字，正负10的38次方 
    // double 双精度 (8个字节): 17位有效数字，正负10的109次方
    double db =  1.0 * 10 / 3 ;
    cout << db << endl; 
    cout << fixed << setprecision(14) << db << endl;

    // 2. 变量、常量
    
    // (1) 变量 
	int n; 
	char c; 
	
    // (2) 常量
    const double pi = 3.1415926535897932;
    //pi = 3.14;
    cout << pi << endl; 
    
    // 3. 运算符
    
    // (1) 算术运算符： + - * / %
    double R = 1.0 / (1.0 / r1 + 1.0 / r2) 

    cout << pow(2, 3) << endl; // 乘方
    cout << sqrt(16) << endl; // 算术平方根 
    cout << cbrt(8) << endl; // 算术立方根 
    
    cout << abs(-10) << endl; // 整数绝对值 
    cout << fabs(-8.3) << endl; // 浮点数绝对值 
    
    cout << ceil(1.32) << endl; // 向上取整 
    cout << floor(1.82) << endl; // 向下取整
    cout << int(1.82) << endl; // 向下取整
    cout << round(3.45) << endl; // 四舍五入取整 
        
    cout << ceil(-1.32) << endl; // 向上取整 
    cout << floor(-1.82) << endl; // 向下取整
    cout << int(-1.82) << endl; // 向下取整
    cout << round(-3.45) << endl; // 四舍五入取整
    
    cout << round(3.433 * 100) / 100 << endl;
    cout << fixed << setprecision(2) << 3.433 << endl;
     
    // 2. 关系运算符 > , >= , <, <=, ==, !=
    
    int n; 
    cin >> n;
    if (!(n > 0)) {
        cout << "真 true 成立" << endl;
    } else {
        cout << "假 false 不成立" << endl;
    }
    
    // 3. 逻辑运算符： 逻辑与 &&, 逻辑或 ||, 逻辑非 !
    
    // n > 0 && n < 100 (相当于 0 < n < 100)
    // n < 0 || n > 100 (相当于 n < 0, 或 n > 100)
    // !(n > 0)  (相当于 非正数) 
    
    return 0;
}

课堂笔记

一维数组的排序

一维数组的查找

一位数组的基本操作

自定义函数

哥德巴赫猜想

打擂台算法

数学专题

流程控制结构-循环结构嵌套

流程控制结构-循环结构

常用缩写

编程四步骤

还没有账户？

登录