10195 三角形个数

题目描述

输入一根木棒的长度 n,1≤n≤10000,将该木棒分成三段,每段的长度为正整数,输出由该三段小木棒组成的不一样的三角形个数。

输入格式

见题

输出格式

见题

样例

输入 #1

10
输出 #1

2
数据范围与提示

穷举三角形三条边长(假设为 a、b、c)的可能值,判断能否构成一个三角形,若能则计数,最后输出计数器的值。为了保证组成的三角形不重复,只要在穷举时设定 1≤a≤b≤c≤n-2。优化思想很简单但很重要,“能算不举”,穷举两条边,根据木棒长度直接计算出第三条边长。

分类标签

[枚举]

C++题解代码

#include <bits/stdc++.h>
using namespace std;

int k;
int r;
int n;


// The main procedure
int main() {
  cin>>n;
  r = 0;
  for (int i = 1; i <= (n-2); i++) {
    for (int j = i; j <= ((n-1)-i); j++) {
      k = ((n-j)-i);
      if (k >= j) {
        if (((i+j) > k) && (((i+k) > j) && ((j+k) > i))) {
          r++;
        }
      }
    }
  }
  cout<<r;
  return 0;
}

Blockly题解代码图片