组装三角形

[编程题]组装三角形

热度指数：5727 时间限制：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)

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)