問(wèn)題描述
100 可以表示為帶分?jǐn)?shù)的形式：100 = 3 + 69258 / 714坛善。
還可以表示為：100 = 82 + 3546 / 197澎媒。
注意特征：帶分?jǐn)?shù)中搞乏，數(shù)字1~9分別出現(xiàn)且只出現(xiàn)一次（不包含0）。
類似這樣的帶分?jǐn)?shù)戒努，100 有 11 種表示法请敦。
輸入格式
從標(biāo)準(zhǔn)輸入讀入一個(gè)正整數(shù)N (N<1000*1000)
輸出格式
程序輸出該數(shù)字用數(shù)碼1~9不重復(fù)不遺漏地組成帶分?jǐn)?shù)表示的全部種數(shù)。
注意：不要求輸出每個(gè)表示储玫，只統(tǒng)計(jì)有多少表示法侍筛！
樣例輸入1
100
樣例輸出1
11
樣例輸入2
105
樣例輸出2
6
思路
這里的拆分形式可以表達(dá)為：N=A+B/C
而A、B撒穷、C中匣椰，1~9的數(shù)字在這三個(gè)數(shù)中匯總起來(lái)只會(huì)出現(xiàn)一次
注意是1~9出現(xiàn)且僅出現(xiàn)一次！６死瘛禽笑！
A、B蛤奥、C之間是有關(guān)系的
- 對(duì)A而言他是一個(gè)在1N-1（因?yàn)槭?9而不是0~9）之間的數(shù)
- B可以改寫為(N-A)*C
- B是可以整除C的
- B是可以整除(N-A)的
- 1~9在他們之中出現(xiàn)且僅出現(xiàn)一次
- 注意ABC中不能有重復(fù)數(shù)字
那么可以先遍歷A佳镜，得到一個(gè)數(shù)字M=N-A
比如說(shuō)
N=100，遍歷到A=3凡桥，那么M=97
B=M*C蟀伸，即B=97*C
此時(shí)A是一位數(shù)字3，那么其他8位數(shù)字是可能出現(xiàn)在B和C之中，B又需要大于C啊掏，所以B的位數(shù)應(yīng)該大于等于C蠢络，那么B至少應(yīng)該是4位數(shù)字，反過(guò)來(lái)說(shuō)C至多是4位數(shù)字
那么我們用B的所有排列迟蜜，利用排列8個(gè)中選4個(gè)谢肾，8個(gè)中選5個(gè)，8個(gè)中選6個(gè)小泉，8個(gè)中選7個(gè)，得到所有B的可能冕杠，此時(shí)B是可以整除C得到97的微姊，那么反過(guò)來(lái)B可以整除97得到C的，那么首先判斷B的候選數(shù)是否可以整除M(在這里是97)分预，如果可以兢交，那么相除得到C，判斷得到的C是否出現(xiàn)和B或者和A相同的數(shù)字笼痹，如果沒(méi)有配喳，那么這一組數(shù)字便是需要的A、B凳干、C晴裹，否則繼續(xù)遍歷
實(shí)現(xiàn)
遍歷A從1到N-1，得到M=N-A
計(jì)算A所占的位數(shù)
那么B的位數(shù)是 (9-A所占位數(shù))/2~9-A所占位數(shù)-1
C的位數(shù)是 9-A所占位數(shù)-B所占位數(shù)
遍歷B的值救赐，對(duì)A中剩余未出現(xiàn)的數(shù)字涧团，取B所有可能出現(xiàn)的位數(shù)的排列，判斷B%M==0经磅，如果是泌绣，那么判斷整除得到的C的位數(shù)是否正確，C中的數(shù)字是否與1~9中除了AB出現(xiàn)過(guò)的數(shù)字一一對(duì)應(yīng)预厌，如果一一對(duì)應(yīng)阿迈，那么是一個(gè)可能解，否則繼續(xù)循環(huán)
判斷是否一一對(duì)應(yīng)
可以先轉(zhuǎn)換為集合轧叽，再使用python中的集合方法判斷兩個(gè)集合元素是否相同
排列的實(shí)現(xiàn)
利用遞歸苗沧，取返回從下標(biāo)a到下標(biāo)b的n個(gè)排列，在函數(shù)中炭晒，遍歷將原數(shù)組中下標(biāo)a與下標(biāo)a+i位置的數(shù)調(diào)換崎页，調(diào)用取從下標(biāo)a+1到下標(biāo)b的n-1個(gè)排列，與下標(biāo)a組合腰埂，這樣就可以得到排列
組合的實(shí)現(xiàn)
如果需要得到組合飒焦，依然可以利用遞歸，取返回從下標(biāo)a到下標(biāo)b的n個(gè)組合，在函數(shù)中牺荠，遍歷將原數(shù)組中下標(biāo)a與下標(biāo)a+i位置的數(shù)調(diào)換翁巍，注意這里是調(diào)用取從下標(biāo)a+i+1到下標(biāo)b的n-1個(gè)排列，與下標(biāo)a+i組合休雌，得到組合
Python源代碼（未剪枝灶壶，自然超時(shí)了，只有33分）
import math
N=int(input())
count=0
def get_outset(num_set,standard_set):
# 得到standard列表中num_set沒(méi)有出現(xiàn)的部分
out_set=[]
for i in standard_set:
if(i not in num_set):
out_set.append(i)
return out_set
def judge(perm,M,num_set):
global count
B = int("".join(perm))
if (B % M == 0):
out_set_C = get_outset(str(B), "".join(num_set))
C = list(str(int(B / M)))
flag = 1
if(len(C)==len(out_set_C)):
for alpha in C:
if (alpha not in out_set_C):
flag = 0
break
set_C=set(C)
if(len(C)!=len(set_C)):
flag=0
if (flag == 0):
return
else:
count += 1
def get_permutation(num_set,a,b,num,M):
# 求排列
if(num==0):
# 這里已經(jīng)得到了B對(duì)應(yīng)的排列杈曲，進(jìn)行檢測(cè)
perm=num_set[0:a]
judge(perm,M,num_set)
return
for i in range(a,b):
copy_set=num_set[::]
copy_set[a],copy_set[i]=copy_set[i],copy_set[a] # swap
get_permutation(copy_set,a+1,b,num-1,M)
for A in range(1,N):
M=N-A
if('0' in str(A)):
continue
if(len(str(A))!=len(set(list(str(A))))):
continue
out_set=get_outset(str(A),"123456789")
min_length_B= math.ceil((9-len(str(A)))/2)
max_length_B=9-len(str(A))
for num in range(min_length_B,max_length_B):
get_permutation(out_set,0,len(out_set),num,M)
print(count)
剪枝(66分)慢慢剪
用C的排列驰凛，B=M*C，判斷B的數(shù)字是否符合規(guī)則
import math
N=int(input())
count=0
def get_outset(num_set,standard_set):
# 得到standard列表中num_set沒(méi)有出現(xiàn)的部分
out_set=[]
for i in standard_set:
if(i not in num_set):
out_set.append(i)
return out_set
def judge(perm,M,num_set):
global count
C = int("".join(perm))
B= M * C
if(C>B):
return
out_set_B = get_outset(str(C), "".join(num_set))
flag = 1
if(len(str(B))==len(out_set_B)):
if (len(str(B)) == len(set(list(str(B))))):
for alpha in str(B):
if (alpha not in out_set_B):
flag = 0
break
if (flag == 0):
return
else:
count += 1
def get_permutation(num_set,a,b,num,M):
# 求排列
if(num==0):
# 這里已經(jīng)得到了C對(duì)應(yīng)的排列担扑，進(jìn)行檢測(cè)
perm=num_set[0:a]
judge(perm,M,num_set)
return
for i in range(a,b):
copy_set=num_set[::]
copy_set[a],copy_set[i]=copy_set[i],copy_set[a] # swap
get_permutation(copy_set,a+1,b,num-1,M)
for A in range(1,N):
M=N-A
if('0' in str(A)):
continue
if(len(str(A))!=len(set(list(str(A))))):
continue
out_set=get_outset(str(A),"123456789")
max_length_C= math.ceil((9-len(str(A)))/2)
min_length_C= 1
for num in range(min_length_C,max_length_C):
get_permutation(out_set,0,len(out_set),num,M)
print(count)
