经典编程题——折纸问题_无限折纸编程

眼过千遍不如coding一遍，简单记录一下笔试题

题目描述：

请把纸条竖着放在桌⼦上，然后从纸条的下边向上⽅对折，压出折痕后再展开。此时有1条折痕，突起的⽅向指向纸条的背⾯，这条折痕叫做“下”折痕 ；突起的⽅向指向纸条正⾯的折痕叫做“上”折痕。如果每次都从下边向上⽅ 对折，对折N次。请从上到下计算出所有折痕的⽅向。给定折的次数n,请返回从上到下的折痕的数组，若为下折痕则对应元素为"down",若为上折痕则为"up"。

分析及测试用例

假如沿着上往下折，所以折痕从下往上数依次为：
1：{“down”}
2：{“down”,“down”,“up”}
3：{“down”,“down”,“up”,“down”,“down”,“up”,“up”}
因为从上往下折，每次折的时候，中间折痕是down
每次折都是在往相反的方向复刻上一折的折痕

思路：

因为要求输出字符串数组，所以操作不好操作，可以先基于1,-1操作，最后在遍历一遍相应的替换即可；
每次中间 “down” 的位置依次为2的n次方
数组的第一个位置为1(down),从第二次开始，每次与2的n次方与左边值等距离的右边值为左边值得相反数，递归求解即可

coding

void getFold(int index,int n,vector<int> vec)  //先得到int数组得目的就是整数还有个取反操作
{
	if (n >= 1)
	{
		vec[index] = 1;   //每次折痕的位置都为1（down）
		int newindex = 2 * index + 1;  //下一次折纸得位置
		for (int i = 0;i<index;i++)
		{
			vec[index + i] = vec[index - i];  //折纸两侧的折痕相反
		}
		getFold(newindex, n - 1, vec);
	}
}
long long getnum(int n)   //折n次得多少折痕
{
	long long x = 1;
	while (n--)
	{
		x *= 2;
	}
	return x-1;
}
vector<string> foldPaper(int n)  //遍历int数组，得到string数组
{
	int sum = static_cast<int>(getnum(n));
	vector<int> vec(sum);
	vector<string> vecstr(sum);
	getFold(0, n, vec);
	for (auto&x:vec)
	{
		if (x == 1)
		{
			vecstr.emplace_back("down");
		}
		else
		{
			vecstr.emplace_back("up");
		}
	}
	return vecstr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

其他解法：

void esayFinds(int n,bool isdown,vector<string> &vec)
{
	if (n == 0)  return;
	esayFinds(n - 1, true,vec);
	if (isdown)
	{
		vec.emplace_back("down");
	}
	else
	{
		vec.emplace_back("up");
	}
	esayFinds(n - 1,false, vec);
}

vector<string> foldPaper(int n) 
{
	vector<string> vec;
	esayFinds(n, true,vec);
	return vec;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

朋友们可以评论一下这是什么思路得解法