質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.35%

  • C

    4212questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

  • C++

    4070questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

  • 配列

    581questions

    配列は、各データの要素(値または変数)が連続的に並べられたデータ構造です。各配列は添え字(INDEX)で識別されています。

  • GCC

    152questions

    GCCはGNU Compiler Collectionの略です。LinuxのC言語コンパイラのデファクトスタンダードであり、数多くの他言語やプラットフォームサポートもします。

  • g++

    13questions

    g++はGNUコンパイラコレクション(gcc)のC++コンパイラーです。

配列の要素間の和を全パターン求めるプログラムを作成したい。

解決済

回答 8

投稿 編集

  • 評価
  • クリップ 2
  • VIEW 2,701

n_k

score 5

皆様ありがとうございました。

前提・実現したいこと

<CもしくはC++>
配列の要素間の和を全パターン求めるプログラムを作成したい。

【例】
/*-------------------------------------------------*/
要素n=3つの配列の中身がA=[a=1,b=10,c=100]とする。
和のパターンは
B=[11,101,110,111]のm=4種類となる。
※B=[a+b, a+c, b+c, a+b+c]
/*-------------------------------------------------*/

nとA(配列)が与えられたときにmとB(配列)が得られるようにしたいです。
要素数が1の時は除外します。

網羅するという点で困っております。
ご助言頂けると助かります。よろしくお願いします。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 8

+4

集合を表す変数Sを用意して,そのビットが立っているかを見るような実装をするとこうなります

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
    vector<int> A{1, 10, 100};
    set<int> B;
    for(int S = 0; S < (1<<A.size()); S++) {
        int sum = 0;
        if(__builtin_popcount(S) > 1) {
            for(int i = 0; i < A.size(); i++) {
                if(S >> i & 1) sum += A[i];
            }
            B.insert(sum);
        }
    }
    for(auto e: B) cout << e << endl;
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

checkベストアンサー

+2

こんにちは。

epistemeさんの回答を参考にしつつ、next_permutationを使ってみました。
効率無視でなるべく短いコードで。

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <bitset>

