言成言成啊 | Kit Chen's Blog

C考研算法题

每天看一遍,争取在理解思路的基础上背过

1到100内的素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<stdio.h>
int main(){
int flag=1;//用来判断是否是素数,
for(int i=2;i<=100;i++){
for(int j=2;j<i;j++){
if(i%j==0) {
flag=0;//如果不是负数,改成0
break;
}
}
if(flag==1){
printf("%d ",i);
}
flag=1;
}
return 0;
}

分解质因数

99=3x3x11

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<stdio.h>

/**
* 短除法分解质因法
* 思路:
* 输入n,k=2(最小的素数)
* 1.从k开始除,若能整除,就输出该数,并将n赋值为n/k
* 2.若不能整除,则k++,重新执行1步
* 输出n
* @return
*/
int main() {
int n;
while (scanf("%d", &n)) {
int k;
for (k = 2; k < n; k++) {
while (n != k) {
if (n % k == 0) {
printf("%d*", k);
n = n / k;
} else
break;
}
}
printf("%d\n", n);
}
return 0;
}

一个数的约数

20的正约数有:1、2、4、5、10、20。

注意:一个数的约数必然包括1及其本身。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
int main()
{
int n;
while(scanf("%d",&n)){
for(int i=1;i<n;i++){
if(n%i==0){
printf("%d、",i);
}
}
printf("%d\n",n);
}
return 0;
}

统计字母数字出现的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <string.h>

int main() {
int num = 0, upper = 0, lower = 0;
char s[20];
while (gets(s)) {
for (int i = 0; i < strlen(s); i++) {
if (s[i] >= 'a' && s[i] <= 'z') {
lower++;
}
if (s[i] >= 'A' && s[i] <= 'Z') {
upper++;
}
if (s[i] >= '0' && s[i] <= '9') {
num++;
}
}
printf("数字=%d,大写字母=%d,小写字母=%d\n", num, upper, lower);
}
return 0;
}

统计正整数出现的次数

例如

输入1,2,2,3,3,3,5,5,5,6

输出0:0次 1:1次 2:2次 3:3次 4:0次 5:3次 6:1次 7:0次 8:0次 9:0次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <stdio.h>

int main() {
int a[10] = {
1, 2, 2, 3, 3, 3, 5, 5, 5, 6
};
int b[10] = {0};
for (int i = 0; i < 10; i++) {
b[a[i]]++;
}
for (int i = 0; i < 10; i++) {
printf("%d:%d次 ", i, b[i]);
}
return 0;
}

分解一个n位数

输入333

输出 300 30 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>
#include <math.h>

int main() {
int n, i = 0;
int b[10] = {
0
};
scanf("%d", &n);
while (n != 0) {
b[i] = n % 10;
n /= 10;
i++;
}
for (int j = 0; j < i; j++) {
printf("%d ", b[j] * (int) pow(10, i - j - 1));
}
return 0;
}

俩数的最大公约数和最小公倍数

最大公因数,也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。a,b的最大公约数记为(a,b),同样的,a,b,c的最大公约数记为(a,b,c),多个整数的最大公约数也有同样的记号。

互质数为数学中的一种概念,即两个或多个整数的公因数只有1的非零自然数。公因数只有1的两个非零自然数,叫做互质数。

约数,又称因数。整数a除以整数b(b≠0) 除得的商正好是整数而没有余数,我们就说a能被b整除,或b能整除a。a称为b的倍数,b称为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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <stdio.h>

/**
* 最大公约数
* Greatest Common Divisor
* @param a
* @param b
* @return
*/
int GCD(int a, int b) {
int temp;
if (a < b) {
temp = a;
a = b;
b = temp;
}
while (temp != 0) {
temp = a % b;
a = b;
b = temp;
}
return a;
}

/**
* 最小公倍数
* Least Common Multiple
* @param a
* @param b
* @return
*/
int LCM(int a, int b) {
for (int i = a; i > 0; i++) {
if (i % a == 0 && i % b == 0) {
return i;
}
}
}

int main() {
int a, b;
scanf("%d%d", &a, &b);
printf("最大公约数:%d", GCD(a, b));
printf("最小公倍数:%d", LCM(a, b));
return 0;
}

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
int main(){
int a[10]={
1,9,8,7,6,5,4,3,2,10
};
int temp;
for(int i=0;i<10-1;i++){
for(int j=0;j<10-i-1;j++){
if(a[j]>a[j+1]){
temp=a[j+1];
a[j+1]=a[j];
a[j]=temp;
}
}
}
for(int i=0;i<10;i++){
printf("%d ",a[i]);
}
return 0;
}

已排好序的数组插入一个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<stdio.h>

int main() {
int a[11] = {
1, 2, 3, 3, 5, 6, 7, 8, 9, 10
};
int temp;
scanf("%d", &temp);
for (int i = 9; i >= 0; i--) {
if (temp < a[i]) {
a[i + 1] = a[i];
} else {
a[i + 1] = temp;
break;
}
}
for (int i = 0; i < 11; i++) {
printf("%d ", a[i]);
}
return 0;
}

