JOJ 1007解题

阳光穿透心脏的1/2处 2022-06-08 07:18 170阅读 0赞

## ![art.gif][] [1007][]: Triangles ##

--------------------

<table style="font-family:Verdana,Arial,Helvetica,sans-serif; font-size:14px; color:rgb(0,0,0); margin:2px auto; text-align:start">  
 <tbody> 
  <tr> 
   <th style="background-color:rgb(255,238,79); padding-right:5px"> Result</th> 
   <th style="background-color:rgb(255,238,79); padding-right:5px">TIME Limit</th> 
   <th style="background-color:rgb(255,238,79); padding-right:5px">MEMORY Limit</th> 
   <th style="background-color:rgb(255,238,79); padding-right:5px">Run Times</th> 
   <th style="background-color:rgb(255,238,79); padding-right:5px">AC Times</th> 
   <th style="background-color:rgb(255,238,79); padding-right:5px">JUDGE</th> 
  </tr> 
  <tr> 
   <td align="center" style="font-family:Verdana,Arial,Helvetica,sans-serif; font-size:14px"> <span><img src="http://acm.jlu.edu.cn/joj/images/ok1.gif" width="20" height="20" alt="" style="border:0px"></span></td> 
   <td align="center" style="font-family:Verdana,Arial,Helvetica,sans-serif; font-size:14px"> 3s</td> 
   <td align="center" style="font-family:Verdana,Arial,Helvetica,sans-serif; font-size:14px"> 8192K</td> 
   <td align="center" style="font-family:Verdana,Arial,Helvetica,sans-serif; font-size:14px"> 7020</td> 
   <td align="center" style="font-family:Verdana,Arial,Helvetica,sans-serif; font-size:14px"> 2611</td> 
   <td align="center" style="font-family:Verdana,Arial,Helvetica,sans-serif; font-size:14px"> Standard</td> 
  </tr> 
 </tbody> 
</table>

A triangle can be made up out of dots, like the ones shown below:

![1007.gif][]

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就是三角数，否则就不是三角数。

知道了这些就不难理解上面的解题思路了！！

有不妥之请留言，共同探讨，共同进步！

[art.gif]: http://acm.jlu.edu.cn/joj/images/art.gif
[1007]: http://acm.jlu.edu.cn/joj/problemstatus.php?pid=1007
[1007.gif]: http://acm.jlu.edu.cn/joj/images/problems/1007.gif