b计算循环次数_第1页
b计算循环次数_第2页
b计算循环次数_第3页
b计算循环次数_第4页
b计算循环次数_第5页
已阅读5页，还剩2页未读， 继续免费阅读

付费下载

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

Problem

BCount

the

Number

of

Cycles2011年5月题目大意定义：如果一个01矩阵中有任何4个1分别在矩形的4个顶点上，则这4个1构成一个四环。给你一个大小为M×N的01矩阵，你需要求出矩阵中四环的数目。解题思路本题是一道简单思维题，主要考核参赛选手的思维能力。此题有个简单的想法就是暴力枚举，时间

复杂度为n^4,根据数据范围来看会超时。由分析可得，将矩阵的两行进行向量点乘，如果结果s小于2，说明这两行不存在四环，如果结果s大于等于2，则这两行的四环数目为C（2，S）。解题思路（续）所以此题可以将各行两两一组进行点乘，然后将各组四环数目相加，即得到最后答案。复杂度为n^3。核心代码及解释result=0;for(i=1;

i<=m;i++)for(j=i+1;

j<=m;

j++){sum=0;for(k=1;

k<=n;

k++)sum+=Matrix[i][k]*Matrix[j][k];//将各行两两进行点乘result+=sum*(sum-1)/2;//将各组四环数目相加}printf("%d\n",result);}int

main(){int

i,j,k,kk;int

m,n,sum,result;while(scanf("%d%d",&m,&n)!=EOF){for(i=1;

i<=m;i++)for(j=1;

j<=n;j++)scanf("%d",&Matrix[i][j]);

retur

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论