[算法][排列/剪枝]带分数

带分数

100 可以表示为带分数的形式：100=3+69258/714

还可以表示为：100=82+3546/197

注意特征：带分数中，数字 1∼9分别出现且只出现一次（不包含0）。

类似这样的带分数，100 有 11 种表示法。

输入格式

一个正整数。

输出格式

输出输入数字用数码 1∼9不重复不遗漏地组成带分数表示的全部种数。

数据范围

1≤N<10^6

输入样例1：

100

输出样例1：

11

输入样例2：

105

输出样例2：

6

N = a + b/c

（1~9）进行全排列

分割成a|b|c

a的长度必然小于等于N

遍历 a <= len(N)的部分

如何推导b的末位

每次循环里 N - a的值可以得到，所以现在需要求 b 和 c

因为 N = a + b/c 即 b = (N - a) * c

对于每一个切割好的分组 c的最后一位是确定的

b的末位 = （N - a) * c的末位 % 10 (得到的余数)

e.g. : N=100 a=3 遍历到c[-1]=4

即97*4=388 %10 = 8

即可以推出b的末位

分割排列为 a(前al+1位) b(中间部分) c(剩余部分)

检查b是否被c整除且满足N=a+b/c

from itertools import *
n = int(input())
bit = len(str(n))   # n的位数 
cnt = 0
for num in permutations("123456789"):
    print(num)
    a, b, c = 0, 0, 0
    for al in range(bit):          # al: a的位数，a<=n
        a = int("".join(num[:al+1]))   # 一个a
        bLast = (n - a) * int(num[-1]) % 10  # b的尾数，(n-a)c%10
        if bLast == 0: continue              # b的尾数不可能等于0，因为只用到1~9
        bl = num.index(str(bLast))        # 根据b的尾数，确定b的长度
        if bl <= al or bl >= 8: continue    # b的末位位置不会在a的位数前面，也不会在第8,9位
        b = int("".join(num[al+1:bl+1]))
        c = int("".join(num[bl+1:]))
        if b % c == 0 and n == a + b // c:   # 判断是否符合条件,//:整数除法
            cnt += 1
print(cnt)

灵感来源：带分数-python