4

私が書いた次のコードがあり、完全に動作します。なぜそれが機能するのか理解に苦しむだけです。より具体的には、std::next_permutation を使用するために最初に配列をソートする必要があるのはなぜですか?どの構成からでも開始できません。

そして、私を最も悩ませているのは、なぜ sort(sides, sides+3) と next_permutation(sides, sides+3) を書かなければならないのか、なぜ「+3」! 配列に3つの要素があるからですか？任意の数の要素を使用していた場合はどうなりますか?

bool valid(int sides[], ofstream &outfile)
{
  int i = 0;
  for(; i < 3; i++) {
    if(sides[i] <= 0) {
      outfile << "This is not a valid triangle because it\n "
              << "contains negative sides or contains a\n"
              << "side length of 0\n\n";
      return false;
    }
  }

  do{
    std::sort(sides,sides+3);
    if(sides[0] + sides[1] > sides[2])
      ;
    else{
      outfile << "This is not a valid triangle because "
              << sides[0] << " + " << sides[1]
              << " is not greater than " << sides[2];
      return false;
    }
  }while(std::next_permutation(sides,sides+3));

  return true;
}
4

3 に答える 3

2

ユークリッド幾何学は次のことを教えてくれます:
二辺の和は常に残りの一辺よりも大きい

三角形ABCを考えてみましょう。
AB = 3
BC = 5
AC = 4

std::sort は、辺を昇順に並べ替えます。そのため、配列には最初に短辺が含まれます。

ソート後
サイド[0] = AB = 3
サイド[1] = AC = 4
サイド[2] = BC = 5

std::next_permutation は、辺の次の可能な組み合わせを返します。例:

AC = 3
BC = 5
AB = 4

簡単な例:

#include <iostream>     // std::cout
#include <algorithm>    // std::next_permutation, std::sort

int main () {
  int myints[] = {1,2,3};

  std::sort (myints,myints+3);

  std::cout << "The 3! possible permutations with 3 elements:\n";

  while ( std::next_permutation(myints,myints+3) )
  {
    std::cout << myints[0] << ' ' << myints[1];
    std::cout << ' ' << myints[2] << '\n';
  }

  std::cout << "After loop: " << myints[0] << ' ';
  std::cout << myints[1] << ' ' << myints[2] << '\n';

  return 0;
}

さらに読む: http://www.cplusplus.com/reference/algorithm/next_permutation/

于 2013-08-01T19:26:20.627 に答える