Prática 4 - Recursão - Introdução à Computação 2 - 2023-2

FAC. DE FILOSOFIA, CIÊNCIAS E LETRAS DE RIBEIRÃO PRETO UNIVERSIDADE DE SÃO PAULO Introdução à Computação II - 5954006 2o semestre 2023 Prof. Renato Tinós 1 PRÁTICA 4: Recursão Considere o problema de descobrir uma senha em um sistema computacional. A senha é composta por n letras maiúsculas (as letras são “ABCDEFGHIJKLMNOPQRSTUVWXYZ”). Considere que é possível verificar se um string s (vetor com n letras) é a senha correta através de um comando “verif s” que é chamado dentro de um programa em C++ e que acessa o sistema computacional e retorna 1 caso a senha esteja correta e 0 caso a senha esteja errada. A chamada do comando (que é dado para o Sistema Operacional Windows) deve ser a seguinte: #include <iostream> #include <cstdlib> #include <string.h> using namespace std; .... char sb[106], s[100]; int sucesso; .... sucesso=system(strcat(strcpy(sb,"verif "),s)); … sendo que s contém o string que será verificado. Um exemplo do uso do comando é dado no programa ex_senha.cpp anexo. FAC. DE FILOSOFIA, CIÊNCIAS E LETRAS DE RIBEIRÃO PRETO UNIVERSIDADE DE SÃO PAULO Introdução à Computação II - 5954006 2o semestre 2023 Prof. Renato Tinós 2 Pede-se: a) Desenvolva uma função utilizando recursão para descobrir qual é a senha correta. Considere que o tamanho n da senha seja digitado pelo usuário (1<n<6). b) Quais são as senhas para n=2, n=3 e n=4? c) Comente sobre a viabilidade e eficiência deste algoritmo baseado em sua complexidade computacional. Para isso, faça a análise assintótica - notação “O” – do tempo do programa desenvolvido. Considere que o comando “verif s” é O(1). PRÁTICA 4: RECURSÃO – RESPOSTAS Questão 1) #include <iostream> #include <cstdlib> #include <string.h> using namespace std; char senhaCorreta[6]; bool verificarSenha(char* s) { if (strcmp(s, senhaCorreta) == 0) { return true; } else { cout << "sh: 1: verif: not found" << endl; return false; } } void descobrirSenha(char* s, int n, int pos = 0) { if (pos == n) { if (verificarSenha(s)) { cout << "Sucesso! Senha: " << s << endl; exit(0); } return; } for (char c = 'A'; c <= 'Z'; ++c) { s[pos] = c; descobrirSenha(s, n, pos + 1); } } int main() { int n; cout << "Entre com o tamanho da senha (maior que 1 e menor que 6): "; cin >> n; cout << "Entre com a senha com " << n << " letras maiusculas: "; cin >> senhaCorreta; char* s = new char[n+1]; s[n] = '\0'; descobrirSenha(s, n); delete[] s; return 0; } Questão 2) A senha correta dependerá da entrada do usuário, sendo que a função de recursão ficará testando o código para todas as 26𝑛 possibilidades, onde 26 são as letras do alfabeto e 𝑛 será o número de caracteres da senha. Para as entradas com 𝑛 = 2, 𝑛 = 3 𝑒 𝑛 = 4, temos: • 𝑛 = 2 → 262 = 676 𝑝𝑜𝑠𝑠𝑖𝑏𝑖𝑙𝑖𝑑𝑎𝑑𝑒𝑠 𝑑𝑒 𝑠𝑒𝑛ℎ𝑎 • 𝑛 = 3 → 263 = 17576 𝑝𝑜𝑠𝑠𝑖𝑏𝑖𝑙𝑑𝑖𝑎𝑑𝑒𝑠 𝑑𝑒 𝑠𝑒𝑛ℎ𝑎 • 𝑛 = 4 → 264 = 456976 𝑝𝑜𝑠𝑠𝑖𝑏𝑖𝑙𝑖𝑑𝑎𝑑𝑒𝑠 𝑑𝑒 𝑠𝑒𝑛ℎ𝑎 Questão 3) A abordagem usada neste algoritmo para descobrir a senha correta tem uma complexidade de tempo de: 𝑂(26𝑁) Para esta complexidade de tempo, temos que N é o tamanho da senha. Isso ocorre porque o algoritmo tenta todas as combinações possíveis de letras maiúsculas para uma senha de tamanho N, através da recursão. Se tratando de viabilidade, este algoritmo funcionará e encontrará a senha correta eventualmente, desde que a senha esteja dentro do conjunto de possibilidades que o algoritmo está verificando (neste caso, senhas de tamanho N compostas por letras maiúsculas). Porém, em termos de eficiência, este algoritmo é bastante ineficiente. A complexidade exponencial do tempo significa que o tempo necessário para encontrar a senha correta aumentará muito rapidamente à medida que o tamanho da senha aumenta. Por exemplo, para uma senha de tamanho 6, o algoritmo teria que verificar 266 = 308915776 𝑝𝑜𝑠𝑠𝑖𝑏𝑖𝑙𝑖𝑑𝑎𝑑𝑒𝑠 𝑑𝑒 𝑠𝑒𝑛ℎ𝑎 Assim, embora este algoritmo seja viável para senhas muito pequenas, ele se torna impraticável e ineficiente para senhas maiores. Métodos mais eficientes, como por exemplo o “ataque de dicionário”, seriam necessários para senhas maiores ou para um conjunto maior de caracteres possíveis na senha.