- 论坛徽章:
- 11
|
前面那个题目,原理好像都很简单,实现起来细节就不一般的麻烦了
目前用python实现了,在n<=100000的范围内做过全量测试的,算n,k的位置的(可以翻译为C++代码,这会比较麻烦点,用stl会好点)
另外一个问题,求位置K对应的数是,应该如何构造?
--附件:
class nw:
"""数的权值和位置 Number Weight """
res_f = None
@staticmethod
def n2da(num):
"""数 转换到 数位数组: 12345 => [1,2,3,4,5]"""
return map(int, str(num))
@staticmethod
def da2n(dig_arr):
"""数位数组 转换到 数: [2,0,1,2] => 2012"""
return int(''.join(map(str, dig_arr)))
@staticmethod
def da_len(num):
"""长度位数,也就是数位数组的元素个数"""
return len(nw.n2da(num))
@staticmethod
def nval(num,n):
"""第N位数字,从左到右 1,2...，也就是数位数组的第n-1个元素"""
assert(1 <= n <= nw.da_len(num))
return nw.n2da(num)[n-1]
@staticmethod
def nsum(num,n):
"""num的前n位数字之和,从左到右 1,2...，也就是数位数组的第n-1个元素之和"""
assert(1 <= n <= nw.da_len(num))
return sum(nw.n2da(num)[:n])
@staticmethod
def weight(num):
"""权重，也就是数位数组的元素之和"""
return sum(nw.n2da(num))
@staticmethod
def less(x,y):
"""小于"""
wx,wy = map(nw.weight, [x,y])
if wx < wy:
return True
if wx > wy:
return False
return str(x) < str(y)
#
@staticmethod
def lw2c(length, weight):
"""数位长度为 length, 权重为 weight,的数字，总共有多少个？
限制 length <= 19, weight<=163
"""
# len(str(10**1 )=19 w(int('1'+'9'*1)= 163
if nw.res_f is None:
#最长支持19位,权重最大163的数组
nw.res_f = [[0]*163 for i in range(19)]
res = nw.res_f
# w=0 1 2 3 ... 9 10 11 ... 163
# l= 1 1 1 1 1 ... 1 0 0 ... 0
# 2 0 1
# 3 0
# ...
# 19 0
# f(0 ,0) = 1
# f(l, 0) = 0 权重为0的没有
# f(0, w) = 0
# 下面动态规划
# 对于长度l,权重w的数字，为f(l,w), 应该求和:
# f(l-i, w-j) j=1...9, i=1,l
# i f(l-1,w-j) i=1时,由1到9为第一位 加上 长度为l-1位序列的所有元素拼起来
# i 0 f(l-2,w-j) i=2时,中间空一格0
# i 0 0 f(l-3,w-j)
# i 0 0 0 f(l-4,w-j)
# i 0 0 ...0 f( 1,w-j) l-(l-1)
# i 0 0 ...0 0 l-(l)
for j in range(10):
res[0][j] = 1
for l in range(19):
for w in range(1,163):
for j in range(1,10):
for i in range(1,l+1):
if w>=j:
res[l][w] += res[l-i][w-j]
# i0000(l-i)
if length<=0 or weight<0:
return 0
if 19<length or 163<=weight:
raise IndexError('out of range')
return nw.res_f[length-1][weight]
@staticmethod
def lwi2c(num, length, weight):
"""数位长度为 length, 权重为 weight, 并且第一位是nnum的数字 总共有多少个？
限制 length <= 19, weight<=163
第一位是nnum的权重为nweight的nlen位数有多少个"""
# num + '0'*i + lw2c(length-i, weight-num)
# i = 1,2,... length
if not (0 <= num <= 9):
return 0
if num > weight:
return 0
if num == weight: #num 00000
return 1
count = 0
for i in range(1,length):
#print 'will(i)',i,length,weight,num,'+=',nw.res_f[length-i][weight-num]
#假定子问题已经求得了
#count += nw.res_f[length-i-1][weight-num]
count += nw.lw2c(length-i,weight-num)
return count
@staticmethod
def last_not_of(da,k):
for i in range(len(da)-1,-1, -1):
if da[i] == k:
continue
break
else:
i = -1
return i
class nb:
"""number builder 数字构建"""
trace_log = []
@staticmethod
def log():
s = '\n'.join(nb.trace_log)
nb.trace_log = []
return s
@staticmethod
def b4wn(nweight,nnum):
"""build for wight number: 构造权值为weight，小于等于nnum 的数字
（nnum隐式地限制了数位长度），求总个数"""
#
'''
nnum = 1743, da = [1, 7, 4, 3], w = 20
#小于4位的部分
xxx
xx
x
所有的 i位的 w=20的: lw2c(4-i,20) i=1,2,3, len(da)-1
#LOOP
i=0
jxxx
lwi2c(j,LEN-i,20-sum(da[:i])) j = range(1,da[i])
i=1
1jxx :
1jxx lwi2c(j,4-i,20-sum(da[:i])-j) j= range(da[i])
i=2
17jx
lwi2c(j,4-i,20-sum(da[:i])-j) j=1,2,3 range(1,da[i])
#i=3
174j
lwi2c(j,4-i,20-sum(da[:i])-j) j=1,2,3 range(1,da[i]+1)
'''
da_n = nw.n2da(nnum)
LEN = len(da_n)
if LEN == 1:
return sum([
nw.weight(j) == nweight and 1 or 0 for j in range(nnum+1)
])
ncount = 0
#小于LEN位的数，一定小于nnum的
#print 'len % 4d + % 4d'%(i,nw.lw2c(i,nweight))
##print 'x xx xxx ... da_n=',da_n,'LEN =',LEN
#ncount += sum([nw.lw2c(i,nweight) for i in range(1,LEN)])
for i in range(1,LEN):
nn = nw.lw2c(i,nweight)
ncount += nn
##print 'count '+' '*(LEN-i) +'x'*i + ':',nn,'lw2c(i=%d,nweight=%d)'%(i,nweight)
#N位的数，前面i位和 nnum的前面i位相同的，
#只要接下来的一位是 1,2,..,da_n[i]-，就能保证比nnum小，然后构造剩下的位
#注意接下来的这位不能是0，因为nnum可以是1000002的形式,所以此位是0的，
#已经被前面的非0的数位处理了
for i in range(len(da_n)):
for j in range(1,da_n[i]):
nn = nw.lwi2c(j,LEN-i,nweight-sum(da_n[:i]))
ncount += nn
#print 'count '+'f'*i+ str(j) +'x'*(LEN-1-1) + ':',nn,'lwi2c(j=%d,LEN=%d,nweight=%d)'%(j,LEN-i,nweight-sum(da_n[:i])-j)
#N的
if nw.weight(nnum) == nweight:
##print '@@@'
ncount += 1
return ncount
@staticmethod
def c_x999(w):
"""对指定的权值，产生一个值最小的数，这个数的形式是 x999"""
sret = str(w%9)+'9'*(w/9)
return int(sret)
@staticmethod
def c_999x(w):
"""对指定的权值，产生一个值最大的数，这个数的形式是 999x(不考虑后面是0的情况)"""
sret = str(w%9)+'9'*(w/9)
return int(sret)
@staticmethod
def c_1000x999_nw(n,w):
"""构造权为 w 并且小于n, 同时排最前的一个数
先尝试 x999 是否满足 这个数是权为w并且值最小的数，它不满足就再没有比N小的了
把 x999的最高位 -1 ，试图组装 1 00...0 (x-1)9999 形式的数，这个是排的尽量前的
每次插入一个0，判断新数是不是小于N，
是，
数 = 新数
继续
不是
返回 数
"""
assert(w >= 0)
if w < 2:
return w
v_x999 = nb.c_x999(w)
if v_x999 > n:
return -1
v_1000x999 = v_x999
da = [1] + nw.n2da( nb.c_x999(w-1) )
m = 0
while True:
ntry = nw.da2n(da)
#print 'mv',mv
if ntry <= n:
v_1000x999 = ntry
#print 'v_1000x999',v_1000x999
da.insert(1,0)
m += 1
continue
break
return v_1000x999
@staticmethod
def calc_nextmin_nm(n,m):
"""计算小于n的数中权和m相同,并且排在m后面的一个,无则返回-1
由这个排在前面的m开始,依次计算紧排在下一位的
1,再后面添一个0
满足<n就返回
2,最后一位非0位减1，它的前一位+1
3,非0位的前一位+1，非零位，后面贪心算法尽量 0000k
有满足<n就返回
4，返回-1
"""
if m*10 <= n:
return m*10
_last_not_of = nw.last_not_of
#
da = nw.n2da(m)
i = _last_not_of(da,0)
if i <= 0:
print 'i*calc_nextmin_nm(n,m)',n,m
return -1
j = _last_not_of(da[:i],9)
if j < 0:
print 'j*calc_nextmin_nm(n,m)'
return -1
#print 'p1*calc_nextmin_nm(n,m)=',m,n,'i,j =',i,j,'da =',da
da[i] -= 1
da[j] += 1
#print 'p2*calc_nextmin_nm(n,m)=',m,n,'i,j =',i,j,'da =',da
first = nw.da2n(da[:j+1])
second = nb.c_x999(sum(da[j+1:]))
if second == 0:
if first <= n:
return first
return -1
while first*10 + second <= n:
first *= 10
#print 'o*calc_nextmin_nm(n,m)=',m,n,'first =',first,'da =',da
return first+second
@staticmethod
def calc_pos_nk(n,k):
"""计算n个数中k的权重排序后的位置
"""
if k == 0:return 1
nb.trace_log.append('calc_pos_nk (n,k)='+str((n,k)))
wk = nw.weight(k)
#权重比
beforek = sum([
nb.b4wn(i,n) for i in range(0,wk)
])
#print 'beforek =',beforek
nb.trace_log.append('calc_pos_nk(n=%d,k=%d): beforek=%d'%(n,k,beforek))
"""
满足排在k之前的,前面位数都要要比k的位数小
假如 k = 4563在它之前的有, 记K(i)为k的第i位,i=1,2,3,4; w(k)为 k的权
1x fisrt_nw(K[:i]+[j,],wk,n) j=1,2,...K[i]-1, i=0
2x
3x
40x fisrt_nw(K[:i]+[j,],wk,n) j=0,1,2,...K[i]-1, i=1
41x
42x
43x
44x
450x
451x i=2
4560x fisrt_nw(K[:i]+[j,],wk,n) j=0,1,2,...K[i]-1, i=1
4561x
4563 fisrt_nw(K[:],0,n)
注意,只要找出前缀,调用 fisrt_nw(prefix,wk,n)就可以了
"""
count = beforek
da = nw.n2da(k)
all_prefix = []
i = 0
for j in range(1,da[i]):
prefix = [j]
all_prefix.append(prefix)
#最后一个非0的位
e = nw.last_not_of(da,0)
#依次固定1,2...e位
for i in range(1,e+1):
for j in range(0,da[i]):
prefix = da[:i]+[j]
all_prefix.append(prefix)
nb.trace_log.append('all_prefix =\n'+'\n'.join(map(lambda x:''.join(map(str,x)),all_prefix)))
#计算
for a in all_prefix:
c = nb.fisrt_nw(a,wk,n)
count += c
nb.trace_log.append('calc %s: c=%d'%(''.join(map(str,a)),c))
#fff000
count += len(da) - 1 - e
count += 1
nb.trace_log.append('calc_pos_nk (n,k)='+str((n,k))+' return '+str(count))
return count
@staticmethod
def fisrt_nw(da,w,n):
"""前面几位是da数位数组,权重是w(包含da)的数,并且不超过n的个数
nw.lwi2c的增强版
"""
FFF = nw.da2n(da)
#筛子过滤法则 不填充的,要填充的
#剩下的权重
wk = w - sum(da)
first,nmin,nmax = nw.da2n(da),nb.c_x999(wk),nb.c_999x(wk)
nb.trace_log.append('fisrt_nw: FFF=%d da=%s,w=%d,n=%d,wk=%d: begin'%(FFF,str(da),w,n,wk))
if wk < 0:
nb.trace_log.append('fisrt_nw: wk[%d] < 0: '%(wk))
return 0
count = 0
if wk == 0:
c = 0
while first <= n:
c += 1
first *= 10
count += c
nb.trace_log.append('fisrt_nw[FFF]: FFF=%d ret=%d'%(FFF,c))
return count
#最大长度
lmin = nw.da_len(nmin)
lmax = len(nw.n2da(n)) - len(da)
if lmax < lmin:
return 0
for l in range(lmin,lmax):
#不填充
c = nw.lw2c(l,wk)
count += c
nb.trace_log.append('fisrt_nw[FFF[1-9][0-9]{1,l-1}]: FFF=%d l=%d ret=%d'%(FFF,l,c))
#要填充的 fff 000x 00x 0x
for j in range(1,l):
c = nw.lw2c(l-j,wk)
count += c
nb.trace_log.append('fisrt_nw[FFF0{j}[1-9]{l-j}]: FFF=%d j=%d ret=%d'%(FFF,j,c))
#l==lmax的情况
nmax000 = nw.da2n((nw.n2da(nmax)+[0,]*lmax)[:lmax])
fff000 = first*(10**lmax)
if fff000 + nmax000 <= n:
c = nw.lw2c(lmax,wk)
count += c
nb.trace_log.append('fisrt_nw[FFF[1-9][0-9]{lmax-1}]: FFF=%d lmax=%d ret=%d'%(FFF,lmax,c))
for j in range(1,lmax):
c = nw.lw2c(lmax-j,wk)
count += c
nb.trace_log.append('fisrt_nw[FFF0{j}[1-9]{lmax-j}: FFF=%d j=%d lmax=%d ret=%d'%(FFF,j,lmax,c))
elif fff000 + nmin > n:
pass
else:
c = 0
ntry = fff000+nmin
while ntry <= fff000+nmax000:
c += 1
ntry = nb.calc_nextmin_nm(n, ntry)
if ntry == -1 :
break
if c > 1000:
raise RuntimeError("too long"
count += c
nb.trace_log.append('fisrt_nw[FFF0*nmin~FFF0*nmax]: FFF=%d nmin=%d nmax=%d ret=%d'%(FFF,nmin,nmax,c))
nb.trace_log.append('fisrt_nw: FFF=%d da=%s,w=%d,n=%d,wk=%d end: ret=%d'%(FFF,str(da),w,n,wk,count))
return count
@staticmethod
def calc_num_nk(n,k):
posk = None
#反推posk
"""
先算出 位置k 落在的weight值 w1,w2
然后 算出 weight-1 之前的所有个数
然后在保证weight不变,构造...
"""
return posk
pass
|
|
免费注册
发表于 2014-08-12 14:17
发表于 2014-08-12 15:28