时间戳

首页 > 解决方案 > 根据一些给定的限制计算有效密码的数量

c++ - 根据一些给定的限制计算有效密码的数量

问题描述

我必须根据一些给定的限制来计算可能有多少个有效密码。限制如下：

  1. 最小10字符数和最大14字符数。
  2. 字符可以包括英文小写字母（'a'-'z'）、大写字母（'A'-'Z'）、数字（'0'-'9'）和特殊字符（'!','@','#','$','%','^','&','*','(',')'）
  3. 有效密码必须至少包含小写字母、大写字母、数字和特殊字符中的一种。
  4. 密码不能包含自己的学生证。学生证为 7 位数字。前两位数字表示年份 ( 00, 01, ... , 99)，后两位数字表示部门代码 ( 00, 01, ... 99)，最后三位数字表示部门内的滚动 ( 000 - 180)。因此，学生 ID 可以是：1210142，其中12表示他来自批次12，10是部门代码，并且142是卷号。有 ID 的学生1210142不能有类似的密码，Ti@s1210142mE但可以有类似的密码Ti@s121014m2E。
  5. 一个学生可以在他/她自己的密码中使用另一个学生的 ID。

鉴于限制可以生成多少个有效密码？

我写了一个简单的 C++ 程序来模拟它。但由于它只是一个幼稚的实现，它需要大量的时间（可能比我的一生还要长）才能吐出答案。是否有任何聪明的方法可以使用代码找出答案，可能使用正则表达式或类似的东西？

到目前为止我的努力：

#include <iostream>
#include <algorithm>

inline bool is_valid_password(const std::string &generated_password, const std::string &student_id){
    bool small = false, captial = false, digit = false, special = false;
    for(const char &c : generated_password){
        if(c >= 'a' && c <= 'z') small = true;
        else if(c >= 'A' && c <= 'Z') captial = true;
        else if(c >= '0' && c <= '9') digit = true;
        else if(c == '!' || c == '@' || c == '#' || c == '$' || c == '%' || c == '^' || c == '&' || c == '*' || c == '(' || c == ')') special = true;
    }
    if(small && captial && digit && special){
        return generated_password.find(student_id) == std::string::npos;
    }
    return false;
}

char valid_character_set [] = {
        'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',
        'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z',
        '0','1','2','3','4','5','6','7','8','9',
        '!','@','#','$','%','^','&','*','(',')'
};

long long comb(int N, int K, const std::string &student_id)
{
    std::string bitmask(K, 1); // K leading 1's
    bitmask.resize(N, 0); // N-K trailing 0's

    long long counter = 0;

    // print integers and permute bitmask
    do {
        std::string generated_password = "";

        for (int i = 0; i < N; ++i) // [0..N-1] integers
        {
            if (bitmask[i]){
                generated_password += valid_character_set[i];
            }
        }

        if(is_valid_password(generated_password, student_id)) {
            //std::cout << "valid password found: " << generated_password << '\n';
            counter++;
        }

    } while (std::prev_permutation(bitmask.begin(), bitmask.end()));

    return counter;
}

int main(int argc, char const *argv[])
{
    std::cout << "Enter your student id: ";
    std::string student_id; std::cin >> student_id;
    std::cout << "Your student id is: " << student_id << "\n";



    // all possible 10 character passwords

    std::cout << comb(72, 10, student_id) << '\n';

    return 0;
}

标签： c++regex

解决方案

我不知道你是否熟悉编写正则表达式，但如果不熟悉，你可以在这个网站上学习和尝试很多。在我看来，正则表达式是一个非常强大的概念，值得花一些时间来学习它。

无论如何，当你熟悉正则表达式时，C++ 中有一个非常有用的正则表达式标准库。只包括

#include<regex>

然后你可以实例化你自己的正则表达式对象：

std::regex r = regex("yourRegexPattern");

使用该对象，您可以调用一些有用的函数，例如regex_match()（这可能是您的用例的正确函数），regex_search()或regex_replace().

更多信息，我已经链接了上面的官方参考，或者你可以谷歌“c++ regex”

编辑：固定链接

推荐阅读