信息学奥赛一本通 第五章 第五章 数 组 第一节C语言非C++

第五章 数 组

第一节 一维数组

2034:【例5.1】反序输出

#include <stdio.h>int main() 
{// 定义一个大小为105的数组a,用于存储用户输入的整数// ai用于记录数组a中已存储的整数的个数// x用于临时存储用户输入的整数int a[105], ai = 0, x;// 使用while循环,不断从标准输入读取整数,直到用户输入EOF(在Windows下输入EOF的方法是按Ctrl+Z,然后回车)while(scanf("%d", &x) != EOF)// 将读取到的整数存入数组a,然后ai加1a[ai++] = x;// 使用for循环,从后向前遍历数组a,将其中的整数打印出来for(int i = ai - 1; i >= 0; --i)printf("%d ", a[i]);return 0;
} 

2035:【例5.2】平移数据

#include <stdio.h>int main() 
{// 定义一个大小为105的数组a,用于存储用户输入的整数// n用于记录用户将要输入的整数的个数// x用于临时存储用户输入的整数// temp用于临时保存数组a的第一个元素int a[105], n, x, temp;// 读取用户将要输入的整数的个数scanf("%d", &n);// 使用for循环,从标准输入读取n个整数,并存入数组afor(int i = 0; i < n; ++i){scanf("%d", &x);a[i] = x;}// 将数组a的第一个元素临时保存到temptemp = a[0];// 使用for循环,将数组a的元素向右移动一位for(int i = 1; i < n; ++i)a[i-1] = a[i];// 将原先的第一个元素(现在保存在temp中)放到数组a的最后一位a[n-1] = temp;// 使用for循环,按顺序打印数组a的所有元素for(int i = 0; i < n; ++i)printf("%d ", a[i]);return 0;
} 

2036:【例5.3】开关门

#include <stdio.h>
#include <stdbool.h>  // C语言需要引入stdbool.h库才能使用bool类型int main()
{bool a[1005] = {0}; // a[i]表示第i号门是否关着。第1个人将门全都打开,初值为false。int n; // n个门,n个人scanf("%d", &n); // 读取用户输入的门和人的数量for(int i = 2; i <= n; ++i) // i为人编号,从第2个人开始操作for(int j = 1; j <= n; ++j) // j为门编号,遍历所有的门if (j % i == 0) // 如果门编号是人编号的倍数a[j] = a[j] ? false : true; // 如果门开着,则关上。如果门关着,则打开。for(int j = 1; j <= n; ++j) // 遍历所有门if(a[j] == false) // 如果第j个门开着printf("%d ", j);return 0;
}

2037:【例5.4】约瑟夫问题

#include <stdio.h>
#include <stdbool.h>  // C语言需要引入stdbool.h库才能使用bool类型int main()
{bool isOut[1005] = {0}; // isOut[i]:第i人是否出列,初值为false,都没有出列。使用下标:0~n-1 int n, m, p = 0; // p:当前位置scanf("%d %d", &n, &m); // 读取用户输入的人数和每次出列的人的位置for(int i = 1; i <= n; ++i) // 一共输出n次{for(int j = 0; j < m-1; ++j) // 找m-1个在列的人{while(isOut[p] == true) // 如果当前位置的人已经出列,就继续向下一个位置移动p = (p+1)%n;p = (p+1)%n; // 移动到下一个位置} // 此时p指向第m-1个数的下一个位置 while(isOut[p] == true) // 再找下一个人,就是第m个在列的人p = (p+1)%n;isOut[p] = true; // 此时p指向第m个人 让该人出列 printf("%d ", p+1); // 下标从0开始,人编号从1开始,从下标转为人编号,需要加1 }return 0;
}

2038:【例5.5】最大数位置

#include <stdio.h>int main()
{int n, a[1005], mxi = 1; // mxi:最大值的下标 scanf("%d", &n); // 读取用户输入的整数个数for(int i = 1; i <= n; ++i) // 读取用户输入的整数,存储到数组a中scanf("%d", &a[i]);for(int i = 1; i <= n; ++i) // 遍历数组a,找到最大值的下标{if(a[i] > a[mxi]) // 如果当前整数大于当前的最大值mxi = i; // 更新最大值的下标}printf("%d", mxi); // 打印最大值的下标return 0;
}

2039:【例5.6】冒泡排序

#include <stdio.h>void swap(int *a, int *b) { // 辅助函数,用于交换两个整数的值int temp = *a;*a = *b;*b = temp;
}int main()
{int n, a[25];scanf("%d", &n); // 读取用户输入的整数个数for(int i = 1; i <= n; ++i) // 读取用户输入的整数,存储到数组a中scanf("%d", &a[i]);for(int i = 1; i <= n-1; ++i) // 进行n-1轮比较for(int j = 1; j <= n-i; ++j) // 每轮比较n-i次{if(a[j] < a[j+1]) // 如果前一个数小于后一个数swap(&a[j], &a[j+1]); // 交换这两个数}for(int i = 1; i <= n; ++i) // 打印排序后的数组printf("%d\n", a[i]);return 0;
}

