1順ループで再現する方法
1順ループで再現する方法
はじめまして、C言語問題で行き詰ったので質問させていただいてます。
「演習問題」
寿司屋さんにある特殊な注文がありました。合計20個で2600円になるように作ってほしい。
さらだ巻き120円カンパチ130円マグロ150円。
という演習問題を出されたのですが、
これを多重ループで作成することはできたのですが、
どうしても1順ループで作成することができません。
なにかアドバイスや答えなど、
お暇な方がいたらお願いいたします。
「演習問題」
寿司屋さんにある特殊な注文がありました。合計20個で2600円になるように作ってほしい。
さらだ巻き120円カンパチ130円マグロ150円。
という演習問題を出されたのですが、
これを多重ループで作成することはできたのですが、
どうしても1順ループで作成することができません。
なにかアドバイスや答えなど、
お暇な方がいたらお願いいたします。
Re: 1順ループで再現する方法
問題はこれで正しいのでしょうか。
カンパチ20個で130 * 20 = 2600円となるため,コンピュータに解かせる必要が無いのですが……。
カンパチ20個で130 * 20 = 2600円となるため,コンピュータに解かせる必要が無いのですが……。
Re: 1順ループで再現する方法
ナップサック問題ですね。
「1順ループ」が何かよくわかりませんが、1重ループのことであると仮定します。
1つの直感的な例としては、ループで深さ優先探索(もちろんメモ化する)を行い、
商品の種類が少ないので、商品を選ぶ部分のループをunroll(直接「さらだ巻きを選んでみる、カンパチを選んでみる、マグロを選んでみる」と書く)すれば、1重ループでできると思います。
もしくは動的計画法を使うのであれば、 というループをしたかったら、 と書けば1重ループに変換できます。
「1順ループ」が何かよくわかりませんが、1重ループのことであると仮定します。
1つの直感的な例としては、ループで深さ優先探索(もちろんメモ化する)を行い、
商品の種類が少ないので、商品を選ぶ部分のループをunroll(直接「さらだ巻きを選んでみる、カンパチを選んでみる、マグロを選んでみる」と書く)すれば、1重ループでできると思います。
もしくは動的計画法を使うのであれば、 というループをしたかったら、 と書けば1重ループに変換できます。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
Re: 1順ループで再現する方法
オフトピック
>カンパチ20個で130 * 20 = 2600円となるため,コンピュータに解かせる必要が無いのですが……。
演習問題という性質上,それをわざわざプログラム書いてやる必要があるかないか なんてことを突っ込んでも無意味では?
【「カンパチ20で達成」という答えを(も)導き出せる】プログラムを書くのが目的なのであって.
演習問題という性質上,それをわざわざプログラム書いてやる必要があるかないか なんてことを突っ込んでも無意味では?
【「カンパチ20で達成」という答えを(も)導き出せる】プログラムを書くのが目的なのであって.
Re: 1順ループで再現する方法
返信ありがとうございます。
深夜テンションで書いた結果色々とことば足らずでした。
問題なのですが、全てのパターンの組み合わせを表示する
とい大事な部分が抜けておりました。。。
深夜テンションで書いた結果色々とことば足らずでした。
問題なのですが、全てのパターンの組み合わせを表示する
とい大事な部分が抜けておりました。。。
Re: 1順ループで再現する方法
マグロが 0個、1個、... 20個(または 2600/150個まで)のループを作ると、
残りの個数と金額で、サラダ巻きとカンパチの鶴亀算となり、答えが出ます。
個数が負になったり、割り算が割り切れない場合に注意が必要です。
残りの個数と金額で、サラダ巻きとカンパチの鶴亀算となり、答えが出ます。
個数が負になったり、割り算が割り切れない場合に注意が必要です。
Re: 1順ループで再現する方法
まずは多重ループで実現できているコードを提示しないと回答がつきにくいと思いますが、いかがでしょう?
たとえば以下のように再帰を使えば見た目のループ数は1つにできます。
たとえば以下のように再帰を使えば見た目のループ数は1つにできます。
#include <stdio.h>
const int aLOOP[] = { 3, 2, 4, }; // 各次元のループ数
const int N_DIM = sizeof(aLOOP)/sizeof(aLOOP[0]); // 次元数
int aVal[N_DIM] = {0}; // 表示用
// 表示
void print( void){
for( int j = 0; j < N_DIM; j++){
printf("[%2d]", aVal[j]);
}
printf( "\n");
}
// 再帰による多重ループ
// nDim : 次元位置 0~N_DIM-1
void loop( int nDim){
printf("loop(%2d) start.\n", nDim);
for( int i = 0; i < aLOOP[nDim]; i++){
aVal[nDim] = i; // 表示用
if( nDim == (N_DIM-1)){ // 最終
print(); // 表示
}
else if(nDim < (N_DIM-1)){ // 途中
loop( nDim+1); // 次へ
}
}
printf("loop(%2d) end.\n", nDim);
}
int main() {
loop(0);
return 0;
}
Re: 1順ループで再現する方法
とりあえず、変換するループを用意します。Edit さんが書きました:失礼します。
みけCATさんの方法で3重ループを1重ループに
するにはどうすればいいのでしょうか
for (int i = 0; i < L; i++) {
for (int j = 0; j < M; j++) {
for (int k = 0; k < N; k++) {
printf("%d %d %d\n", i, j, k);
}
}
}
for (int i = 0; i < L; i++) {
for (int jk = 0; jk < M * N; jk++) {
int j = jk / N;
int k = jk % N;
printf("%d %d %d\n", i, j, k);
}
}
for (int ijk = 0; ijk < L * (M * N); ijk++) {
int i = ijk / (M * N);
int jk = ijk % (M * N);
int j = jk / N;
int k = jk % N;
printf("%d %d %d\n", i, j, k);
}
#include <cstdio>
int main(void) {
int L = 5;
int M = 3;
int N = 2;
for (int i = 0; i < L; i++) {
for (int j = 0; j < M; j++) {
for (int k = 0; k < N; k++) {
printf("%d %d %d\n", i, j, k);
}
}
}
puts("-----------");
for (int ijk = 0; ijk < L * (M * N); ijk++) {
int i = ijk / (M * N);
int jk = ijk % (M * N);
int j = jk / N;
int k = jk % N;
printf("%d %d %d\n", i, j, k);
}
return 0;
}
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
Re: 1順ループで再現する方法
オフトピック
みけCAT さんの手法は勉強になりました。
後のために一般化してみました。
後のために一般化してみました。
#include <cstdio>
// 多重→1重ループ
int main(void) {
// 各次元長=L0...Ln, 位置=v0...vnの場合
// 1次元位置 = (L1*...*Ln)*v0 + (L2*...*Ln)*v1 +...+ (Ln)*vn-1 + vn
// ※L0は作用しない
const int aL[] = { 4, 3, 2, };
const int N_DIM = sizeof(aL)/sizeof(aL[0]);
// 総長
int nTotalLen(1);
for( int i = 0; i < N_DIM; i++){
nTotalLen *= aL[i];
}
for (int i = 0; i < nTotalLen; i++) {
int nLenPos = i;
int nTaniLen= nTotalLen;
// 各次元位置
for( int j = 0; j < N_DIM; j++){
nLenPos = nLenPos % nTaniLen; // この次元での長さ
nTaniLen= nTaniLen / aL[j]; // この次元の単位長
int v = nLenPos / nTaniLen; // この次元での位置
printf( "[%2d]", v);
}
printf( "\n");
}
return 0;
}