降低以下代码复杂度n=int(input().strip()) def fun(n): if n==1 or n==2: return 1 elif n==3: return 2 else: return fun(n-1)+fun(n-3) print(fun(n))
时间: 2024-02-19 11:57:55 浏览: 27
可以使用记忆化搜索来优化这段代码,避免重复计算。具体来说,可以使用一个字典来存储已经计算过的值,避免重复递归。
具体代码如下所示:
```python
n = int(input().strip())
# 利用字典存储已经计算过的值
memo = {}
def fun(n):
if n == 1 or n == 2:
return 1
elif n == 3:
return 2
# 如果已经计算过,直接返回结果
if n in memo:
return memo[n]
# 否则递归计算
result = fun(n - 1) + fun(n - 3)
# 将结果存入字典
memo[n] = result
return result
print(fun(n))
```
使用记忆化搜索后,代码的复杂度将大大降低。
相关问题
计算出 1到 n 之间所有数的因子求和的值,n <= 1e14.C++代码
以下是C++代码实现:
```c++
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n; // 题目中的 n
LL get_sum_of_divisors(LL x) {
LL res = 0;
for (LL i = 1; i <= sqrt(x); i++) {
if (x % i == 0) {
res += i;
if (i != x / i) {
res += x / i;
}
}
}
return res;
}
int main() {
scanf("%lld", &n);
LL res = 0;
for (LL i = 1; i <= sqrt(n); i++) {
if (n % i == 0) {
res += i * get_sum_of_divisors(n / i);
if (i != n / i) {
res += (n / i) * get_sum_of_divisors(i);
}
}
}
printf("%lld\n", res);
return 0;
}
```
算法思路:
首先,我们可以把 $1$ 到 $n$ 的所有数分解质因数,然后根据每个数分解出的质因数求出它的因子,并对因子求和。
但是这个算法时间复杂度为 $O(n \log n)$,显然无法通过此题。
我们可以优化这个算法,对于每个数 $x$,我们可以枚举它的因子 $i$,然后 $x/i$ 也是它的因子之一,所以可以直接在枚举因子的同时计算它的因子之和,时间复杂度为 $O(\sqrt{n} \log n)$,可以通过此题。
n=input() p=n.lower() m=input() for i in range(0,len(n)): if "," in n or "+" in n or "-" in n or "." in n: for j in range(0,len(m)): if m[j:j+1:1].isupper()==True: m=m.replace(m[j],"") m=m.replace(n[i:i+1:1],"") m=m.replace(p[i:i+1:1],"") print(m)时间优化
可以将时间复杂度优化为 $O(len(n)+len(m))$。
首先,可以将 n 转为小写,然后判断 n 是否包含特殊字符,如果包含,就遍历 m 中的字符,判断是否为大写字母,如果是,就将其去除。这样可以将两层循环合并为一层循环。
其次,可以将字符串转为列表,然后遍历列表,将 n 和 p 中的字符替换为空字符串,最后将剩余的字符拼接为字符串。
优化后的代码如下:
```python
n = input()
p = n.lower()
m = input()
# 判断是否包含特殊字符
if any(c in n for c in ",+-."):
m = ''.join(c for c in m if c.islower() or not c.isupper())
# 将 n 和 p 转为列表,遍历替换
n_list = list(n)
p_list = list(p)
for i in range(len(n_list)):
if n_list[i] in ",+-.":
n_list[i] = p_list[i] = ''
m = ''.join(c for c in m if c not in n_list and c not in p_list)
print(m)
```
这样代码的效率会更高一些。