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

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

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

#1

投稿記事 by Edit » 5年前

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

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

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

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

YuO
記事: 941
登録日時: 9年前
住所: 東京都世田谷区

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

#2

投稿記事 by YuO » 5年前

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

たいちう
記事: 418
登録日時: 9年前

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

#3

投稿記事 by たいちう » 5年前

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

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

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

#4

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

ナップサック問題ですね。
「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重ループに変換できます。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

アバター
usao
記事: 1573
登録日時: 6年前

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

#5

投稿記事 by usao » 5年前

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

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

Edit

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

#6

投稿記事 by Edit » 5年前

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

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

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

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

かずま

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

#7

投稿記事 by かずま » 5年前

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

Edit

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

#8

投稿記事 by Edit » 5年前

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

Edit

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

#9

投稿記事 by Edit » 5年前

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

can110
記事: 27
登録日時: 5年前

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

#10

投稿記事 by can110 » 5年前

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

たとえば以下のように再帰を使えば見た目のループ数は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;
}

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

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

#11

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

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で殴ればいい!(死亡フラグ)

can110
記事: 27
登録日時: 5年前

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

#12

投稿記事 by can110 » 5年前

オフトピック
みけ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;
}

閉鎖

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