0

考虑 26 个字母和 10 个数字的集合。

编写一个函数，返回长度为 N 的密码数量，其中至少包含 L 个小写字母、至少 U 个大写字母和至少 D 个数字。

函数签名int cntPass(int N,int L,int U,int D)

我的做法：

我试图使用递归来解决它，但我认为它是错误的。我的（错误）递归如下：

f(N,L,U,D)=f(N,L-1,U,D)+f(N,L,U-1,D)+f(N,L,U,D-1) [具有必要的基本条件，但它不起作用]。

我正在寻找更好的方法或不同的逻辑来解决这个问题。

谢谢。

4

2 回答 2

5

这只是一个简单的组合问题。结果是N C L * NL C U * NLU C D * 26 L * 26 U * 10 D * 62 N - U - L - D，可以稍微简化为 26 L + U * 10 D * 62 N - U - L - D * N！/（U！* L！* D！*（N - L - U - D）！）。

我们在 N 个位置中为小写字符选择 L 个位置。然后在其余 N - L 个位置中为大写字母选择 U 个位置。并在其余 N - L - U 位中选择 D 位作为数字。剩下的就是一切。

L 小写字母每个有 26 个选项。U 大写字母也一样。D 位各有 10 个选项。对于其余的 (N - L - U - D)，我们可以为每个字符使用 26 + 26 + 10 个字符中的任何一个。

于 2013-02-04T10:57:51.737 回答
2

@nhahtdh 的答案是完全正确的。但是，如果需要大量数字，计算组合因子可能会有点棘手（请参阅注释以了解这样做的好方法）。

这是一种不通过阶乘但使用递归来计算相同数字的方法：不考虑函数 int cntPass(int N,int L,int U,int D)，而是添加最后一个参数，它表示可以是 3 中任何一个的位数：

int cntPass(int N,int L,int U,int D,int A)

注意我们有 A = NLUD。现在，递归基于对第一个字符的选择：我们有 26 个小写字母选择，26 个大写字母选择，10 个数字选择。

现在，给定 N、L、U、D 和 A，可以

  • 将小写字母作为第一个字符-> 26 种可能性。对于这些可能性中的每一种，我们对其余密码都有 cntPass(N-1,L-1,U,D,A) 可能性。注意如果L=0，这不起作用，除非A>0，即仍有一些字符可以自由选择。在这种情况下，我们也有 26 种可能性，每个可能性都有 cntPass(N-1,L,U,D,A-1)。
  • 大写的同上
  • 同上的数字。

为了结束递归，我们可以设置 N=1 时的可能性数量，或者等效地设置 N=0 时的数量（为符号 1）。

这是一个 Matlab 代码（使用 Matlab 进行快速测试），它使得它：

function [number]=Nword(N,LowerCase,UpperCase,Digit,Any)
number = 0;
if ( LowerCase > 0)
   number = number + 26*Nword( N-1, LowerCase-1, UpperCase, Digit, Any);
elseif (Any > 0)
    number = number + 26*Nword( N-1, LowerCase, UpperCase, Digit, Any-1);
end

if ( UpperCase > 0)
   number = number + 26*Nword( N-1, LowerCase, UpperCase-1, Digit, Any);
elseif( Any > 0)
    number = number + 26*Nword( N-1, LowerCase, UpperCase, Digit, Any-1);
end

if ( Digit > 0)
   number = number + 10*Nword( N-1, LowerCase, UpperCase, Digit-1, Any);
elseif( Any > 0)
    number = number + 10*Nword( N-1, LowerCase, UpperCase, Digit, Any-1);
end

if (number == 0)
   number = 1; 
end

return
于 2013-02-04T12:32:50.857 回答