[lua]笔试-按字典序列出指指定的序列的位置

it2024-08-23  27

计算方法: n的阶乘记为f(n), s为输入序列, sub(i)为s的i到n的子序列。A(i)为第i位对应的字母在子序列sub(i)中的字典顺序 N(s) = sum_{1,n} T(i)*(A(i) - 1) + 1 T(i)为i - 1的阶乘。

--[[ 在线编程题1 比大小: Time Limit: 3000/2000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others) Problem Description: 现在有"abcdefghijkl”12个字符,将其所有的排列中按字典序排列,给出任意一种排列,说出这个排列在所有的排列中是第几小的? abcdefghijkl hgebkflacdji gfkedhjblcia 1 302715242 260726926 计算方法: n的阶乘记为f(n), s为输入序列, sub(i)为s的i到n的子序列。A(i)为第i位对应的字母在子序列sub(i)中的字典顺序 N(s) = sum_{1,n} T(i)*(A(i) - 1) + 1 T(i)为i - 1的阶乘。 --]] local s = "abcdefghijkl" local function factorial(n) local f = 1 for i=1,n do f = f * i end return f end function N(s) if type(s) ~= 'string' or #s == 0 then error('unexpected input') end local A = {a=1,b=2,c=3,d=4,e=5,f=6,g=7,h=8,i=9,j=10,k=11,l=12} local sum = 0 local len = #s for i=1, len - 1 do local T = factorial(len - i) local a = string.sub(s,i,i) sum = sum + T * (A[a] - 1) for k, v in pairs(A) do if k > a then A[k] = A[k] - 1 end end A[a] = 0 end sum = sum + 1 return sum end print(N("abcdefghijkl")) print(N("hgebkflacdji")) print(N("gfkedhjblcia")) print(N("bacd")) 1 302715242 260726926

转载于:https://www.cnblogs.com/lotushy/p/4863780.html

相关资源:cocos2d-x 面试题
最新回复(0)