首页 > 代码库 > 三角形数

三角形数

三角形数

时间限制(普通/Java):1000MS/3000MS          运行内存限制:65536KByte
总提交:460            测试通过:114

描述

一定数目的点或圆在等距离的排列下可以形成一个等边三角形,这样的数被称为三角形数。比如10个点可以组成一个等边三角形,因此10是一个三角形数:

    x

   x x

  x x x

 x x x x

开始18个三角形数是13610152128364555667891105120136153171

请求出第n个三角形数。

输入

输入数据包含多组测试用例。

每组测试用例为一个整数N,长度不超100。

输出

对于每组测试用例,输出对应的三角形数。

样例输入

1
2
3
4
5
11111111

样例输出

1
3
6
10
15
61728399382716

题目来源

南京邮电大学计算机学院首届ACM程序设计大赛(2009)


分析:显然大数运算。不知道怎么个大数,实在想不出,求助百度,都是Java的BigInteger,只好又自己想了。

最后:高斯求和~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

(首项+末项)*项数/2。

输入char型数组input[]转换成int数组a[],int数组b[]为a数组加上1得到的。为了方便相乘,数组a和b都是和正常的顺序相反的。

然后a数组和b数组相乘得到数组c。

for(int i=0;i<N;i++)
	{
		for(int j=0;j<N;j++)
		{
			c[i+j] += a[i] * b[j];
		}
	}
	for(int i=0; i<2*N-1;i++)  
	{  
		c[i+1] += c[i]/10;  
		c[i] = c[i]%10;
	}  


为了除以2,将数组c倒过来变成正常的顺序,再除以2。

int remainder = 0; // 余数
	for(int i=0;i<num;i++)
	{
		int tmp = remainder*10 + a[i];
		output[i] = tmp / 2; 
		remainder = tmp % 2;
	}

不过运行时间有点长。。。在想想有什么简便的方法?

暂时没想到 敲打