特定の数値を集計するさまざまな方法100

Question

5つの異なる数値を合計して100を得る方法を示すコードを書いておきます。例えば、数字は2,5,10,20,50であり、回。ここでは50+50は片道で、20+20+20+20+20です。私はこれをどのようにプログラムするのか分かりません。

私はそれが再帰関数によって行われるべきである、と私は実際にどのように知らずに1を書くことを試みたと思うので、これは私が思い付いたことが最善です：

#include<iostream> 
#include<vector> 

using namespace std; 


int i,sum,n=5,counter=0; 


int add(vector<int> &m){ 

    if(m.size()==0) return 0 ; 

    for(i=0 ; i<m.size() ; i++){ 

      sum=m[i]+add(m); 
      cout<< sum<<endl; 
     if(n>0) n--; 
     m.resize(n); 
    } 


} 


int _tmain(int argc, _TCHAR* argv[]) 
{ 
    int i,sum,n=5; 

vector<int> m; 

m.resize(5); 

m[0]=2; 
m[1]=5; 
m[2]=10; 
m[3]=20; 
m[4]=50; 

add(m); 


    return 0; 
} 

Answer 1

楽しみのためだけに

#include <iostream> 
#include <vector> 
#include <iterator> 
#include <numeric> 
#include <algorithm> 

static const int terms[] = { 2,5,10,20,50, /*end marker*/0 }; 

using namespace std; 
typedef vector <int> Solution; 
typedef vector <Solution> Solutions; 

inline int Sum(const Solution& s) 
{ 
    return accumulate(s.begin(), s.end(), 0); 
} 

template <typename OutIt> 
    OutIt generate(const int target, const int* term, Solution partial, OutIt out) 
{ 
    const int cumulative = Sum(partial); // TODO optimize 

    if (cumulative>target) 
     return out;   // bail out, target exceeded 

    if (cumulative == target) 
    { 
     (*out++) = partial; // report found solution 
     return out; 
    } else 
    { 
     // target not reached yet, try all terms in succession 
     for (; *term && cumulative+*term<=target; term++) 
     { 
      partial.push_back(*term); 
      out = generate(target, term, partial, out); // recursively generate till target reached 
      partial.pop_back(); 
     } 
     return out; 
    } 
} 

Solutions generate(const int target) 
{ 
    Solutions s; 

    generate(target, terms, Solution(), back_inserter(s)); 

    return s; 
} 

void Dump(const Solution& solution) 
{ 
    std::copy(solution.begin(), solution.end(), std::ostream_iterator<int>(std::cout, " ")); 
    std::cout << std::endl; 
} 

#ifdef _TCHAR 
int _tmain(int argc, _TCHAR* argv[]) 
#else 
int main(int argc, char* argv[]) 
#endif 
{ 
    Solutions all = generate(100); 
    for_each(all.rbegin(), all.rend(), &Dump); 
    return 0; 
} 

努力で$、0.02

---

実際に質問に答えるために、ソリューションの不要な出力をすべて削除し、コードを大幅に最適化しました。それは今はるかに効率的である（私は速くtarget=2000と25Xでそれをベンチマーク）それはまだ大きなtarget sまで拡張できません...

#include <iostream> 
#include <vector> 

using namespace std; 

size_t generate(const int target, vector<int> terms) 
{ 
    size_t count = 0; 

    if (terms.back()<=target) 
    { 
     int largest = terms.back(); 
     terms.pop_back(); 
     int remain = target % largest; 

     if (!remain) 
      count += 1; 

     if (!terms.empty()) 
      for (; remain<=target; remain+=largest) 
       count += generate(remain, terms); 
    } 

    return count; 
} 

int main(int argc, char* argv[]) 
{ 
    static const int terms[] = {2,5,10,20,50}; 
    std::cout << "Found: " << generate(1000, vector<int>(terms, terms+5)) << std::endl; 
    return 0; 
} 

うまくいけば、よりスマートなモジュロ演算はPengOneが提案内容を反映するために開始されますこの問題に近づいています。

Answer 2

これにはありません右に見える：

m[0]=2; 
... 
m[0]=50; 

moud [4] = 50;

