首页 > 试题广场 >

折纸问题

[编程题]折纸问题

热度指数：9557 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

请把纸条竖着放在桌⼦上，然后从纸条的下边向上⽅对折，压出折痕后再展开。此时有1条折痕，突起的⽅向指向纸条的背⾯，这条折痕叫做“下”折痕；突起的⽅向指向纸条正⾯的折痕叫做“上”折痕。如果每次都从下边向上⽅对折，对折N次。请从上到下计算出所有折痕的⽅向。

给定折的次数n,请返回从上到下的折痕的数组，若为下折痕则对应元素为"down",若为上折痕则为"up".

测试样例：

返回：["down"]

算法知识视频讲解

Python

华科平凡

python极其简单的解法，使用中序遍历。

class FoldPaper:
    def foldPaper(self, n):
        res = []
        def midTraversal(n, postion):
            if n == 0:
                return
            midTraversal(n - 1, "left")
            if postion == "left":
                res.append("down")
            else:
                res.append("up")
            midTraversal(n - 1, "right")

        midTraversal(n,"left")
        return res

发表于 2017-09-12 11:09:38 回复(1)

C/C++

nbgao

class FoldPaper {
public:
    vector<string> foldPaper(int n) {
        vector<string> v;         Push(v, n, "down");         return v;
    }
    void Push(vector<string> &v, int n, string s)
    {
        if(n>0)
        {
            Push(v, n-1, "down");
            v.push_back(s);
            Push(v, n-1, "up");         }     }
};

发表于 2017-10-30 00:34:49 回复(0)

牛客783404号

我们用一个假想的一维数组来模拟这个满二叉树，如果折叠N次，那么共有 2 ^N -1条折痕，也就是说，这棵想象中的满二叉树，有 2 ^N -1个结点。从1开始按层次遍历标号各结点。显然，除根结点外，偶数号结点均为左结点，奇数号结点均为右结点。也就是说，遇到偶数，就输出Down，遇到奇数，就输出Up.

用迭代来实现二叉树的中序遍历即可搞定。

class FoldPaper {

public:

vector<string> foldPaper(int n) {

// write code here

vector<string>result;

if(n<=0)

return result;

int num=pow(2,n)-1;

int tree=1;

stack<int> node;

while(tree<=num||!node.empty())

{

while(tree<=num)

{

node.push(tree);

tree*=2;

}

tree=node.top();

node.pop();

if(tree%2==0||tree==1)

result.push_back("down");

else

result.push_back("up");

tree=tree*2;

tree++;

}

return result;

}

};

发表于 2016-05-30 15:37:05 回复(0)

waterbinbin


	classFoldPaper {



	public:



	    vector<string> printFoldPaper(inti,intn,bool isDownOrUp){



	        if(i>n)



	            returndownOrUp;



	        printFoldPaper(i+1,n,true);



	        if(isDownOrUp)



	            downOrUp.push_back("down");



	        else



	            downOrUp.push_back("up");



	        printFoldPaper(i+1,n,false);



	        returndownOrUp;



	    }



	    vector<string> foldPaper(intn) {



	        // write code here



	        returnprintFoldPaper(1,n,true);



	         



	    }



	private:



	    vector<string> downOrUp;



	};

发表于 2015-09-12 10:10:36 回复(0)

Python

TimeMac

Python简单解法：（非递归）（需要有可变数组实现）
折n次为n-1次的折痕结果中左右依次插入‘down’和‘up’
例如：
n=1：['down']
n=2：['down', 'down', 'up']
n=3：['down', 'down', 'up', 'down', 'down', 'up', 'up']
从前往后插缝隙就是先插‘down’，下一个插‘up’
我是从后往前插入缝隙就是先插‘up’，后插入‘down’

class FoldPaper:
    def foldPaper(self, n):
        result = ['down']
        for i in range(n-1):
            for j in range(len(result),-1,-1):
                if j & 1:
                    result.insert(j,'up')
                else:
                    result.insert(j,'down')
        return result

编辑于 2018-10-14 23:41:27 回复(0)

Angelべ天行

import java.util.*;

