[已解决]今日一题

永恒的蓝色梦想

描述：
给定 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不在第一位

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

from math import factorial

nums = tuple(ord(i) - 48 for i in input().split())
basic = sum(nums)
n, digit = len(nums), 0
result = [0]
while digit < n:
    temp = result[-1] * (n - digit)
    temp += basic * pow(10, digit) * factorial(n - 1) // factorial(n - digit - 1)
    result.append(temp)
    digit += 1
print(result)
print(sum(result))

跳转到最佳答案楼层

March2615

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

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

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

from math import factorial

nums = tuple(ord(i) - 48 for i in input().split())
basic = sum(nums)
n, digit = len(nums), 0
result = [0]
while digit < n:
    temp = result[-1] * (n - digit)
    temp += basic * pow(10, digit) * factorial(n - 1) // factorial(n - digit - 1)
    result.append(temp)
    digit += 1
print(result)
print(sum(result))

永恒的蓝色梦想

暴力程序：

from itertools import chain, permutations


def parse(tup, /) -> int:
    result = 0

    for i in tup:
        result = result * 10 + i

    return result


nums = tuple(ord(i) - 48 for i in input().split())

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
哦？怎么发现的？

就凭这段代码：

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加反斜杠没有用，配合*才有用，只不过是一种习惯

请不要胡说。

>>> def a(arg):
    return arg

>>> a(6)
6
>>> a(arg=6)
6
>>> def b(arg, /):
    return arg

>>> b(6)
6
>>> b(arg=6)
Traceback (most recent call last):
  File "<pyshell#7>", line 1, in <module>
    b(arg=6)
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

import copy


def cartesian_product(test_list):
    r = len(test_list)
    trip_str = "!"
    test_list_str = [str(i) for i in test_list] + [trip_str] * (r - 1)
    pools = [tuple(test_list_str)] * r
    result = [[]]
    for pool in pools:
        pre_result = copy.deepcopy(result)
        result.clear()
        for x in pre_result:
            for y in pool:
                if x.count(y) < test_list_str.count(y):
                    result.append(x + [y])
    for prod in result:
        prod_str = "".join(prod).strip(trip_str)
        if trip_str not in prod_str:
            yield prod_str


nums = tuple(ord(i) - 48 for i in input().split())
print(sum(set([int(s) for s in cartesian_product(nums) if s])))

经过测试应该没有问题

xgqfrms

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