ページ 11

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

Posted: 2022年12月06日(火) 17:56
by チャイナ
課題について自分で考えてみたのですが、分からなかったため教えていただきたいです。

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

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

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

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

Posted: 2022年12月06日(火) 18:17
by usao
組み合わせの全パターンの数だけループして,各パターンについて合計が10mを超えないか否かを調べてやればいいよね.

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

コード:

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

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

Posted: 2022年12月06日(火) 18:20
by usao
各棒の 有る/無し は,上記の i の値の bitパターン から得れば良いと思う.

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

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

Posted: 2022年12月06日(火) 18:26
by チャイナ
ご返信ありがとうございます!

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

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

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

Posted: 2022年12月06日(火) 19:12
by usao
> 組み合わせが、{5}、{5、4}、{5、3}、{5、3、2}、・・・

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

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

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

Posted: 2022年12月06日(火) 19:16
by みけCAT
再帰で、
・今考えている長さを切り出し、また同じ長さについて考える
・今考えている長さは切り出さず、次の長さについて考える
をするといいと思います。

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]))

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

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

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

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

Posted: 2022年12月07日(水) 07:00
by dic
{5,5}や最大で{2,2,2,2,2}がありなら
再帰でとくのがいいと思います。
深さが5までで、10m以内になるように呼び出していけばできると思います。

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

オイラもかぶった

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

Posted: 2022年12月07日(水) 11:20
by あたっしゅ
東上☆海美☆「

コード:

//
// 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 通り

であってるみみ ?

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

Posted: 2022年12月07日(水) 11:27
by usao
> 7 通り

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

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

Posted: 2022年12月07日(水) 20:59
by あたっしゅ
東上☆海美☆「

コード:

//
// 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 通りみみ。

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

Posted: 2022年12月08日(木) 19:08
by dic
さすがですな

答えはどうなんだろう

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

Posted: 2022年12月16日(金) 12:41
by あたっしゅ
東上☆海美☆「
よく考えてみると {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 で同じ。
とりあえず、手動でやってみたみみ。
かなり減るな。

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

Posted: 2022年12月16日(金) 18:08
by あたっしゅ
東上☆海美☆「
>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]成功

と、出せるようになった。

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

Posted: 2022年12月16日(金) 18:10
by あたっしゅ
東上☆海美☆「
#14> 3 2 2 [7] は、3 3 2 2 と同じじゃないな。

3 2 2 [7] は、3 2 2 3 だから 3 3 2 2 と同じだな。