public class FoldPaper {
ArrayList<String>res = new ArrayList<>();
public String[] foldPaper(int n) {
FoldPaper1(n,"down");
String []result =res.toArray(new String [res.size()]);
return result;
}
/*
*递归函数，怎么写，需要什么参数？
*终止条件层数 n==0
*递归状态 if 他不是最底层，就先插入左节点，然后是自己，然后是右节点
*输入参数层数n，和状态，左边就是"down"，右边就是"up"，顶层也是"down"
*/
public void FoldPaper1(int n,String style){
if(n==0){
return ;
}
FoldPaper1(n-1,"down");
res.add(style);
FoldPaper1(n-1,"up");
}
}

发表于 2018-03-29 12:35:57 回复(0)

_恰同学少年

 public static String[] foldPaper(int n) {
        int length = (1<<n) - 1 ;
        int middle = length / 2;
        String[] result = new String[length];
        if(n == 1){
            result[0] = "down";
            return result;
        }else{
            result[0] = "down";
            for(int i=1;i<=middle;i=i*2+1){
                result[i] = "down";
                for(int j=i-1;j>=0;j--){
                    int k = i-j;
                    if(result[j].equals("down")){
                        result[i+k] = "up";
                    }else{
                        result[i+k] = "down";
                    }
                }
            }
            return result;
        }

可以先折四下找出规律

1: down

2：down down up

3: down down up down down up up

4: down down up down down up up down down down up up down up up

可以找出的规律：

折痕数为折的次数的2次方-1，所以算出length=(1<<n)-1;

多折一次，最中间的折痕永远是down,且字符串数组关于中间折痕永远轴对称相反，比如以折2次为例，折痕处为down最中间的一个，然后两边位置互反。

编程时先将每次中间折痕的下标元素赋值为down,然后将中间游标值往左移以为，在对称轴做对称赋值即可

发表于 2017-09-28 10:27:16 回复(1)

BrainerGao


	classFoldPaper {



	public:



	    vector<string> printprocess(inti,intn,bool down){



	        if(i>n)



	            returnDownUpString;  



	        printprocess(i+1,n,true);         



	        if(down)



	            DownUpString.push_back("down");



	        else             



	            DownUpString.push_back("up");         



	        printprocess(i+1,n,false);         



	        returnDownUpString;



	    }



	    vector<string> foldPaper(intn) {



	        // write code here



	        returnprintprocess(1,n,true);



	    }



	private:



	    vector<string> DownUpString;



	};

编辑于 2017-01-15 16:54:49 回复(0)

fingthinking

构造一颗完全二叉树：

import java.util.*;

public class FoldPaper {
    public String[] foldPaper(int n) {
        // write code here
        List<String> list = new LinkedList<String>();
        fold(n,list,"down");
        String[] strs = new String[(int) (Math.pow(2,n)-1)];
        return list.toArray(strs);
    }

    public static void fold(int n, List<String> list,String str){
        if(n != 0){
            fold(n-1,list,"down");
            list.add(str);
            fold(n-1,list,"up");
        }
    }
}

发表于 2016-09-30 12:32:49 回复(1)

petersun

class FoldPaper:
    def foldPaper(self, n):
        return self.foldPapers(n,True)
    
    def foldPapers(self,n,down):
        if n==1:
            return self.foldOnce(down)
        return self.foldPapers(n-1,True) \
        + self.foldOnce(down) + self.foldPapers(n-1,False)
        
    def foldOnce(self,down):
        if down:
            return ["down"]
        else:
            return ["up"]

n=1对应最后一次对折出现的折痕，n=n对应第一次对折位置在最中间的折痕

down

down up

down up down up

down up down up down up down up

编辑于 2015-09-17 14:16:56 回复(0)

D.ony

简单起见，假设下用d来表示，上用u来表示。

首先，第一次折叠后，序列是d。

第二次折叠后，序列是ddu。

第三次折叠后，序列是ddudduu。

经过分析发现，每次的序列，是在前一次的每个间隔中，以dudu。。。的顺序插入的。

比如：第一次的是d，它有左右两个空位，分别插入d u后就变为了ddu。

第二次是ddu，从第一个d左边到第三个位置的u右边，共有四个空位，分别插入dudu后，结果是ddudduu

递归函数如下：

recursion(n)

{

if n == 1

return d

else

a = recursion(n-1)

for i = 1 to (2^n - 1)

if i % 4 == 1

b[i] = 'd'

else if i % 4 == 3

b[i] = 'u'

else

b[i] = a[i/2]

return b[2^n - 1]

}

有不对的地方欢迎批评指正，谢谢。

发表于 2015-09-09 10:01:30 回复(0)

鹤舞青春1002

给一个很长很窄的纸条，把纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开，此时折痕是凹下去的，也就是突起的方向指向纸条的下方；
如果从纸条的下边向上方对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是：下折痕、下折痕、上折痕；
如果纸条每次都从下边向上方对折，在对折n次之后展开。此时所有折痕突起的方向是什么样的呢？
请写一个函数，输入一个整数代表纸条的对折次数记为fTimes，从上到下依次打印所有折痕的突起方向。
例如：
fTimes = 1
打印：down
fTimes = 2
打印：down down up

提示：折痕其实是二叉树结构。该二叉树的特点是：根节点是下，每一个节点的左节点是下，右节点是上。该二叉树的中序遍历即为答案，但不需要构造一颗二叉树，用递归方法可打印出来。

[cpp] view plain copy

void printupdown_core( int index, int num, bool Isdown)
{
if (index==num)
return ;
printupdown_core(index+1,num,true );
if (Isdown)
cout<<"down\t" ;
else
cout<<"up\t" ;
printupdown_core(index+1,num,false );
}
//左节点是“下”，右节点是“上”
void printupdown( int num)
{
if (num<=0)
return ;
printupdown_core(1,num,true );
cout<<"down\t" ;
printupdown_core(1,num,false );
}

发表于 2015-12-23 20:45:00 回复(3)

Radio--active


	classFoldPaper {



	public:



	    vector<string> foldPaper(intn) {



	        // write code here



	        vector<string> v;



	        pushs(v,n,"down");



	        returnv;



	    }



	    voidpushs(vector<string> &v,intn,string s){



	        if(n>0){



	            pushs(v,n-1,"down");



	            v.push_back(s);



	            pushs(v,n-1,"up");



	        }



	    }



	};

发表于 2015-12-12 23:07:45 回复(2)

牛客270206号


	
	
		n = 1, size = 1： "down",
	

	
		n = 2, size = 3:  "down", "down", "up"
	

	
		n = 3, size = 7:  "down", "down", "up", "down", "down", "up", "up"
	

	
		
	

	
		可以观察到每次迭代的时候，数组的新size是2*size+1. 前面的部分并没有改变，最中间的值永远是"down",后半部分直接把前面的值翻转一下就可以得到。
	

	
		
	

	
		class FoldPaper
	

	
		{
	

	
		    public string[] foldPaper(intn)
	

	
		    {
	

	
		        // write code here
	

	
		        int length = (2<< n-1) -1;
	

	
		        string[] result = new string[length]; 
	

	
		        int size =1;
	

	
		        result[0] = "down";
	

	
		        for(int i =2; i <= n; i++) {
	

	
		            result[size] = "down";
	

	
		            for(int j = size+1; j < 2* size +1; j++) {
	

	
		                result[j] = result[2* size - j] =="down"?"up":"down";
	

	
		            }
	

	
		            size =2* size +1;
	

	
		        }
	

	
		        return result;
	

	
		    }
	

	
		}

编辑于 2016-02-21 09:41:28 回复(2)

爱吃青菜皮卷面的byr

import java.util.*;

public class FoldPaper {
    private ArrayList<String>res = new ArrayList<>();
    public String[] foldPaper(int n) {
        // write code here
        printProcesses(1,n,true);
        String []str= res.toArray(new String[]{});
        return str;
    }

    public void printProcesses(int n, int N ,boolean down){
        if (n>N){
            return;
        }
        printProcesses(n+1,N,true);
        res.add(down?"down":"up");
        printProcesses(n+1,N,false);
    }

/*    public static void main(String[] args) {
        String[]res = new FoldPaper().foldPaper(3);
        for (String s:res){
            System.out.println(s);
        }
    }*/

}

考察的是二叉树的中序遍历，可以试着折两下子，发现每一次折都会在最新的折痕上下位置出现两个新的折痕，一上一下，上为down，下为up。打印的时候，从上往下打印，类似于二叉树的中序遍历。

编辑于 2018-03-16 11:34:23 回复(1)

京小木

public String[] foldPaper(int n) {
		// write code here
		int length = 1;
		for (int i = 0; i < n; i++) {
			length = 2 * length;
		}
		length = length - 1;// 计算折痕数为2^n-1
		String[] fold = new String[length];  if (n == 1) {
			fold[0] = "down";// 只有一个折痕时
			return fold;
		} else if (n > 1) {
			fold[0] = "down";
			for (int j = 1; j <= (length / 2); j = (j * 2) + 1) {
				fold[j] = "down";// 每次第(length+1)/2个折痕都为"down",并根据该折痕为中心点两侧相对
				for (int k = j; k > 0; k--) {
					if (fold[j - k].equals("down")) {
						fold[j + k] = "up";
					} else {
						fold[j + k] = "down";
					}
				}
			}
			return fold;
		} else {
			return null;
	}
  }

编辑于 2016-03-15 23:16:47 回复(2)

Java

伊翁迪杰斯

递归中序遍历
import java.util.*;

public class FoldPaper {
    public String[] foldPaper(int n) {
        
        List<String> list = new LinkedList<String>();
        listProcess(1,n,true,list);
        int len = (2<< n-1) -1;
        String[] strs = new String[len];
        for(int i=0; i<len; i++){
            strs[i] = list.get(i);
        }
        
        return strs;
    }
    
    public void listProcess(int i, int n, boolean isDown, List<String> list){
        if(i>n){
            return;
        }
        listProcess(i+1,n,true,list);
        list.add(isDown?"down":"up");
        listProcess(i+1,n,false,list);
    }
}

发表于 2017-08-02 09:04:42 回复(0)

尼见

我用的是二叉树的中序遍历做的，但是测试用例10通不过，郁闷

import java.util.*;

public class FoldPaper {

public static void main(String[]args){

foldPaper(6);

}

private static List<String> list = new ArrayList<>();

public static String[] foldPaper(int n) {

Node root = createTree(0, n);

InOrder(root);

int size = (int) Math.pow(2, n) - 1;

String[] result = new String[size];

for (int i = 0; i < size; i++) {

result[i] = list.get(i);

}

return result;

// write code here

}

private static void InOrder(Node node) {

if (node != null) {

InOrder(node.left);

String param;

if (node.data == 0) {

param = "down";

} else {

param = "up";

}

System.out.println(param);

list.add(param);

InOrder(node.right);

} else {

return;

}

private static Node createTree(int value, int num) {

Node node = new Node(value);

if (num > 1) {

node.left = createTree(0, num - 1);

node.right = createTree(1, num - 1);

}

return node;

}

private static class Node {

public Node(int value) {

this.data = value;

}

int data;

Node left;

Node right;

}

发表于 2016-04-14 15:38:28 回复(1)

xbreak

Solution with Java:

public class FoldPaper {

    public String[] foldPaper(int n) {
        if(n <= 0)
            return new String[]{};
        inOrder(n, "down");
        String [] ss = new String[list.size()];
        list.toArray(ss);
        ss[ss.length/2] = "down";   //root node is down
        return ss;
    }
   List<String> list = new ArrayList<String>();
    public void inOrder(int n, String str){
        if(n == 0)
            return ;
        inOrder(n-1, "down");
        list.add(str);
        inOrder(n-1, "up");
    }
}

发表于 2017-08-28 09:27:41 回复(0)

Java

不许对我狗叫丶

想请教一下各位，实在不知道自己这个错在哪里了，在牛客刷题比较少，实际输出不能看到全部？根据正确的代码作为对数器和这个比较，也暂时没发现什么问题，还请各位赐教

import java.util.*;

public class FoldPaper {
    public String[] foldPaper(int n) {
        if (n == 0) return new String[0];
        // write code here
        //就是个中序遍历

        Queue<Node> queue = new LinkedList();
        Node root = new Node("down");
        queue.add(root);
        int height = 1;
                //这里是在用层序遍历建二叉树
        while (true) {
            int num = queue.size();

            while (num > 0) {
                Node cur = queue.poll();
                cur.left = new Node("down");
                queue.add(cur.left);

                cur.right = new Node("up");
                queue.add(cur.right);

                num--;
            }
                        //高度等于n说明建树完毕
            if (++height == n) {
                break;
            }
        }
                //用逗号分隔得到数组
        return inOrder(root).split(",");

    }

    static StringBuilder path = new StringBuilder();
        中序遍历拼接结果，用逗号做分割
    public String inOrder(Node root) {
        if (root == null) return "";
        inOrder(root.left);
        path.append(root.val+",");
        inOrder(root.right);
        return path.toString();
    }
}

class Node {
    String val;
    Node right;
    Node left;
    public Node (String val) {
        this.val = val;
    }
}

编辑于 2022-06-06 18:59:11 回复(0)