組み合わせ?のプログラムの考え方が分かりません!!

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
チャイナ

組み合わせ?のプログラムの考え方が分かりません!!

#1

投稿記事 by チャイナ » 1年前

課題について自分で考えてみたのですが、分からなかったため教えていただきたいです。

問)10mの長さの棒から{5m、4m、3m、2m}の棒を切り取るときの組み合わせを答えよ。

組み合わせが、{5}、{5、4}、{5、3}、{5、3、2}、・・・って感じです。2次元配列にしたいのですがfor文を使ってみてもどうすればいいか分からなくなってしまいました。

皆さんの考え方をぜひ教えていただきたいです!

アバター
usao
記事: 1889
登録日時: 11年前

Re: 組み合わせ?のプログラムの考え方が分かりません!!

#2

投稿記事 by usao » 1年前

組み合わせの全パターンの数だけループして,各パターンについて合計が10mを超えないか否かを調べてやればいいよね.

4種類の棒の 有る/無し の組み合わせは16パターンで,「全て無し」パターンについては調べるまでもないから,単純に残りの 15 種類分だけ回るループを書けばいいよ.

コード:

for( int i=1; i<=15; ++i )
{ /*i番目のパターンについて調べて可であれば表示する*/ }

アバター
usao
記事: 1889
登録日時: 11年前

Re: 組み合わせ?のプログラムの考え方が分かりません!!

#3

投稿記事 by usao » 1年前

各棒の 有る/無し は,上記の i の値の bitパターン から得れば良いと思う.

…っていう話が「ちょっと何言ってるかわかんないですね」とかいう場合であっても,
せいぜい 15 パターンしかないのだから,好きなように全部のパターンをハードコーディングしてやってもいいと思う.

チャイナ

Re: 組み合わせ?のプログラムの考え方が分かりません!!

#4

投稿記事 by チャイナ » 1年前

ご返信ありがとうございます!

なるほど。15種類ループですね。

問題なのですが、組み合わせは同じのを何回も使っていい、という条件です。明記し忘れました!すみません。

アバター
usao
記事: 1889
登録日時: 11年前

Re: 組み合わせ?のプログラムの考え方が分かりません!!

#5

投稿記事 by usao » 1年前

> 組み合わせが、{5}、{5、4}、{5、3}、{5、3、2}、・・・

っていう記述から,それを読み取るのは難易度高いw

つーことは,{5,5} っていうパターンも有りだと.
そしたら 15 パターンとかいう話では無くなるし,力業の全探索みたいなのはやりたくない気がする.

アバター
みけCAT
記事: 6734
登録日時: 14年前
住所: 千葉県
連絡を取る:

Re: 組み合わせ?のプログラムの考え方が分かりません!!

#6

投稿記事 by みけCAT » 1年前

再帰で、
・今考えている長さを切り出し、また同じ長さについて考える
・今考えている長さは切り出さず、次の長さについて考える
をするといいと思います。

Python で実装してみました。

コード:

def compute(sourceLength, targetLengthList):
	ans = []
	# 全ての切り取る長さの候補を試し終わった
	if len(targetLengthList) == 0:
		return [[]]
	# 今の切り取る長さの候補を試す
	if targetLengthList[0] <= sourceLength:
		# この長さを切り取った後のパターンを生成する
		putterns = compute(sourceLength - targetLengthList[0], targetLengthList)
		# 生成したパターンに、この長さを切り取るという情報を加える
		ans += [[targetLengthList[0]] + puttern for puttern in putterns]
	# 次の切り取る長さの候補に移る
	ans += compute(sourceLength, targetLengthList[1:])
	# 結果を返す
	return ans

print(compute(10, [5, 4, 3, 2]))
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
usao
記事: 1889
登録日時: 11年前

Re: 組み合わせ?のプログラムの考え方が分かりません!!

#7

投稿記事 by usao » 1年前

まぁ,ふつーに(?),
・5を0個切り出す世界
・5を1個切り出す世界
・5を2個切り出す世界
のそれぞれについて,「残りの長さについて 4,3,2 の組み合わせを列挙」という,元の長さと棒の種類が小さくなった問題を解く,という話にしていくのが素直かな.
(言うまでもないが,そこでも,4をX個切り出す世界のそれぞれについて「残りの長さについて 3,2 の組み合わせを列挙」というさらなる小さい問題にしていく感じ.)

C言語なら再帰で書くのが楽かな.
(って書いてたら話が被ったようだが,せっかくだから送信しちゃうぜ)

dic
記事: 657
登録日時: 14年前
住所: 宮崎県
連絡を取る:

Re: 組み合わせ?のプログラムの考え方が分かりません!!

#8

投稿記事 by dic » 1年前

{5,5}や最大で{2,2,2,2,2}がありなら
再帰でとくのがいいと思います。
深さが5までで、10m以内になるように呼び出していけばできると思います。

ソースは・・・おやすみなさい。

オイラもかぶった

アバター
あたっしゅ
記事: 665
登録日時: 14年前
住所: 東京23区
連絡を取る:

Re: 組み合わせ?のプログラムの考え方が分かりません!!

#9