int main()
{
    std::vector<unsigned> array={0b1, 0b10, 0b100};
    static const unsigned prec=3;
    std::set<unsigned> result;

    std::sort (array.begin(), array.end());
    for (size_t n=2; n <= array.size(); ++n)
    {
        reverse(array.begin()+n, array.end());
        do
        {
            unsigned x=0;
            for (size_t i=0; i < n; ++i) x |= array[i];
            result.insert(x);        
        } while (next_permutation(array.begin(),array.end()));
    }

    std::cout << "m = " << result.size() << "\nB = [ ";
    for (auto element : result ) std::cout << static_cast<std::bitset<prec>>(element) << ' ';
    std::cout << "]" << std::endl;
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/07/05 13:18 編集

    bitwise-orで良いの?と思わなくもないですが、正解は質問者のみぞ知る...

    キャンセル

+2

効率云々を考慮せず、愚直に実装。

#include <iostream>
#include <array>
#include <set>

using namespace std;

int main() {
  set<int> B;
  const int n = 3;
  array<int,n> A = { 1, 10, 100 };
  // すべての組み合わせに対し
  for ( int i = 0; i < n; ++i ) {
    for ( int j = 0; j < n; ++j ) {
      // (重複を除外して)その和をsetに投げ込む
      if ( i != j ) {
        B.insert(A[i]+A[j]);
      }
    }
  }
  int m = B.size();
  cout << "m = " << m << endl;
  cout << "B = [ ";
  for ( int item : B ) cout << item << ' ';
  cout << "]\n";
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/07/05 11:49

    これだと、111が取れませんね

    キャンセル

  • 2017/07/05 11:51 編集

    n_k さん向けのコメント: 以下の様にするとループ回数が減らせます。

    for ( int i = 0; i < n - 1; ++i ) {
    for ( int j = i + 1; j < n; ++j ) {
    B.insert(A[i]+A[j]);
    }
    }

    たしかに 111 取れないすね

    キャンセル

  • 2017/07/05 11:51

    ありがとうございます、すいません、質問が悪かったようなので質問を修正させていただきます。

    キャンセル

  • 2017/07/05 11:53

    今の問題だと配列が5個あった場合に、2個, 3個, 4個, 5個 の総当たりが必要ですね。

    キャンセル

  • 2017/07/05 11:54 編集

    あ、要素数2~n での総和なのか...組み合わせ列挙のトコをいじらんならんですね。
    # 要素数 1は除外? 問題をきっちり定義しておくれ。

    キャンセル

+2

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

std::set<int> calc(int *a, size_t n)
{
  std::set<int> result;
  for (size_t m = 2; m <= n; m++) {
    // n個中からm個を選択
    std::vector<bool> selector(n);
    for (size_t i = 0; i < m; i++)
      selector[i] = true;
    // m個選択の組み合わせを列挙
    do {
      int sum = 0;
      for (size_t i = 0; i < m; i++)
        sum += selector[i] ? a[i] : 0;
      result.insert(sum);
    } while (std::prev_permutation(selector.begin(), selector.end()));
  }
  return result;
}

int main()
{
  constexpr size_t N = 3;
  int A[] = { 1, 10, 100 };

  std::set<int> B = calc(A, N);

  std::copy(B.begin(), B.end(), std::ostream_iterator<int>(std::cout, " "));
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+2

#include <iostream>
#include <array>
#include <set>

int main() {
  const int n = 3;
  std::set<int> results;
  std::array<int, n> A = { 1, 10, 100 };

  // 2~N の搾取を全通り試す
  for (int v = 2; v <= A.size(); v++) {
    for (int i = 0; i < n; ++i) {
      int sum = A[i], c = 1;
      for (int j = i; j < n; ++j) {
        if (i == j) continue;
        sum += A[j];
        if (++c >= v) break;
      }
      results.insert(sum);
    }
  }
  for (int v : results)
    std::cout << v << ' ' << std::endl;
}


※計算量に無駄があります

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+2

考えつくままに書くとこんな感じ。
1から順に数字をビットパターンと見なして、1のところの添え字の要素だけ足します。
要素数が、unsigned long long intのビット数未満だと出来ると思います。

#include <stdio.h>
int main(){
    int A[] = {1,10,100};
    int sizeA;
    int ANS[9999];
    int nANS;
    int sum;
    unsigned long long int max;
    unsigned long long int i;
    int j;
    int k;

    sizeA = sizeof A/sizeof A[0];

    for(nANS=0; nANS<sizeA; nANS++){
        ANS[nANS] = A[nANS]; /* 「1つだけの和」を除外するために最初に登録しておく */
    }
    max = 1 << sizeA;
    for(i=1; i<max; i++){ /* 1以上の全てのビットパターンを網羅 */
        sum = 0;
        for(j=0; j<sizeA; j++){
            if( i & 1<<j ){ /* ビットが立っていれば足す*/
                sum += A[j];
            }
        }
        ANS[nANS] = sum;
        for(k=0; ANS[k]!=sum; k++){};
        if( k==nANS ){
            nANS++; /* 既出でなければ登録 */
        }
    }
    for(k=sizeA; k<nANS; k++){
        printf("%d\n",ANS[k]);
    }
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/07/05 15:33

    みんなC++ですね。C++はリファレンス見ないと書けない。

    キャンセル

+2

昼休みの間に終わってしまった・・・。
折角書いたので投稿しておきます。
参考まで。
コードの長さではC++には勝てないですね。

#include <stdio.h>

#define getbit(v,n) (v >> n & 1)

int getbitnum(int v)
{
    int sum = 0;
    for(int i = 0; i < sizeof(int)*8; i++) sum += getbit(v,i);
    return sum;
}

void calc(int *pa, int n, int *pb, int *pbn)
{
    int i, j;
    int max = 0;
    int sum;

    for(i = 0; i < n; i++){
        if(i != 0) max <<= 1;
        max |= 1;
    }

    *pbn = 0;
    for(i = 1; i <= max; i++){
        if(getbitnum(i) > 1){
            sum = 0;
            for(j = 0; j < n; j++) sum += (pa[j] * getbit(i, j));
            for(j = 0; j < *pbn && pb[j] != sum; j++);
            if(j == *pbn) pb[(*pbn)++] = sum;
        }
    }
}

int main(void)
{
    int a[] = { 1, 10, 100 };
    int b[128];
    int bn;
    calc(a, sizeof(a)/sizeof(int), b, &bn);
    for(int i = 0; i < bn; i++) printf("%d\n", b[i]);
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+2

私もアイデア(アルゴリズム)をば。

1項だけの場合、像I(1)は空集合。

n+1項(n>1)の場合の像I(n+1)は、n項の場合の像I(n)、n項からなる原像A(n)、n+1項目の要素a(n+1)を用いて、
I(n+1) = I(n) ∪ {n+i | r∈I(n)} ∪ {n+a | a∈A(n)}
と表される。

日本語で書くなら、再帰呼び出しを使えば書けますよ、ということ(実は再帰使わなくても可能)。これならメモリが許す限り、要素数が64bit超えようが、ソートできなかろうが、どんな場合でも対応できます。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.35%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る

  • C

    4212questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

  • C++

    4070questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

  • 配列

    581questions

    配列は、各データの要素(値または変数)が連続的に並べられたデータ構造です。各配列は添え字(INDEX)で識別されています。

  • GCC

    152questions

    GCCはGNU Compiler Collectionの略です。LinuxのC言語コンパイラのデファクトスタンダードであり、数多くの他言語やプラットフォームサポートもします。

  • g++

    13questions

    g++はGNUコンパイラコレクション(gcc)のC++コンパイラーです。