分页： 1 / 1
#1 来一个编程题吧
发表于 ： 2024年 2月 4日 14:02
由 TheMatrix
这个问题不要求效率的话，在leetcode里也是hard的。
问题的大意是：以质因数分解的形式遍历正整数。
要求这样遍历：以总指数和参与的质数的个数同步增长的方式遍历。
比如考虑20以内的质数：[2, 3, 5, 7, 11, 13, 17, 19]。一共8个。这些是参与的质数的个数。那么总指数小于等于8，可以叫level。
比如：
level=1，有[20,21]，两个。
level=2，有[2030,2130,2031,2131,2230,2032]，共6个。
level=3，有[203050,213050,...]，共...我也不知道多少个。
结果可以列成序列的形式：
(2,0,0,3) - 这代表2273。
能去掉duplicate最好。
#2 Re: 来一个编程题吧
发表于 ： 2024年 2月 4日 20:47
由 YWY
level 1: 20, 21; total number is 2 = 21.
level 2: 2i3j with i, j in {0, 1, 2}; total number is 9 = 32 with duplicates from level 1; removing level 1, there are 32 - 21 numbers.
...
level n: there are (n+1)n numbers, including numbers from lower levels; if we removed the numbers from lower levels, there are (n+1)n - nn-1 numbers.
#3 Re: 来一个编程题吧
发表于 ： 2024年 2月 5日 11:47
由 TheMatrix
YWY 写了： 2024年 2月 4日 20:47
level 1: 2
0, 2
1; total number is 2 = 2
1.
level 2: 2
i3
j with i, j in {0, 1, 2}; total number is 9 = 3
2 with duplicates from level 1; removing level 1, there are 3
2 - 2
1 numbers.
...
level n: there are (n+1)
n numbers, including numbers from lower levels; if we removed the numbers from lower levels, there are (n+1)
n - n
n-1 numbers.
level 2应该是6个。
#4 Re: 来一个编程题吧
发表于 ： 2024年 2月 5日 17:11
由 YWY
TheMatrix 写了： 2024年 2月 5日 11:47
level 2应该是6个。
Level 2: 2
03
0, 2
13
0, 2
23
0, 2
03
1, 2
13
1, 2
23
1, 2
03
2, 2
13
2, 2
23
2. The first 2 numbers, 2
03
0 and 2
13
0, are from level 1.
#5 Re: 来一个编程题吧
发表于 ： 2024年 2月 5日 17:42
由 TheMatrix
YWY 写了： 2024年 2月 5日 17:11
Level 2: 2
03
0, 2
13
0, 2
23
0, 2
03
1, 2
13
1, 2
23
1, 2
03
2, 2
13
2, 2
23
2. The first 2 numbers, 2
03
0 and 2
13
0, are from level 1.
哦。我说的是总指数。指数相加。
#6 Re: 来一个编程题吧
发表于 ： 2024年 2月 5日 21:43
由 YWY
TheMatrix 写了： 2024年 2月 5日 17:42
哦。我说的是总指数。指数相加。
At level n, we need to find the total number of monomials in n variables with total degree up to n. This number is known to be "2n-choose-n". This allows duplicates from lower levels.
Note that each level is contained in the next level (i.e., level i is contained in level i+1). If we remove lower levels from level n, the answer is 2n-choose-n minus (2n-2)-choose-(n-1).
#7 Re: 来一个编程题吧
发表于 ： 2024年 2月 5日 21:58
由 TheMatrix
YWY 写了： 2024年 2月 5日 21:43
At level n, we need to find the total number of monomials in n variables with total degree up to n. This number is known to be "2n-choose-n". This allows duplicates from lower levels.
Note that each level is contained in the next level (i.e., level i is contained in level i+1). If we remove lower levels from level n, the answer is 2n-choose-n minus (2n-2)-choose-(n-1).
这是对的。
怎么证明呢？
#8 Re: 来一个编程题吧
发表于 ： 2024年 2月 5日 22:25
由 YWY
#9 Re: 来一个编程题吧
发表于 ： 2024年 2月 6日 11:44
由 TheMatrix
嗯。这个问题我以前也问过。有人给过方法。nonnegative的更绕一些。
#10 Re: 来一个编程题吧
发表于 ： 2024年 2月 6日 12:56
由 TheMatrix
这是个编程题。我们还是上个程序吧。
这个问题抽象出来之后，没有我想象的难。和素数没有什么关系。主要是个排列组合的问题。
不过用到递归的话，在leetcode里应该都算hard的。
代码： 全选
def level_n(N):
result = [[]]
for nstep in range(N):
nresult = []
for path in result:
s = sum(path)
nresult += [path+[i] for i in range(N-s+1)]
result = nresult
return result
#11 Re: 来一个编程题吧
发表于 ： 2024年 2月 6日 13:04
由 Dahuaidanyimei
抱歉我懒，直接copy 进了 copilot，结果我也没验证：
def prime_factors(n):
factors = []
for i in range(2, int(n**0.5) + 1):
while n % i == 0:
factors.append(i)
n //= i
if n > 1:
factors.append(n)
return factors
def count_prime_factors(n):
factors = prime_factors(n)
unique_factors = set(factors)
return len(unique_factors)
def generate_sequence(limit):
sequence = []
for i in range(1, limit + 1):
total_exponent = count_prime_factors(i)
num_unique_factors = count_prime_factors(total_exponent)
sequence.append((total_exponent, num_unique_factors))
return sequence
# Example usage for 20:
result = generate_sequence(20)
print(result)
#12 Re: 来一个编程题吧
发表于 ： 2024年 2月 6日 15:36
由 TheMatrix
Dahuaidanyimei 写了： 2024年 2月 6日 13:04
抱歉我懒，直接copy 进了 copilot，结果我也没验证：
def prime_factors(n):
factors = []
for i in range(2, int(n**0.5) + 1):
while n % i == 0:
factors.append(i)
n //= i
if n > 1:
factors.append(n)
return factors
def count_prime_factors(n):
factors = prime_factors(n)
unique_factors = set(factors)
return len(unique_factors)
def generate_sequence(limit):
sequence = []
for i in range(1, limit + 1):
total_exponent = count_prime_factors(i)
num_unique_factors = count_prime_factors(total_exponent)
sequence.append((total_exponent, num_unique_factors))
return sequence
# Example usage for 20:
result = generate_sequence(20)
print(result)
能运行 - 调整一下缩进 - 这就不错了。