投稿記事 by あたっしゅ » 1年前

東上☆海美☆「

コード:

//
// https://dixq.net/forum/viewtopic.php?f=3&t=21547
// 組み合わせ?のプログラムの考え方が分かりません!! - ミクプラ(ja)
//
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


const int BUFMAX = 5 * 2 + 1;
char buf[ BUFMAX ];

void
clearBuf()
{
	memset( buf, 0, BUFMAX );
}


int
calc(int sum, char* pBuf, const int* a, const int* b)
{
	while (*a != 0  && * b != 0) {
		sum += *b;

		*pBuf++ = (*b) + '0';
		*pBuf++ = ' ';
		*pBuf = 0;

#ifdef _DEBUG
		printf( ":%d:", *b );
#endif
		if (sum == 10) {
			printf("%s[%d]成功\n", buf, sum);

			return sum;
		} else if (sum > 10) {
			printf("%s[%d]失敗\n", buf, sum);

			return sum;
		}

		calc(sum, pBuf, a, b);

		while (*b != 0) {
			b++;
			if (*b == 0) {
				break;
			}
			else
			{
#ifdef _DEBUG
				printf("$%d$", *b);
#endif
				calc(sum, pBuf, a, b);
			}
		}
	}
	return sum;
}


int
main() try
{
	const int	array[] = {5, 4, 3, 2, 0};
	const int*	ptr = array;

	clearBuf();

	int i = 0;
	while ( array[ i ] > 0 ) {
		calc(0, buf, &array[ i ], &array[ i ] );
		i++;
	}

	return EXIT_SUCCESS;
}

catch (...)
{
	return EXIT_FAILURE;
}

// end.
5 5 [10]成功
5 3 2 [10]成功
4 4 2 [10]成功
4 3 3 [10]成功
4 2 2 2 [10]成功
3 3 2 2 [10]成功
2 2 2 2 2 [10]成功

の 7 通り

であってるみみ ?
VTuber:
東上☆海美☆(とうじょう・うみみ)
http://atassyu.php.xdomain.jp/vtuber/index.html
レスがついていないものを優先して、レスするみみ。時々、見当外れなレスしみみ。

中の人:
手提鞄あたッしュ、[MrAtassyu] 手提鞄屋魚有店
http://ameblo.jp/mratassyu/
Pixiv: 666303
Windows, Mac, Linux, Haiku, Raspbery Pi, Jetson Nano, 電子ブロック 持ち。

アバター
usao
記事: 1889
登録日時: 11年前

Re: 組み合わせ?のプログラムの考え方が分かりません!!

#10

投稿記事 by usao » 1年前

> 7 通り

最初に {5} とかも例示されている,すなわち,(ぴったり10にする必要は無くて)余りを出してもいいという話だと思うから違うんじゃない?

アバター
あたっしゅ
記事: 665
登録日時: 14年前
住所: 東京23区
連絡を取る:

Re: 組み合わせ?のプログラムの考え方が分かりません!!

#11

投稿記事 by あたっしゅ » 1年前

東上☆海美☆「

コード:

//
// https://dixq.net/forum/viewtopic.php?f=3&t=21547
// 組み合わせ?のプログラムの考え方が分かりません!! - ミクプラ(ja)
//
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


const int	BUFMAX = 5 * 2 + 1;
char		buf[ BUFMAX ];


int
calc(int sum, char* pBuf, const int* a, const int* b)
{
	while (*a != 0  && * b != 0) {
		sum += *b;

		*pBuf++ = (*b) + '0';
		*pBuf++ = ' ';
		*pBuf = 0;

#ifdef _DEBUG
		printf( ":%d:", *b );
#endif
		if (sum == 10) {
			printf("%s[%d]成功\n", buf, sum);

			return sum;
		} else if (sum > 10) {
#ifdef _DEBUG
			printf("%s[%d]失敗\n", buf, sum);
#endif
			return sum;
		} else {
			printf("%s[%d]\n", buf, sum);
		}

		calc(sum, pBuf, a, b);

		while (*b != 0) {
			b++;
			if (*b == 0) {
				break;
			}
			else
			{
#ifdef _DEBUG
				printf("$%d$", *b);
#endif
				calc(sum, pBuf, a, b);
			}
		}
	}
	return sum;
}


int
main() try
{
	memset(buf, 0, BUFMAX);

	{
		const int	array[] = { 5, 4, 3, 2, 0 };
		const int*	ptr = array;
		int			i = 0;

		while ( *ptr > 0) {
			calc(0, buf, ptr, ptr );

			ptr++;
		}
	}

	return EXIT_SUCCESS;
}

catch (...)
{
	return EXIT_FAILURE;
}


// end.
5 [5]
5 5 [10]成功
5 4 [9]
5 3 [8]
5 3 2 [10]成功
5 2 [7]
5 2 2 [9]
4 [4]
4 4 [8]
4 4 2 [10]成功
4 3 [7]
4 3 3 [10]成功
4 3 2 [9]
4 2 [6]
4 2 2 [8]
4 2 2 2 [10]成功
3 [3]
3 3 [6]
3 3 3 [9]
3 3 2 [8]
3 3 2 2 [10]成功
3 2 [5]
3 2 2 [7]
3 2 2 2 [9]
2 [2]
2 2 [4]
2 2 2 [6]
2 2 2 2 [8]
2 2 2 2 2 [10]成功

