0

26 個のアルファベットと 10 桁の数字のセットを考えてみましょう。

少なくとも L 個の小文字、少なくとも U 個の大文字、および少なくとも D 個の数字を含む、長さ N のパスワードの数を返す関数を作成してください。

関数シグネチャ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に少し簡略化できます。- う - ら - 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 でない限り、これは機能しないことに注意してください。つまり、選択できない文字がまだいくつかあります。この場合、それぞれに cntPass(N-1,L,U,D,A-1) を使用した 26 の可能性もあります。
  • 大文字の同上
  • 数字の同上。

再帰を終了するには、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 に答える