5.[必备]数学推导和规律观察-比如机考数学题
2025/12/29大约 8 分钟
5.[必备]数学推导和规律观察-比如机考数学题
递归典型题+找规律典型题-汉诺塔
注释推导逻辑，先找规律，然后看能不能抽象出一个具体函数，如果抽1个函数不行，就看看加几层？或者多个函数一起
- 纯自己注释推导的汉诺塔，重点是go的指针
go
func hanota(A *[]int, B *[]int, C *[]int) {
// src -> dst 借助mid
// 1个：
// 【1】直接src -> dst
// 2个：
// 【1】将0从src -> mid
// 【2】将1从src->dst
// 【3】将0从mid->dst
// 3个：
// 将1和2绑定为1个大元素【看做整体】
// 【1】将0从src -> mid
// 【2】将大整体从src->dst
// 【3】将0从mid->dst
// 4个可以类似3个的来
// 总结规律：无论是3，4, 5个都可以按照2个的规律来，只需要将这种3步骤抽象为1个函数即可
// 也就是要足够抽象的1个函数
// 那么这个抽象的函数咋设计？
// 本质就是将 数组（让他来模拟1个元素或好几个元素组成的大整体） 从某个src 移动到 某个dst
// func movSrc2DstByMid(src *[]int, dst *[]int, mid *[]int)
// 然后你可能会遇到卡点，你觉得，那如何模拟那个0和大整体呢？
// 计算机的套路：既然现在解决不了，那就加一层辅助
// 那我们加个要移动多少元素作为1个整体不就ok了？
// 改造为, 将src的nums个元素移动到dst通过mid
// func movSrc2DstByMid(nums int, src *[]int, dst *[]int, mid *[]int)
length := len(*A)
movSrc2DstByMid(length, A, C, B)
}
func movSrc2DstByMid(nums int, src *[]int, dst *[]int, mid *[]int){
if nums == 0 {
return
}
if nums == 1 {
*dst = append(*dst, (*src)[len(*src)-1]) // 加入1个
*src = (*src)[0:len(*src)-1] // 删除1个
return
}
// 然后就是通用的了
// 【1】将0从src -> mid
movSrc2DstByMid(1, src, mid, dst)
// 【2】将大整体从src->dst
movSrc2DstByMid(nums-1, src, dst, mid)
// 【3】将0从mid->dst
movSrc2DstByMid(1, mid, dst, src)
}cpp
//start里面的最上面n个元素，借助helo杆子，移到end杆子上
void recursive( vector<int> & start, int n, vector<int> &help, vector<int> & end)
{
//1==n, 递归边界
if( 1==n )
{
end.push_back( start.back() );
start.pop_back();
return ;
}
//2==n，虚拟的n=2的绑定递归
recursive( start, n-1, end, help);
end.push_back( start.back() );
start.pop_back();
recursive( help, n-1, start, end);
}
class Solution {
public:
void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
int n=A.size();
recursive( A, n, B, C);
}
};找规律题-约瑟夫环（圆圈中最后剩下的数字）
- 剑指 Offer 62. 圆圈中最后剩下的数字
- 公式:参考原理
从n个(多的)中, 每次删除第m(少的)**个数字, 求出这个圆圈里剩下的最后一个数字
class Solution {
public:
int lastRemaining(int n, int m) {
//f(n,m)= (f'(n-1,m)+m)%n;
if (1 == n) {
return 0;
}
//初始化的位置 f(1,m)=0;
int f = 0;
for (int new_n = 2; new_n <= n; ++new_n) {
f = (f + m) % new_n;
}
return f;
}
};gcd求最大公约数『模板』
- 题目传送门：一行代码求两个数的最大公约数
- 辗转相除法『迭代写法』
#include<bits/stdc++.h>
using namespace std;
int n, m;
//================================
// 我们希望a>=b
int gcd(int a, int b) {
// 我们希望a>=b
if (a < b) {
swap(a, b);
}
while (a % b) {
int temp = a % b;
a = b; //大=小的
b = temp; //小=余数
}
return b;
}
//================================
int main() {
while (~scanf("%d%d", &n, &m)) {
printf("%d\n", gcd(n, m));
}
return 0;
}lcm最小公倍数『模板』
和『最大公约数』关系密切，得到最大公约数后，很简单
int lcm(int a, int b){
int gcdNum=gcd(a,b);
return a/gcdNum * b; //注意，学习这种防止溢出的写法
}数字-找规律题解⭐️
1.剑指 Offer 44. 数字序列中某一位的数字
数字规律！
class Solution {
public:
int findNthDigit(int n) {
if( 0==n ) return 0;
/*规律
1-9（总共9-1+1=9）
10-99（总共99-10+1=90）
1000-999（总共999-1000+1=900）
...
*/
int Left=1; //目前，开始的数字位置
long long count=9; //至今数位个数
long long cur_digit_length=1; //当前元素的数位
int res=0;
while( n > count )
{
n-=count;
cur_digit_length++;
Left*=10; //更新
count= 9 * Left * cur_digit_length;
}
long long num= Left+(n-1)/cur_digit_length;
return to_string(num)[ (n-1)%cur_digit_length ] - '0';
}
};大数算法『模板』
1.大数加法
- 牛客网，两个链表生成相加链表
1、『逆向思维』去模拟2.大数乘法⭐️
- 牛客网，大数乘法（两个正数版本）『我的博客题解』
- 乘法的坑比加法多！✔️
- LeetCode43. 字符串相乘
- 对『写代码前，测试先行』的理解更深刻
1、注意，两个为0的时候，要特判『不然，会有一个样例过不了』
2、『逆向思维』去模拟
3、用数组的下标0,1,2去模拟，10^0,10^1啥的
4、一定要找到第1个不是0的数字，然后再组装回来
样例举例
Len1 Len2 Len 长度
0 123 0 特判
123 0 0 特判
-------------------------
2 3 6 Len1+Len2-1
2 5 10 Len1+Len2
10 10 100 Len1+Len2-1
20 50 1000 Len1+Len2
规律：我们的结果最大只需开
Len1+Len2
然后，自己想办法，获得啥时候-1class Solution {
public:
string multiply(string num1, string num2) {
//代码健壮性
if( 0==num1.size() || 0==num2.size() )
{
throw "error num1.size()||nums2.size()";
}
string res;
//*0的特判
if( 1==num1.size() && '0'==num1[0] )
{
return res+="0";
}
if( 1==num2.size() && '0'==num2[0] )
{
return res+="0";
}
reverse( num1.begin(), num1.end() );
reverse( num2.begin(), num2.end() );
//可能是Len1+Len2-1 Len1+Len2 两种
//vector自动初始化为全0
vector<int> temp( num1.size()+num2.size() );
for( int one=0; one<num1.size(); ++one )
{
for(int two=0; two<num2.size(); ++two )
{
int val=(num1[one]-'0')*(num2[two]-'0');
temp[ one+two ]+=val;
//注意要处理进位！！
int carry=temp[one+two]/10;
temp[one+two]%=10;
int curPos=one+two+1;
while( carry )
{
temp[ curPos ]+=carry;
carry=temp[ curPos ]/10;
temp[curPos]%=10;
++curPos;
}
}
}
int pos=num1.size()+num2.size();
while( pos-- )
{
if( temp[pos] )
{
break;
}
}
//搞定，10*10=100，temp中显示的0010这样的状况
while( pos>=0 )
{
res+=(temp[pos]+'0');
--pos;
}
return res;
}
};3.大数阶乘-N的阶乘
- 方法1: string和int进行
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
// 计算阶乘
// 减少代码的技巧: 用字符串乘以整数 而不是 字符串*字符串
string factorial(string a, int x) {
string res;
// 进位
int carry = 0;
int sum;
for (int i = a.size() - 1; i >= 0; i--) {
sum = carry + (a[i] - '0') * x;
int val = sum % 10;
res += (val + '0');
carry = sum / 10;
}
// 坑: ⭐️多的进位[逐个]插入
// 因为数字x可能很大, 导致carry其实可能远大于10, 所以要慢慢进位
while (0 != carry) {
int val = carry % 10;
res += (val + '0');
carry /= 10;
}
// 记得翻转
reverse(res.begin(), res.end());
return res;
}
int main() {
int n;
while (cin >> n) {
// 0的阶乘=1
string res = "1";
// 计算i>=1的阶乘
for (int i = 1; i <= n; ++i) {
res = factorial(res, i);
}
cout << res << endl;
}
return 0;
}方法2:参考题解：牛客网, 借助2个string来, 只是代码量稍微少点
用long数组存储阶乘结果，数组中的每个数存储阶乘的4位10进制数，不足的用0补充。STL提取出“全排列”『模板』
- 46. 全排列不含重复数字的数组
- 47. 全排列 II可包含重复数字的序列
1.不含重复数字/可包含重复数字『均可』
next_permutation的源代码实现下一个排列的算法模板：『Left（前边） Right（后边） 』
next_permutation()会取得[Left,Right)所标示之序列的下一个排列组合。- 如果没有下一个排列组合，便返回
false，否则返回true - 『4步伐』
- 1.首先，从『最尾端开始往前』寻找两个相邻元素，令靠近左边的第1元素为LeftOne，靠近左边的第二元素为LeftTwo，且满足
- 2.找到这样一组相邻元素后，再从『最尾端开始往前』检验,找出第1个大于LeftOne（）的元素，令为Temp
- 3.
iter_swap( LeftOne, Temp ) - 4.再将LeftTwo及其之后的所有元素颠倒排列
上1个排列的算法『
prev_permutation()会取得[Left,Right)所标示之序列的上一个排列组合。- 如果没有上一个排列组合，便返回
false，否则返回true - 『4步伐』
- 1.首先，从『最尾端开始往前』寻找两个相邻元素，令靠近左边的第1元素为LeftOne，靠近左边的第二元素为LeftTwo，且满足
- 2.找到这样一组相邻元素后，再从『最尾端开始往前』检验,找出第1个小于LeftOne（）的元素，令为Temp
- 3.
iter_swap( LeftOne, Temp ) - 4.再将LeftTwo及其之后的所有元素颠倒排列
格雷码的由来
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> res;
int count=1<<n;
for(int loop=0; loop<count; ++loop){
res.push_back( loop^( loop>>1 ) );
}
return res;
}
};位运算-规律
1.交换
int a=1;
int b=2;
a=a^b;
b=a^b;
a=a^b;记忆：观察知道，右边都是a^b
2.异或的性质
0^x=0
如果：
a^b=other;
那么：
(a^other==b);
(b^other==a);