FGO Blog

摺紙問題
一張紙沿一個方向對摺，凹為0，凸為1
以0／1顯示相對應對摺數之規律

#include <iostream>
#include <string>
#include <math.h>

using namespace std;

int main() {
    string result = ""; //length=2ˆn-1
    short layer; //n
    string buf;
    string second = "001";
    
    getline(cin, buf);
    layer = stoi(buf, nullptr);
	if (layer == 1) cout << 0;
	else if (layer == 2) cout << second;
	else result = second;
	
	string prefix,suffix;
	for (auto i=3; i<=layer; i++){
		auto temp_len = pow(2,i)-1;
		auto mid = pow(2,i-1)/2;
		string temp;
		
		//prefix part
		for (auto j=0; j<mid-1; j++){
			temp += result[j];
		}
		prefix = temp;
		temp = "";
		
		//suffix part
		for (auto j=mid; j<(pow(2,i-1)-1); j++){
			temp += result[j];
		}
		suffix = temp;
		temp = "";
		
		//repeat part
		result = prefix + '0' + suffix + '0' + prefix + '1' + suffix;
	}
	
	cout << result;
}

規律解釋:
摺一次是0
摺兩次是001(不明白的自己摺一次)
然後因為之後的都是取之前的 前半部+0+後半部+0+前半部+1+後半部 這種規律,所以很快就做出來了
只是這個做法不太美觀,用STL的string也不夠快……