有没有人会的？（救救我）

常规
1

3. 递归练习1

XJOI - 题目ID：7975100分

最新提交：

Memory Limit Exceeded

0 分

历史最高：

Memory Limit Exceeded

0 分

时间限制: 200ms

空间限制: 32000kB

题目描述

时间：0.2 空间：32M

题目描述：

给定一个正整数n。

设 k 是最小的 2的幂 使得 n/k 的整数部分为 0 ，则输出

[n/k] [n/ (k/2)] … [n/2] [n]

这里中括号的意思是下取整

输入格式：

一个正整数表示 n

输出格式：

一行正整数表示答案。

样例输入1：

5

样例输出1：

0 1 2 5

样例提示：

5/8=0, 5/4=1, 5/2=2, 5/1=5

约定：

1<=n<=10000

谁懂啊，原来A的代码再交一遍就MlE 0了 :smiling_face_with_tear:

2 个赞
2

为什么我能看到递归练习2，就是找不到递归练习1 :thinking:

2 个赞
3

我也是

2 个赞
4

不道啊

2 个赞
5

萌新发问：为什么要用递归
枚举出一个k，复杂度为 log_2 n
再按题目要求输出不就行了吗，整个复杂度不过logn级别的呀
你也可以直接用位移运算符来计算除法，这样甚至连k都省了，还更快，还有为什错误提示是MLE，这里申请的变量理应是常数级别的，也不存在越界的可能性
（刚学c++与算法一个月，勿喷）

2 个赞
6

给你解释一下递归比for和while的好处：递归可以无限调用自己，到一个边界后可以退回到上一个点枚举另一种情况（大佬勿喷）
不过这题我也不知道为什么要用递归 :slightly_smiling_face:

3 个赞
7

救救我啊！递归练习2的AC代码也MLE 0了…… :sob:

3 个赞
8

递归练习而
ACcode

#include<bits/stdc++.h>
using namespace std;
void f(int n){
	if(n==1){
		cout<<1<<" ";
	}
	else{
		f(n/2);
		cout<<n<<" ";
		f(n-n/2);
	}
}
int main(){
	int n;
	cin>>n;
	f(n);
	return 0;
}
3 个赞
9 
#include <iostream>

int main(int argc , char** argv)
{
	int n;
	std::cin >> n;
	
	int k;
	for (k=1; (n/k > 0); k *= 2);
	
	for (; k >= 1; k /= 2)
	{
		std::cout << (n / k) << " ";
	}
	
	return 0;
}

思路我已经发了
更快的有位移运算，直接右移，但是还是得看初始的i值（位移i位），时间复杂度依然logn

2 个赞
10

ok

1 个赞
11

所以，递归练习一有没有会的？

1 个赞
12

不是发你了吗？

2 个赞
13

练习1？

1 个赞
14

我发的代码对应的就是你发的问题啊

2 个赞