2040:【例5.7】筛选法找质数

#include <stdio.h>
#include <stdbool.h> // 引入stdbool库,可以使用bool类型和true/false值
#include <math.h> // 引入math库,可以使用sqrt函数int main()
{bool isPrime[1005] = {}; // isPrime[i]:i是否是质数 int n;scanf("%d", &n); // 读取用户输入的整数for(int i = 2; i <= n; ++i) // 初值状态下,把每个数字都标记为质数isPrime[i] = true; // isPrime[0]与isPrime[1]都为false,0和1都不是质数 for(int i = 2; i <= (int)sqrt(n); ++i) // 遍历2到根号n的整数{if(isPrime[i]) // 如果当前整数是质数{for(int j = 2*i; j <= n; j += i) // 则它的倍数都不是质数,把它们标记为合数isPrime[j] = false;}}for(int i = 2; i <= n; ++i) // 打印出所有的质数{if(isPrime[i])printf("%d\n", i);}return 0;
}

1102:与指定数字相同的数的个数

#include <stdio.h>int main()
{int a[105], n, m, ct = 0; // 定义一个数组a,整数n和m,计数器ctscanf("%d", &n); // 读取用户输入的整数nfor(int i = 0; i < n; ++i) // 读取n个整数到数组a中scanf("%d", &a[i]);scanf("%d", &m); // 读取需要查找的整数mfor(int i = 0; i < n; ++i) // 遍历数组{if(a[i] == m) // 如果当前元素等于mct++; // 计数器加1}printf("%d\n", ct); // 打印出整数m在数组a中出现的次数return 0;
}

1103:陶陶摘苹果

#include <stdio.h>int main()
{int a[15], h, ct = 0; // 定义一个数组a来存储苹果的高度,整数h代表陶陶的身高,计数器ct用来计算陶陶能摘到的苹果数量for(int i = 1; i <= 10; ++i) // 读取10个苹果的高度scanf("%d", &a[i]);scanf("%d", &h); // 读取陶陶的身高for(int i = 1; i <= 10; ++i) // 遍历每一个苹果{if(h + 30 >= a[i]) // 如果陶陶的身高加上手能够伸到的最高点(即陶陶的身高加上30cm)大于等于这个苹果的高度ct++; // 那么陶陶就能够摘到这个苹果,所以计数器加1}printf("%d", ct); // 打印出陶陶能够摘到的苹果数量return 0;
}

1104:计算书费

#include <stdio.h>int main()
{// 定义一个数组a来存储10种书的单价,sum用来计算总花费,num用来存储每种书的数量float a[10]={28.9, 32.7, 45.6, 78, 35, 86.2, 27.8, 43, 56, 65};float sum = 0, num;for(int i = 0; i < 10; ++i) // 遍历每一种书{scanf("%f", &num); // 输入这种书的数量sum += a[i] * num; // 将这种书的总价加到sum中}printf("%.1f", sum); // 打印出总花费return 0;
}

1105:数组逆序重存放

#include <stdio.h>int main()
{// 定义一个整数n来存储数组的长度,定义一个数组a来存储用户输入的整数int n, a[105];scanf("%d", &n); // 读取数组的长度for(int i = 0; i < n; ++i) // 读取n个整数,并存储在数组a中scanf("%d", &a[i]);for(int i = n-1; i >= 0; --i) // 从后向前遍历数组printf("%d ", a[i]); // 打印出数组中的每一个元素return 0;
}

106:年龄与疾病

#include <stdio.h>int main()
{// 定义一个整数n来存储人数,定义一个整数age来存储每个人的年龄,定义一个数组r来存储四个年龄段的人数int n, age, r[4] = {0};scanf("%d", &n); // 读取人数for(int i = 0; i < n; ++i) // 读取每个人的年龄,并根据年龄划分年龄段{scanf("%d", &age); // 读取年龄if(age >= 0 && age <= 18)r[0]++; // 如果年龄在0-18之间,第一个年龄段的人数加一else if (age >= 19 && age <= 35)r[1]++; // 如果年龄在19-35之间,第二个年龄段的人数加一else if (age >= 36 && age <= 60)r[2]++; // 如果年龄在36-60之间,第三个年龄段的人数加一elser[3]++; // 如果年龄大于60,第四个年龄段的人数加一}for(int i = 0; i < 4; ++i) // 计算每个年龄段的人数占总人数的百分比,并输出printf("%.2lf%%\n", (double)r[i] / n * 100);return 0;
}

