网站建设技术 论坛,深圳建设外贸网站,建设工程教育网站,网站后台管理怎么做目录
1.题目
2.三种常规解法
方法1:递归做
编辑
方法2:改用循环做
初写的代码
提交结果
分析
修改后的代码
提交结果
for循环的其他写法
提交结果
方法3:循环数组
提交结果
3.方法4:矩阵
算法
代码实践
1.先计算矩阵n次方
2.后将矩阵n次方嵌入递推式中
提…目录
1.题目
2.三种常规解法
方法1:递归做
编辑
方法2:改用循环做
初写的代码
提交结果
分析
修改后的代码
提交结果
for循环的其他写法
提交结果
方法3:循环数组
提交结果
3.方法4:矩阵
算法
代码实践
1.先计算矩阵n次方
2.后将矩阵n次方嵌入递推式中
提交结果 1.题目
https://leetcode.cn/problems/three-steps-problem-lcci/ 三步问题。有个小孩正在上楼梯楼梯有n阶台阶小孩一次可以上1阶、2阶或3阶。实现一种方法计算小孩有多少种上楼梯的方式。结果可能很大你需要对结果模1000000007。 示例1: 输入n 3 输出4说明: 有四种走法示例2: 输入n 5输出13提示: n范围在[1, 1000000]之间 2.三种常规解法
方法1:递归做
和之前青蛙跳台阶的思想一样(参见35.【C语言】详解函数递归文章),先找递推公式,再写递归
int recursion(int n)
{if (n1)return 1;if (n2)return 2;if (n3)return 4;return (recursion(n-1)recursion(n-2)recursion(n-3))%1000000007;
}
int waysToStep(int n)
{return recursion(n);
}
算法上没问题,但是时间复杂度过高,提交后没有通过 方法2:改用循环做
初写的代码
int waysToStep(int n)
{if (n1)return 1;if (n2)return 2;if (n3)return 4; int a1;int b2;int c4;int d0;for (int i3;in;i){dabc;ab;bc;cd;}return c%1000000007;
}
提交结果 分析
虽然代码中返回值写成c%1000000007,但是没有完全领会题目的意思,c的值并没有真正改变,可以看看报错的数字:当n61时,2082876103 1748130326相加溢出了,可以设想2082876103和1748130326产生的原因,n某个数溢出了,可以使程序溢出的n的临界值
将代码最后改成return c;测试n的值
多次尝试后 当未模1000000007时,
n34n35n3461569347411324368522082876103
61569347411324368521748130326(大于1000000007),求出了出错提示上的两个数字
abc可能数值超过int的范围,因此要分两次模1000000007,由于dabc,则程序的计算顺序为:先算ab,后算c,则应该对(ab)先模1000000007再c,再对d模一次 修改后的代码 d(ab)%1000000007c;d%1000000007;ab;bc;cd;
提交结果 for循环的其他写法
for (int i3;in;i){d(ab)%1000000007c;ab;bc;cd;c%1000000007;}提交结果 方法3:循环数组
int waysToStep(int n)
{if (n1)return 1;if (n2)return 2;if (n3)return 4;int* arr(int*)malloc(sizeof(int)*(n1));arr[1]1;arr[2]2;arr[3]4;for (int i4;in;i){arr[i](arr[i-3]arr[i-2])%1000000007arr[i-1];arr[i]%1000000007;}return arr[n];}
提交结果 3.方法4:矩阵
算法 改写成矩阵形式 ① ② ③ 将上方三个式子合三为一
(关键式子)
递推 ......
可以一直递推到
************************************************************************************************************** **************************************************************************************************************
设则最终答案为
代码实践
1.先计算矩阵n次方
//矩阵[1,1,1;1,0,0;0,1,0]的n次方(n为计算次数)
#define _CRT_SECURE_NO_WARNINGS
#include stdlib.h
#include stdio.h
int main()
{int arr1[3][3] { 1,1,1,1,0,0,0,1,0 };int arr2[3][3] { 0 };int arr3[3][3] { 1,1,1,1,0,0,0,1,0 };int n;scanf(%d, n);for (int i 1; i n; i){if (i % 2)//i为奇数{for (int i 0; i 3; i){for (int j 0; j 3; j){arr2[i][j] 0;for (int k 0; k 3; k){arr2[i][j] arr3[i][k] * arr1[k][j];}}}}else{for (int i 0; i 3; i){for (int j 0; j 3; j){arr3[i][j] 0;for (int k 0; k 3; k){arr3[i][j] arr2[i][k] * arr1[k][j];}}}}}if (n % 2){for (int i 0; i 3; i){for (int j 0; j 3; j){printf(%d , arr2[i][j]);}printf(\n);}}else{for (int i 0; i 3; i){for (int j 0; j 3; j){printf(%d , arr3[i][j]);}printf(\n);}}return 0;
}
2.后将矩阵n次方嵌入递推式中
int waysToStep(int n)
{if (n1)return 1;if (n2)return 2;if (n3)return 4;long long arr1[3][3] { 1,1,1,1,0,0,0,1,0 };long long arr2[3][3] { 0 };long long arr3[3][3] { 1,1,1,1,0,0,0,1,0 };n-4;//不是-3,计算的是矩阵n次方的运行次数for (int i 1; i n; i){if (i % 2)//i为奇数{for (int i 0; i 3; i){for (int j 0; j 3; j){arr2[i][j] 0;for (int k 0; k 3; k){arr2[i][j] (arr3[i][k] * arr1[k][j])%1000000007;}}}}else{for (int i 0; i 3; i){for (int j 0; j 3; j){arr3[i][j] 0;for (int k 0; k 3; k){arr3[i][j] (arr2[i][k] * arr1[k][j])%1000000007;}}}}}if (n%2)return (arr2[0][0]*4arr2[0][1]*2arr2[0][2])%1000000007;elsereturn (arr3[0][0]*4arr3[0][1]*2arr3[0][2])%1000000007;
}
提交结果 封装成函数
其实封装成函数代码看起来更简洁
void calc_matirx_power(long long int (*a)[3] ,long long int (*b)[3] ,long long int (*c)[3] )
{for (int i 0; i 3; i){for (int j 0; j 3; j){a[i][j] 0;for (int k 0; k 3; k){a[i][j] (b[i][k] * c[k][j])%1000000007;}}}
}int waysToStep(int n)
{if (n1)return 1;if (n2)return 2;if (n3)return 4;long long arr1[3][3] { 1,1,1,1,0,0,0,1,0 };long long arr2[3][3] { 0 };long long arr3[3][3] { 1,1,1,1,0,0,0,1,0 };n-4;//不是-3,计算的是矩阵n次方的运行次数for (int i 1; i n; i){if (i % 2)//i为奇数{calc_matirx_power(arr2,arr3,arr1);}else{calc_matirx_power(arr3,arr2,arr1);}}if (n%2)return (arr2[0][0]*4arr2[0][1]*2arr2[0][2])%1000000007;elsereturn (arr3[0][0]*4arr3[0][1]*2arr3[0][2])%1000000007;
}
注意calc_matrix_power参数类型的写法:long long int (*a)[3]
这种写法可以看看这篇文章:★♛★指针重难点合集 提交结果
