首页 > 试题广场 >

折纸问题

[编程题]折纸问题
  • 热度指数：9636 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

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

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

测试样例： 
1
返回：["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头像 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号头像 牛客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头像 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头像 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べ天行头像 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头像 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头像 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头像 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.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头像 鹤舞青春1002

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

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

[cpp] view plaincopy
  1. void  printupdown_core( int  index, int  num, bool  Isdown)  
  2. {  
  3.     if (index==num)  
  4.         return ;  
  5.     printupdown_core(index+1,num,true );  
  6.     if (Isdown)  
  7.             cout<<"down\t" ;  
  8.         else   
  9.             cout<<"up\t" ;  
  10.     printupdown_core(index+1,num,false );  
  11. }  
  12.   
  13. //左节点是“下”，右节点是“上”   
  14. void  printupdown( int  num)  
  15. {  
  16.     if (num<=0)  
  17.         return ;  
  18.     printupdown_core(1,num,true );  
  19.     cout<<"down\t" ;  
  20.     printupdown_core(1,num,false );  
  21. }  
发表于 2015-12-23 20:45:00 回复(3)
Radio--active头像 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号头像 牛客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头像 爱吃青菜皮卷面的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头像 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
一千块头像 一千块
Java 中序遍历解法 
import java.util.*;

public class FoldPaper {
    public String[] foldPaper(int n) {
        // 初始 1 down
        TreeNode root = createTree(n, 1);
        StringBuilder sb = new StringBuilder();
        printTree(root, sb);
        return sb.toString().split(",");
    }

    /**
     * 中序遍历构建二叉树
     *
     * @param k    折纸次数
     * @param flag 1 凸 0 凹
     * @return
     */
    TreeNode createTree(int k, int flag) {
        if (k <= 0) {
            return null;
        }

        TreeNode left = createTree(k - 1, 1);
        TreeNode node = new TreeNode(flag);
        node.left = left;
        TreeNode right = createTree(k - 1, 0);
        node.right = right;

        return node;
    }

    /**
     * 中序遍历打印
     *
     * @param root
     */
    void printTree(TreeNode node, StringBuilder sb) {
        if (node == null) {
            return;
        }

        printTree(node.left, sb);
        sb.append(node.val == 1 ? "down" : "up").append(",");
        printTree(node.right, sb);
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}


编辑于 2025-03-19 10:21:56 回复(0)
提交观点

问题信息

递归
来自：面试常考算法题(一)
难度：
79条回答 29004浏览

热门推荐

通过挑战的用户

查看代码

相关试题

折纸问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号