1007: Triangles
Result | TIME Limit | MEMORY Limit | Run Times | AC Times | JUDGE |
---|---|---|---|---|---|
3s | 8192K | 7020 | 2611 | Standard |
A triangle can be made up out of dots, like the ones shown below:
The number of dots in each one is called a triangular number. More precisely, a number is said to be triangular if it is of the form ½ n(n+1). The numbers 1, 3, 6, 10, and 15 are all triangular.
Given a number, determine if it is triangular. If it is, draw the corresponding right triangle, if it is not, say so.
Input
A positive integer less than 2000. Each case will be on a separate line. A zero (0) denotes the end of input.
Output
The phrase “<num> is a triangular number.” followed by a right triangle of “*” characters, or the phrase “<num> is not a triangular number.” The triangle should be oriented with the hypotenuse on the right and the right angle in the lower left.
Sample Input
3
4
6
0
Sample Output
3 is a triangular number.
*
**
4 is not a triangular number.
6 is a triangular number.
*
**
***
代码如下:
#include <iostream>
#include <queue>
#include <cmath>
using namespace std;
bool isTriangle(int n)
{
n = 2*n;
int srt = (int)sqrt(n);
if (srt * (srt + 1) == n)
return true;
return false;
}
void printTriangle(int n)
{
for (int i = 1 ; i <= n; i ++)
{
for(int j = 1; j <= i ; j ++)
cout<<"*";
cout<<endl;
}
}
int main()
{
queue<int> input;
int a;
while (cin>>a && a!=0)
{
input.push(a);
}
while (!input.empty())
{
if(isTriangle(input.front()))
{
cout << input.front() << " is a triangular number."<<endl;
printTriangle((int)sqrt(input.front()*2));
}
else
{
cout << input.front() << " is not a triangular number."<<endl;
}
input.pop();
}
return 0;
}
主要解题思路: 如果一个数是三角数,那么一定有N= 1/2*n(n+1),因此就有:2*N = n*(n + 1); 可以推出:n < sqrt(n*(n+1)) < n + 1,所以我们可以得出:n = (int)sqrt( n*(n+1))(注:截取整数部分,这个结果一定不是一个整数) 然后再验证是否有:n*(n + 1) == 2*N,如果是,那么N就是三角数,否则就不是三角数。 知道了这些就不难理解上面的解题思路了!! 有不妥之请留言,共同探讨,共同进步!