插入排序,选择排序,冒泡排序,顺序搜索,二分搜索,迭代,求最大公因数,最小公倍数等简单模板

2023-12-25 22:02:50

1.排序

1.插入排序模板

插入排序就如同一副扑克牌,我们一张一张的开始摸牌,一张一张的放,找到相应的位置,让后面的牌往后挪一格,再把这个牌放到挪往后的这个空位上

#include<stdio.h>
#include<math.h>
#include<string.h>

int main(){
	for(int i = 1; i <= 6; i++) scanf("%d",&a[i]);
	//摸6张牌,从小到大排序
	for(int i = 1; i <= 6; i++){
		int temp = a[i];//摸牌
		for(int j = i; j > 0&&a[j-1] > temp; j--){
			//从第i张牌开始比较,只要前一张牌比它大并且没比较到第一张牌就换位置
			a[j] = a[j+1];//往后挪一格
		}
		a[i] = temp;//新牌落位
	}
	return 0;
}

2.冒泡排序模板

冒泡排序

冒泡排序其实我之前写过一个模板

http://t.csdnimg.cn/ghWXo

这次多加点注释,讲的更详细

冒泡排序其实它的名字就十分的形象,就把每个元素都看作是一个泡泡,每次都比较泡泡的大小,如果那个泡泡更大,就让它到前面去,这样一遍又一遍的比较下去,使得泡泡成功变为从小到大的排序

借助动图理解

#include<stdio.h>
#include<math.h>
#include<string.h>

int main(){
	int a[7];
	for(int i = 1; i <= 6; i++) scanf("%d",&a[i]);
	//将6个元素,从小到大排序
	for(int i = 1; i <= 5; i++){
		int flag = 0;
		//6个元素只用冒泡5次,或者说n个元素,冒泡n-1次
		//对于最后一次冒泡的时候,它后面的元素都已经比较好了
		for(int j = 1; j <= 6-i; j++){
			//6个元素要冒泡6-冒泡的次数
			//举个例子,三个数,第一次冒泡,要比较两次
			//对第二次来说,却只要比较一次就可以了
			if(a[j] > a[j+1])
			{//如果这个数比它的下一个数大,就交换位置
				int t = a[j+1];
				a[j+1] = a[j];
				a[j] = t;
				flag = 1;//flag有优化的作用,如果在进行完这个if后
				//flag仍然为0,说明一次比较都没有进行,即说明此时已经排序好了
			}
		}
		if(flag == 0) break;
	}
	for(int i = 1; i <= 6; i++) printf("%d ",a[i]);
	return 0;
}

3.选择排序模板

选择排序是找一个数组中最大的那个数,把它放在第一个位置,再从剩下的数中找到最大的放在第二个位置,以此类推,直到只有两个数,把这两个数中更大的放在倒数第二个位置,另外一个放在最后

#include<stdio.h>
#include<math.h>
#include<string.h>

int main(){
	int a[7];
	for(int i = 1; i <= 6; i++) scanf("%d",&a[i]);
	for(int i = 1; i <= 5; i++){
		int k = i;//记录下标
		for(int j = k+1; j <= 6; j++){
			if(a[j] < a[k]) k = j;
		}//此时k为值最大的那个数的下标
		if(k!=i) {int t = a[k]; a[k] = a[i]; a[i] = t;}
	}
	for(int i = 1; i <= 6; i++) printf("%d ",a[i]);
	return 0;
}

2.搜索

1.顺序搜索

顺序搜索就是写个循环从头搜索到尾,效率很低

2.二分搜索

二分搜索就是对一个已经排序好的数组,不断的二分找我们要找的那个数字

http://t.csdnimg.cn/J6kJd

这是我之前写过的一个二分模板,这次写个更加规范的

#include<stdio.h>
#include<math.h>
#include<string.h>

int main(){
	int a[] = {1,2,3,4,5,6,7,8,9,10};
	int left = 0,right = 9,mid,found;
	//left为第一个数的下标,也就是0
	//right为第二个数的下标,也就是1
	//mid为二分的那个值
	//found用来判断是否找到了,找到则为1
	found = 0;
	int x;
	scanf("%d",&x);
	//要找x
	while(left <= right && !found){
		mid = (left + right)/2;
		if(a[mid] > x) right = mid - 1;
		else if(a[mid] < x) left = mid + 1;
		else if(a[mid] == x) found = 1;
	}
	if(found == 1) printf("found");
	else printf("nofound");
	return 0;
}

?

3.迭代

1.基础迭代

?

#include<stdio.h>
const int N = 1e5 + 10;

