Lista de Exercícios - Força Bruta

Prévia do material em texto

Alcides Tiago Medeiros Dantas – 20211014040078 
TECNOLOGIA EM ANÁLISE E DESENVOLVIMENTO DE SISTEMAS – IFRN 
NATAL – RN 
2022 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Lista de Exercícios – Força Bruta 
ALGORITMOS 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1. (20 pontos) Escreva um texto explicando o processo de construção de um algoritmo através da 
técnica de força bruta. 
 A construção de um algoritmo por meio da técnica de força bruta consiste em listar todos os 
candidatos possíveis de uma solução, verificando cada um individualmente a fim de saber quais 
satisfazem o problema. Normalmente esse método é utilizado quando a simplicidade da 
implementação é mais relevante que a velocidade de execução, visto que aqui o custo computacional 
é proporcional ao número de candidatos existentes. 
 
2. (20 pontos) Escreva e explique o algoritmo global de força bruta. Detalhe para que serve cada uma 
das partes/funções do algoritmo. 
 O algoritmo global de força bruta consiste em, enquanto se tem possíveis candidatos a uma 
solução, selecionar cada candidato um a um e verificar se trata-se de uma solução válida para o 
problema. Caso o candidato recém-analisado seja uma solução válida, obtém-se uma resposta (saída), 
utiliza-se ela da forma que se desejar e segue-se para um possível próximo candidato. Senão, apenas 
prossegue-se para um possível próximo candidato. Representando de forma simbólica o que foi 
descrito acima, as diferentes partes do algoritmo global de força bruta são: 
➢ P => Dados do problema a ser resolvido; 
➢ Primeiro (P) => Gera o primeiro candidato C a ser analisado dentro da solução de P; 
➢ Próximo (P, C) => Gera o próximo candidato de P que se encontra após C; 
➢ Válido (P, C) => Confere se o candidato C é uma solução para o problema P; 
➢ Saída (P, C) => Se o candidato C é uma solução para P, então usa-se ela de alguma forma. 
 
3. (20 pontos) Escreva um algoritmo que receba dois números e mostre o MMC - Mínimo Múltiplo 
Comum - entre eles. Use o algoritmo global de força bruta descrito na questão anterior. Implemente em 
Linguagem C/C++ o algoritmo definido, realize um conjunto de testes e faça um gráfico com o tempo 
de execução dos testes. Verifique e descreva se os testes confirmam a análise de complexidade 
que você fez. 
Algoritmo em C: 
#include <stdio.h> 
 
long long MMC (long long a, long long b){ 
 long long maior = a, i; 
 
 if (b > maior){ 
 maior = b; 
 } 
 
 for (i = maior; i < a * b; i++){ 
 if (i % a == 0 && i % b == 0){ 
 return i; 
 } 
 } 
 return a * b; 
} 
 
int main(){ 
 
 long long n1, n2; 
 scanf("%lld %lld", &n1, &n2); 
 
 printf("O MMC entre %lld e %lld é: %lld\n", n1, n2, MMC(n1, n2)); 
 
 return 0; 
} 
 
Notação O: O(n) 
Testes com dois números de entrada, seus respectivos MMC’s e o tempo de execução em segundos: 
 
Gráfico referente aos MMC’s presentes na tabela em função do tempo de execução: 
Análise final: Ao analisar o gráfico acima, em escala logarítmica, pode-se perceber sua linearidade 
conforme se dobra os dois números envolvidos e consequentemente dobra-se seus MMC’s presentes 
no eixo X, assim como também o tempo de execução aproximado no eixo Y. Dessa forma, 
confirmamos a complexidade O(n) informada anteriormente. 
 
4. (20 pontos) Descreva e implemente um algoritmo que leia dois números inteiros a e b e mostre se 
eles são primos entre sí. A implementação deve ser feita em Linguagem C/C++. Descreva a 
complexidade do seu algoritmo usando a notação O. 
 Descrição do algoritmo: Dois números são chamados de primos entre si quando possuem em 
