蓝桥杯 蛇形填数
发布时间
阅读量：
阅读量
目录
- 题目
- 思路
- 代码
题目
如下图所示，小明用从 1 开始的正整数“蛇形”填充无限大的矩阵。
1 2 6 7 15 …
3 5 8 14 …
4 9 13 …
10 12 …
11 …
…
容易看出矩阵第二行第二列中的数是 5。请你计算矩阵中第 20 行第 20 列的数是多少？
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。
本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分
思路
我们讨论n行n列位置上的数，可以发现要求这个(n,n)，可以通过求p1和p2，计算它们的平均数。p1是n阶三角形的最大一个数，p2是n-1阶三角形的最大一个数再加上1。
answer=(f(m)+f(m-1)+1)/2
而p1>p2，且p1和p2都可通过计算三角形底边m得到。从1开始累加到m即可得到n阶三角形中最大的数字。于是先计算底边m。
f(x)=x*(x+1)/2
不是每个三角形的底边都穿过n行n列，而是隔一个三角形才出现一个，由此出现线性关系2n。三角形最长的边为m，代入n=2时，m=5，由此有：
m=2n-1
代码
#include<iostream>
using namespace std;
//计算从1累加到x的值
int f(int x){
return x*(x+1)/2;
}
int main(){
int n;
while(1){
cin>>n;
//计算三角形的底边
int m=2*n-1;
//大三角形+小三角形加一，两数取平均数
cout<<((f(m)+f(m-1)+1)/2)<<endl;
}
system("pause");
return 0;
}全部评论 (0)
还没有任何评论哟~