최소 합계를 기준으로 배열 요소 찾기

StackOverflow https://stackoverflow.com/questions/853007

  •  21-08-2019
  •  | 
  •  

문제

저는 C++로 6개의 난수를 주고 이를 배열에 저장하는 루프를 작성했습니다.내가 하고 싶은 것은 숫자 "x"보다 큰 값을 얻을 때까지 배열의 요소를 합산하는 것이지만 반드시 모든 요소를 ​​추가하지 않고도 이 작업을 수행하고 싶습니다.목표는 합이 x 값이 되는 첫 번째 요소를 찾는 것입니다.

예를 들어 배열은 [1,2,3,4,5,6], 그리고 x = 6, 그래서 제가 찾고 있는 것은 요소입니다. [1,2,3].

나는 표준 라이브러리를 살펴보고 "valarray"의 sum 함수를 사용해 보았지만 이것은 단지 모든 요소의 합계를 제공할 뿐입니다.이를 성공적으로 코딩하는 방법에 대한 아이디어를 주시면 대단히 감사하겠습니다.

도움이 되었습니까?

해결책

덧셈을 수행하는 펑터를 작성하세요.

#include <algorithm>
struct SumToo
{
     SumToo(int val):m_val(val),m_sum(0) {}
     int m_val;
     int m_sum;

     bool operator()(int next)
     {
         m_sum += next;
         return m_sum >= m_val;
     }
 };

 int main()
 {
       int data[] = {1,2,3,4,5,6};

       int* find = std::find_if(data,data+6,SumToo(6));
 }

다른 팁

나는 그 합계가 임계값을 충족하거나 초과할 때까지 배열의 첫 번째 X 요소만 원한다고 가정합니다(질문은 약간 모호했습니다).

그렇다면 루프 없이는 이를 수행하는 방법을 모르겠습니다.

int sum = 0;
int i = 0;
for( ; i < len; ++i ) {
    sum += array[i];
    if( sum >= 6 ) {
        break;
    }
}

이제 "i"에는 합계가 임계값을 충족하거나 초과하는 인덱스가 포함됩니다.

상태 저장 조건자와 함께 find_if 사용을 제안하는 답변은 피하세요.STL 알고리즘은 조건자를 복사하는 것이 안전하다고 가정하므로 상태 저장 조건자는 위험합니다.이 경우, 조건자의 복사본이 만들어지면 각각은 서로 다른 '누계'를 가지게 되며 반드시 모든 값에 대해 또는 올바른 순서로 작동하지는 않습니다.

특히 술어의 Operator() 멤버를 const 멤버 함수로 구현하지만 해당 멤버를 변경 가능한 것으로 레이블을 지정하는 솔루션은 피하십시오. 이는 상태 저장 술어가 아니라고 생각하게 만드는 나쁜 결과입니다.

단순히 반복하여 답을 찾는 답 중 하나를 사용하거나 누산기를 사용하는 답을 사용하는 것이 가장 올바른 방법이므로(코드가 약간 다루기 어려워 보이더라도) 사용하는 것이 좋습니다.

C 배열과 find_if에는 경고가 적용되지 않을 수도 있습니다.미래에 위험한 상황에서 잘못된 솔루션을 사용하게 될 수 있기 때문에 상태 저장 조건자가 문제를 해결하는 올바른 방법이라는 것을 배우기를 원하지 않습니다.

참조:C++ 코딩 표준:101 규칙, 지침 및 모범 사례, 항목 87

다음은 약간 더 일반적인 버전입니다.

#include <iostream>
#include <algorithm>

// return an iterator _Last such that sum 
// of all elements in the range [_First, _Last)
// satisfies the predicate Func
template<class InIt,
class Ty,
class Fn> inline
InIt accumulate_if(InIt First, InIt Last, Ty Val, Fn Func)
{   
    for (; Func(Val) && First != Last; ++First)
        Val = Val + *First;
    return (First);
}

int main() {
    int num[] = {1, 2, 3, 4, 5, 6};
    int *last = accumulate_if(num, num + sizeof num / sizeof num[ 0 ], 
                              0, std::bind2nd(std::less<int>(), 6));
    std::copy(num, last, std::ostream_iterator<int>(std::cout, "\n"));
    return 0;
}

다음에서 숫자를 빼세요. 엑스 0 이하가 될 때까지 하나씩.

원하시는대로 추가사항은 없습니다 :)

이것이 효과가 있기를 바랍니다:

/* Returns an index i, given array valarray[0,1..n] and number x where i is an index to valarry such that sum over j of valarray[j] for j = 0 to i > x */
int getFirstSum(int *valarray, int n, int x)
{
   int i = 0;
   int sum = x;
   while(sum > x && i < n)
   {
      i++;
      sum -= valarray[i];
   }
   return i;
}

다음과 같을 것이다:

struct StopAtValue{
  StopAtValue(int sum) : m_sum(sum), m_accumulated(0){}
  bool operator()(int val){
    m_accumulated += val;
    return m_accumulated >= sum;
  }
  int m_sum;
  int m_accumulated;
}


int* pos = std::find_if(&array[0], &array[n], StopAtValue(6));

글쎄요, 저는 벡터를 사용하겠습니다 

T addUntil(T array[],size_t len,T thres){
    vector<T> vec = vector_from_array(array,len)
    T sum;
    for (size_t i=0;i< vec.size(),sum<thresh;i++){
          sum+= vec[i];
    }
    return sum;
}

T를 정의하려면 연산자+와 연산자<가 필요합니다.

누계를 유지하는 펑터와 함께 std::find_if()를 사용할 수 있으며, 최상위에 놓이는 요소를 찾은 경우에만 펑터에서 true를 반환할 수 있습니다.

예를 들어:

#include <cstdlib>
#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
using namespace std;

// functor returns true when the running total >= findVal
struct running_total : public unary_function<int, bool>
{
    running_total(int findVal) : findVal_(findVal), runningTtl_(0) {};
    bool operator()(int rhs) const
    {
        runningTtl_ += rhs;
        if( runningTtl_ >= findVal_ )
            return true;
        else
            return false;
    }
private:
    mutable int runningTtl_;
    const int findVal_;
};

int main()
{

    int nums[] = {1, 2, 3, 4, 5, 6};
    size_t count = sizeof(nums)/sizeof(nums[0]);

    const int scanTtl = 6;  // running total to scan to
    int * pos = find_if(&nums[0], &nums[0]+count, running_total(scanTtl));

    cout << "Elements Totaling " << scanTtl << " : ";
    copy(&nums[0], pos+1, ostream_iterator<int>(cout, ", "));

    return 0;
}
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top