题目
| 莱布尼兹三角形 |
| 难度级别：B； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
|
试题描述
|
|
如下图所示的三角形，请编程输出图中排在第 n 行从左边数第 m 个位置上的数。
|
|
输入
|
|
一行包括两个正整数，分别为 n 和 m，两数间用一个空格分隔。
|
|
输出
|
|
一个如样例所示格式的分数。
|
|
输入示例
|
|
6 2
|
|
输出示例
|
|
1/30
|
|
其他说明
|
|
数据范围：1<= m <= n <= 100.
|
分析
这道题也是前100道题中为数不多的需要用到算法解决的题了。所用算法为：递推。
递推大概就类似于找规律，通过对数组下标的利用最终在对应位置找到结果。
所以，咱们要先找到规律。
经过观察，我们发现：下一行的第1、2个数相加就等于上一行的第1个数，下一行的第2、3个数相加就等于上一行的第2个数……以此类推，第x行的第a、b个数相加就等于第x-1行的第a个数。同时左右两边则为1/1,1/2,1/3……即分母依次增加1。
发现规律后，我们就可以根据它写代码了。
同时有一点特别要注意：位置越靠下的数的分母越大，int会存不下。
代码
#include<bits/stdc++.h>
using namespace std;
long long a[105][105],n,m;//越往下分子越大，避免炸掉。
int main()
{
a[1][1]=1;
scanf("%lld%lld",&n,&m);
for(long long i=1;i<=n;i++)//本题可以只计算分母，避免精度不够。
{
for(long long j=1;j<=i;j++)
{
if(j==1) a[i][j]=i;//左右两边为1/1,1/2,1/3……
else a[i][j]=a[i-1][j-1]*a[i][j-1]/(a[i][j-1]-a[i-1][j-1]);//第x行的第a、b个数相加就等于第x-1行的第a个数。
}
}
printf("1/%lld",a[n][m]);//输出第n行m列。
return 0;
}