組み合わせ?のプログラムの考え方が分かりません!!
組み合わせ?のプログラムの考え方が分かりません!!
課題について自分で考えてみたのですが、分からなかったため教えていただきたいです。
問)10mの長さの棒から{5m、4m、3m、2m}の棒を切り取るときの組み合わせを答えよ。
組み合わせが、{5}、{5、4}、{5、3}、{5、3、2}、・・・って感じです。2次元配列にしたいのですがfor文を使ってみてもどうすればいいか分からなくなってしまいました。
皆さんの考え方をぜひ教えていただきたいです!
問)10mの長さの棒から{5m、4m、3m、2m}の棒を切り取るときの組み合わせを答えよ。
組み合わせが、{5}、{5、4}、{5、3}、{5、3、2}、・・・って感じです。2次元配列にしたいのですがfor文を使ってみてもどうすればいいか分からなくなってしまいました。
皆さんの考え方をぜひ教えていただきたいです!
Re: 組み合わせ?のプログラムの考え方が分かりません!!
各棒の 有る/無し は,上記の i の値の bitパターン から得れば良いと思う.
…っていう話が「ちょっと何言ってるかわかんないですね」とかいう場合であっても,
せいぜい 15 パターンしかないのだから,好きなように全部のパターンをハードコーディングしてやってもいいと思う.
…っていう話が「ちょっと何言ってるかわかんないですね」とかいう場合であっても,
せいぜい 15 パターンしかないのだから,好きなように全部のパターンをハードコーディングしてやってもいいと思う.
Re: 組み合わせ?のプログラムの考え方が分かりません!!
ご返信ありがとうございます!
なるほど。15種類ループですね。
問題なのですが、組み合わせは同じのを何回も使っていい、という条件です。明記し忘れました!すみません。
なるほど。15種類ループですね。
問題なのですが、組み合わせは同じのを何回も使っていい、という条件です。明記し忘れました!すみません。
Re: 組み合わせ?のプログラムの考え方が分かりません!!
> 組み合わせが、{5}、{5、4}、{5、3}、{5、3、2}、・・・
っていう記述から,それを読み取るのは難易度高いw
つーことは,{5,5} っていうパターンも有りだと.
そしたら 15 パターンとかいう話では無くなるし,力業の全探索みたいなのはやりたくない気がする.
っていう記述から,それを読み取るのは難易度高いw
つーことは,{5,5} っていうパターンも有りだと.
そしたら 15 パターンとかいう話では無くなるし,力業の全探索みたいなのはやりたくない気がする.
Re: 組み合わせ?のプログラムの考え方が分かりません!!
再帰で、
・今考えている長さを切り出し、また同じ長さについて考える
・今考えている長さは切り出さず、次の長さについて考える
をするといいと思います。
Python で実装してみました。
・今考えている長さを切り出し、また同じ長さについて考える
・今考えている長さは切り出さず、次の長さについて考える
をするといいと思います。
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で殴ればいい!(死亡フラグ)
Re: 組み合わせ?のプログラムの考え方が分かりません!!
まぁ,ふつーに(?),
・5を0個切り出す世界
・5を1個切り出す世界
・5を2個切り出す世界
のそれぞれについて,「残りの長さについて 4,3,2 の組み合わせを列挙」という,元の長さと棒の種類が小さくなった問題を解く,という話にしていくのが素直かな.
(言うまでもないが,そこでも,4をX個切り出す世界のそれぞれについて「残りの長さについて 3,2 の組み合わせを列挙」というさらなる小さい問題にしていく感じ.)
C言語なら再帰で書くのが楽かな.
(って書いてたら話が被ったようだが,せっかくだから送信しちゃうぜ)
・5を0個切り出す世界
・5を1個切り出す世界
・5を2個切り出す世界
のそれぞれについて,「残りの長さについて 4,3,2 の組み合わせを列挙」という,元の長さと棒の種類が小さくなった問題を解く,という話にしていくのが素直かな.
(言うまでもないが,そこでも,4をX個切り出す世界のそれぞれについて「残りの長さについて 3,2 の組み合わせを列挙」というさらなる小さい問題にしていく感じ.)
C言語なら再帰で書くのが楽かな.
(って書いてたら話が被ったようだが,せっかくだから送信しちゃうぜ)
Re: 組み合わせ?のプログラムの考え方が分かりません!!
{5,5}や最大で{2,2,2,2,2}がありなら
再帰でとくのがいいと思います。
深さが5までで、10m以内になるように呼び出していけばできると思います。
ソースは・・・おやすみなさい。
オイラもかぶった
再帰でとくのがいいと思います。
深さが5までで、10m以内になるように呼び出していけばできると思います。
ソースは・・・おやすみなさい。
オイラもかぶった
Re: 組み合わせ?のプログラムの考え方が分かりません!!
東上☆海美☆「
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 通り
であってるみみ ?
」
//
// 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 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, 電子ブロック 持ち。
東上☆海美☆(とうじょう・うみみ)
http://atassyu.php.xdomain.jp/vtuber/index.html
レスがついていないものを優先して、レスするみみ。時々、見当外れなレスしみみ。
中の人:
手提鞄あたッしュ、[MrAtassyu] 手提鞄屋魚有店
http://ameblo.jp/mratassyu/
Pixiv: 666303
Windows, Mac, Linux, Haiku, Raspbery Pi, Jetson Nano, 電子ブロック 持ち。
Re: 組み合わせ?のプログラムの考え方が分かりません!!
> 7 通り
最初に {5} とかも例示されている,すなわち,(ぴったり10にする必要は無くて)余りを出してもいいという話だと思うから違うんじゃない?
最初に {5} とかも例示されている,すなわち,(ぴったり10にする必要は無くて)余りを出してもいいという話だと思うから違うんじゃない?
Re: 組み合わせ?のプログラムの考え方が分かりません!!
東上☆海美☆「
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 通りみみ。
」
//
// 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 [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, 電子ブロック 持ち。
東上☆海美☆(とうじょう・うみみ)
http://atassyu.php.xdomain.jp/vtuber/index.html
レスがついていないものを優先して、レスするみみ。時々、見当外れなレスしみみ。
中の人:
手提鞄あたッしュ、[MrAtassyu] 手提鞄屋魚有店
http://ameblo.jp/mratassyu/
Pixiv: 666303
Windows, Mac, Linux, Haiku, Raspbery Pi, Jetson Nano, 電子ブロック 持ち。
Re: 組み合わせ?のプログラムの考え方が分かりません!!
さすがですな
答えはどうなんだろう
答えはどうなんだろう
Re: 組み合わせ?のプログラムの考え方が分かりません!!
東上☆海美☆「
よく考えてみると {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 で同じ。
とりあえず、手動でやってみたみみ。
かなり減るな。
」
よく考えてみると {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, 電子ブロック 持ち。
東上☆海美☆(とうじょう・うみみ)
http://atassyu.php.xdomain.jp/vtuber/index.html
レスがついていないものを優先して、レスするみみ。時々、見当外れなレスしみみ。
中の人:
手提鞄あたッしュ、[MrAtassyu] 手提鞄屋魚有店
http://ameblo.jp/mratassyu/
Pixiv: 666303
Windows, Mac, Linux, Haiku, Raspbery Pi, Jetson Nano, 電子ブロック 持ち。
Re: 組み合わせ?のプログラムの考え方が分かりません!!
東上☆海美☆「
>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]成功
と、出せるようになった。
」
>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, 電子ブロック 持ち。
東上☆海美☆(とうじょう・うみみ)
http://atassyu.php.xdomain.jp/vtuber/index.html
レスがついていないものを優先して、レスするみみ。時々、見当外れなレスしみみ。
中の人:
手提鞄あたッしュ、[MrAtassyu] 手提鞄屋魚有店
http://ameblo.jp/mratassyu/
Pixiv: 666303
Windows, Mac, Linux, Haiku, Raspbery Pi, Jetson Nano, 電子ブロック 持ち。
Re: 組み合わせ?のプログラムの考え方が分かりません!!
東上☆海美☆「
#14> 3 2 2 [7] は、3 3 2 2 と同じじゃないな。
3 2 2 [7] は、3 2 2 3 だから 3 3 2 2 と同じだな。
」
#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, 電子ブロック 持ち。
東上☆海美☆(とうじょう・うみみ)
http://atassyu.php.xdomain.jp/vtuber/index.html
レスがついていないものを優先して、レスするみみ。時々、見当外れなレスしみみ。
中の人:
手提鞄あたッしュ、[MrAtassyu] 手提鞄屋魚有店
http://ameblo.jp/mratassyu/
Pixiv: 666303
Windows, Mac, Linux, Haiku, Raspbery Pi, Jetson Nano, 電子ブロック 持ち。