[已解决]今日一题

永恒的蓝色梦想

描述：
给定 N 个 1 位数字。对于所有 X <= N，用其中任意 X 个数字都可以组合成 1 个 X 位的数字。要求所有可能组合出来的 X 位数字的和。例如给定 2、5、8，则可以组合出：2、5、8、25、28、52、58、82、85、258、285、528、582、825、852，它们的和为 3675。

输入格式：
在一行中给出 N 个可能重复的 1 位数字，以空格分隔。保证 N > 0 。

输出格式：
所有可能组合出来的 X 位数字的和。

要求：
禁止使用暴力解法。

---

本题灵感来自于 https://fishc.com.cn/forum.php?mod=viewthread&tid=176899 。

最佳答案

月排行榜 / 总排行榜

March2615

2020-8-6 10:59:55

LZXXXXX 发表于 2020-8-9 12:13
刚学编程，当习题练练手了，暴力不暴力的我就不懂了
以2 5 8为例，思路是用排列数公式分别算三位 ...

兄弟思路差不多，但这个思路有个致命问题：如何判断0不在第一位

附上我的代码，当时我就想到这个问题才把我的回复给编辑了

1. from math import factorial
   
2. 
   
3. nums = tuple(ord(i) - 48 for i in input().split())
   
4. basic = sum(nums)
   
5. n, digit = len(nums), 0
   
6. result = [0]
   
7. while digit < n:
   
8.     temp = result[-1] * (n - digit)
   
9.     temp += basic * pow(10, digit) * factorial(n - 1) // factorial(n - digit - 1)
   
10.     result.append(temp)
    
11.     digit += 1
    
12. print(result)
    
13. print(sum(result))

复制代码

跳转到最佳答案楼层

March2615

LZXXXXX 发表于 2020-8-9 12:13
刚学编程，当习题练练手了，暴力不暴力的我就不懂了
以2 5 8为例，思路是用排列数公式分别算三位 ...

兄弟思路差不多，但这个思路有个致命问题：如何判断0不在第一位

附上我的代码，当时我就想到这个问题才把我的回复给编辑了

1. from math import factorial
   
2. 
   
3. nums = tuple(ord(i) - 48 for i in input().split())
   
4. basic = sum(nums)
   
5. n, digit = len(nums), 0
   
6. result = [0]
   
7. while digit < n:
   
8.     temp = result[-1] * (n - digit)
   
9.     temp += basic * pow(10, digit) * factorial(n - 1) // factorial(n - digit - 1)
   
10.     result.append(temp)
    
11.     digit += 1
    
12. print(result)
    
13. print(sum(result))

复制代码

永恒的蓝色梦想

暴力程序：

1. from itertools import chain, permutations
   
2. 
   
3. 
   
4. def parse(tup, /) -> int:
   
5.     result = 0
   
6. 
   
7.     for i in tup:
   
8.         result = result * 10 + i
   
9. 
   
10.     return result
    
11. 
    
12. 
    
13. nums = tuple(ord(i) - 48 for i in input().split())
    
14. 
    
15. print(sum(set(map(parse, chain.from_iterable(permutations(nums, length) for length in range(len(nums), 0, -1))))))

复制代码

陈尚涵

永恒的蓝色梦想 发表于 2020-8-6 11:34
暴力程序：

我还真不会

但是我发现你用的是3.8

永恒的蓝色梦想

陈尚涵 发表于 2020-8-6 16:15
我还真不会

但是我发现你用的是3.8

哦？怎么发现的？

陈尚涵

永恒的蓝色梦想 发表于 2020-8-6 17:23
哦？怎么发现的？

就凭这段代码：

1. def parse(tup, /) -> int:

复制代码

我可是知道3.8加的新特性

永恒的蓝色梦想

陈尚涵 发表于 2020-8-6 17:25
就凭这段代码：

噢，确实是

陈尚涵

永恒的蓝色梦想 发表于 2020-8-6 17:26
噢，确实是

你还不知道Python3.8函数末尾加"/"的意思是必须传参数

陈尚涵

永恒的蓝色梦想 发表于 2020-8-6 17:26
噢，确实是

我好像说错了什么

陈尚涵

永恒的蓝色梦想 发表于 2020-8-6 17:26
噢，确实是

不是，Python3.8加反斜杠没有用，配合*才有用，只不过是一种习惯

永恒的蓝色梦想

陈尚涵 发表于 2020-8-6 17:27
你还不知道Python3.8函数末尾加"/"的意思是必须传参数

我又不傻，而且不懂不要瞎说好吧：
https://www.zhihu.com/question/287097169/answer/637396902

永恒的蓝色梦想

陈尚涵 发表于 2020-8-6 17:31
不是，Python3.8加反斜杠没有用，配合*才有用，只不过是一种习惯

请不要胡说。

1. >>> def a(arg):
   
2.     return arg
   
3. 
   
4. >>> a(6)
   
5. 6
   
6. >>> a(arg=6)
   
7. 6
   
8. >>> def b(arg, /):
   
9.     return arg
   
10. 
    
11. >>> b(6)
    
12. 6
    
13. >>> b(arg=6)
    
14. Traceback (most recent call last):
    
15.   File "<pyshell#7>", line 1, in <module>
    
16.     b(arg=6)
    
17. TypeError: b() got some positional-only arguments passed as keyword arguments: 'arg'

复制代码

陈尚涵

永恒的蓝色梦想 发表于 2020-8-6 17:32
我又不傻，而且不懂不要瞎说好吧：
https://www.zhihu.com/question/287097169/answer/637396902

貌似有点健忘学习到了

陈尚涵

一天了貌似没人

March2615

太菜了，想知道答案

永恒的蓝色梦想

March2615 发表于 2020-8-7 15:09
太菜了，想知道答案

我发的求助帖啊我就是来求助的

超过光速c

永恒的蓝色梦想 发表于 2020-8-6 17:32
我又不傻，而且不懂不要瞎说好吧：
https://www.zhihu.com/question/287097169/answer/637396902

故意想要和大佬搭讪

永恒的蓝色梦想

超过光速c 发表于 2020-8-8 17:02
故意想要和大佬搭讪

……企业级理解

BSOD

1. import copy
   
2. 
   
3. 
   
4. def cartesian_product(test_list):
   
5.     r = len(test_list)
   
6.     trip_str = "!"
   
7.     test_list_str = [str(i) for i in test_list] + [trip_str] * (r - 1)
   
8.     pools = [tuple(test_list_str)] * r
   
9.     result = [[]]
   
10.     for pool in pools:
    
11.         pre_result = copy.deepcopy(result)
    
12.         result.clear()
    
13.         for x in pre_result:
    
14.             for y in pool:
    
15.                 if x.count(y) < test_list_str.count(y):
    
16.                     result.append(x + [y])
    
17.     for prod in result:
    
18.         prod_str = "".join(prod).strip(trip_str)
    
19.         if trip_str not in prod_str:
    
20.             yield prod_str
    
21. 
    
22. 
    
23. nums = tuple(ord(i) - 48 for i in input().split())
    
24. print(sum(set([int(s) for s in cartesian_product(nums) if s])))

复制代码

经过测试应该没有问题

xgqfrms

https://fishc.com.cn/forum-365-1.html