【矩阵快速幂】封装类及测试用例及样例

这篇具有很好参考价值的文章主要介绍了【矩阵快速幂】封装类及测试用例及样例。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

作者推荐

视频算法专题

通俗的说,就是矩阵的乘方。

封装类

核心代码

class CMat
{
public:
	// 矩阵乘法
	static vector<vector<long long>> multiply(const vector<vector<long long>>& a, const vector<vector<long long>>& b) {
		const int r = a.size(), c = b.front().size(),iK = a.front().size();
		assert(iK == b.size());
		vector<vector<long long>> ret(r, vector<long long>(c));
		for (int i = 0; i < r; i++)
		{
			for (int j = 0; j < c ; j++) 
			{
				for (int k = 0; k < iK; k++)
				{
					ret[i][j] = (ret[i][j] + a[i][k] * b[k][j] ) % s_llMod;
				}
			}
		}
		return ret;
	}

	// 矩阵快速幂
	static vector<vector<long long>> pow( const vector<vector<long long>>& a, vector<vector<long long>> b, long long n) {
		vector<vector<long long>> res = a;
		for (; n; n /= 2) {
			if (n % 2) {
				res = multiply(res, b);
			}
			b = multiply(b, b);
		}
		return res;
	}
	static vector<vector<long long>> TotalRow(const vector<vector<long long>>& a)
	{
		vector<vector<long long>> b(a.front().size(), vector<long long>(1, 1));
		return multiply(a, b);
	}
protected:
	const static long long s_llMod = 1e9 + 7;
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}
}


int main()
{
	vector<vector<long long>> pre = { {1,2} };
	vector<vector<long long>> mat = { {2,3},{1,10} };
	{	
		auto res = CMat::pow(pre, mat, 0);
		Assert(pre, res);
	}
	{
		auto res = CMat::multiply(pre, mat);
		Assert(vector<vector<long long>>{ {4, 23}}, res);
		auto res2 = CMat::pow(pre, mat,1);
		Assert(res2, res);
	}
	{
		auto res = CMat::pow(pre, mat, 2);
		auto res1 = CMat::multiply(pre, mat);
		auto res2 = CMat::multiply(res1, mat);
		Assert(res2, res);
		Assert(vector<vector<long long>>{ {31, 242}}, res);
	};

	for (int i = 3; i < 100; i++)
	{
		auto res = pre;
		for (int j = 0; j < i; j++)
		{
			res = CMat::multiply(res, mat);
		}
		auto res2 = CMat::pow(pre, mat, i);
		Assert(res2, res);
	}
	
}

具体例子

题目、分析和原理见:

【动态规划】【矩阵快速幂】【滚动向量】C++算法552. 学生出勤记录 II

原解法用二维表示状态,改成一维。 i是缺勤数量,j是连续迟到数,新的状态为:3*i+j
6种状态,故转移矩阵为6行6列,故结果矩阵为6列,6个数据1行就足够了。
令旧结果矩阵为mat1,转移矩阵为mat2,新矩阵为mat3,K mat1的列数,mat2的行数。则:
mat3[r][c] = Sum [ 0 , k ) i ^{i}_{[0,k)} [0,k)i(mat1[r][i]*mat2[i][c])

i在mat1中列号,在mat2中是行号。 也就是旧状态在第几列,mat2就在第几行。
新状态就是mat2的行号。

class Solution {
public:
	int checkRecord(int n) {
		vector<vector<long long>> pre(1, vector<long long>(6));//1行6列	
		pre[0][0] = 1;
		vector<vector<long long>> mat(6, vector<long long>(6));
		{	
			//之前的状态在pre是第几列,矩阵中就是第几行。新状态的列号就矩阵的列号
			//处理一次缺勤 ,缺勤两次排除
			for (int i = 0; i < 3; i++)
			{
				mat[i][3]++;
			}
			//处理请假
			for (int i = 0; i < 2; i++)
			{
				for (int j = 0; j < 2; j++)
				{
					const int pre = 3 * i + j;
					mat[pre][pre + 1]++;
				}
			}
			//处理正常
			for (int i = 0; i < 2; i++)
			{
				for (int j = 0; j < 3; j++)
				{
					const int pre = 3 * i + j;
					const int cur = 3 * i;
					mat[pre][cur]++;
				}
			}
		}
		auto res = CMat::pow(pre, mat, n);
		res = CMat::TotalRow(res);
		return res[0][0];
	}
};

测试用例

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}

int main()
{
int n;
{
Solution sln;
n = 0;
auto res = sln.checkRecord(n);
Assert(1, res);
}
{
Solution sln;
n = 1;
auto res = sln.checkRecord(n);
Assert(3, res);
}
{
Solution sln;
n = 2;
auto res = sln.checkRecord(n);
Assert(8, res);
}
{
Solution sln;
n = 3;
auto res = sln.checkRecord(n);
Assert(19, res);
}
{
Solution sln;
n = 4;
auto res = sln.checkRecord(n);
Assert(43, res);
}
{
Solution sln;
n = 5;
auto res = sln.checkRecord(n);
Assert(94, res);
}
{
Solution sln;
n = 6;
auto res = sln.checkRecord(n);
Assert(200, res);
}
{
Solution sln;
n = 7;
auto res = sln.checkRecord(n);
Assert(418, res);
}
{
Solution sln;
n = 10101;
auto res = sln.checkRecord(n);
Assert(183236316, res);
}
}

