1順ループで再現する方法

[Edit]

はじめまして、C言語問題で行き詰ったので質問させていただいてます。

「演習問題」
寿司屋さんにある特殊な注文がありました。合計20個で2600円になるように作ってほしい。
さらだ巻き120円カンパチ130円マグロ150円。

という演習問題を出されたのですが、
これを多重ループで作成することはできたのですが、
どうしても1順ループで作成することができません。

なにかアドバイスや答えなど、
お暇な方がいたらお願いいたします。

[YuO]

問題はこれで正しいのでしょうか。
カンパチ20個で130 * 20 = 2600円となるため，コンピュータに解かせる必要が無いのですが……。

[たいちう]

問題の説明や現状の説明のためにも、多重ループで作成したプログラムを載せてはどうかと。

[みけCAT]

ナップサック問題ですね。
「1順ループ」が何かよくわかりませんが、1重ループのことであると仮定します。

1つの直感的な例としては、ループで深さ優先探索(もちろんメモ化する)を行い、
商品の種類が少ないので、商品を選ぶ部分のループをunroll(直接「さらだ巻きを選んでみる、カンパチを選んでみる、マグロを選んでみる」と書く)すれば、1重ループでできると思います。

もしくは動的計画法を使うのであれば、

コード:

for(i=0;i<M;i++) {
  for(j=0;j<N;j++) {
    /* 処理 */
  }
}

というループをしたかったら、

コード:

for(ij=0;ij<M*N;ij++) {
  int i=ij/N;
  int j=ij%N;
  /* 処理 */
}

と書けば1重ループに変換できます。

[usao]

オフトピック

>カンパチ20個で130 * 20 = 2600円となるため，コンピュータに解かせる必要が無いのですが……。

演習問題という性質上，それをわざわざプログラム書いてやる必要があるかないか　なんてことを突っ込んでも無意味では？
【「カンパチ20で達成」という答えを（も）導き出せる】プログラムを書くのが目的なのであって．

[Edit]

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

深夜テンションで書いた結果色々とことば足らずでした。

問題なのですが、全てのパターンの組み合わせを表示する

とい大事な部分が抜けておりました。。。

[かずま]

マグロが 0個、1個、... 20個(または 2600/150個まで)のループを作ると、
残りの個数と金額で、サラダ巻きとカンパチの鶴亀算となり、答えが出ます。
個数が負になったり、割り算が割り切れない場合に注意が必要です。

[Edit]

失礼します。
みけCATさんの方法で3重ループを1重ループに
するにはどうすればいいのでしょうか

[Edit]

皆さんのおかげでなんとか完成しました。
ありがとうございました。

[can110]

まずは多重ループで実現できているコードを提示しないと回答がつきにくいと思いますが、いかがでしょう？

たとえば以下のように再帰を使えば見た目のループ数は１つにできます。

コード:

#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;
}

[みけCAT]

失礼します。
みけ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;
}

[can110]

オフトピック

みけCAT さんの手法は勉強になりました。
後のために一般化してみました。

コード:

#include <cstdio>

// 多重→１重ループ
int main(void) {
	// 各次元長=L0...Ln, 位置=v0...vnの場合
	// １次元位置 = (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;
}