comum entre seus divisores apenas o número 1. Dessa forma, recebido dois números a e b, deve-se 
inicialmente verificar a primalidade deles por meio de, por exemplo, uma função. Caso os dois números 
lidos sejam primos, obrigatoriamente eles são primos entre si (podendo-se encerrar o programa), visto 
que cada um deles só possui como divisor ele mesmo e o número 1, fazendo com que a intersecção 
entre os divisores desses dois números seja apenas o valor 1. Caso contrário, se apenas um ou os dois 
valores não forem primos, deve-se percorrer um laço a procura de algum número que é divisor de 
ambos os valores. Se um divisor em comum for encontrado, significa que os dois valores a e b possuem, 
além do número 1, pelo menos um divisor em comum, descaracterizando-os como primos entre si. Por 
outro lado, após o fim do laço, caso não haja nenhum divisor em comum entre a e b, eles são primos 
entre si. 
 
 Algoritmo em C: 
#include <stdio.h> 
 
int Testa_Primo(int num){ 
 
 if (num == 2){ 
 return 1; 
 } 
 
 if (num % 2 == 0 || num == 1){ 
 return 0; 
 } 
 
 for (int i = 3; i * i < num + 1; i += 2){ 
 if (num % i == 0){ 
 return 0; 
 } 
 } 
 
 return 1; 
} 
 
int main(){ 
 int n1, n2; 
 scanf("%d %d", &n1, &n2); 
 
 int pri1 = Testa_Primo(n1); 
 int pri2 = Testa_Primo(n2); 
 
 if (pri1 && pri2){ //Se os dois são primos, obrigatoriamente são primos entre si. 
 printf("%d e %d São primos entre si!\n", n1, n2); 
 } 
 
 else{ //Se um ou os dois não são primos, deve-se procurar um divisor em comum entre eles. 
 int repetiu = 0; 
 int menor = n1; 
 if (n2 < menor){ 
 menor = n2; 
 } 
 
 for (int i = 2; i < menor + 1; i++){ 
 if (n1 % i == 0 && n2 % i == 0){ 
 printf("\n"); 
 printf("%d e %d NÃO são primos entre si!\n", n1, n2); 
 printf("Primeiro divisor em comum encontrado: %d\n", i); 
 repetiu = 1; 
 break; 
 } 
 } 
 
 if (repetiu == 0){ 
 printf("%d e %d são primos entre si!\n", n1, n2); 
 } 
 } 
 
 return 0; 
} 
 
 Descrição da notação O: O laço que identifica se os valores a e b são primos executa em tempo 
O(√n), visto que ele só é executado até a raiz do valor a ou do valor b. Já o outro laço, que é 
executado apenas quando algum dos dois valores lidos não é primo, procura pelo menos um divisor 
em comum entre a e b (podendo ser um deles com o outro), incrementando e percorrendo um a um 
elemento e indo até o menor dos dois valores lidos. Dessa forma, esse último laço explicado executa 
em tempo O(n), que trata-se também da notação O desse algoritmo como um todo, visto que refere-
se ao termo de maior grau envolvido. 
 Notação O: O(n). 
 
5. (20 pontos) Determine, usando a técnica de força bruta, qual o espaço de solução para o problema 
Festa de formatura, em anexo. Explique como você chegou a essa solução. 
DICA: De quantas formas diferentes eu posso colocar os alunos nas cadeiras? 
 
 
 
 
 Resposta: 
 O espaço de solução para o problema, caso não se tenha restrições, consiste em uma permutação 
entre todos os formandos, visto que nesse caso não seria relevante quem senta ao lado de quem. Por outro 
lado, caso existam restrições, o espaço de solução vai ser menor que o valor da permutação entre todos os 
formandos. Dessa forma, o maior valor possível dentro espaço de soluções gira em torno do fatorial do 
número de formandos, que trata-se da permutação entre todos eles. 
 Por outra via, caso existam restrições, iremos montar pequenos bloquinhos para cada conjunto de 
