paizaラーニングレベルアップ問題集の「山折り谷折り」をやってみた

paiza×Qiita記事投稿キャンペーンということで、paizaラーニングレベルアップ問題集の[山折り谷折り](https://paiza.jp/works/mondai/real_event/origami)をやってみました。
- - -
##### 解法1
紙の左端を$0$、右端を$2^N$、$N$回折った後の折り目に左から順に$1,2,\dots,2^N-1$と番号を付けます。すると
- $1$回目　$2^{N-1}$番目の折り目が谷折り(`0`)
- $2$回目　$1\times2^{N-2}$番目の折り目が谷折り(`0`)、$3\times2^{N-2}$番目の折り目が山折り(`1`)
- $3$回目　$1\times2^{N-3}$番目の折り目が谷折り(`0`)、$3\times2^{N-3}$番目の折り目が山折り(`1`)、$5\times2^{N-3}$番目の折り目が谷折り(`0`)、$7\times2^{N-3}$番目の折り目が山折り(`1`)
- (中略)
- $k$回目　$(2i-1)\times2^{N-k}$番目の折り目が谷折り(`0`)（resp. 山折り(`1`)）ならば、既に折り目が付いている$2i\times2^{N-k}=i\times2^{N-(k-1)}$番目の折り目を対称軸として、$(2i+1)\times2^{N-k}$番目の折り目が山折り(`1`)（resp. 谷折り(`0`)）

になります。ここで、$2^N$は、多くのプログラミング言語でシフト演算を用いて`1<<N`と書くことができます。したがって、以下のような雛型になります。
```
A[1<<N]: 配列
for(k=1;k<=N;k++){//k回目の作業
    for(i=1;i<=(1<<(k-1));i++){
        //左から(2i-1)*2^(N-k)番目の折り目は、iが奇数なら0:谷、偶数なら1:山
        A[(2*i-1)*(1<<(N-k))]=(i-1)%2;
    }
}
for(i=1;i<(1<<N);i++){
    A[i]を改行無しで出力
}
改行を出力
```
※上のプログラムでは、要素`A[0]`は未定義のままです。
`A[1<<N]`を文字配列とすれば、`A[1]`以降を文字列として一行で出力できるでしょう。
- - -
##### 解法2
$i$番目の折り目を対称軸として、$j$番目の折り目が谷折りならば$2i-j$番目の折り目は山折り、$j$番目の折り目が山折りならば$2i-j$番目の折り目は谷折りになります。

結論から言うと、関数`reverse`を
```
reverse(s: 文字列){
    t=""
    for(c: 文字 : sの末尾から先頭まで){
        if(c=='0')t+='1';
        else if(c=='1')t+='0';
    }
    return t;
}
```
と定義すれば、
```
String origami(N: 整数：紙を折る回数){
    if(N==0)return ""
    s=origami(N-1)
    return s+"0"+reverse(s)
}

N = 入力値
origami(N)を出力
```
が答えになります。
- - -
##### サンプルコード(C)
:::note
ここから先は、この問題の解き方の記事というよりも、C言語における文字列の扱い方に主眼を置いた内容となります。
:::
C言語には文字列結合演算子がありませんが、`strcat`関数等使うと以下のように書けます。
###### 出力用の文字列配列を引数に入れる
```c
#include <stdio.h>
#include <string.h>

char* reverse(char *dst, const char *src) {
	int n = (int) strlen(src);
	for (int i = 0; i < n; i++) {
		char c = src[n - i - 1]; //実は、src[n + ~i]とも書けます。
		if (c == '0')
			dst[i] = '1';
		else if (c == '1')
			dst[i] = '0';
	}
	dst[n] = '\0';
	return dst;
}

char* origami(char *dst, int n) {
	if (n == 0) {
		dst[0] = '\0';
		return dst;
	}
	char s[1 << (n - 1)];
	strcpy(dst, origami(s, n - 1));
	strcat(dst, "0");
	char t[1 << (n - 1)];
	strcat(dst, reverse(t, s));
	return dst;
}

int main() {
	int n;
	scanf("%d", &n);
	char str[1 << n];
	puts(origami(str, n));
	return 0;
}
```
$N=20$の時は$1,048,575$文字の出力になりますが、[paiza.io](https://paiza.io/)では$10^5$文字しか確認することはできません。
- - -
###### `malloc`を使う
`free`での解放忘れにご注意ください。
※以下の例では、`malloc`でのメモリ確保失敗した場合に単に`abort();`で強制終了させてしまっています。
```c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char* reverse(const char *src) {
	int n = (int) strlen(src);
	char *dst = (char*) malloc(n + 1);
	if (!dst)
		abort();
	for (int i = 0; i < n; i++) {
		char c = src[n - i - 1]; //実は、src[n + ~i]とも書けます。
		if (c == '0')
			dst[i] = '1';
		else if (c == '1')
			dst[i] = '0';
	}
	dst[n] = '\0';
	return dst;
}

char* origami(int n) {
	char *str = NULL;
	if (n == 0) {
		if ((str = (char*) malloc(1)) == NULL)
			abort();
		str[0] = '\0';
		return str;
	}
	char *s = origami(n - 1);
	char *t = reverse(s);
	if ((str = (char*) malloc(strlen(s) + strlen(t) + 2)) == NULL)
		abort();
	strcpy(str, s);
	strcat(str, "0");
	strcat(str, t);
	free(t);
	free(s);
	return str;
}

int main() {
	int n;
	scanf("%d", &n);
	char *str = origami(n);
	puts(str);
	free(str);
	return 0;
}
```
- - -
:::note alert
Cでは、以下のように、関数内で宣言した配列を返却することはできません。
```c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char* reverse(const char *src) {
	int n = (int) strlen(src);
	char dst[n + 1]; //関数内で配列を宣言
	for (int i = 0; i < n; i++) {
		char c = src[n + ~i];
		if (c == '0')
			dst[i] = '1';
		else if (c == '1')
			dst[i] = '0';
	}
	dst[n] = '\0';
	return dst; //関数内で宣言した配列を返す
}

char* origami(int n) {
	if (n == 0) {
		return "";
	}
	char *s = origami(n - 1);
	char *t = reverse(s);
	char str[strlen(s) + strlen(t) + 2]; //関数内で配列を宣言
	strcpy(str, s);
	strcat(str, "0");
	strcat(str, t);
	return str; //関数内で宣言した配列を返す
}

int main() {
	int n;
	scanf("%d", &n);
	puts(origami(n));
	return 0;
}
```
:::