編集 あなたは決して値100を宣言しません。あなたは100に達した時をどのように知っていますか？

Answer 3

この問題は、理論的にはgenerating functionsを使用して解決できます。生成関数は関数ではなく、何も生成しません（良い名前、え？）が、情報をうまく追跡します。結論は、あなたの問題に対する答えは、いくつかの方法が、ここでは理由として説明だ

1/(1-x^2) * 1/(1-x^5) * 1/(1-x^10) * 1/(1-x^20) * 1/(1-x^50) 

の拡大にx^100の係数に等しいということであるということです。思い出してください。1/(1-x) = 1 + x + x^2 + x^3 + ...。これは、問題を解決するために使用する基本的な生成関数です。

番号A、B、...、N（この例では2,5,10,20,50）を何回でも繰り返し使用できるとします。次いでf(x)で（発生）関数

f(x) = 1/(1-x^A) * 1/(1-x^B) * ... * 1/(1-x^N) 

x^Mの係数を考慮すると、a,b,...,nが非負整数で

M = a*A + b*B + ... + n*N

形の和としてMを書き込むいくつかの方法です。

これはなぜ機能しますか？拡張子f(x)の任意の単項式は、1/(1-x^A)から1つの項を取ることから来るので、いくつかの非負のためにx^(a*A)のように見えるでしょうaと同様に他の言葉。指数が加算されるので、x^Mの係数は、そのような合計を書くことのすべての方法ですMを取得します。

私はこれはプログラミングの答えではないことを知っていますが、うまくいけば、あなたはプログラムを書くためにアイデアを使うことができます。ここで

Answer 4

は、再帰的なソリューションです：http://ideone.com/ip98M

#include <iostream> 

template<size_t N> 
void find_combinations_helper(int total, const int (&denoms)[N], int denoms_used, int remaining, int (&counts)[N]) 
{ 
    if (remaining == 0) { 
     int partial_sum = 0; 
     for(int i = 0; i < denoms_used; ++i) { 
      if (counts[i]) { 
       std::cout << counts[i] << "*" << denoms[i]; 
       partial_sum += counts[i] * denoms[i]; 
       if (partial_sum < total) std::cout << " + "; 
      } 
     } 
     std::cout << "\n"; 
     return; 
    } 

    if (denoms_used == N) return; 

    for(counts[denoms_used] = 0; remaining >= 0; (remaining -= denoms[denoms_used]), ++counts[denoms_used]) 
     find_combinations_helper(total, denoms, denoms_used + 1, remaining, counts); 
} 

template<size_t N> 
void find_combinations(int total, const int (&denoms)[N]) 
{ 
    int solutions[N]; 
    find_combinations_helper(total, denoms, 0, total, solutions); 
} 

int main(void) { 
    const int bill_denoms[] = { 50, 20, 10, 5, 2 }; 
    find_combinations(100, bill_denoms); 
} 

Answer 5

あなたが機能addため、現時点で持っているコードがあなたにスタックオーバーフローを取得します:)あなたは、ベクトルを変更する前add(m)への再帰呼び出しを行うのでm 。したがって、addは常に修正されていないベクトルで呼び出され、ベースケースは決してヒットしません。

私はあなたが何をしたいのかcatchedが、何についての場合、私は知らない。

#include <iostream> 
#include <sstream> 
#include <vector> 

void add(int i, std::string s, int sum) 
{ 
    if (sum == 100) 
    { 
     std::cout << s << "=100" << std::endl; 
     return; 
    } 
    if (sum > 100) 
    { 
     return; 
    } 
    if (sum < 100) 
    { 
     std::ostringstream oss; 
     oss << s << "+" << i; 
     add(i, oss.str(), sum+i); 
    } 
} 

int main() 
{ 
    std::vector<int> m; 

    m.resize(5); 

    m[0]=2; 
    m[1]=5; 
    m[2]=10; 
    m[3]=20; 
    m[4]=50; 

    // This loop will initiate m.size lines of recursive calls 
    // one for each element of the array 
    for (size_t i = 0; i < m.size(); i++) 
    { 
    add(m[i], "", 0); 
    } 

    return 0; 
}