数组奇偶数分类

设计一个C语言函数,将整数数组a[n]划分为左右两部分,使左边所有元素值为奇数,右边所有元素值为偶数

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
29
30
31
32
33
34
35
36
#include<stdio.h>

void divide(int a[], int n) {
int i = 0, j = n - 1, temp;
while (i < j) {
//若是奇数,则自增
//若不是奇数,则执行下步的交换
while (a[i] % 2 != 0) {
i++;
}
//若是偶数,则自减
//若不是偶数,则执行下步的交换
while (a[j] % 2 != 1) {
j--;
}
//这是保证左边是奇数,右边偶数
if (i < j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
//为了帮助理解
printf("结束的i=%d,j=%d\n", i, j);
for (int k = 0; k < n; k++) {
printf("%d ", a[k]);
}
}

int main() {
int a[10] = {
1, 9, 1, 2, 9, 7, 5, 1, 9, 3
};
divide(a, 10);
return 0;
}

数组逆序

矩阵逆序

设给定一个m行n列整型矩阵A,编写一个函数swap,使得它对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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <stdio.h>

#define m 3
#define n 4

void swap(int a[m][n]) {
int i, j, temp;
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
printf("%d ", a[i][j]);
}
printf("\n");
}
printf("================\n");

//关键代码
for (i = 0; i < m / 2; i++) {
for (j = 0; j < n; j++) {
temp = a[i][j];
a[i][j] = a[m - i - 1][n - j - 1];
a[m - i - 1][n - j - 1] = temp;
}
}
//如果不是奇数行的话,截止到上面部分的代码,就能完美实现该功能了。
//比如,是3行的话,3/2=1,那么数组就会在区间[0,1)取值,如果将区间改成闭区间,那么偶数行又会出问题,相当于换了一遍,又再换回去了。
//所以如果是奇数行的话,需要再加逻辑单独处理
if (m % 2 != 0) {
i = m / 2;
for (j = 0; j <= n / 2; j++) {
temp = a[i][j];
a[i][j] = a[m - i - 1][n - j - 1];
a[m - i - 1][n - j - 1] = temp;
}
}

//输出结果
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
printf("%d ", a[i][j]);
}
printf("\n");
}
}

int main() {
int a[m][n] = {
0, 1, 2, 3,
10, 11, 12, 13,
20, 21, 22, 23
};
swap(a);
return 0;
}

向量逆序

已知在一维数组A[M+N]中,依次存放着两个向量{1,3,5,7,9}跟{2,4},现要求将向量逆序,变成{2,4}和{1,3,5,7,9}

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
29
30
31
32
#include <stdio.h>

#define M 5
#define N 2

void reverse(int a[], int n) {
int i, temp;
for (i = 0; i < n / 2; i++) {
temp = a[i];
a[i] = a[n - 1 - i];
a[n - 1 - i] = temp;
}
}

int main() {
int i;
int a[M + N] = {
1, 3, 5, 7, 9, 2, 4
};
//将整个数组进行逆序
reverse(a, M + N);
//将前部分数组进行正序
reverse(a, N);
//将后部分数组进行正序
reverse(a + N, M);

//输出验证结果
for (i = 0; i < M + N; i++) {
printf("%d ", a[i]);
}
return 0;
}

奇偶数分类并排序

有100个正整数存放在数组中,试编一函数,要求:

  1. 所有的奇数按从小到大的顺序存放在数组的前半部
  2. 所有的偶数按从小到大的顺序存放在数组的后半部

例如:1,4,3,2,5,9,7

输出:1,3,5,7,9,2,4

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <stdio.h>

#define N 7

