算法竞赛入门第七章(1)：暴力枚举

例题1 :此题比较简单,先写一个10取5的排列函数,然后进行进行查表。当然如果解约空间就可以直接循环加判定字母是否重复来解。

def create(m,obj = list(range(10))): def remove_2(x,L): L = L[::] L.remove(x) return L ans = [] if m==0:return [0] for i in obj: ans_tmp = create(m-1,remove_2(i,obj)) for each in ans_tmp: ans.append(i*10**(m-1)+each) return ans def proc(): obj = set(create(5)) n = int(input()) for i in obj: if i*n in obj:print('{0}/{1}={2}'.format(str(i*n).zfill(5),str(i).zfill(5),n)) proc()

例题2：此题当然可以直接枚举,但是更加简单的办法是采用累加数组这个概念(在编程珠玑里面重点介绍),然后 S[i+1，j]=S[j]S[i] ，我们只需要找到S[0]到S[j-1]里面的最小值即可。这样以O(N)的复杂度就解决问题。

(a): 注意一个细节,当累乘的值等于0时要将所有的值都重新初始化一遍,这是因为如果我们无法计算乘上0再除以0的结果。所以一旦某个值为0,那么就应该从头开始。

def proc(): n = int(input()) S = [1]+[float(x) for x in input().split()] min_p,min_n = 1,1 M,ans = 1,0 for i in range(1,n+1): M *= S[i] if M==0:M,min_p,min_n=1,1,1;continue ans_tmp = max(M/min_p,M/min_n) ans = max(ans,ans_tmp) if M>0:min_p = min(min_p,M) elif M<0:min_n = max(min_n,M) return ans

例题3 :经过简单的分析计算,可以发现 k+1≤y≤2k ，那么只要在这个基础之上进行枚举就可以了。

def fractions(): k = int(input()) for y in range(k+1,2*k+1): x = (k*y)//(y-k) if x*y==k*(x+y):print('1/{0} = \ 1/{1} + 1/{2}'.format(k,x,y)) fractions()