int main(){
	int a[N];
	int n,i;
	scanf("%d",&n);
	a[1] = 1,printf("%5d",a[1]);
	a[2] = 1,printf("%5d",a[2]);
	for( i = 3; i <= n;i++){
		a[i] = a[i - 1] + a[i - 2];
		printf("%5d",a[i]);
	}
	return 0 ;
}

4.求最大公因数,最小公倍数

最大公因数?的英文是 "Greatest Common Divisor"

最小公倍数?Least Common Multiple

以下用gcd代表最大公因数,用lcm代表最小公倍数

1.最直接的方法

让那两个数中更大的那个数一直加一,直到能被那两个数整除为止,得到的这个数就是最小公倍数

让那两个数中更小的那个数一直减一,直到那两个数能被这个数整除为止,得到的这个数就是最大公因数

#include<stdio.h>
#include<math.h>
#include<string.h>

int lcm(int x,int y){
	int max = x>y?x:y;
	while(max%x != 0||max%y != 0) max++;
	//只要max不能同时被这两个数整除就加一
	return max;
}

int gcd(int x,int y){
	int min = x < y?x:y;
	while(x % min != 0|| y % min != 0) min--;
	//直到那两个数能被这个数整除为止
	return min;
}
int main(){
	int x,y;
	scanf("%d%d",&x,&y);
	//找x和y的最小公倍数和最大公因数
	int lc,gc;
	lc = lcm(x,y);
	gc = gcd(x,y);
	printf("%d %d",lc,gc);
	return 0;
}

?

取巧一点

最小公倍数其实就是x乘y除以最大公因数

可以变成这样

#include<stdio.h>
#include<math.h>
#include<string.h>

int gcd(int x,int y){
	int min = x < y?x:y;
	while(x % min != 0|| y % min != 0) min--;
	//直到那两个数能被这个数整除为止
	return min;
}

int lcm(int x,int y){
	return x*y/gcd(x,y);
}

int main(){
	int x,y;
	scanf("%d%d",&x,&y);
	//找x和y的最小公倍数和最大公因数
	int lc,gc;
	lc = lcm(x,y);
	gc = gcd(x,y);
	printf("%d %d",lc,gc);
	return 0;
}

2.辗转相除法(欧几里得法)

这是之前写的,现在写个更具模板化的

http://t.csdnimg.cn/s0mdb?

#include<stdio.h>
#include<math.h>
#include<string.h>

int gcd(int x,int y){
	int t;
	while(y){
		t = x % y;
		x = y;
		y = t;
	}
	return x;
}

int lcm(int x,int y){
	return x*y/gcd(x,y);
}

int main(){
	int x,y;
	scanf("%d%d",&x,&y);
	//找x和y的最小公倍数和最大公因数
	int lc,gc;
	lc = lcm(x,y);
	gc = gcd(x,y);
	printf("%d %d",lc,gc);
	return 0;
}

辗转相除法,也称为欧几里得算法,是一种用于计算两个正整数最大公约数(Greatest Common Divisor, GCD)的古老而有效的算法。它的基本原理是利用了数学中的一个重要定理:对于任意两个整数a和b(假设a>b),它们的最大公约数与b和a除以b的余数c的最大公约数相同,即gcd(a, b) = gcd(b, c)。

以下是一个例子来说明辗转相除法的原理:

假设我们要找到15750和27216的最大公约数。

1. 首先,我们将较大的数27216除以较小的数15750,得到商1和余数11466(27216 = 1 × 15750 + 11466)。

2. 然后,我们将上一步的除数15750作为新的被除数,余数11466作为新的除数进行下一轮计算。将15750除以11466,得到商1和余数4284(15750 = 1 × 11466 + 4284)。

3. 接着,我们将上一步的除数11466作为新的被除数,余数4284作为新的除数进行下一轮计算。将11466除以4284,得到商2和余数3198(11466 = 2 × 4284 + 3198)。

4. 再次交换被除数和除数,将4284作为新的被除数,3198作为新的除数。将4284除以3198,得到商1和余数1086(4284 = 1 × 3198 + 1086)。

5. 继续这个过程,将3198作为新的被除数,1086作为新的除数。将3198除以1086,得到商3和余数22(3198 = 3 × 1086 + 22)。

6. 最后,将1086作为新的被除数,22作为新的除数。将1086除以22,得到商49和余数0(1086 = 49 × 22 + 0)。

由于我们已经得到了余数为0,这意味着当前的除数22就是原问题中两个数15750和27216的最大公约数。

所以,15750和27216的最大公约数为22。这就是辗转相除法的原理和一个实际应用的例子。通过反复进行除法和交换除数和余数的操作,直到余数为0,最后的除数就是两个原始数的最大公约数。

不会写?不要怕!

和我一起念口诀歪踢尔科斯歪尔科斯y,t,x,y,x,(

文章来源:https://blog.csdn.net/2301_79431343/article/details/135185414
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。