感谢张学长为大家整理的笔记~
考点整合
A + B 问题
分离一个整数每一位
从后往前
从前往后→
字符数组(字符串) / 看成一堆字符
栈(先入后出) → 递归
while → 循环版的if （while循环的直接应用 → 模拟）
gcd 和 lcm
打擂法 求max, min
判断素数
O(n)
O(sqrt( n)) → 分离因子的快捷的求法
打印素数表
数列求和、斐波那契数列(递推)
递推和递归
递推往往用迭代(循环)来实现
讲从前往后分离整数的递归写法
实现方式
递推
递归
c++库函数 __gcd()
求gcd(a, b) → 辗转相除法
- 除数作为新的被除数, 原来的被除数 % 除数的结果作为新的除数
- 看除数是否为0，如果除数不为0，就循环上述操作
- 如果除数为0，gcd(a, b) = a;
判断平方数
语法点
while
do-while
for
break, continue
while循环
循环版的if
if()
{
}
判断()内为真, 如果为真执行{}里的内容
while()
{
}
反复判断 ()内是否为真, 如果为真执行{}里的内容
如果里面没有修正条件, 可能会死循环
int n = 1;
while(n % 2 == 0)
{
printf("%d", n);
n++; //修正条件, 防止死循环
}
// TLE
while循环最开始可能进不去
int n = 1;
while(n < 0)
{
printf("%d", n);
}
//如果最开始就不满足while()括号内的条件,while循环会直接进不去 → 可能在一些特殊的情况下没有/没有输出
while(1) //死循环
{
//一定要有一个break条件
}
do-while
一定要执行一次的while循环
do
{
i++;
j++;
}while(i < n);
do i++; while();
//会先执行一次do{}中的语句,再判断是否满足while()里的条件
int n = 1;
do
{
printf("%d", n);
}
while(n < 0);
for
基本语法
for(1; 2; 3)
{
;
}
1: 初始化变量
for(int i = 1; ; ;) i 是个局部变量, for循环结束之后会销毁 → 如果i用不到
int i;
for(i = 1; ; ) for循环结束之后,i的值为循环运行之后的i的值 → 如果i用的到
2: 判断条件
3: 修正条件
执行流程:
1 初始化 → 判断 2 是否成立
如果2成立 → {} → 3 修正条件 → 2 → {} → 3
如果2不成立 → 退出循环
可以根据人的需求来自由的控制循环次数
int n = 5;
for(int i = 1; i <= n; i++)
{
sum += i;
}
for(int i = 1; i <= n; i += 2)
{
sum += i;
}
for(int i = 2; i <= n; i += 2)
int i, n;
int sum = 0;
while(i < n)
{
sum += i;
i++;
}
for(int i = 1; i <= n; i++)
{
sum += i;
}
for(int i = 0, j = 1; i <= n && j <= m; i++, j++)
for(int i = 0; i < n; i++)
break 和 continue
break和continue适用于三种循环
break → 直接跳出当前循环
break 不能用在if
break跳出来的是当前的循环体,而不是整个循环体
break和return的区别
break → 跳出循环
return → 跳出函数
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
for(int k = 0; k < n; k++)
{
for(int l = 0; l < n; l++)
{
break;
return 0; //程序直接结束
}
//break出来会跳到这儿
break;
}
//break出来会跳到这儿
break;
}
//break出来会跳到这儿
break;
}
//break出来会跳到这儿→ 跳出了整个循环
continue → 跳过当前的这个值,继续运行后面的值
//求奇数的和
for(int i = 1; i <= n; i++)
{
if(i % 2 == 0) continue;
sum += i;
}
具体应用
A + B 问题 → 多组输入
组数（数据的个数）已知 → for / while
组数（数据的个数）未知 → while( EOF )
有额外的结束条件 → 多一个if
没有额外的结束条件
注意: 多组数据每一组数据输出的时候一般都要加上 \n
while 7-1 7-8 7-9
for 7-1
a series of / 多组输入 / 题目中没有给出有几组具体的数据 → 不确定组数
//没有额外的结束条件
int a, b;
while(scanf("%d %d", &a, &b) != EOF)
while(~scanf("%d %d", &a, &b))
while(scanf("%d %d", &a, &b) == 2)
1 2
3 4
EOF
-1 → 11111111
~(-1) → 00000000 → 0
//scanf()的返回值 如果成功，该函数返回成功匹配和赋值的个数。如果到达文件末尾或发生读错误，则返回 EOF。
EOF → end of file 文件结束符
#define EOF -1 <stdio.h>
//有额外的结束条件
while(scanf("%d %d", &a, &b) != EOF)
{
if(额外条件) break;
if(a == 0 && b == 0) break;
printf("%d\n", a + b);
}
while(scanf("%d %d", &a, &b) != EOF && (a || b))
组数已知 → while(t--) / for(int i = 0; i < t; i++)
int t;//组数
while(t--)
{
//对每一组数据的操作
for(int i = 0; i < n; i++)
}
for(int i = 0; i < t; i++)
{
for(int j = 0; j < n; j++)
}
t组测试样例, 每一组 n 个数
while(t--)
{
for(int i = 0; i < n; i++)
}
分离每一位
从后往前分离每一位
//3 2 1
int n = 123444;
int cnt = 0;
while(n)
{
int dig = n % 10;
// printf("%d ", dig);
n /= 10;
cnt++;
}
从前往后分离每一位
看成字符数组
栈
/
/法一:
12344
* 当成字符串
char s[100];
scanf("%s", s);
for(int i = 0; i < strlen(s); i++)
{
printf("%c", s[i]);
}
//法二:
* 当成很多字符，一个一个读进去
char c;
scanf("%c", &c);
char c;
c = getchar();
char c;
while((c = getchar()) && c >= '0' && c <= '9') //注意赋值运算符的优先级低, 需要用括号提高优先级
{
// '0' '1' '2'
printf("%c ", c);
//变成数
int dig = c - '0';
}
控制行末空格
pta 忽略最后\n, 但一般不会忽略行末空格
n = 5
for(int i = 0; i < n; i++)
{
printf("%d ", i);
}
0 1 2 3 4
//方法一: 特判第一个或者最后一个
for(int i = 0; i < n; i++)
{
if(i == 0) printf("%d", i);
else printf(" %d", i);
}
0 1 2 3 4
for(int i = 0; i < n; i++)
{
if(i < n - 1) printf("%d ", i);
else printf("%d", i);
}
for(int i = 0; i < n; i++)
{
if(i == n - 1) printf("%d", i);
else printf("%d ", i);
}
//方法二:
int f = 0; //标志, 当第一次出现的时候, 不打印空格, 后面的数都先打印一个空格,在打印这个数
int i = 0;
while(i < n)
{
if(f == 0)
{
f = 1;
}
else printf(" ");
printf("%d", i);
i++;
}
最大公约数gcd 和 最小公倍数lcm
实现方式
递推
递归
c++库函数 __gcd()
求gcd(a, b) → 辗转相除法
- 除数作为新的被除数, 原来的被除数 % 除数的结果作为新的除数
- 看除数是否为0，如果除数不为0，就循环上述操作
- 如果除数为0，gcd(a, b) = a;
被除数 除数
4 16
16 4
4 0
2 7
7 2
2 1
1 0
/*
a = 4 b = 16
a = 16 b = 16
a = 16 b = 0
*/
/递推实现/
//错误示范
while(b) //错误示范 → a的值被b的值覆盖掉了, 而我们需要用原来的a的值
{
a = b;
b = a % b;
}
//正确示范
int gcd(int a, int b)
{
while(b)
{
int r = a; //暂存原来a的值
a = b;
b = r % b;
}
return a;
}
/递归实现/
递归 → 函数里面, 函数自己调用自己
int gcd(int a, int b)
{
if(b == 0) return a;
else return gcd(b, a % b);
}
int gcd(int a, int b)
{
return !b ? a : gcd(b, a % b);
}
/*c++库函数 __gcd(x, y)*/
#include <algorithm>
int a = 5, b = 10;
int ans = __gcd(a, b);
printf("%d", ans);
递推与递归
一般指的是函数中的两种实现的方式
递归 → 函数自己调用自己
斐波那契数列 → f(1) = 1, f(2) = 1, f(n) = f(n - 1) + f(n - 2);
回溯 → 原问题的解
n = 5
f(5) 5
f(3) 2 f(4) 3
f(1) f(2) f(2)1 f(3) 2
f(1) f(2)
缩小规模 ↓
回溯+合并子问题的答案 ↑
f(1) = 1;
f(2) = 1;
输入n
f(n) = f(n - 1) + f(n - 2)
n = 5
int Fibonacci(int n)
{
if(n == 1 || n == 2) return 1; //递归边界
return Fibonacci(n - 1) + Fibonacci(n - 2); //缩小规模的式子(递归表达式)
}
int main()
{
int n;
scanf("%d", &n);
int ans = Fibonacci(n);
printf("%d", ans);
return 0;
}
//系统栈
int n;
scanf
int ans = 0;
int a = 1, b = 1;
int f[1] = 1;
int f[2] = 1;
for(int i = 3; i <= n; i++)
{
f[i] = f[i - 1] + f[i - 2];
}
f[n];
从前往后分离整数之栈写法
#include <stdio.h>
const int N = 10010;
int stk[N]; //整型数组来模拟一个栈
int tt; //代表栈顶元素的位置
void push(int x)
{
stk[++tt] = x;
}
int top()
{
return stk[tt];
}
void pop()
{
tt--;
}
int is_empty()
{
if(tt == 0) return 1;
else return 0;
}
void get_dig(int x)
{
while(x)
{
push(x % 10);
x /= 10;
}
while(!is_empty())
{
printf("%d ", top());
pop();
}
}
int main()
{
int n;
scanf("%d", &n);
get_dig(n);
return 0;
}
打擂法
设置一个初始值
可以用第一个元素作为初始值
求max, max = 非常小的数
求min, min = 非常大的数
//求n个数的最大值和最小值
#include <stdio.h>
int main()
{
int n;
scanf("%d", &n);
int tmp;
int max, min;
scanf("%d", &tmp);
max = tmp;
min = tmp;
int max_id = 0;
int min_id = 0;
for(int i = 1; i < n; i++)
{
int x; //当前读入的元素是x
scanf("%d", &x);
if(x > max)
{
max = x;
max_id = i;
}
if(x < min)
{
min = x;
min_id = i;
}
}
printf("%d %d", max, min);
return 0;
}
int main()
{
int min = 0x3f3f3f3f;
int max = -0x3f3f3f3f;
for(int i = 0; i < n; i++)
{
if(x > max) max = x;
if(x < min) min = x;
}
return 0;
}
本文含有隐藏内容，请 开通VIP 后查看