首页 > 试题广场 >

折纸问题

[编程题]折纸问题
  • 热度指数：3322 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
请把一张纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。此时折痕是凹下去的，即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折2次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。给定一个输入参数N，代表纸条都从下边向上方连续对折N次，请从上到下打印所有折痕的方向。
[要求]
时间复杂度为，额外空间复杂度为

输入描述:
第一行一个整数N。表示对折次数


输出描述:
输出若干行，若该折痕向下，输出"down"，否则输出"up"
示例1

输入

1

输出

down
示例2

输入

2

输出

down
down
up

备注:
算法知识视频讲解
添加回答
Java
牛客617355593号头像 牛客617355593号
import java.util.*;
public class Main{
    
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        printAllFlods(Integer.valueOf(in.nextLine().trim()));
    }
    
    public static void printAllFlods(int fTimes) {
        if(fTimes<1)
            return;
        printProcess(1,fTimes,true);
    }
    public static void printProcess(int index,int n,boolean isDown) {
        if(index==n) {
            System.out.println(isDown?"down":"up");
            return;
        }
        printProcess(index+1,n,true);
        System.out.println(isDown?"down":"up");
        printProcess(index+1,n,false);
    }
}
发表于 2021-11-05 14:04:21 回复(0)
Spectre_头像 Spectre_ 
// 时间复杂度O(2^N)，空间复杂度O(N)

#include<iostream>

using namespace std;

void printProcess(int i, int& n, bool down)
{
    if (i > n) return ;
    printProcess(i + 1, n, true);
    cout << (down ? "down" : "up") << endl;
    printProcess(i + 1, n, false);
}

int main()
{
    int n; cin >> n;
    printProcess(1, n, true);
    return 0;
}

发表于 2019-10-15 22:42:26 回复(0)
C/C++
天命剑主头像 天命剑主
#include <iostream>
#include <cmath>

using namespace std;
//这个解法不符合要求，但是简单
int main() {
    int n;
    cin >> n;
    int size = pow(2, n);
    int a[size];
    int i = 1;
    a[0] = -1;
    int len = 1;
    for (; i < n; i++) {
        a[len] = -1;
        for (int j = 1; j <= len; j++) {
            a[len + j] = -a[len - j];
        }
        len = len * 2 + 1;
    }
    for (int index = 0; index < len; index++) {
        if (a[index] == -1) {
            cout << "down" << endl;
        } else {
            cout << "up" << endl;
        }
    }
    return 0;
}
发表于 2019-10-11 16:22:44 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int n;
void F(int i, bool d){
    if(i>n)
        return ;
    F(i+1, true);
    cout<<(d?"down":"up")<<endl;
    F(i+1, false);
}

int main(){
    cin>>n;
    F(1, true);
    return 0;
}

发表于 2020-03-08 00:16:43 回复(0)
痴心的大师兄喜欢摸鱼头像 痴心的大师兄喜欢摸鱼
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        // 先构建  再中序遍历打印
        dfs(0,N,"down");

    }
    public static void dfs(int curLayers, int layers,String str) {
        if(curLayers >= layers) {
            return;
        }
        // 递归序1
        dfs(curLayers+1, layers, "down" );
        // 递归序2  中序遍历
        System.out.println(str);
        dfs(curLayers+1, layers, "up" );
        // 递归序3
    }
   
}
发表于 2024-07-18 16:09:40 回复(0)
pein531头像 pein531
将对折几次的结果写出来看看就能发现规律。其实就是个根节点为down的满二叉树结构，所有的节点都满足左孩子为down，右孩子为up，对折n次就是输出n层树的中序遍历序列。 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    private static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        dfs(1, true);
    }
    
    private static void dfs(int depth, boolean isLeft) {
        if(depth > n) return;
        dfs(depth + 1, true);
        System.out.println(isLeft? "down": "up");
        dfs(depth + 1, false);
    }
}

编辑于 2021-11-13 22:27:45 回复(0)
牛客60179657号头像 牛客60179657号
import java.util.*;
public class Main{
    public static void main(String[]args){
        Scanner s =new Scanner(System.in);
        int a =s.nextInt();
        int length=(int)Math.pow(2,a)-1;
        String[] result=new String[length];
        int left=0;
        int right=length-1;
        boolean n=true;
        report(result,left,right,n);
        for(int i=0;i<length;i++){
            System.out.println(result[i]);
        }
    }
    public static void report(String[] result,int left,int right,boolean n){
        if(left>right){
            return;
        }
        int mid =(left+right)/2;
        report(result,left,mid-1,true);
        if(n){
            result[mid]="down";
        }else{
            result[mid]="up";
        }
        report(result,mid+1,right,false);
    }
}
发表于 2022-11-17 17:51:16 回复(0)
牛客887263087号头像 牛客887263087号
#include <iostream>
using namespace std;

void InOrderPrint(int i, int N, bool isDown){
    if(i > N)
        return;
    InOrderPrint(i + 1, N, true);
    string s = isDown == true ? "down" : "up";
    cout << s << endl;
    InOrderPrint(i + 1, N, false);
}

int main(void){
    int N;
    cin >> N;
    InOrderPrint(1, N, true);
    return 0;
}
知道是一道二分题，但无从下手的时候
首先把它加框 分成 左子树 + 处理信息 + 右子树
写完后写终止条件
发表于 2021-05-21 10:26:38 回复(0)
明月知何人头像 明月知何人
运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。点击对比用例标准输出与你的输出
case通过率为95.00%
发表于 2020-01-08 17:23:40 回复(0)
谜摆头像 谜摆 
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
void inPrint(vector<bool>& tree,int index)
{
	if (index >= tree.size())return;
	inPrint(tree, index * 2 + 1);
	printf("%s\n", tree[index]?"up":"down");
	inPrint(tree, index * 2 + 2);
}

int main()
{
	int count = 0;
	scanf("%d", &count);
	if (count < 0)
	{
		printf("-1");
		return 0;
	}
	//true为上，false为下
	vector<bool> tree(pow(2, count) - 1, false);
	int endIndex = 0;
	int curIndex = 0;
	while (endIndex < tree.size())
	{
		bool flag = false;
		while (curIndex<=endIndex)
		{
			if (flag)tree[curIndex] = true;
			flag = !flag;
			curIndex++;
		}
		endIndex = 2 * (endIndex + 1);
	}
	inPrint(tree,0);
}

发表于 2019-08-08 18:55:19 回复(0)
提交观点

问题信息

模拟 数学 思维
上传者：小小
难度：
10条回答 5970浏览

热门推荐

通过挑战的用户

查看代码

相关试题

折纸问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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