首页 > 试题广场 >

组装三角形

[编程题]组装三角形

热度指数：5742 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

牛牛手里有N根木棒,分别编号为1~N,现在他从N根里想取出三根木棒，使得三根木棒构成一个三角形,你能计算出牛牛有多少种取法吗?(考虑两种取法中使用的木棒编号有一个不一样就认为是不同的取法)。

输入描述:

首先输入一个正整数N，接下来的一行共有N个正整数表示每个木棒的长度。

N ≤ 50, 木棒的长度 ≤ 10000.

输出描述:

输出一个整数表示方法数。

示例1

输入

5
1 2 3 4 5

输出

算法知识视频讲解

Java

培生

	public static int sanjiaoxing(int[] arrys) {
		int n = 0;

		int length = arrys.length;

		for (int i = 0; i < length - 2; i++) {
			for (int j = i + 1; j < length - 1; j++) {
				for (int k = j + 1; k < length; k++) {
					if (arrys[i] < arrys[j] + arrys[k] && arrys[j] < arrys[i] + arrys[k]
							&& arrys[k] < arrys[i] + arrys[j]) {
						n++;
					}
				}
			}
		}

		return n;
	}

发表于 2019-08-13 15:09:18 回复(0)

小六神通

利用了暴力枚举

#include <iostream>

using namespace std;

bool IsTri(int n1, int n2, int n3)

{

if ((n1 + n2) > n3 && (n1 + n3) > n2 && (n2 + n3) > n1)

{

return true;

}

return false;

}

int main()

