はじめまして。

いま、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件)

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



再帰を使えばできますね。
今までとってきた合計が
・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;
}
************************************
    • good
    • 0

私の意見としては、全パターンを検索して答えを求めるしか無いと


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

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Qfp = fopen(argy[1], "r");の[1]の意味は

https://oshiete.goo.ne.jp/qa/8940272.html
 の11行目に
fp = fopen(argv[1], "r");の[1]の意味が分かりません。
試したいのですが、ソフトがうまく動きません
 よろしくお願いいたします。

Aベストアンサー

前の例題も読みました。

大分苦戦しているようですが、配列については理解が進みましたでしょうか?
お答えしますと、最初のパラメータ文字列が代入されています。

古いC言語の約束でして大変有名なものです。

コマンドラインコンソールから実行ファイル名を書いて、
パラメータをスペースで区切って指定したとします。

このパラメータ文字列が[1]以降に入ります。
例として、"test"と言う名前の実行ファイルがあったとします。

例)> test test1 test2 3 4

このようにコマンドラインから入力し実行すると、

argc = 5
argv[0] = "test"
argv[1] = "test1"
argv[2] = "test2"
argv[3] = "3"
argv[4] = "4"

と文字列が入ってきます。

以下はサンプル。

void main( int argc , char *argv[])
{
if( argc < 2 )
{
// パラメータ指定がなかった場合の表示
printf( "test に続けて4つまでパラメータを入力できます\n");
exit(0);
}
if( argc > 5 )
{
 // パラメータが5つ以上あった場合の表示
printf( "5つ以上のパラメータは受け付けません\n");
exit(-1);
}

// 正常ルート
printf( "パラメータの数は%d個ですね?ニヤッ\n", argc-1);
printf( "最初のパラメータは%sでしょ?\n", argv[1]);
printf( "残りはargv[2]以降ですが、面倒なので表示しません\n");
}

と言う具合に、引数を活用できます。argv[0]には、実行ファイル名が入ります。
argc は実行ファイルの名前も含めてカウントされます。

プログラムによっては必要な引数の数が変わりますし、
ユーザーのコマンドラインからの入力ミスなどでパラメータがなかったり、
必要なパラメータが不足していたりしますので、
argcとargvを使って最初にシンタックスエラーチェックをするのが常道です。

実行ファイル名の指定がなく、プログラムが実行されることはないと思われます
から、argcは1以上の値になります。

argc, argvの活用は、
実行コマンドを手打ちで打ち込むコンソール形式でよく用いられる基本的な
アプリケーションの開発手法です。

ご質問の箇所は、
第一パラメータにプログラム内で読み込むファイルのファイル名を指定してるの
でしょう。(よくあります)

しかし、Windowsなどのウィンドウを使用するアプリケーションは、
これとは違っておりますので注意が必要です。
(C言語とは別に、Windowsに特化した開発ノウハウの勉強が必要です)

Windows系で上記の様な基本的なプログラムを作成する場合は、
プロジェクトの作成時に(VisualStudioなどで)コンソールアプリケーション
を選んで作成します。実行時にコンソールが開きます。

Linuxの場合は、コンソールがデフォルトになっているでしょうから、
(特殊な設定がなければ)そのまま作成できます。

テキストエディタでソースを記述し、gcc などでコンパイルします。
実行形式ファイルが出来ていれば、想定どおりの動作をするでしょう。

ファイルの読み込みが出来るようになったら、
ファイルの内容を書き換えて保存したり、
ファイル名を変えたり、
ディレクトリ内のファイルを全て表示したり、
ファイル内に含まれる文字列を検索し、該当するファイルをリストしたりなど、

有用なサンプルプログラムを沢山作って練習します。

ファイルを読み込む先は、char型の配列でバイトサイズのメモリーとして確保
します。メモリーと変数の関係を充分に理解することをお勧めします。
殆どのプログラムは、このメモリーの確保やメモリーサイズの計算と格闘する
場合が多くなるからです。

バイナリー形式のファイル(すべてはバイナリー形式として良いのですが)に
ついて理解が深まった後は、
bmpの画像ファイル、wavなどの音声ファイルをあけて、
これの中身を書き換えて遊びます。

特にwavファイルは、音量の変更や周波数フィルタなども掛けれますので、
メモリ、配列、ファイルの関係を(焦らずに)ゆっくり理解するだけで、
今の知識レベルでも面白いことが沢山出来ます。

以上、ご参考に成れば。

前の例題も読みました。

大分苦戦しているようですが、配列については理解が進みましたでしょうか?
お答えしますと、最初のパラメータ文字列が代入されています。

古いC言語の約束でして大変有名なものです。

コマンドラインコンソールから実行ファイル名を書いて、
パラメータをスペースで区切って指定したとします。

このパラメータ文字列が[1]以降に入ります。
例として、"test"と言う名前の実行ファイルがあったとします。

例)> test test1 test2 3 4

このようにコマンドラインから...続きを読む

Qchar c = 'a'; char h[1] = c; エラー

char型のものを char[]型に代入したいです。

char c = 'a';
char h[1] = c;

として、

h[0] は \x97
h[1] は \x00

にしたいです。
型変換の方法を教えてください。

Aベストアンサー

とりあえず、確認を。

C では、'a'の表す値は 0x61 = 97 であって、 \x97 ではないと思います。
(\xnnn を、十六進数の意味に取りましたが、あってますでしょうか?
この場合、C では通常 0xnnn のように書くと思います。)
ので、 これは 0x61 のことをおっしゃっていると仮定します。

> char h[1] = c;
っと、これではたぶんコンパイルが通りません。

