1. 写出一个高效的算法来搜索m×n矩阵中的值,判断一个值是否在这个矩阵中出现。
这个矩阵具有以下特性:
每行中的整数从左到右是排序的。
每一列的整数从上到下是排序的。
在每一行或每一列中没有重复的整数。
样例:
矩阵:
1 2 9 10
3 4 11 12
5 7 12 14
6 9 14 16
整数:7
结果:1
提示:这个矩阵叫做杨氏矩阵,在搜索过程中,遵循杨氏矩阵的搜索规律,从左上角开始,key小于矩阵中该点的值,往左走,大于则往下走
#include<stdio.h> int main() { int a[4][4] = {
{1,2,9,10},{3,4,11,12},{5,7,12,14},{6,9,14,16} }; int row,col,key,sum = 0; row
= 0; col = 3; printf("整数:"); scanf_s("%d", &key); if (key<a[0][0] ||
key>a[3][3]) sum=0; else { while (row < 4 && col >= 0) { if (key < a[row][col])
col--; else if (key > a[row][col]) row++; else if (key == a[row][col]) { sum =
1; break; } } } printf("结果:%d\n", sum); return 0; }
Ps.
本段代码没有采用从控制台输入矩阵的方式,而是在代码段中写入矩阵并按要求进行处理。可能与题意有偏差。(控制台输入矩阵可以考虑输入矩阵大小后对其进行动态内存分配)
2. 写出一个高效的算法来搜索m×n矩阵中的值,返回这个值出现的次数。
这个矩阵具有以下特性:
每行中的整数从左到右是排序的。
每一列的整数从上到下是排序的。
在每一行或每一列中没有重复的整数。
样例:
矩阵:
1 3 5 7
2 4 7 8
3 5 9 10
给出key = 3,返回 2
#include<stdio.h> int main() { int a[3][4] = { {1,3,5,7},{2,4,7,8},{3,5,9,10}
}; int row, col, key, sum = 0; row = 0; col = 3; printf("整数:"); scanf_s("%d",
&key); if (key<a[0][0] || key>a[2][3]) sum = 0; else { while (row < 3 && col >=
0) { if (key < a[row][col]) { col--; continue; } else if (key > a[row][col]) {
row++; continue; } else if (key == a[row][col]) { sum++; row++; continue; } } }
printf("结果:%d\n", sum); return 0; }
3. 给定一个包含 m * n 个要素的矩阵,(m 行, n 列),按照螺旋顺序,返回该矩阵中的所有要素。
样例:
给定如下矩阵:
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
应返回 [1,2,3,6,9,8,7,4,5]。
#include<stdio.h> int main() { int a[3][3] = { {1,2,3},{4,5,6},{7,8,9} }; int
temp[9] = { 0 }; int i,j,c=0,k=0; while (k<9) { for (i=c,j=c; j < 3 - c; j++,
k++) { if (k == 9)break; temp[k] = a[i][j]; } for (j--,i++; i < 3 - c; i++,
k++) { if (k == 9)break; temp[k] = a[i][j]; } for (j--,i--; j >= c; j--, k++) {
if (k == 9)break; temp[k] = a[i][j]; } for (j++,i--; i > c; i--, k++) { if (k
== 9)break; temp[k] = a[i][j]; } i++; c++; } for (k = 0; k < 9; k++) {
printf("%d", temp[k]); } return 0; }
4.完成fun函数和相应的测试主函数
* 编写一个函数:int fun(float score[], int m, float below[]);
score为一数组,代表一个班学生的成绩表,该成绩表有m个元素(m个学生),函数返回低于平均值的元素个数,并将低于平均分的分数放在below
所指的数组中,如果函数输入数据异常,函数返回-1。例如,当 score 数组中的数据为
10.1、20.2、30.3、40.4、50.5、60.6、70.7、80.8、90.9时,函数返回的认输应该是 4,below
中的数据应为10.1、20.2、30.3、40.4。
*
编写主函数,用于测试fun函数。要求从键盘输入数组元素的个数n,利用随机数函数产生n个0~100之间的浮点数(带1位小数),即产生的每个数大于等于0.0且小于100.0,调用fun函数,用以确定fun函数是否正确。
提示和要求:
*
主函数能够测试fun函数的各种情况,比如输入异常情况,观测fun函数是否返回-1;正常输入时,观测fun函数能否正确给出结果。数组score,数组below以及函数返回值等内容输出到显示器,方便观测函数是否正确。
* 随机数产生函数是rand(),随机数种子设置函数是srand(),请自行设置随机数种子以产生不同的随机数,需要的头文件是stdlib.h
#include<stdio.h> #include<stdlib.h> #include<time.h> void func(float score[],
int m, float below[]) { int i,num=0,k=0,t; float avr,sum=0; if (score == NULL
|| m <= 0) t = -1; else { for (i = 0; i < m; i++) { sum =sum+ score[i]; } avr =
sum / m; for (i = 0; i < m; i++) { if (score[i] < avr) { num++; below[k] =
score[i]; k++; } } t=num; } } int fun(float score[], int m, float below[]) {
int i, num = 0, k = 0; float avr, sum = 0; if (score == NULL || m <= 0) return
-1; else { for (i = 0; i < m; i++) { sum = sum + score[i]; } avr = sum / m; for
(i = 0; i < m; i++) { if (score[i] < avr) { num++; below[k] = score[i]; k++; }
} return num; } } int main() { int n,i,c,result; printf("Please enter the
amounts of students:"); scanf_s("%d", &n); printf("Please enter the type:");
scanf_s("%d", &c); float t1; srand((unsigned)time(NULL)); float* a, below[1000]
= { 0 }; a = (float *)calloc(n, sizeof(float)); if (a == NULL||below==NULL) {
printf("#error! Failed to Malloac.\n"); } else { switch (c) { case(1): for (i =
0; i < n; i++) { t1 = (rand() % 10001); *(a + i) = t1 / 100; } func(a, n,
below); printf("The results:\n"); for (i = 0; *(below + i) != '\0'; i++) {
printf("%.1f ", below[i]); } break; case(2): for (i = 0; i < n; i++) { t1 =
(rand() % 10001); *(a + i) = t1 / 100; } result=fun(a, n, below); printf("The
results:"); printf("%d", result); break; default:break; } } free(a); return 0; }