1107:校门外的树

#include <stdio.h>
#include <stdbool.h>int main()
{bool a[10005]; // 声明一个布尔数组a,如果位置i有树,a[i]保存为true,否则保存为falseint l, m, start, end, s = 0; // s:树木数量统计 scanf("%d %d", &l, &m); // 输入树木的总范围和砍树的区域个数for(int i = 0; i <= l; ++i) // 将a[0]~a[m]先设为有树 a[i] = true;for(int i = 0; i < m; ++i) // 遍历m个砍树的区域 {scanf("%d %d", &start, &end); // 输入每个区域的起始点和终止点 for(int j = start; j <= end; ++j) // 将a[start]到a[end]设为无树 a[j] = false;}for(int i = 0; i <= l; ++i) // 遍历所有的位置{if(a[i]) // 如果第i位置有树s++; // 树的数量加一,或将这两行写为 s += a[i]; }printf("%d", s); // 输出最后的树的数量return 0;
}

1108:向量点积计算

#include <stdio.h>int main()
{int a[1005], b[1005], n, sum = 0; // 声明两个数组a和b来存储输入,n为数组长度,sum用来存储最终结果scanf("%d", &n); // 输入数组长度for(int i = 0; i < n; ++i) // 输入数组ascanf("%d", &a[i]);for(int i = 0; i < n; ++i) // 输入数组bscanf("%d", &b[i]);for(int i = 0; i < n; ++i) // 计算两个数组对应元素的乘积,并累加到sumsum += a[i]*b[i];printf("%d", sum); // 输出结果return 0;
}

1109:开关灯

#include <stdio.h>
#include <stdbool.h>int main()
{bool a[5005] = {false}; // a[i]表示第i号灯是否亮。第1个人将灯全部关闭,因此将所有元素初始化为false。int n, m; // n盏灯,m个人scanf("%d%d", &n, &m); // 输入灯的数量和人的数量for(int i = 2; i <= m; ++i) // i为人编号,从第2个人开始操作{for(int j = 1; j <= n; ++j) // j为灯编号,遍历所有的灯{if (j % i == 0) // 如果灯编号是人编号的倍数{if(a[j]) // 如果灯开着,则关上。如果灯关着,则打开。a[j] = false;elsea[j] = true;}}}bool isFirst = true; // 是否是第一个要输出的数字for(int j = 1; j <= n; ++j) // 遍历所有灯{if(a[j] == false) // 如果第j盏灯关着{if (isFirst)isFirst = false;elseprintf(",");printf("%d", j);}}return 0;
}

1110:查找特定的值

#include <stdio.h>int main()
{int n, a[10005], x; // n是数组的长度,x是要查找的数scanf("%d", &n); // 输入数组的长度for(int i = 1; i <= n; ++i) // 输入数组的所有元素scanf("%d", &a[i]);scanf("%d", &x); // 输入要查找的数for(int i = 1; i <= n; ++i) // 遍历数组,查找是否有等于x的元素{if(a[i] == x) // 如果找到了就输出其下标并返回{printf("%d", i);return 0;}}printf("-1"); // 如果没有找到就输出-1return 0;
}

1111:不高兴的津津

#include <stdio.h>int main()
{int a[10], in, out, maxDay = 1, maxTime = 0;//a[i]:星期i上课总时间 in:校内上课时间 out:校外上课时间 maxDay:上课时间最长的那天的星期。(最大值的下标)maxTime:最大上课时间 for(int i = 1; i <= 7; ++i) // 读取一周每天的上课时间{scanf("%d%d", &in, &out);a[i] = in + out; // 将校内和校外的上课时间相加}for(int i = 1; i <= 7; ++i) // 遍历一周的上课时间,找出最大的{if(a[i] > maxTime) // 如果当天上课时间大于当前最大上课时间{maxTime = a[i]; // 更新最大上课时间maxDay = i; // 记录最大上课时间的星期} }if(maxTime <= 8) // 如果最大的上课时间不超过8小时,输出0printf("0");else // 如果最大的上课时间超过8小时,输出最大上课时间的星期printf("%d", maxDay);return 0;
}

1112:最大值和最小值的差

#include <stdio.h>int main() 
{// 已知每个整数的绝对值不会大于10000,据此为mx,mn设置初始值 int mx = -10005, mn = 10005, n, a; // mx:最大值,mn:最小值 scanf("%d", &n); // 输入整数个数for(int i = 0; i < n; ++i) // 循环n次,读入数字 {scanf("%d", &a);if(a > mx) // 如果当前数字大于最大值,则更新最大值mx = a;if(a < mn) // 如果当前数字小于最小值,则更新最小值mn = a;}printf("%d", mx - mn); // 输出最大值与最小值之差return 0;
}

