コインの裏表のパターンを表示させたいです

[あつきんぐ]

C言語初心者ですが、わからないことがあります。

コインをn回投げた時の裏表全てのパターンを表示させるプログラムを作成したいです。

n＝3のとき、

1.表表表
2.表表裏
3.表裏表
4.表裏裏
5.裏表表
6.裏表裏
7.裏裏表
8.裏裏裏

となり、列を見ると左から2^3、2^2、2^1ごとに表と裏が交互に表示してることはわかりましたが、それを書くプログラムが思いつきません。
この解釈の仕方であってるのでしょうか。あっているのであればそれを表示させるプログラムのヒントを教えてください。
間違っているのならほかの方法のヒントを教えてください。

補足：forとかifなど基本的なことしか使えません…それを考慮して教えてください

[みけCAT]

1.の行を0行目とします。
左から3番目→2^1周期で繰り返しているので、何行目かを2^1で割った余りが2^0未満なら表、そうでなければ裏
左から2番目→2^2周期で繰り返しているので、何行目かを2^2で割った余りが2^1未満なら表、そうでなければ裏
左から1番目→2^3周期で繰り返しているので、何行目かを2^3で割った余りが2^2未満なら表、そうでなければ裏
一般に、右からn番目→2^n周期で繰り返しているので、何行目かを2^nで割った余りが2^(n-1)未満なら表、そうでなければ裏
このように判定するのが一つの方法でしょう。

もう一つの方法は、表/裏が0/1に対応する2進数になっていることがすぐにわかるので、ビット演算で判定することです。
↓実装例

► スポイラーを表示

コード:

#include <stdio.h>

int main(void) {
  int n = 3, i, j;
  for (i = 0; i < (1 << n); i++) {
    printf("%d.", i + 1);
    for (j = n - 1; j >= 0; j--) {
      if (i & (1 << j)) {
        printf("裏");
      } else {
        printf("表");
      }
    }
    printf("\n");
  }
  return 0;
}

[akasann]

古いものを再びもってきますが、上記のコードに見とれてしまいました。

7,8行のところが少し理解できません

コード:

   for (i = 0; i < (1 << n); i++) {
    printf("%d.", i + 1);
    for (j = n - 1; j >= 0; j--) {
      if (i & (1 << j)) {
        printf("裏");
      } else {
        printf("表");
      }
    }
    printf("\n");
  }

2個めのfor文の中身のところと、if文の中身のところが理解できません。if文が分ればなんとなく理解できると思いますが・・
例えば、i=0でj=2の時の処理はどのような構造となっているのでしょうか？
000(0) AND 100(1を左に2個シフト) ->000(0)
となり偽の判定がくだり表ということでよろしいのでしょうか？

深く言うと2個めのfor文が大きい数から小さくして言っている理由もしりたいところです。

説明が伝わったか分りませんが解答、アドバイス、説明をお願いできませんか？

[みけCAT]

2個めのfor文の中身のところと、if文の中身のところが理解できません。if文が分ればなんとなく理解できると思いますが・・
例えば、i=0でj=2の時の処理はどのような構造となっているのでしょうか？
000(0) AND 100(1を左に2個シフト) ->000(0)
となり偽の判定がくだり表ということでよろしいのでしょうか？

そんな感じですね。
iと「1を左にjビットシフトしたもの」とのANDをとることで、iの下からjビット目(0-origin)が1かどうかを判定しています。

深く言うと2個めのfor文が大きい数から小さくして言っている理由もしりたいところです。

上の桁から下の桁の順で出力するためです。

[かずま]

ビット演算を使わないやり方です。

コード:

#include <stdio.h>

int main(void)
{
    static const char *s[] = { "表", "裏" };
    int k = 0, a[3];
    for (a[0] = 0; a[0] < 2; a[0]++)
        for (a[1] = 0; a[1] < 2; a[1]++)
            for (a[2] = 0; a[2] < 2; a[2]++) {
                printf("%d.", ++k);
                for (int i = 0; i < 3; i++)
                    printf(s[a[i]]);
                putchar('\n');
            }
    return 0;
}

ビット演算は使うけど、if文を使わないやり方です。

コード:

#include <stdio.h>

#define N 3

int main(void)
{
    static const char *s[] = { "表", "裏" };
    for (int i = 0; i < (1 << N); i++) {
        printf("%d.", i+1);
        for (int j = N; j--; ) printf(s[i >> j & 1]);
        putchar('\n');
    }
    return 0;
}

[Re]