/**
* 对数组进行排序
* @param a
* @param n
*/
void inOrder(int a[], int n) {
int temp;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (a[j] > a[j + 1]) {
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
}

/**
* 对数组进行分类
* 奇数放到左边,偶数放到左边
* @param a
* @param n
*/
void sort(int a[], int n) {
int i = 0, j = n - 1;
int temp;
while (i < j) {
//如果是奇数,则后移
while (a[i] % 2 != 0) {
i++;
}
//如果是偶数,则前移
while (a[j] % 2 == 0) {
j--;
}
//奇偶数互换
if (i < j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
inOrder(a, i);
inOrder(a + i, n - i);
}


int main() {
int a[N] = {
1, 4, 3, 2, 5, 9, 7
};
sort(a, N);
for (int i = 0; i < N; i++) {
printf("%d ", a[i]);
}
return 0;
}

数组排序

设给定数组变量A和B,它们的值满足条件:

A[i]<=A[i+1],B[j]<=B[j+1],其中i=0,1,…,m,j=0,1,…,n

试写一个程序,将A和B合并成一个有序数组C,使得C[k]<=C[k+1],k=0,1,…,m+n

这个题最笨的方法,就是将元素,一股脑存储到c中,然后再对C进行冒泡排序。

此处,用另一个思路。

  1. 将a、b两个数组之间从下标0开始,进行比较,更小的就放到c数组中
  2. 将a或者b中剩余的数,依次存放到c中
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<stdio.h>

#define m 5
#define n 6

void sort(int a[], int b[], int c[]) {
int i = 0, j = 0, k = 0;
while (i < m && j < n) {
if (a[i] < b[j]) {
c[k] = a[i];
i++;
} else {
c[k] = b[j];
j++;
}
k++;
}
if (i == m) {
for (int d = m; d < n; d++, k++) {
c[k] = b[d];
}
}
if (i == n) {
for (int d = n; d < m; d++, k++) {
c[k] = a[d];
}
}

for (i = 0; i < m + n; i++) {
printf("%d ", c[i]);
}

}

int main() {
int a[m] = {
2, 4, 6, 8, 10
};
int b[n] = {
1, 3, 5, 7, 9, 11
};
int c[m + n];
sort(a, b, c);
return 0;
}

有15个数按由大到小顺序存放在一个数组中,输入一个数,要求用者半查找法找出该数是第几个元素的值

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
#include<stdio.h>

#define N 10

int main() {
int a[N] = {
20, 19, 18, 17, 16, 15, 14, 13, 12, 11
};
int i, num, low = 0, high = N - 1, mid;
scanf("%d", &num);
while (low <= high) {
mid = (low + high) / 2;
if (a[mid] == num) {
break;
} else if (a[mid] > num) {
low = mid + 1;
} else {
high = mid - 1;
}
}
if (low > high) {
printf("查找失败\n");
} else {
printf("%d的下标为%d\n", a[mid], mid);
}
return 0;
}

平台问题

设给定N个元素的一维整型数组变量A,若有下面条件:

  • A[i-1]!=A[i]
  • A[i]=A[i+1]=…=A[k]
  • A[k]!=A[k+1]

则称A[i],A[i+1]…A[k]为饱和平台,并定义其长度为k+1-i。

写一个函数,使得它对任给的数组变量A求出最长平台的长度。

例如,假如有序列(3,3,2,2,4,4,4),则(3,3)和(2,2)以及(4,4,4)都是饱和平台,并且最长的平台的长度是3

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<stdio.h>

int getLen(int a[], int n) {
int max = 0, mark = 1;
for (int i = 0; i < n; i++) {
if (a[i] == a[i + 1]) {
mark++;
} else {
mark = 1;
}
if (mark > max)
max = mark;
}
return max;
}

int main() {
int a[] = {
2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4
};
printf("最长平台的长度:%d\n", getLen(a, sizeof(a) / sizeof(a[0])));

return 0;
}

特殊值

设有N个非负数,存放于一维数组中,要求将其中的0移动到后面,非0的数保持原有次序。

例如,当 N=7 时,原有序列 7,0,0,3,0,5,0 移动后称为 7,3,5,0,0,0,0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<stdio.h>
void sort(int a[],int n){
int temp;
for(int i=0;i<n-1;i++){
for(int j=0;j<n-i-1;j++){
if(a[j]==0){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
for(int i=0;i<n;i++){
printf("%d ",a[i]);
}
}
int main(){
int a[]={
7,0,0,3,0,5,0
};
sort(a, sizeof(a)/ sizeof(a[0]));
return 0;
}

最垃圾的思想,冒泡。虽然能做出来,但是效率很低

换个思想

  1. 找到第一个0元素
  2. 从当前位置找第一个非0元素
  3. 两个元素互换,找不到就结束

循环执行

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<stdio.h>

void sort(int a[], int n) {
int temp;
for (int i = 0; i < n; i++) {
if (a[i] == 0) {
for (int j = i; j < n; j++) {
if (a[j] != 0) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
break;
}
}
}
}
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
}

int main() {
int a[] = {
7, 0, 0, 3, 0, 5, 0
};
sort(a, sizeof(a) / sizeof(a[0]));
return 0;
}

编写一个函数,从给定的向量A中删除元素值在x到y(x<=y)之间的所有元素(向量要求各元素之间不能有间断)。

函数原型为:int del(int A,int n,int x,int y)。

其中,参数n为输入向量的维数,返回值为删除元素后的维数。

1
2
3
4
5
6
int del(int a[],int n,int x,int y){
for(int i=x,j=y+1;i<x+(n-y)-1;i++,j++){
a[i]=a[j];
}
return n-(y-x)-1;
}

一开始理解成删除元素下标为x-y的值了

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
#include <stdio.h>

int del(int a[], int n, int x, int y) {
int i = 0, k = 0;
while (i < n) {
if (a[i] >= x && a[i] <= y) {
k++;
} else {
a[i - k] = a[i];
}
i++;
}
return n - k;
}

int main() {
int a[] = {
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
};
int n = del(a, sizeof(a) / sizeof(a[0]), 3, 5);
for (int i = 0; i < n; i++) {
printf("%d ", a[i]);
}
return 0;
}

编写函数,把整数数组中值相同的元素删除得只剩一个,并把剩余元素全部移动到前面。

发布:2020-09-27 21:40:51
修改:2020-10-13 17:01:12
链接:https://meethigher.top/blog/2020/c-algorithm/
标签:c algorithm 
付款码 捐助 分享
阅读量