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

質問

はじめまして。

いま、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になるならば、
それも一つの結果としてカウントします。

下手な説明ですいません。回答お待ちしております。

回答No.2

cherry_moon

要素が正数という前提でいいんでしょうか？

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

最初の成功を見つけるまでの手順はこんな感じです。
(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)
{
/* 初期値は全部０ */
f(0, 0, 0);
return 0;
}
************************************

回答No.1

hamanyan

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