シフトを使わずに作った例です
nとnum[]の添字には同じ数を入れます

コード:

#include<stdio.h>
int main()
{
int a,b,n=4;
int count=duplex(n);
int num[4];
int count2;
for(b=1;b<=count;b++){
count2=count-b;
int a2;
for(a2=0;a2<n;a2++){
num[a2]=count2/duplex(n-a2-1);
count2=count2-duplex(n-a2-1)*num[a2];
if(num[a2]==1){
printf("●");}
else if(num[a2]==0){
printf("○");
}
}
printf("\n");
}
}
int duplex(int c){
int a=1,b;
for(b=0;b<c;b++){
a=a*2;
}
return a;
}

[あんどーなつ]

なぜインデントを使わない。なぜ●〇？

[あんどーなつ]

ifとforしか使えないなら、たぶんこう。

コード:

#include <stdio.h>

#define OMOTE 0
#define URA 1

int main() {
	int coin1 = 0;
    int coin2 = 0;
    int coin3 = 0;
    int count1 = 0;
    int count2 = 0;
    int count3 = 0;
    for (int i = 0; i < 8; i++) {
		if (count1 == 1) {
			if (coin1 == 0)
				coin1 = 1;
			else
				coin1 = 0;
			count1 = 0;
		}
		if (count2 == 2) {
			if (coin2 == 0)
				coin2 = 1;
			else
				coin2 = 0;
			count2 = 0;
		}
		if (count3 == 4) {
			if (coin3 == 0)
				coin3 = 1;
			else
				coin3 = 0;
			count3 = 0;
		}
		if (coin3 == 0)
			printf("表");
		else
			printf("裏");
		if (coin2 == 0)
			printf("表");
		else
			printf("裏");
		if (coin1 == 0)
			printf("表");
		else
			printf("裏");
		printf("\n");
		count1++;
		count2++;
		count3++;
	}
	return 0;
}

[あんどーなつ]

申し訳ないです、nは可変だったのですね。

[あんどーなつ]

すみません、こっちです。配列を使わないので、計算をたくさんしてカバーしています。

コード:

#include <stdio.h>

int main() {
	int n; // コインの数
	int maxrow; // 最大行数
	int i, j, k; // ループ変数
	int kankaku; // 裏返すまでの間隔
	int coin; // 0: 表, 1: 裏
	int count;

	printf("コインの数を指定してください: ");
	scanf("%d", &n);

	// 行数を算出
	maxrow = 1;
	for (i = 0; i < n; i++) {
		maxrow = maxrow * 2;
	}

	// i行j列でループ
	for (i = 1; i <= maxrow; i++) {
		printf("%d. ", i);
		for (j = 1; j <= n; j++) {
			// 裏返すまでの間隔を計算
			kankaku = 1;
			for (k = 1; k <= (n - j); k++) {
				kankaku = kankaku * 2;
			}

			// i行目でコインがどうなっているかを計算
			coin = 0;
			count = 0;
			for (k = 1; k <= i; k++) {
				if (count == kankaku) {
					if (coin == 0)
						coin = 1;
					else
						coin = 0;
					count = 0;
				}
				count++;
			}

			if (coin == 0)
				printf("表");
			else
				printf("裏");
		}
		printf("\n");
	}
}

[あんどーなつ]

しかし、制御文しか使えない状態でコインの表裏問題を先生が出すとは考えづらいですね。
ビットシフトはまだしも配列くらいは使っていいのですよね？

[かずま]

n を可変にし、ビット演算も掛け算割り算も使わないプログラム

コード:

#include <stdio.h>

#define MAX_N 32

int n, k;
const char *a[MAX_N];

void proc(int i)
{
    if (i == n) {
        printf("%d.", ++k);
        for (i = 0; i < n; i++) printf(a[i]);
        putchar('\n');
    }
    else {
        a[i] = "表", proc(i+1);
        a[i] = "裏", proc(i+1);
    }
}

int main(void)
{
    while (printf("n > "), scanf("%d", &n) == 1 && n > 0 && n <= MAX_N) {
        k = 0;
        proc(0);
    }
    return 0;
}

[あんどーなつ]

かずまさんが再帰関数のプログラムを作成していたようでしたので、
C++でイテレータ「もどき」を書いてみました。もちろんただの趣味です。
最初、関数１つでいいかと思ってたのですが、ストリームに出力する場合は２つ（判定と出力）必要だということに気づきました。

コード:

#include <iostream>

using namespace std;

