来一个编程题吧
版主: verdelite, Tlexander
-
- 论坛支柱
TheMatrix 的博客 - 帖子: 9773
- 注册时间: 2022年 7月 26日 00:35
#1 来一个编程题吧
这个问题不要求效率的话,在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最好。
问题的大意是:以质因数分解的形式遍历正整数。
要求这样遍历:以总指数和参与的质数的个数同步增长的方式遍历。
比如考虑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最好。
-
- 论坛支柱
- 帖子: 9202
- 注册时间: 2022年 7月 22日 17:25
- 昵称(选填): YWY(夜未央)
#2 Re: 来一个编程题吧
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.
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.
持仓抄底锁利,你钱你定
看牛观猪喊熊,自娱自乐
股市变幻莫测,不作不死
赌途曲折无常,吃枣药丸
看牛观猪喊熊,自娱自乐
股市变幻莫测,不作不死
赌途曲折无常,吃枣药丸
-
- 论坛支柱
TheMatrix 的博客 - 帖子: 9773
- 注册时间: 2022年 7月 26日 00:35
#3 Re: 来一个编程题吧
level 2应该是6个。YWY 写了: ↑2024年 2月 4日 20:47 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.
-
- 论坛支柱
- 帖子: 9202
- 注册时间: 2022年 7月 22日 17:25
- 昵称(选填): YWY(夜未央)
#4 Re: 来一个编程题吧
Level 2: 2030, 2130, 2230, 2031, 2131, 2231, 2032, 2132, 2232. The first 2 numbers, 2030 and 2130, are from level 1.
持仓抄底锁利,你钱你定
看牛观猪喊熊,自娱自乐
股市变幻莫测,不作不死
赌途曲折无常,吃枣药丸
看牛观猪喊熊,自娱自乐
股市变幻莫测,不作不死
赌途曲折无常,吃枣药丸
-
- 论坛支柱
TheMatrix 的博客 - 帖子: 9773
- 注册时间: 2022年 7月 26日 00:35
-
- 论坛支柱
- 帖子: 9202
- 注册时间: 2022年 7月 22日 17:25
- 昵称(选填): YWY(夜未央)
#6 Re: 来一个编程题吧
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).
持仓抄底锁利,你钱你定
看牛观猪喊熊,自娱自乐
股市变幻莫测,不作不死
赌途曲折无常,吃枣药丸
看牛观猪喊熊,自娱自乐
股市变幻莫测,不作不死
赌途曲折无常,吃枣药丸
-
- 论坛支柱
TheMatrix 的博客 - 帖子: 9773
- 注册时间: 2022年 7月 26日 00:35
#7 Re: 来一个编程题吧
这是对的。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).
怎么证明呢?
-
- 论坛支柱
- 帖子: 9202
- 注册时间: 2022年 7月 22日 17:25
- 昵称(选填): YWY(夜未央)
#8 Re: 来一个编程题吧
持仓抄底锁利,你钱你定
看牛观猪喊熊,自娱自乐
股市变幻莫测,不作不死
赌途曲折无常,吃枣药丸
看牛观猪喊熊,自娱自乐
股市变幻莫测,不作不死
赌途曲折无常,吃枣药丸
-
- 论坛支柱
TheMatrix 的博客 - 帖子: 9773
- 注册时间: 2022年 7月 26日 00:35
#9 Re: 来一个编程题吧
嗯。这个问题我以前也问过。有人给过方法。nonnegative的更绕一些。YWY 写了: ↑2024年 2月 5日 22:25 https://en.wikipedia.org/wiki/Monomial
https://en.wikipedia.org/wiki/Stars_and ... atorics%29
-
- 论坛支柱
TheMatrix 的博客 - 帖子: 9773
- 注册时间: 2022年 7月 26日 00:35
#10 Re: 来一个编程题吧
这是个编程题。我们还是上个程序吧。
这个问题抽象出来之后,没有我想象的难。和素数没有什么关系。主要是个排列组合的问题。
不过用到递归的话,在leetcode里应该都算hard的。
这个问题抽象出来之后,没有我想象的难。和素数没有什么关系。主要是个排列组合的问题。
不过用到递归的话,在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
-
- 知名作家
- 帖子: 1168
- 注册时间: 2023年 3月 14日 16:18
- 昵称(选填): Badegg
#11 Re: 来一个编程题吧
抱歉我懒,直接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)
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)
-
- 论坛支柱
TheMatrix 的博客 - 帖子: 9773
- 注册时间: 2022年 7月 26日 00:35
#12 Re: 来一个编程题吧
能运行 - 调整一下缩进 - 这就不错了。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)