はじめまして。
いま、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になるならば、
それも一つの結果としてカウントします。
下手な説明ですいません。回答お待ちしております。
A 回答 (2件)
- 最新から表示
- 回答順に表示
No.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;
}
************************************
No.1
- 回答日時:
私の意見としては、全パターンを検索して答えを求めるしか無いと
思います。
つまり、sa[0][0]+sa[0][1] から sa[2][4]+sa[2][5]までの
足し算を順にやって、答えが9となるパターンを探します。
次に、sa[0][0]+sa[0][1] + sa[0][2] から順に計算して・・・
といった感じでしょうか?
int の配列が巨大な場合は、パフォーマンスが悪くなるのが欠点
です。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- その他(ホビー) NEXCO中日本のミニカーについて 1 2023/06/11 13:55
- 車検・修理・メンテナンス Vベルト SA形とA形の違い お世話になります、 現在SA-49を使用している機械があります。 ホー 2 2022/05/14 16:12
- 日用品・生活雑貨 無印良品でウェットシートとシート用ケースを買ったのですが、詰め替え方がわかりません。誰か教えて下さい 1 2023/02/17 14:37
- 虫除け・害虫駆除 「オニヤンマ君」は本当に効果があるのですか? 2 2023/06/27 21:32
- その他(車) DAIHATSU HIJET TRUCK JUMBO EXTEND(ハイゼットジャンボエクステンド) 2 2023/05/01 17:06
- その他(交通機関・地図) 至急教えてください! 京都方面から御殿場アウトレットへ行く場合、御殿場ICより足柄から行く方が空いて 1 2022/11/26 12:05
- 地図・道路 高速道路のSAは24時間営業じゃなくても良い 4 2022/10/24 18:52
- その他(パソコン・周辺機器) Windows10でXBOX360用RAPVX-SA用の非公式ドライバがインストール出来ない 1 2023/01/10 19:37
- その他(宿泊・観光) 淡路島から鳥取県境港に行くんでがおすすめSAありましか? 2 2023/05/02 19:39
- その他(言語学・言語) フィリピン語が分かる方に質問です Hindi ka kawalan sa akin とはどういう意味 3 2023/06/27 16:00
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
C言語での引数の省略方法
-
【C++】関数ポインタの使い方
-
「指定されたキャストは有効で...
-
卒業研究でよく分からないとこ...
-
複数桁10進数の*桁目だけを抽出...
-
c言語
-
#define _CRT_SECURE_NO_WARNIN...
-
if と配列の組み合わせ
-
C言語 エラーの原因がわからな...
-
int型の変数値をバイト列として...
-
std::set<int> で、ある値が何...
-
return 1L
-
C++ でカンマ "," で区切られた...
-
CでBAモデルを作りたいのですが
-
構造体の勉強中です 合計点の高...
-
VS2010C#からのDLL使用について
-
式は定数値が必要です」という...
-
因数分解を行うプログラムについて
-
ラップ関数とはどんなものですか?
-
「{ } で囲むだけ」は正しい?
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
C言語での引数の省略方法
-
「指定されたキャストは有効で...
-
複数桁10進数の*桁目だけを抽出...
-
ラップ関数とはどんなものですか?
-
【C++】関数ポインタの使い方
-
#define _CRT_SECURE_NO_WARNIN...
-
C言語 エラーの原因がわからな...
-
実数の整数部,小数部の取得
-
system関数がうまくいかない
-
(int *)の意味
-
acceptをalarmでタイムアウトさ...
-
if と配列の組み合わせ
-
C言語初心者です、、、お助けく...
-
std::set<int> で、ある値が何...
-
PowerShellがうまくいかない
-
read関数をノンブロッキングで...
-
ColorをRGBで指定する方法
-
(マルチスレッド)_beginthrea...
-
数字列を3桁ごとにカンマで区切...
-
C言語で分からないところがあり...
おすすめ情報