números relacionados com outros que estão contido nas restrições, estes que não podem ser permutados 
entre si, visto que violaria alguma das restrições envolvidas. Da mesma forma, os números que não 
participam das restrições podem ficar em bloquinhos unitários. Dessa maneira, obteremos uma certa 
quantidade de bloquinhos contendo números dentro deles. Após isso, calcularemos o fatorial dessa 
quantidade de bloquinhos e o guardaremos para usá-lo depois, a fim de obter a quantidadede permutações 
possíveis que podemos realizar entre todos os blocos (Item 1 – fatorial da quantidade de blocos). Observe 
que cada bloco que contém mais de um número dentro dele, apesar de não poder realizar permutação dos 
números entre si, pode ser representado de duas formas, sendo de uma forma invertida ou não. Considere, 
por exemplo, um bloco contendo os números 1, 2 e 3. Podemos representar esse bloco como: {1,2,3} e 
{3,2,1}. Sendo assim, devemos multiplicar por dois a quantidade de blocos que podem ter essas duas 
aparências (Item 2 – Potência de base 2 da quantidade de blocos que podem ser representados de uma 
forma e de forma inversa), que são os blocos que possuem mais de um número. Com isso, obteremos uma 
equação no modelo: 
𝑩 ! ∗ 𝟐𝒒 
 
Em que B! é o fatorial da quantidade de blocos formados (como explicado anteriormente) e q é a 
quantidade de blocos que possuem mais de um número e podem ser escritos na forma normal e invertida, 
por isso a utilização de potência de base 2. Ao fim, deve-se multiplicar as duas partes para obter a 
quantidade de formas diferentes que pode-se colocar os alunos nas cadeiras. 
≤ ≤ 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
Festa de formatura 
Ao final do curso, os alunos resolveram fazer uma grande festa de formatura e, cedo, começaram a 
planejar os detalhes para que tudo ocorresse bem. Durante o planejamento, vários problemas tiveram 
que ser resolvidos. Um problema em específico estava causando conflitos: onde cada formando iria se 
sentar durante os discursos dos professores. Este problema ocorreu porque alguns formandos 
definitivamente queriam se sentar ao lado de outros formandos, pois possuem mais afinidades. O 
motivo é que fiquem juntos durante a maior parte da cerimônia e tenham muitas fotos em comum. 
Como eles estavam perdidos e não chegavam a um acordo, você foi contratado para determinar a 
posição de cada um dos formandos. Todos os formandos ficam sentados na fileira da frente do 
auditório, um ao lado do outro, como na figura a seguir: 
 
 
 
Entrada 
A primeira linha da entrada é composta de um número inteiro N (2 N 16), que indica a quantidade 
de formandos. Cada formando recebe um número entre 1 e N , inclusive. A segunda linha contém um 
inteiro R (0 ≤ R ≤ N ), que indica a quantidade de restrições. As próximas R linhas contêm dois inteiros 
A e B (0 ≤ A, B ≤ N ), indicando que o formando A quer sentar-se ao lado do formando B. 
Saída 
Seu programa deve imprimir uma única linha indicando a ordem dos alunos nas poltronas do auditório. Se 
houver mais de uma configuração possível, mostre qualquer uma delas. Caso não seja possível, o programa 
deve mostrar −1. 
 
 
Exemplo de entrada 1 
 
Exemplo de saída 1 
 
5 2 1 4 3 5 (OK) 
3 4 1 2 5 (OK) 3 
 
1 2 
3 4 
1 4 
 5 2 1 4 3 (OK) 
 5 3 4 1 2 (OK) 
 
 
 
Exemplo de entrada 2 
 
Exemplo de saída 2 
 
6 6 5 1 2 3 4 (OK) 
6 4 3 2 1 5 (OK) 
4 3 2 1 5 6 (OK) 
5 1 2 3 4 6 (OK) 
4 
 
 1 2 
1 5 
2 3 
4 3