{

int count = 0;

int N;

cin >> N;

int*arr = new int[N];

for (int i = 0; i < N; i++)

{

cin >> arr[i];

}

//i,j,k三个的值分别为三条边可能的值所在的值域，分别赋给i,j,k并一一测试

for (int i = 0; i < N; i++)

for (int j = 0; j < N;j++)

for (int k = 0; k < N; k++)

{

//这是用来判断此时的值是否满足条件

if ((arr[i] != arr[j] && arr[i] != arr[k] && arr[j] != arr[k]) && IsTri(arr[i],arr[j],arr[k]))

{

//cout << i << " " << j << " " << k << endl;

count++;

continue;

}

else

{

continue;

}

//一种情况下在全排列中会出现6次:3*2*1==6，所以除以6

cout << (count / 6) << endl;

return 0;

发表于 2017-07-25 13:21:42 回复(0)

JavaScript

小儿比春花

给JS草一下存在感


	process.stdin.resume();



	process.stdin.setEncoding('ascii');



	 



	var input = "";



	var input_array = "";



	 



	process.stdin.on('data', function (data) {



	    input += data;



	});



	 



	process.stdin.on('end', function () {



	    input_array = input.split("\n");



	    var arr = input_array[1].split(" ");



	    for(var i = 0; i < arr.length; i++){



	        arr[i] = +arr[i];



	    }



	     



	    arr.sort(function(a, b) { return a - b; });



	    var str = arr.join(",");



	    var count = 0;



	    for(var i = 0; i < arr.length - 1; i++){



	        for(var j = i + 1; j < arr.length; j++){



	            var min = Math.abs(arr[i] - arr[j]);



	            var max = arr[i] + arr[j];



	            for(var k = arr[j] + 1; k < max; k++){



	                if(arr.indexOf(k) >= 0){



	                    var index = arr.indexOf(k);



	                    while(arr[index] == k){



	                        if( index != i && index != j){



	                            count++;



	                        }



	                        index++;



	                    }



	                }



	            }



	        }



	    }



	    console.log(count);



	});

发表于 2017-04-08 18:14:19 回复(0)

sky_han

 暴力解决。。。感觉自己好low。。。
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int count=0;
    vector<int>a(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n-2;i++)
        for(int j=i+1;j<n-1;j++)
            for(int k=j+1;k<n;k++)
            if(a[i]+a[j]>a[k]&&a[i]+a[k]>a[j]&&a[j]+a[k]>a[i])
                count++;
    cout<<count<<endl;
    return 0;
}

发表于 2017-03-28 23:23:49 回复(0)

Scruel

普通版本：复杂度O(n^3)

import java.util.Arrays;
import java.util.Scanner;

/**
 * Created by Scruel on 2017/3/24.
 * Personal blog : http://blog.csdn.net/scruelt  * Github : https://github.com/scruel  */
public class Main {

        public static void main(String[] args) {
                Scanner input = new Scanner(System.in);
                int n = input.nextInt();
                int[] arr = new int[n];
                for (int i = 0; i < n; i++) {
                        arr[i] = input.nextInt();
                }
                System.out.println(solve(arr));
        }

        private static int solve(int[] arr) {
                int cnt = 0;
                Arrays.sort(arr);
                for (int i = 0; i < arr.length; i++) {
                        for (int j = i + 1; j < arr.length; j++) {
                                for (int k = j + 1; k < arr.length; k++) {
                                        if (arr[i] + arr[j] > arr[k])
                                                cnt++;
                                        else
                                                break;
                                }
                        }
                }
                return cnt;
        }
}

二分版本：复杂度O(n^2logn)

import java.util.Arrays;
import java.util.Scanner;

/**
 * Created by Scruel on 2017/3/24.
 * Personal blog : http://blog.csdn.net/scruelt  * Github : https://github.com/scruel  */
public class Main {
        public static void main(String[] args) {
                Scanner input = new Scanner(System.in);
                int n = input.nextInt();
                int[] arr = new int[n];
                for (int i = 0; i < n; i++) {
                        arr[i] = input.nextInt();
                }
                System.out.println(solve(arr));
        }

        private static int solve(int[] arr) {
                int cnt = 0;
                Arrays.sort(arr);
                int n = arr.length;
                //二分查找降低复杂度到O(n^2logn)
                for (int i = 0; i < arr.length; i++) {
                        for (int j = i + 1; j < arr.length; j++) {
                                int num = Arrays.binarySearch(arr, arr[i] + arr[j]);
                                if (num < 0) num = -(num + 2);
                            	if (num == -1) continue;
                                if (arr[num] == arr[i] + arr[j]) {
                                        cnt += num - j - 1;
                                        //去除binarySearch返回的index值不是相等情况中第一个出现的位置的多余统计
                                        for (int k = num - 1; k >= j; k--) {
                                                if (arr[num] == arr[k]) cnt--;
                                                else break;
                                        }
                                } else if (arr[num] < arr[i] + arr[j])
                                        cnt += num - j;
                        }
                }
                return cnt;
        }
}

编辑于 2017-06-11 15:57:51 回复(5)

魅影骑士


	importjava.util.Scanner;



	//组装三角形，暴力枚举三边，然后依次判断三边是否能组成三角形即可



	publicclassMain {



	    publicstaticbooleancheck(inta,intb,intc){



	        returna < b + c && b < a + c && c < a + b;



	    }



	    publicstaticvoidmain(String[] args){



	        Scanner in = newScanner(System.in);



	        while(in.hasNext()){



	            intn = Integer.valueOf(in.nextLine());



	            int[] arr = newint[n];



	            for(inti = 0; i < arr.length; i++){



	                arr[i] = in.nextInt();



	            }



	            intcount = 0;



	            for(inti = 0; i < n; i++){



	                for(intj = i + 1; j < n; j++){



	                    for(intk = j +1; k < n; k++){



	                        if(check(arr[i],arr[j],arr[k])){



	                            count++;



	                        }



	                    }



	                }



	            }



	            System.out.println(count);



	        }



	    }



	}

发表于 2017-03-24 16:15:36 回复(0)

Python 3

彬彬12345

import itertools
n=int(input())
nums=list(map(int,input().split()))
res=[]
count=0
for item in itertools.combinations(nums,3):
    res.append(list(item))
    res[0]=sorted(res[0])
    if res[0][0]+res[0][1]>res[0][2]:
        count+=1
    del res[-1]
print(count)

发表于 2022-04-08 15:27:20 回复(1)

三大爷的剑

尺取办法

package main
import (
    "fmt"
    "sort"
)

func main() {
    var arr []int 
    var count int
    fmt.Scanln(&count)
    
    if count <  3 {
        fmt.Println(0)
        return
    }
    for i := 0; i < count; i++ {
        var num int 
        fmt.Scanf("%d", &num)
        arr = append(arr, num)
    }
    sort.Ints(arr)
    // 尺取
    ans := 0
    for i := 0; i < len(arr) - 2; i ++ {
        l,r := i + 1, i + 2
        
        for r < len(arr) {
            if r == l {
                r ++
                continue
            }
             // 任意两边和大于另一个边
            abL := arr[i] + arr[l]
            if abL > arr[r]  {
                mostLessRight := r
                for mostLessRight < len(arr) && arr[mostLessRight] < abL {
                    mostLessRight ++
                }
                
                ans += mostLessRight - r
                l ++
            }else {
                l ++
            }
        }
    }
    fmt.Println(ans)   
}

发表于 2021-09-05 00:45:39 回复(0)

nooBiee

import sys
 
try:
    n = int(input())
    t = list(map(int, input().split()))
    isum = 0
    for i in t:
        for j in t:
            for k in t:
                if i!=j and i!=k and j!=k:
                    if i+k>j and i+j>k and j+k>i:
                        isum += 1
    print(isum//6)
except:
    pass

发表于 2020-03-19 22:32:25 回复(0)

albert233

class Solution
{
public:
    int triangleNumber(vector<int>& nums)
    {
        int n = nums.size();
        int res = 0;
        for(int i = n - 1; i >= 0; i++)
        {
            int left = 0, right = i - 1;
            while(left < right)
            {
                if(nums[left] + nums[right] > nums[i])
                {
                    res += right - left;
                    --right;
                }
                else 
                    ++left;
            }
        }
        return res;
    }
}

发表于 2020-02-16 13:40:38 回复(0)

JavaScript

Afraaa

发表于 2018-08-30 15:44:36 回复(0)

进步不断

   Python解法：先排列，再计算  
   importitertools,copy  
   m,ss,suml=input(),list(map(int,input().split())),0  
      
   fori initertools.combinations(ss,3):  
       s,flag=list(i),0  
       fori inrange(3):  
           a=copy.deepcopy(s)  
           a.remove(s[i])  
           ifnot(a[0]+a[1]>s[i] andabs(a[0]-a[1])<s[i]):  
               flag=1  
       ifflag==0:  
           suml+=1  
   print(suml)  

发表于 2018-07-19 00:52:56 回复(0)

sunshinebooming

   //三角形，两条最小边之和大于最大边
  
   //暴力枚举，不过枚举之前先给数据从小到大排一下顺序，保证提取出来的前两条边是小边  
   
  
   #include <iostream>
  
   #include <vector>  
   #include <string>  
   #include <algorithm>  
   using namespace std;  
      
   int fun(vector<int> vec)  
   {  
       int cnt = 0;  
       vector<int>::iterator ite1, ite2, ite3;  
          
       sort(vec.begin(), vec.end());  
       for(ite1 = vec.begin();ite1 < vec.end();ite1++)  
           for(ite2 = ite1 + 1;ite2 < vec.end();ite2++)  
               for(ite3 = ite2 + 1;ite3 < vec.end();ite3++)  
               {  
                   if(*ite1 + *ite2 > *ite3)  
                   {  
                       cnt++;  
                   }  
               }  
          
       return cnt;  
   }  
      
   int main(void)  
   {  
       int n;  
       int temp;  
       vector<int> vec;  
       cin >> n;  
       while(n--)  
       {  
           cin >> temp;  
           vec.push_back(temp);  
       }  
          
       cout << fun(vec) << endl;  
       return 0;  
   }  

发表于 2018-05-16 13:56:58 回复(0)

喜欢打地铺

#include <iostream>
using namespace std;

int* order(int array[],int n){
    int temp;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(array[j]<array[i]){
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }
    return array;
}
int main(int argc, const char * argv[]) {
    int n,count=0,m;
    cin>>n;
    int array[n];
    for(int i=0;i<n;i++){
        cin>>array[i];
    }
    int temp;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(array[j]<array[i]){
                temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }
    for(int i=0;i<n-2;i++){
        for(int j=i+1;j<n-1;j++){
            m = j+1;
            while(array[i]+array[j]>array[m] &&m<n){
                count++;
                m++;
            }
        }
    }
    cout<<count;
}

发表于 2017-11-07 14:55:25 回复(0)

Java

传说中的汽水枪

/**
 * 算法的复杂度是O(n平方)
 * 思路是穷举顺序依次取两条边(i,j),i是从2开始(不可能从1开始),j是从i+1开始
 * */
public static int countOfTriangle(int max) {
    if (max <= 3) {
        return 0;
    }
    int count = 0;
    // i最大的是:max - 2,所以i < max - 1
    for (int i = 2; i < max - 1; i++) {
        for (int j = i + 1; j < max; j++) { // j 最大的是:max - 1,所以j < max
            // 第三条边最小的可能值
            int minK = j + 1;
            // 第三条边最大的可能值
            int maxK = Math.min(max, i + j - 1);
            int kCount = 0;
            if (maxK >= minK) {
                kCount = maxK - minK + 1;
            }
            count += kCount;
        }
    }
    return count;
}

编辑于 2017-11-03 13:41:28 回复(0)

牛客375006号

比大多数答案要好。不多说，自己看代码。

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

int main(int argc, const char * argv[]) {
    int n, count = 0;
    cin>>n;
    int l[n];
    for (int i = 0; i < n; i++) {
        cin>>l[i];
    }
    sort(l, l + n);
    int aIndex, bIndex, cIndex;
    for (aIndex = 0; aIndex < n - 2; aIndex++) {
        for (bIndex = aIndex + 1; bIndex < n - 1; bIndex++) {
            for (cIndex = n - 1; cIndex > bIndex; cIndex--) {
                if (l[aIndex] + l[bIndex] > l[cIndex]) {
                    count += cIndex - bIndex;
                    break;
                }
            }
        }
    }
    cout<<count;
    return 0;
}

编辑于 2017-10-19 13:26:41 回复(0)

异想难寻

#include<iostream>
using namespace std;

bool bool***(int a,int b,int c)
{
    int ma = a>b?a:b;
    int mb = a<b?a:b;
    int mc = ma>c?ma:c;
    ma = ma<c?ma:c;
    if(ma+mb > mc)
        return 1;
    return 0;
}

int main()
{
    int n,ret = 0;
    cin >> n;
    int nums[n];
    for(int i=0;i<n;i++)
    {
        cin >> nums[i];
    }
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
            for(int k=j+1;k<n;k++)
            {
                if(bool***(nums[i],nums[j],nums[k]))
                    ret ++;
            }
    cout << ret;
    return 0;
}

发表于 2017-09-01 09:38:22 回复(0)

南邮kd

import java.util.*;

public class Main {

public static void main(String[] args) {

// TODO Auto-generated method stub

Scanner sc=new Scanner(System.in);

while(sc.hasNext()){

int num=sc.nextInt();

int arr[]=new int[num];

int i=0;

while(i<num){

arr[i]=sc.nextInt();

i++;

}

Arrays.sort(arr);

int count=0;

//对数组进行组合匹配;

for(int j=0;j<arr.length-2;j++){

for(int k=j+1;k<arr.length-1;k++){

for(int l=k+1;l<arr.length;l++){

if(arr[j]+arr[k]>arr[l]){ //由于数组是有序的，所以只要满足两边之和>第三边即可;

count++;

}

System.out.println(count);

}

sc.close();

}

发表于 2017-08-23 09:22:27 回复(0)

世界和平0.0

//暴力枚举
 11 #include <stdio.h>
 12 #include <stdlib.h>
 13 
 14 //判断 i j k 是否相等
 15 int func1(int i,int j,int k)
 16 {
 17     int stat1=0;
 18 
 19     if(i == j)
 20         stat1=1;
 21     else if(i==k)
 22         stat1=1;
 23     else if(j==k)
 24         stat1=1;
 25     else
 26         ;
 27 
 28     return stat1;
 29 }
 30 
 31 //测试ijk是否满足条件
 32 int func2(int i,int j,int k)
 33 {
 34     int stat2=0;
 35 
 36     if(i+j>k && i+k>j && j+k>i)
 37                 stat2=1; 
 38                 
 39     return stat2;
 40 }   
 41 
 42 
 43 int main(void)
 44 {
 45     int N=0;
 46     long int cnt=0;
 47     int i=0;
 48     int j=0;
 49     int k=0;
 50 
51     printf("input N(<=10000)\n");
 52     if(scanf("%d",&N) == 1){
 53         if(N<10000 && N>0){
 54             for(i=1; i<=N; i++){
 55                 for(j=i+1; j<=N; j++){
 56                     for(k=j+1; k<=N; k++){
 57                         if(!func1(i,j,k)){
 58                             if(func2(i,j,k))
 59                                 cnt++;
 60                         }
 61                     }
 62                 }
 63             }
 64             printf("***%ld***\n",cnt);
 65         }
 66         else{
 67             printf("error:N\n");
 68             return EXIT_FAILURE;
 69         }
 70     }
 71     else{
 72         printf("error:N\n");
 73         return EXIT_FAILURE;
 74     }
 75 
 76     return 0;
 77 }

发表于 2017-07-19 15:11:25 回复(0)

那年夏天宁静的海00

import java.util.Scanner;

public class test3{

public static void main(String[] args){

Scanner sc = new Scanner(System.in);

while(sc.hasNext()){

int n = sc.nextInt();

long [] arr = new long [n];

for(int i=0;i<n;i++){

arr[i]=sc.nextLong();

}

int res =0;

for(int i=0;i<n;i++){

for(int j=i+1;j<n;j++){

for(int k=j+1;k<n;k++){

if(check(arr[i],arr[j],arr[k])){

res++;

}

System.out.println(res);

}

public static boolean check(long a,long b,long c){

if(a+b>c && a+c>b &&b+c>a){

return true;

}

else{

return false;

}

发表于 2017-07-09 17:15:58 回复(0)

提交观点

问题信息

C++工程师 golang工程师 2017 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师 c#工程师模拟测试开发工程师数学大数据开发工程师 Java工程师牛客

来自：【2017】牛客模考（...

难度：

26条回答 41收藏 9043浏览

通过挑战的用户

有才X

2023-03-14 20:36:44
伊拉斯谟

2023-03-10 17:51:57
小荒

2023-03-09 10:53:49
月澈

2023-03-09 07:28:12
在发呆的小章鱼

2023-03-06 12:10:46