【矩阵快速幂】封装类及测试用例及样例,# 算法基础,数据结构与算法,矩阵,线性代数,c++,动态规划,算法,矩阵乘法

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 **C+

+17**
如无特殊说明,本算法用**C++**实现。

【矩阵快速幂】封装类及测试用例及样例,# 算法基础,数据结构与算法,矩阵,线性代数,c++,动态规划,算法,矩阵乘法文章来源地址https://www.toymoban.com/news/detail-814777.html

到了这里,关于【矩阵快速幂】封装类及测试用例及样例的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 接口自动化框架篇:流程封装与基于加密接口的测试用例设计

    ​接口测试仅仅掌握 Requests 或者其他一些功能强大的库的用法,是远远不够的,还需要具备能根据公司的业务流程以及需求去定制化一个接口自动化测试框架的能力。所以,接下来,我们主要介绍下接口测试用例分析以及通用的流程封装是如何完成的。 首先在做用例分析之

    2024年02月08日
    浏览(46)
  • 怎么快速定位bug?怎么编写测试用例?

    目录 01定位问题的重要性  02问题定位技巧 03初次怎么写用例 作为一名测试人员如果连常见的系统问题都不知道如何分析,频繁将前端人员问题指派给后端人员,后端人员问题指派给前端人员,那么在团队里你在开发中的地位显而易见 , 口碑、升值、加薪那应该是你遥不可

    2024年02月15日
    浏览(56)
  • test-04-test case generate 测试用例生成 tcases 快速开始

    junit5 系列 基于 junit5 实现 junitperf 源码分析 Auto generate mock data for java test.(便于 Java 测试自动生成对象信息) Junit performance rely on junit5 and jdk8+.(java 性能测试框架。性能测试。压测。测试报告生成。) 自动生成测试用例 关于本指南 本指南详细解释了Tcases的工作原理。在涉及示例

    2024年01月19日
    浏览(40)
  • 手把手教你如何快速定位bug,如何编写测试用例,快来观摩......

    手把手教你如何快速定位bug,如何编写测试用例,快来观摩......手把手教你如何快速定位bug,如何编写测试用例,快来观摩......作为一名测试人员如果连常见的系统问题都不知道如何分析,频繁将前端人员问题指派给后端人员,后端人员问题指派给前端人员,那么在团队里你在开发

    2024年01月20日
    浏览(57)
  • 若依SpringBoot添加单元测试类及测试类启动报错

    在admin 模块中添加单元测试 将以下依赖添加到 admin 的 pom.xml 中 在 src 目录下创建 test.java.MainTests 文件 错误提示: java.lang.IllegalStateException: Failed to load ApplicationContext Caused by: org.springframework.beans.factory.BeanCreationException: Error creating bean with name ‘serverEndpointExporter’ defined in class

    2024年01月20日
    浏览(39)
  • 从0开始python学习-50.pytest之多接口用例封装

    1. yaml用例设计--一个yaml中多个用例,且互相存在关联关系 2. 设计多接口用例读取封装 3. 将读取caseinfo的方法进行list格式的兼容设计

    2024年01月21日
    浏览(35)
  • 软考:软件工程:面向对象技术与UML,时序图,用例图,类对象,封装,继承,多态

    提示:系列被面试官问的问题,我自己当时不会,所以下来自己复盘一下,认真学习和总结,以应对未来更多的可能性 关于互联网大厂的笔试面试,都是需要细心准备的 (1)自己的科研经历, 科研内容 ,学习的相关领域知识,要熟悉熟透了 (2)自己的实习经历,做了 什

    2024年02月11日
    浏览(54)
  • 测试用例设计——WEB通用测试用例

    现在项目做完了,我觉得还是有必要总结一下, 学习 到的内容。毕竟有总结才能有提高嘛!总结一下通用的东西,不管什么项目基本都可能会遇到,有写地方也有重复的或者有的是按照个人的习惯来总结的不一定都对,有不对的地方还是希望大家可以指正! 易用性 1、便于

    2024年04月23日
    浏览(28)
  • 自动生成测试用例_接口测试用例自动生成工具

    写用例之前,我们应该熟悉API的详细信息。建议使用抓包工具Charles或AnyProxy进行抓包。 我们先来了解一下另一个项目har2case 他的工作原理就是将当前主流的抓包工具和浏览器都支持将抓取得到的数据包导出为标准通用的 HAR 格式(HTTP Archive),然后 HttpRunner 将 HAR 格式的数据

    2024年02月05日
    浏览(65)
  • 【测试】MeterSphere单接口用例、自动化场景用例测试教程

    1、在对应的模块下创建接口 2、接口的详细信息填写 3、为该接口添加测试用例 设置断言规则 4、调试单接口测试用例通过(若不通过,根据请求内容、响应体和断言结果排查错误) 1、根据测试场景将单接口自动化用例进行组合,形成场景自动化测试用 输入场景用例名称,

    2024年02月13日
    浏览(55)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包