Java教程

计蒜客-白菜君的三角形

本文主要是介绍计蒜客-白菜君的三角形，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

白菜君也加入到这个游戏当中来了，现在规则发生了一些改变。目前有一个长度为 nn 的木棍，当做直角三角形的斜边。蒜头君、花椰妹、白菜君要从许多整数长度的木棍中选出三根，分别长为 a, b, ca,b,c。

现在，蒜头君和花椰妹的木棍组成一条直角边 a + ba+b，白菜君组成另外一条直角边 cc，并且要求 a + b \leq ca+b≤c。请问一共可以有多少种取木棍的方案。

提示：a = 3, b = 4a=3,b=4 与 a = 4, b = 3a=4,b=3 算作同一种方案。

 

 思路一：穷举遍历：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

int main(){
    int n;
    cin>>n;
    int kind = 0;
    long long a=0, b=0, c=0;
    for(int i = 1;i < n;i++){
        for(int j = 1;j <= i; j++){
            if(i + j > n && n + j > i)
            if(i*i + j*j == n*n){
                for(int k = 1;k <= j/2;k++){
                    kind++;
                    // cout<<"a:"<<k<<" b:"<<j-k<<" c:"<<i<<endl;
                }           
            }               
        }
    }
    cout<<kind;
    return 0;
}

 

显然有样例会产生超时   思路二：用斜边平方减去一条边的长度，进行遍历，这样每一个能构成三角形的一组数据都会是直角三角形，只要判断第三边是否为整数就行了。 得到第三边后，去除重复，a+b的组合方式为a+b/2中，所以res+=2。   注意：变量类型要声明为long long，否则数据较大的时候会产生错误的结果。   
#include<iostream>
#include<cmath>
using namespace std;

int main(){
    long long n;
    cin>>n;
    long long res = 0;
    double a_b;
    for(long long c = 1;c < n;c++){
        a_b = sqrt(n*n-c*c); //a + b
        if(a_b == int(a_b) && c >= a_b)
        if(a_b + c > n){
            res += a_b/2;
        }
    }
    cout<<res;
    return 0;
}

 

这篇关于计蒜客-白菜君的三角形的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航