char h[1] = {c};

のように、配列であることを明示して代入してください。
この式では、前半でh という名前の、*長さ1 の* char の配列変数を確保します。
後半で、その中を初期化しています。
添え字は 0 からはじまるので、この場合、h[0] に c の内容が代入されます。
1個しか場所を確保していないので、 h[1] の位置のデータは内容が不定です。
文字列として h を扱いたいのであれば、 C の文字列には終端として 0 が必要ですから、
char c = 'a';
char h[2] = { c, '\0'};

のような書き方が必要になります。
これで、お望みのデータになると思います。

とりあえず、確認を。

C では、'a'の表す値は 0x61 = 97 であって、 \x97 ではないと思います。
(\xnnn を、十六進数の意味に取りましたが、あってますでしょうか?
この場合、C では通常 0xnnn のように書くと思います。)
ので、 これは 0x61 のことをおっしゃっていると仮定します。

> char h[1] = c;
っと、これではたぶんコンパイルが通りません。

char h[1] = {c};

のように、配列であることを明示して代入してください。
この式では、前半でh という名前の、*長さ1 の* char の配列変数...続きを読む

Qint i, int i[1];

C++で、
 int i;
と、
 int i[1];
は、どっちで宣言をしても、iは同じ振るまいですか?

Aベストアンサー

配列、ポインタなどよりももっと基礎的な概念である「右辺値」、「左辺値」を理解しましょう。

int i ;
この形で宣言されたiは代入式の右辺(代入する値)にも左辺(代入される領域)にも使うことが出来ます。
int a ;
a = i ;
i = 10 ;

C言語でも他のほとんどの言語でも「変数は右辺の時と左辺の時とでは解釈が違う」という原則があります。

代入式の右辺に配置出来るのは『値』です。
変数であっても良いし定数であっても、式であってもかまいません。
左辺がポインタ変数の場合は右辺はアドレス値(またはアドレス式)です。
代入式の右に配置可能な値を右辺値といいます。

代入式の左に配置出来るのは『領域』です。
変数であっても良いし、配列要素でもかまいません。
また、領域を示す式(int i[1]のときの*iなど)でもかまいません。
配列名(int i[1]のときのi)や定数は領域を持たないため、左辺に配置することが出来ません。
代入式の左に配置可能な領域を左辺値といいます。

int i[1] ;
この形で宣言されたiは右辺値に利用できます。
int *a ;
a = i ;
しかし、iだけでは領域を持たないため左辺値になりえません。
i = 1 ; //コンパイルエラーが出る。

コンパイル時に「有効な左辺値でない」と言う意味のエラーが出るのは「領域を示さない値を左辺値として使っている時」です。

どちらかと言うと「基礎理論」の部類なのでプログラム言語の本などには書いてないのですが、実は最も大切なのが「基礎理論」です。
頑張って勉強してください。

配列、ポインタなどよりももっと基礎的な概念である「右辺値」、「左辺値」を理解しましょう。

int i ;
この形で宣言されたiは代入式の右辺(代入する値)にも左辺(代入される領域)にも使うことが出来ます。
int a ;
a = i ;
i = 10 ;

C言語でも他のほとんどの言語でも「変数は右辺の時と左辺の時とでは解釈が違う」という原則があります。

代入式の右辺に配置出来るのは『値』です。
変数であっても良いし定数であっても、式であってもかまいません。
左辺がポインタ変数の場合は右辺はアドレス...続きを読む

Qint i,j; \n i=0,j=5;

int i,j;
i=0;
j=5:
と書いてあるソースは普通ですが、
int i,j;
i=0,j=5:
と書いてあるソースもあります。
後者はC++の正しい書式ですか?

カンマ演算子というのは後者のカンマのことですか?

Aベストアンサー

 正しい書式です。

i=0,j=5;
 における、「,」をカンマ演算子といいます。2項の演算子です。カンマで区切られた演算を「左から順番に」実行し、最後の演算を結果として返します。
 したがって、例の文であれば、i=0を実行し、次にj=5を実行。そして、j=5の結果の5を結果として返します。
 ・・・
 が、本来的には、あまり、例のような使い方はしませんね。よく見られるのは、次のような場合です。

 for (i=0,j=0 ; i < 50 ; ++i,++j) {

 のような形でよく見られます。for文の各式は、一つの式でなければならないので、こんな書き方をするわけです。初期化と更新部が一つにまとまり、ループが読みやすくなるのが利点かな。

Qint nII[10] = { 0 }について

久々にCを使ってプログラムを組んでいるのですが、基本的な構文を思い出せず
いくつか教えていただきたく質問させていただきました。

1)配列すべてを初期化するのに、宣言時に

int nII[10] = { 0 };

で大丈夫だった(全ての要素が0で初期化)と記憶しているのですが、間違いないでしょうか?

2)構造体の初期化は

struct tm tm;
memset(&tm, 0, sizeof(struct tm))

で大丈夫でしょうか?

3)構造体の宣言は

typedef struct{
int a;
}HOGE, *LPHOGE;

HOGE st; // <- struct HOGE stと同じ
LPHOGE pst; // <- struct HOGE* pstと同じ

で問題ないでしょうか?

以上、3つ質問になって申し訳ないのですが、よろしくお願いします。

Aベストアンサー

1)OK
2)たぶんOK
3)HOGEという名前の構造体はない(当該の構造体には名前がない)ので、
// 以下のコメント記述が誤っています。ただし、

HOGE st;
LPHOGE pst;
という定義そのものはOK


人気Q&Aランキング

おすすめ情報