OKWAVEのAI「あい」が美容・健康の悩みに最適な回答をご提案!
-PR-
締切り
済み

足し算の結果を求めるプログラム

  • すぐに回答を!
  • 質問No.144447
  • 閲覧数98
  • ありがとう数2
  • 気になる数0
  • 回答数2
  • コメント数0

お礼率 24% (32/133)

はじめまして。

いま、int型の配列saが
int sa[3][6];
として宣言されていて、その中身が

sa[0][0] = 4;
sa[0][1] = 1;
sa[0][2] = 1;
sa[0][3] = 5;
sa[0][4] = 1;
sa[0][5] = 3;

sa[1][0] = 3;
sa[1][1] = 1;
sa[1][2] = 3;
sa[1][3] = 1;
sa[1][4] = 3;
sa[1][5] = 1;

sa[2][0] = 1;
sa[2][1] = 5;
sa[2][2] = 3;
sa[2][3] = 1;
sa[2][4] = 4;
sa[2][5] = 1;

となっているとき、この中身の足し算の結果が
ちょうど9になる組み合わせを探したいのですが、
何かいいアルゴリズムはないのでしょうか?

この中から、2つだけを足し合わせたときの結果ではなく、
3つや4つを足し合わせても9になるならば、
それも一つの結果としてカウントします。

下手な説明ですいません。回答お待ちしております。
通報する
  • 回答数2
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

回答 (全2件)

  • 回答No.1
レベル5

ベストアンサー率 50% (2/4)

私の意見としては、全パターンを検索して答えを求めるしか無いと 思います。 つまり、sa[0][0]+sa[0][1] から sa[2][4]+sa[2][5]までの 足し算を順にやって、答えが9となるパターンを探します。 次に、sa[0][0]+sa[0][1] + sa[0][2] から順に計算して・・・ といった感じでしょうか? int の配列が巨大な場合は、パフォーマンスが悪くなるのが欠 ...続きを読む
私の意見としては、全パターンを検索して答えを求めるしか無いと
思います。
つまり、sa[0][0]+sa[0][1] から sa[2][4]+sa[2][5]までの
足し算を順にやって、答えが9となるパターンを探します。
次に、sa[0][0]+sa[0][1] + sa[0][2] から順に計算して・・・
といった感じでしょうか?
int の配列が巨大な場合は、パフォーマンスが悪くなるのが欠点
です。


  • 回答No.2
レベル9

ベストアンサー率 36% (37/102)

要素が正数という前提でいいんでしょうか? 再帰を使えばできますね。 今までとってきた合計が ・8以下ならば、もうひとつ値をとりにいく。 ・9ならば、成功。 ・10以上ならば、前にとってきたのを次の値にする。 最初の成功を見つけるまでの手順はこんな感じです。 (0,0) 4 (0,0),(0,1) 5 (0,0),(0,1),(0,2) 6 (0,0),(0,1),(0,2),( ...続きを読む
要素が正数という前提でいいんでしょうか?

再帰を使えばできますね。
今までとってきた合計が
・8以下ならば、もうひとつ値をとりにいく。
・9ならば、成功。
・10以上ならば、前にとってきたのを次の値にする。

最初の成功を見つけるまでの手順はこんな感じです。
(0,0) 4
(0,0),(0,1) 5
(0,0),(0,1),(0,2) 6
(0,0),(0,1),(0,2),(0,3) 11 失敗
(0,0),(0,1),(0,2),(0,4) 7
(0,0),(0,1),(0,2),(0,4),(0,5) 10 失敗
(0,0),(0,1),(0,2),(0,4),(1,0) 10 失敗
(0,0),(0,1),(0,2),(0,4),(1,1) 8
(0,0),(0,1),(0,2),(0,4),(1,1),(1,2) 11 失敗
(0,0),(0,1),(0,2),(0,4),(1,1),(1,3) 9 成功

プログラムにするとこんな感じです。
sa[i/6][i%6] として2次元配列を1次元配列っぽく扱ってます。
************************************

#include <stdio.h>

int sa[3][6] = {
{4,1,1,5,1,3},
{3,1,3,1,3,1},
{1,5,3,1,4,1}
};
int select[10]; /* 今までに選んだのはこれ */

void f(int start, int sum, int num)
/* start - 次のは start 以降から選ぶ */
/* sum - 今までの合計は sum */
/* num - 今までに num 個選んだ */
{
int i;

/* 見つかった */
if(sum==9){
for(i=0;i<num;i++)
printf("sa[%d][%d] ",
select[i]/6, select[i]%6);
printf("\n");
return;
}

/* おおきすぎた */
if(sum>9) return;

/* まだ足りないから、つぎのを選ぶ */
for(i=start;i<3*6;i++){
select[num] = i;
f(i+1, sum+sa[i/6][i%6], num+1);
}

return;
}

int main(int argc, char **argv)
{
/* 初期値は全部0 */
f(0, 0, 0);
return 0;
}
************************************
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
こんな書き方もあるよ!この情報は知ってる?あなたの知識を教えて!
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


いま みんなが気になるQ&A

関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