暴力枚举、全排列

1. 带分数

题目分析：

        假设待求的数 num = a+b/c       

         对于样例1：100 = 3 + 69258 / 714，a = 3, b = 69258,  c = 714

        我们首先对'123456789'进行全排列，然后对于其中的每个全排列进行分段。比如样例中涉及的排列之一：369258714，对其进行分段，3、69258、714，最终判断 3 + 69258 / 714 是否等于目标数 100。也就是说，在不改变某个排列中数字前后顺序的情况下，直接进行分段，划分出来的数字依次视为 a, b, c。

        那么对于符合数 num  = a+b/c 的所有情况：

         1. 首先从第1个数字开始划分，确定 a 可能的值，注意：a 必须小于num，比如样例中的num=100，当排列等于 369258714 时，a可取的值有 a=3,a=36两种情况；

         2.怎样求b的值？已知 num = a+b/c ，那么 b = (num - a) * c，但是！c 的值又是未知的，那怎么办呢？c 具体的值未知，但是 c 的最后一位数字是可知的，就是 某排列数的 最后一位数字，比如 100 = 3 + 69258 / 714，c 的 最后一位数字是 4 。同理，b = (num - a) * c 的个位数 与  (num - a) * c[-1] 的个位数是相同的，这样我们就可以得到 b 的个位数啦！比如 369258714 ，当a = 3 时，(100-3)*714 % 10 = (100-3)*4 % 10 = 8，可知b的个位为 8 ，那么就可以得出 b = 69258，c = 714！

        3.   那么，当num = 100时，对于排列 369258714 来说，a, b, c = 3，69258，714

代码：

from itertools import permutations

n = int(input())
num = 0
for item in permutations('123456789'):
    per = ''.join(item)
    for i in range(1, len(str(n)) + 1):
        a = int(per[:i])
        if a > n:
            continue
        # n = a + b/c  =>  b = (n - a) * c
        # 因为用per的最后部分当c，所以c的个位数我们是已知的per[-1]
        # (n - a) * per[-1] 的个位数与 (n - a) * c 的个位数相同
        # 也就是b的个位数，这样就可以确定b和c之间的间隔在哪
        b_last = (n - a) * int(per[-1]) % 10
        b_last_index = per.find(str(b_last))
        if b_last_index < i or b_last_index == 8:
            continue
        b = int(per[i:b_last_index + 1])
        c = int(per[b_last_index + 1:])
        if a + b / c == n:
            print(per)
            print(a, b, c)
            
            num += 1
print(num)

2. 排列序数

题目描述

如果用 a b c d 这 4 个字母组成一个串，有 4!=24 种，如果把它们排个序，每个串都对应一个序号：

abcd 0

abdc 1

acbd 2

acdb 3

adbc 4

adcb 5

bacd 6

badc 7

bcad 8

bcda 9

bdac 10

bdca 11

cabd 12

cadb 13

cbad 14

cbda 15

cdab 16

cdba 17

⋯⋯

现在有不多于 10 个两两不同的小写字母，给出它们组成的串，你能求出该串在所有排列中的序号吗？

输入描述

输入一行，一个串。

输出描述

输出一行，一个整数，表示该串在其字母所有排列生成的串中的序号。注意：最小的序号是 0。

输入输出样例

示例输入

bdca

 输出

11

代码：

from itertools import permutations
s = input()
s1 = sorted(s)
num = 0
for i in permutations(s1):
  if ''.join(i) == s:
    print(num)
    break
  else:
    num+=1

        注意 sorted() 函数 的使用！

s = input() # input()函数输入的是 str 类型数据，假设 s = 'bdca'
print(type(s)) # <class 'str'>
s.sort() # 报错，AttributeError: 'str' object has no attribute 'sort'
s = list(s) # 直接转为 list 类型,s = ['b', 'd', 'c', 'a']
print(type(s)) # <class 'list'>
s.sort() # 排序, s = ['a', 'b', 'c', 'd']
print(s)
s1 = ''.join(s) # s = 'abcd'
print(type(s1)) # <class 'str'>