有多少种方法可以从1, 2, 3, …, n中选出3个不同的整数, 使得以
它们为三边长可以组成三角形? 比如n=5时有3种方法, 即(2, 3,
4) , (2, 3, 5) , (3, 4, 5) 。 n=8时有22种方法。
【输入格式】
输入包含多组测试数据, 每组数据的第一行为整数
n(3≤n≤1000000) 。 输入用n<3的标志结束。
170
【输出格式】
对于每组数据, 输出其方案总数。
【分析】
三重循环的时间复杂度为O(n3) , 采用这种方法肯定超时。 这样的
规模即使是O(n2) 时间的算法都很难承受, 那么只能进行一些数学分析
了。
用加法原理, 设最大边长为x的三角形有c(x) 个, 另外两条边长分
别为y和z, 根据三角形不等式[2]有y+z>x。 所以z的范围是x-y<z<x。
根据这个不等式, 当y=1时x-1<z<x, 显然无解; y=2时只有一个
解(z=x-1) ; y=3时有两个解(z=x-1或者z=x-2) ……直到y=x-
1时有x-2个解。 根据等差数列求和公式, 一共有0+1+2+…+(x-3)
+(x-2) =(x-1) (x-2) /2个解。
可惜, 这并不是c(x) 的正确数值, 因为上面的解包含了y=z的情
况, 而且每个三角形算了两遍(想一想, 为什么) 。 解决方案很简单,
首先统计y=z的情况。 y的取值从x/2+1开始到x-1为止, 一共有x-1-
x/2=(x-1) /2个解, 然后把这部分解扣除, 再除以2, 即
原题要求的实际上是“最大边长不超过n的三角形数目”f(n) 。 根据
加法原理, f(n) =c(1) +c(2) +…+c(n) 。 可以写成递推式
f(n) =f(n-1) +c(n) 。 代码如下。
#include
using namespace std;
long long f[1000010];
int main(){
f[3]=0;
for(long long x=4;x<=1000000;++x)
f[x]=f[x-1]+((x-1)*(x-2)/2-(x-1)/2)/2;
int n;
while(cin>>n&&n>=3) cout<
未经允许不得转载!UVa 11401 数三角形(组合数学)