29 通りで、空集合入れると 30 通りみみ。
VTuber:
東上☆海美☆(とうじょう・うみみ)
http://atassyu.php.xdomain.jp/vtuber/index.html
レスがついていないものを優先して、レスするみみ。時々、見当外れなレスしみみ。

中の人:
手提鞄あたッしュ、[MrAtassyu] 手提鞄屋魚有店
http://ameblo.jp/mratassyu/
Pixiv: 666303
Windows, Mac, Linux, Haiku, Raspbery Pi, Jetson Nano, 電子ブロック 持ち。

dic
記事: 657
登録日時: 14年前
住所: 宮崎県
連絡を取る:

Re: 組み合わせ?のプログラムの考え方が分かりません!!

#12

投稿記事 by dic » 1年前

さすがですな

答えはどうなんだろう

アバター
あたっしゅ
記事: 665
登録日時: 14年前
住所: 東京23区
連絡を取る:

Re: 組み合わせ?のプログラムの考え方が分かりません!!

#13

投稿記事 by あたっしゅ » 1年前

東上☆海美☆「
よく考えてみると {5} と {5, 5} は、同じだから、

5 [5]
5 5 [10]成功

は、5 5 で同じ。

5 3 [8]
5 3 2 [10]成功
5 2 [7]
3 2 [5]

は、5 3 2 で同じ。

4 4 [8]
4 4 2 [10]成功
4 2 [6]

は、4 4 2 で同じ。


4 3 [7]
4 3 3 [10]成功
3 3 [6]

は、4 3 3 で同じ。

4 2 2 [8]
4 2 2 2 [10]成功

は、4 2 2 2 で同じ。

3 3 2 [8]
3 3 2 2 [10]成功
3 2 2 [7]

は、3 3 2 2 で同じ。

2 2 2 2 [8]
2 2 2 2 2 [10]成功

は、2 2 2 2 2 で同じ。
とりあえず、手動でやってみたみみ。
かなり減るな。
VTuber:
東上☆海美☆(とうじょう・うみみ)
http://atassyu.php.xdomain.jp/vtuber/index.html
レスがついていないものを優先して、レスするみみ。時々、見当外れなレスしみみ。

中の人:
手提鞄あたッしュ、[MrAtassyu] 手提鞄屋魚有店
http://ameblo.jp/mratassyu/
Pixiv: 666303
Windows, Mac, Linux, Haiku, Raspbery Pi, Jetson Nano, 電子ブロック 持ち。

アバター
あたっしゅ
記事: 665
登録日時: 14年前
住所: 東京23区
連絡を取る:

Re: 組み合わせ?のプログラムの考え方が分かりません!!

#14

投稿記事 by あたっしゅ » 1年前

東上☆海美☆「
>3 3 2 [8]
>3 3 2 2 [10]成功
>3 2 2 [7]

> は、3 3 2 2 で同じ。

3 2 2 [7] は、3 3 2 2 と同じじゃないな。


とりあえず、

5 5 [0]成功
5 4 1
5 3 2 [0]成功
5 2 2 1
4 6
4 4 2 [0]成功
4 3 3 [0]成功
4 3 2 1
4 2 2 2 [0]成功
3 7
3 3 3 1
3 3 2 2 [0]成功
3 2 2 2 1
2 8
2 2 6
2 2 2 2 2 [0]成功

と、出せるようになった。
VTuber:
東上☆海美☆(とうじょう・うみみ)
http://atassyu.php.xdomain.jp/vtuber/index.html
レスがついていないものを優先して、レスするみみ。時々、見当外れなレスしみみ。

中の人:
手提鞄あたッしュ、[MrAtassyu] 手提鞄屋魚有店
http://ameblo.jp/mratassyu/
Pixiv: 666303
Windows, Mac, Linux, Haiku, Raspbery Pi, Jetson Nano, 電子ブロック 持ち。

アバター
あたっしゅ
記事: 665
登録日時: 14年前
住所: 東京23区
連絡を取る:

Re: 組み合わせ?のプログラムの考え方が分かりません!!

#15

投稿記事 by あたっしゅ » 1年前

東上☆海美☆「
#14> 3 2 2 [7] は、3 3 2 2 と同じじゃないな。

3 2 2 [7] は、3 2 2 3 だから 3 3 2 2 と同じだな。
VTuber:
東上☆海美☆(とうじょう・うみみ)
http://atassyu.php.xdomain.jp/vtuber/index.html
レスがついていないものを優先して、レスするみみ。時々、見当外れなレスしみみ。

中の人:
手提鞄あたッしュ、[MrAtassyu] 手提鞄屋魚有店
http://ameblo.jp/mratassyu/
Pixiv: 666303
Windows, Mac, Linux, Haiku, Raspbery Pi, Jetson Nano, 電子ブロック 持ち。

返信

“C言語何でも質問掲示板” へ戻る