查找算法
题目 1:找班级里的 “小明星”
题目描述:班级有 10 个同学的编号(1 - 10),输入一个编号,判断是否是 “小明星”(假设编号为 5 的是小明星),是就输出 “找到小明星啦!”,否则输出 “没找到哦”。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {int a;cin >> a;if (a == 5) {cout << "找到小明星啦!";} else {cout << "没找到哦";}return 0;
}
解释:通过简单的线性查找,判断输入的编号是否为 5,实现查找功能。
题目 2:找数字在不在数组里
题目描述:有数组里存着 1、3、5、7、9,输入一个数,看看在不在这个数组里,在的话输出 “在”,不在输出 “不在”。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {int a, b = 0;int arr[] = {1, 3, 5, 7, 9};cin >> a;for (int i = 0; i < 5; i++) {if (arr[i] == a) {b = 1;break;}}if (b == 1) {cout << "在";} else {cout << "不在";}return 0;
}
解释:用线性查找遍历数组,检查输入的数是否存在于数组中。
题目 3:找成绩中的最高分位置
题目描述:输入 5 个同学的成绩,找出最高分是第几个输入的(从 1 开始数)。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {int a, max = 0, pos = 0;for (int i = 1; i <= 5; i++) {cin >> a;if (a > max) {max = a;pos = i;}}cout << pos;return 0;
}
解释:遍历输入的成绩,同时记录当前最高分及其位置,属于线性查找的应用。
题目 4:找第一个大于 10 的数
题目描述:输入若干个数(最多 10 个),直到输入 0 为止,找出第一个大于 10 的数,输出它的位置(从 1 开始),如果没有就输出 0。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {int a, pos = 0;for (int i = 1; ; i++) {cin >> a;if (a == 0) break;if (a > 10) {pos = i;break;}}cout << pos;return 0;
}
解释:线性查找输入的数,找到第一个大于 10 的数并记录位置。
题目 5:二分查找猜数字(范围 1 - 100)
题目描述:系统随机选一个 1 - 100 的数,用户输入猜测的数,程序提示 “大了”“小了” 或 “猜对了”,直到猜对。
代码:
cpp
运行
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
int main() {srand(time(0));int target = rand() % 100 + 1;int a;while (true) {cin >> a;if (a > target) {cout << "大了" << endl;} else if (a < target) {cout << "小了" << endl;} else {cout << "猜对了";break;}}return 0;
}
解释:虽然是交互性的,但体现了二分查找的思想,通过缩小范围来找到目标数。
题目 6:找数组中相同的数的个数
题目描述:数组里有 1、2、2、3、3、3,输入一个数,找出数组中这个数的个数。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {int a, count = 0;int arr[] = {1, 2, 2, 3, 3, 3};cin >> a;for (int i = 0; i < 6; i++) {if (arr[i] == a) {count++;}}cout << count;return 0;
}
解释:线性遍历数组,统计输入数出现的次数。
题目 7:找名字在不在列表里
题目描述:名字列表有 “小明”“小红”“小刚”,输入一个名字,判断在不在列表里,在的话输出 “是班级同学”,不在输出 “不是”。
代码:
cpp
运行
#include <iostream>
#include <string>
using namespace std;
int main() {string a, b = "不是";string names[] = {"小明", "小红", "小刚"};cin >> a;for (int i = 0; i < 3; i++) {if (names[i] == a) {b = "是班级同学";break;}}cout << b;return 0;
}
解释:线性查找字符串数组,判断输入的名字是否存在。
题目 8:二分查找有序数组中的数
题目描述:有有序数组 1、3、5、7、9,输入一个数,用二分查找判断在不在数组里,在输出 “在”,不在输出 “不在”。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {int a, left = 0, right = 4, mid;int arr[] = {1, 3, 5, 7, 9};cin >> a;while (left <= right) {mid = (left + right) / 2;if (arr[mid] == a) {cout << "在";return 0;} else if (arr[mid] < a) {left = mid + 1;} else {right = mid - 1;}}cout << "不在";return 0;
}
解释:标准的二分查找,利用数组有序的特点,每次缩小一半范围查找目标数。
题目 9:找连续相同数的起始位置
题目描述:数组是 1、2、2、2、3,输入要找的数(比如 2),输出它在数组中连续出现的起始位置(从 0 开始)。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {int a, pos = -1;int arr[] = {1, 2, 2, 2, 3};cin >> a;for (int i = 0; i < 5; i++) {if (arr[i] == a) {pos = i;break;}}cout << pos;return 0;
}
解释:线性查找,找到目标数第一次出现的位置。
题目 10:找能被 5 整除的数的位置
题目描述:输入 5 个数,找出第一个能被 5 整除的数的位置(从 1 开始),如果没有输出 0。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {int a, pos = 0;for (int i = 1; i <= 5; i++) {cin >> a;if (a % 5 == 0) {pos = i;break;}}cout << pos;return 0;
}
解释:线性查找输入的数,找到第一个能被 5 整除的数的位置。
递推算法
题目 1:兔子繁殖问题(斐波那契数列简单版)
题目描述:一对兔子,从出生后第 3 个月起每个月都生一对兔子,小兔子长到第 3 个月后每个月又生一对兔子。输入月份数(1 - 10),求第 n 个月有多少对兔子。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {int a = 1, b = 1, n, c;cin >> n;if (n <= 2) {cout << 1;return 0;}for (int i = 3; i <= n; i++) {c = a + b;a = b;b = c;}cout << c;return 0;
}
解释:利用递推,第 n 个月的兔子对数等于前两个月的和,初始前两个月都是 1 对。
题目 2:计算累加和(递推版)
题目描述:输入一个数 n(1 - 100),计算 1 + 2 + 3 + … + n 的和。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {int a = 0, n;cin >> n;for (int i = 1; i <= n; i++) {a = a + i;}cout << a;return 0;
}
解释:递推累加,从 1 开始依次加到 n,得到总和。
题目 3:阶乘计算(递推版)
题目描述:输入一个数 n(1 - 10),计算 n 的阶乘(n! = 1×2×…×n)。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {int a = 1, n;cin >> n;for (int i = 1; i <= n; i++) {a = a * i;}cout << a;return 0;
}
解释:递推累乘,从 1 开始依次乘到 n,得到阶乘结果。
题目 4:正方形边长递推
题目描述:第一个正方形边长为 1,第二个正方形边长是前一个的 2 倍,输入第 n 个(1 - 5),求边长。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {int a = 1, n;cin >> n;for (int i = 2; i <= n; i++) {a = a * 2;}cout << a;return 0;
}
解释:递推,每个后续正方形边长是前一个的 2 倍,从第一个开始计算到第 n 个。
题目 5:存款利息计算(简单递推)
题目描述:本金 100 元,年利率 3%,每年利息计入本金,输入年数(1 - 5),求 n 年后的本金和。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {double a = 100;int n;cin >> n;for (int i = 1; i <= n; i++) {a = a * 1.03;}cout << a;return 0;
}
解释:递推计算每年的本金和,每年在上一年基础上乘以 1.03。
题目 6:数字三角形递推(简单版)
题目描述:数字三角形第一行是 1,第二行是 2、3,第三行是 4、5、6,输入行数 n(1 - 5),求第 n 行最后一个数。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {int a = 0, n;cin >> n;for (int i = 1; i <= n; i++) {a = a + i;}cout << a;return 0;
}
解释:第 n 行最后一个数是 1 到 n 的和,通过递推累加得到。
题目 7:等比数列求和
题目描述:等比数列首项 1,公比 2,输入项数 n(1 - 10),求前 n 项和。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {int a = 0, b = 1, n;cin >> n;for (int i = 1; i <= n; i++) {a = a + b;b = b * 2;}cout << a;return 0;
}
解释:递推计算等比数列前 n 项和,每次累加当前项并更新下一项。
题目 8:台阶走法(简单递推)
题目描述:上台阶,每次可以走 1 级或 2 级,输入台阶数 n(1 - 10),求有多少种走法。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {int a = 1, b = 2, n, c;cin >> n;if (n == 1) {cout << 1;return 0;} else if (n == 2) {cout << 2;return 0;}for (int i = 3; i <= n; i++) {c = a + b;a = b;b = c;}cout << c;return 0;
}
解释:递推,第 n 级台阶的走法等于前两级的和,类似斐波那契数列。
题目 9:计算幂次(递推版)
题目描述:输入底数 a(1 - 10)和指数 n(1 - 5),计算 a 的 n 次幂。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {int a, n, res = 1;cin >> a >> n;for (int i = 1; i <= n; i++) {res = res * a;}cout << res;return 0;
}
解释:递推累乘,计算底数的 n 次幂。
题目 10:图形层数对应的星数
题目描述:第 1 层有 1 颗星,第 2 层有 3 颗星,第 3 层有 5 颗星,输入层数 n(1 - 5),求第 n 层的星数。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {int a = 1, n;cin >> n;for (int i = 2; i <= n; i++) {a = a + 2;}cout << a;return 0;
}
解释:递推,每层比前一层多 2 颗星,从第一层开始计算到第 n 层。
贪心算法
题目 1:分糖果(尽量多给)
题目描述:有 10 颗糖果,要分给小朋友,每个小朋友分 3 颗,最多能分给几个小朋友。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {int candies = 10, each = 3, count = 0;while (candies >= each) {candies = candies - each;count++;}cout << count;return 0;
}
解释:贪心策略,每次尽可能多给(分 3 颗),统计能分的次数。
题目 2:找零问题(尽量用大面额)
题目描述:要找零 n 元(1 - 100),只有 1 元、5 元、10 元,求最少需要多少张纸币。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {int n, count = 0;cin >> n;count += n / 10;n = n % 10;count += n / 5;n = n % 5;count += n;cout << count;return 0;
}
解释:贪心,优先用大面额(10 元、5 元、1 元)
题目 3:安排活动时间(选最多活动)
题目描述:有 3 个活动,时间分别是 (1-2 点)、(2-3 点)、(1-3 点),选时间不冲突的最多活动数量。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {// 活动结束时间分别为2、3、3int count = 1; // 先选第一个活动int last = 2; // 记录最后结束时间// 检查第二个活动(结束3)if (2 >= last) { // 开始时间2 >= 上一个结束时间2count++;last = 3;}// 检查第三个活动(开始1 < 上一个结束时间3,冲突)cout << count;return 0;
}
解释:贪心策略选结束最早的活动,再选不冲突的下一个,最多能选 2 个。
题目 4:背包问题(选价值最高的物品)
题目描述:背包能装 5kg,物品有 (2kg, 价值 10)、(3kg, 价值 15)、(4kg, 价值 18),选总重量不超且价值最高的。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {int max_val = 0;// 尝试各种组合,贪心选价值密度高的if (18 <= 5) max_val = 18; // 只选4kg的if (15 + 10 <= 5) max_val = 25; // 3+2=5kg,总价值25更高cout << max_val;return 0;
}
解释:简化贪心,比较可能的组合,选总价值最高的(3kg+2kg)。
题目 5:分披萨(每人最多 2 块)
题目描述:1 个披萨切 8 块,有 5 个小朋友,每人最多 2 块,最多能满足几个小朋友。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {int pieces = 8, kids = 5, each = 2;int max_kids = pieces / each; // 8/2=4if (max_kids > kids) max_kids = kids;cout << max_kids;return 0;
}
解释:贪心尽量每人分 2 块,8 块最多满足 4 个小朋友。
题目 6:选最大数(用 3 个不同数字组成最大数)
题目描述:输入 3 个不同的 1 位数,选其中 2 个组成最大的两位数。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {int a, b, c, max1, max2;cin >> a >> b >> c;// 找最大的数字max1 = a;if (b > max1) max1 = b;if (c > max1) max1 = c;// 找第二大的数字max2 = a;if ((b > max2 && b < max1) || (max1 == a && b > max2)) max2 = b;if ((c > max2 && c < max1) || (max1 == a && c > max2) || (max1 == b && c > max2)) max2 = c;cout << max1 * 10 + max2;return 0;
}
解释:贪心选最大的两个数字,大的放十位,小的放个位。
题目 7:时间安排(最早开始的先做)
题目描述:3 件事开始时间是 8 点、9 点、7 点,按最早开始时间排序输出。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {int a = 8, b = 9, c = 7, t;// 排序:7 < 8 < 9if (a > b) { t = a; a = b; b = t; }if (a > c) { t = a; a = c; c = t; }if (b > c) { t = b; b = c; c = t; }cout << a << " " << b << " " << c;return 0;
}
解释:贪心按最早开始时间排序,优先处理早开始的事。
题目 8:买笔(尽量买贵的)
题目描述:有 10 元钱,笔有 3 元 / 支和 2 元 / 支,最多能买几支。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {int money = 10, a = 3, b = 2, count = 0;// 先买便宜的更划算(2元能买更多)count = money / b; // 10/2=5支cout << count;return 0;
}
解释:贪心选便宜的笔(2 元),能买更多数量。
题目 9:拼车(每车最多坐 3 人)
题目描述:有 10 个小朋友要坐车,每车最多 3 人,最少需要几辆车。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {int kids = 10, per_car = 3, cars = 0;cars = kids / per_car; // 10/3=3if (kids % per_car != 0) cars++; // 余1人需再加1辆cout << cars;return 0;
}
解释:贪心每车坐满 3 人,有余数就多一辆车,共需 4 辆。
题目 10:选水果(按单价最低买)
题目描述:苹果 5 元 / 斤,香蕉 3 元 / 斤,橘子 4 元 / 斤,有 10 元钱,买哪种水果最多。
代码:
cpp
运行
#include <iostream>
using namespace std;
int main() {int money = 10, a = 5, b = 3, c = 4;int max_apple = money / a; // 2斤int max_banana = money / b; // 3斤int max_orange = money / c; // 2斤int max = max_banana;cout << max;return 0;
}
解释:贪心选单价最低的香蕉,10 元能买 3 斤最多。
递归算法
题目 1:递归计算 n 的阶乘
题目描述:输入 n(1-5),用递归计算 n 的阶乘(n! = 1×2×…×n)。
代码:
cpp
运行
#include <iostream>
using namespace std;
int fact(int a) {if (a == 1) return 1; // 终止条件return a * fact(a - 1); // 递归调用
}
int main() {int n;cin >> n;cout << fact(n);return 0;
}
解释:递归函数fact(a)
计算 a!,当 a=1 时返回 1,否则返回 a×(a-1)!。
题目 2:递归计算 1 到 n 的和
题目描述:输入 n(1-10),用递归计算 1+2+…+n 的和。
代码:
cpp
运行
#include <iostream>
using namespace std;
int sum(int a) {if (a == 1) return 1; // 终止条件return a + sum(a - 1); // 递归调用
}
int main() {int n;cin >> n;cout << sum(n);return 0;
}
解释:递归函数sum(a)
计算 1 到 a 的和,a=1 时返回 1,否则返回 a + 1 到 a-1 的和。
题目 3:递归求斐波那契数列第 n 项
题目描述:斐波那契数列第 1、2 项是 1,后面每项是前两项和,输入 n(1-5),用递归求第 n 项。
代码:
cpp
运行
#include <iostream>
using namespace std;
int fib(int a) {if (a == 1 || a == 2) return 1; // 终止条件return fib(a - 1) + fib(a - 2); // 递归调用
}
int main() {int n;cin >> n;cout << fib(n);return 0;
}
解释:递归函数fib(a)
返回第 a 项,前两项为 1,后面项是前两项之和。
题目 4:递归输出 1 到 n
题目描述:输入 n(1-5),用递归从 1 输出到 n。
代码:
cpp
运行
#include <iostream>
using namespace std;
void print(int a) {if (a == 0) return; // 终止条件print(a - 1); // 先递归再输出cout << a << " ";
}
int main() {int n;cin >> n;print(n);return 0;
}
解释:递归函数print(a)
先调用print(a-1)
,再输出 a,实现从 1 到 n 的输出。
题目 5:递归输出 n 到 1
题目描述:输入 n(1-5),用递归从 n 输出到 1。
代码:
cpp
运行
#include <iostream>
using namespace std;
void print(int a) {if (a == 0) return; // 终止条件cout << a << " "; // 先输出再递归print(a - 1);
}
int main() {int n;cin >> n;print(n);return 0;
}
解释:递归函数print(a)
先输出 a,再调用print(a-1)
,实现从 n 到 1 的输出。
题目 6:递归计算 a 的 n 次方
题目描述:输入 a(1-3)和 n(1-3),用递归计算 a 的 n 次方。
代码:
cpp
运行
#include <iostream>
using namespace std;
int power(int a, int b) {if (b == 1) return a; // 终止条件:a^1 = areturn a * power(a, b - 1); // 递归调用
}
int main() {int a, n;cin >> a >> n;cout << power(a, n);return 0;
}
解释:递归函数power(a,b)
计算 a^b,b=1 时返回 a,否则返回 a×a^(b-1)。
题目 7:递归求最大公约数
题目描述:输入两个数(1-10),用递归求它们的最大公约数(辗转相除法)。
代码:
cpp
运行
#include <iostream>
using namespace std;
int gcd(int a, int b) {if (b == 0) return a; // 终止条件:余数为0时,a是最大公约数return gcd(b, a % b); // 递归调用(交换并取余)
}
int main() {int a, b;cin >> a >> b;cout << gcd(a, b);return 0;
}
解释:用辗转相除法递归求最大公约数,当 b=0 时返回 a,否则递归计算 gcd (b, a% b)。
题目 8:递归计算数的位数
题目描述:输入一个正整数(1-999),用递归计算它的位数。
代码:
cpp
运行
#include <iostream>
using namespace std;
int count_digits(int a) {if (a < 10) return 1; // 1位数时终止return 1 + count_digits(a / 10); // 递归调用(去掉最后一位)
}
int main() {int n;cin >> n;cout << count_digits(n);return 0;
}
解释:递归函数count_digits(a)
,a<10 时是 1 位,否则位数 = 1 + 去掉最后一位的位数。
题目 9:递归求 1 到 n 的乘积
题目描述:输入 n(1-4),用递归计算 1×2×…×n 的乘积(即阶乘,换种描述)。
代码:
cpp
运行
#include <iostream>
using namespace std;
int product(int a) {if (a == 1) return 1; // 终止条件return a * product(a - 1); // 递归调用
}
int main() {int n;cin >> n;cout << product(n);return 0;
}
解释:和阶乘逻辑相同,用不同描述帮助理解递归的累加思想。
题目 10:递归判断是否为偶数
题目描述:输入一个数(1-10),用递归判断是否为偶数(每次减 2,直到 0 或 1)。
代码:
cpp
运行
#include <iostream>
using namespace std;
bool is_even(int a) {if (a == 0) return true; // 减到0是偶数if (a == 1) return false; // 减到1是奇数return is_even(a - 2); // 递归减2
}
int main() {int n;cin >> n;if (is_even(n)) cout << "是偶数";else cout << "是奇数";return 0;
}
解释:递归函数每次减 2,直到 a=0(偶数)或 a=1(奇数),判断是否为偶数。