1113:不与最大数相同的数字之和

#include <stdio.h>int main()
{int a[105], n, mx = -1000000, s = 0; // s:求的和 scanf("%d", &n); // 输入整数个数for(int i = 0; i < n; ++i) // 读入n个整数{scanf("%d", &a[i]);if(a[i] > mx) // 如果当前整数大于最大值,则更新最大值mx = a[i];}for(int i = 0; i < n; ++i) // 遍历n个整数{if(a[i] != mx) // 如果当前整数不等于最大值,则累加到求和s中s += a[i];}printf("%d", s); // 输出累加的和return 0;
}

1114:白细胞计数

#include <stdio.h>
#include <math.h>int main()
{int n, min_i, max_i;double a[305], ave = 0, dmax = 0; // ave:平均值 dmax:样本减平均值的绝对值的最大值scanf("%d", &n); // 输入整数个数min_i = max_i = 0; // 设a[0]为初始的最大值与最小值 for(int i = 0; i < n; ++i) // 读入n个整数{scanf("%lf", &a[i]);if(a[i] > a[max_i]) // 如果当前整数大于最大值,则更新最大值max_i = i;if(a[i] < a[min_i]) // 如果当前整数小于最小值,则更新最小值min_i = i;}for(int i = 0; i < n; ++i) // 求和ave += a[i];ave = (ave - a[max_i] - a[min_i]) / (n - 2); // 求平均值 for(int i = 0; i < n; ++i) // 计算样本减平均值的绝对值的最大值{if(i != max_i && i != min_i){if(fabs(a[i] - ave) > dmax)dmax = fabs(a[i] - ave);}}printf("%.2lf %.2lf", ave, dmax); // 输出平均值和样本减平均值的绝对值的最大值,保留两位小数return 0;
}

1115:直方图

#include <stdio.h>int main()
{int a[10005] = {0}, n, num, fmax = 0; // a[i]表示数字i的个数,fmax:最大数字 scanf("%d", &n); // 输入整数个数for(int i = 0; i < n; ++i) // 读入n个整数{scanf("%d", &num); // 读入一个整数a[num]++; // 对应的整数出现次数+1if(num > fmax) // 如果当前整数大于最大值,则更新最大值fmax = num;}for(int i = 0; i <= fmax; ++i) // 输出每个数字出现的次数printf("%d\n", a[i]);return 0;
}

1116:最长平台

#include <stdio.h>int main()
{int n, len = 0, maxLen = 0, lastNum = -1, num;// len:当前平台长度, maxLen:最大平台长度, lastNum:上一个数字, num:当前数字scanf("%d", &n);for(int i = 0; i < n; ++i){scanf("%d", &num);if(num == lastNum) // 如果这个数和上一个数相同, 当前平台长度加一len++;else // 如果这个数和上一个数不同{if(len > maxLen) // 如果当前平台长度大于之前的最大平台长度, 更新最大平台长度maxLen = len;lastNum = num; // 更新上一个数字为当前数字len = 1; // 重置当前平台长度为1}}if(len > maxLen) // 如果最后一个平台的长度大于最大平台长度, 更新最大平台长度maxLen = len;printf("%d\n", maxLen); // 输出最大平台长度return 0;
}

1117:整数去重

#include <stdio.h>
#include <stdbool.h>int main()
{bool isExist[20005] = {0}; // 初始化一个布尔数组,用于记录每个数是否已经存在int n, num;scanf("%d", &n);for(int i = 0; i < n; ++i){scanf("%d", &num);if(isExist[num] == false) // 如果这个数在之前没有出现过{printf("%d ", num); // 输出这个数isExist[num] = true; // 标记这个数已经出现过}}return 0;
}

1118:铺地毯

#include <stdio.h>typedef struct Carpet
{int xmin, xmax, ymin, ymax;
} Carpet;// 初始化地毯的边界坐标
void initCarpet(Carpet *carpet, int a, int b, int g, int k)
{carpet->xmin = a;carpet->ymin = b;carpet->xmax = a + g;carpet->ymax = b + k;
}// 判断点(x,y)是否在地毯内
int isPointInCarpet(Carpet *carpet, int x, int y)
{return x >= carpet->xmin && x <= carpet->xmax && y >= carpet->ymin && y <= carpet->ymax;
}int main()
{int n, a, b, g, k, x, y;Carpet carp[10005];scanf("%d", &n);for(int i = 1; i <= n; ++i){scanf("%d %d %d %d", &a, &b, &g, &k);initCarpet(&carp[i], a, b, g, k);}scanf("%d %d", &x, &y);for(int i = n; i >= 1; --i){if(isPointInCarpet(&carp[i], x, y)){printf("%d", i);return 0;}}printf("-1");return 0;
}