class printer {
	public:
		virtual int is_end() = 0;
		virtual void print() = 0;
};
class printer1 : public printer {
	int state = 0;
public:
	virtual int is_end() { return (state == 2); };
	virtual void print() {
		cout << ((state == 0) ? "表" : "裏") << endl;
		state++;
	};
};
class printerN : public printer {
	int size = 2;
	int state = 0;
	printer *sub = 0;
	void create_sub() {
		if (size == 2) sub = new printer1();
		else sub = new printerN(size-1);
	}
public:
	printerN(int n) {
		size = n;
		create_sub();
	};
	virtual int is_end() { return (state == 2); };
	virtual void print() {
		cout << ((state == 0) ? "表" : "裏");
		sub->print();
		if (sub->is_end()) {
			state++;
			delete sub;
			if (state < 2) create_sub();
		}
	}
};

int main() {
	//printer *p = new printer1();
	printer *p = new printerN(3);
	while (!p->is_end()) p->print();
	return 0;
}

[あんどーなつ]

先ほどのC++のコードはクラスを３つ作りましたが、１つにまとめました。
少し短くなりました。

コード:

#include <iostream>

using namespace std;

class printer {
	int size = 2;
	int state = 0;
	printer *sub = nullptr;
public:
	printer(int n) {
		size = n;
		if (n >= 2) sub = new printer(n-1);
	};
	int is_end() { return (state == 2); };
	void print() {
		cout << ((state == 0) ? "表" : "裏");
		if (size == 1) {
			cout << endl;
			if (state != 2) state++;
			return;
		}
		sub->print();
		if (!sub->is_end()) return;
		state++;
		delete sub;
		if (state < 2) sub = new printer(size-1);
	};
};

int main() {
	printer p(3);
	while (!p.is_end()) p.print();
	return 0;
}

[あんどーなつ]

このコインの課題をC++のクロージャを使って解こうと思ったのですが、うまく書けませんでした。腕に自信のある方は挑戦ねがいます。

[かずま]

このコインの課題をC++のクロージャを使って解こうと思ったのですが、うまく書けませんでした。腕に自信のある方は挑戦ねがいます。

コード:

#include <iostream>

using namespace std;

auto proc(int n)
{
    static const char *s[] = { "裏", "表" };
    int m = 1 << n, i = m;
    return [&, m]() {
        cout << m - --i << ".";
        for (int j = n; j--; ) cout << s[i >> j & 1]; 
        endl(cout);
        return i;
    };
}

int main()
{
    for (int n; cout << "n > ", cin >> n && n > 0 && n < 32; ) {
        auto print = proc(n);
        while (print()) ;
    }
}

gcc -std=c++14 でコンパイル。
さらに文字コードが Shift-JIS の場合、--input-charset=cp932 も必要。

[かずま]

gcc -std=c++14 でコンパイル。

g++ -std=c++14 でコンパイル。

[あんどーなつ]

かずまさん さすがです。

14歳からの・・・を読み始めたのに、掲示板が面白すぎて先に進めないわー

[あんどーなつ]

クロージャで再帰をやろうとしましたが、断念しました。
最初にパッと思いついたやつですけど、コンテナを使うと再帰は簡単に書けました。

コード:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> req(int n) {
	if (n == 0) { return vector<string>{"\n"}; }
	vector<string> v;
	auto sub = req(n-1);
	for_each(sub.cbegin(), sub.cend(),
		[&](string s) { v.push_back("表" + s); } );
	for_each(sub.cbegin(), sub.cend(),
		[&](string s) { v.push_back("裏" + s); } );
	return v;
}

int main() {
	cout << "コインの数を指定してください: ";
	int coins;
	cin >> coins;
	auto v = req(coins);
	int i = 1;
	for_each(v.cbegin(), v.cend(),
		[&](string s) {
			cout << i++ << "." << s; } );
	return 0;
}

[akasann]

2個めのfor文の中身のところと、if文の中身のところが理解できません。if文が分ればなんとなく理解できると思いますが・・
例えば、i=0でj=2の時の処理はどのような構造となっているのでしょうか？
000(0) AND 100(1を左に2個シフト) ->000(0)
となり偽の判定がくだり表ということでよろしいのでしょうか？

そんな感じですね。
iと「1を左にjビットシフトしたもの」とのANDをとることで、iの下からjビット目(0-origin)が1かどうかを判定しています。

深く言うと2個めのfor文が大きい数から小さくして言っている理由もしりたいところです。

上の桁から下の桁の順で出力するためです。

返信ありがとうございます。ビット演算子の使い方はなんとなくわかりました。