Exercícios

Universidade Federal de Sergipe Departamento de Computação COMP0412 Projeto e Análise de Algoritmos 20232 Profs Giovanny Lucero e Breno Piva Prova 2 1 Um anagrama de uma palavra é outra palavra formada com exatamente as mesmas letras Assim por exemplo amor é um anagrama de roma e viceversa pois ambas palavras contêm as mesmas letras e nas mesmas quantidades Como outro exemplo alice é um anagrama de celia Escreva um programa que dado uma sequência de palavras diferentes encontre todos os conjuntos de anagramas existentes Por simplicidade assuma que todas as palavras usam o alfabeto Inglês ou seja sem acentos e que todas as letras são minúsculas Entrada 1 O número total de palavras em uma linha Este número não ultrapassará 100000 2 Todas as palavras uma por linha Qualquer palavra terá no máximo 20 caracteres Saída Os conjuntos de anagramas Cada conjunto listado em uma única linha com seus elementos ordenados lexicograficamente A ordem da listagem destes conjuntos segue a ordem lexicográfica da primeira palavra de cada conjunto Exemplo Entrada Saída 14 maria ramo amaro celia joao omara alice amor pera maroa roma pare aroma amora alice celia amaro amora aroma maroa omara amor ramo roma joao maria pare pera 2 Um trominó é uma ficha em forma de L formado por três quadrados 1x1 adjacentes O problema consiste em cobrir com trominós qualquer tabuleiro de 2ⁿ 2ⁿ quadrados que tem um quadrado faltando Os trominós devem cobrir todos os quadrados do tabuleiro exceto o faltante sem sobreposições Complete o código listado embaixo adicionando uma função que gere uma sequência de movimentos válidos que resolve o problema Um movimento válido representa a colocação de um trominó no tabuleiro sem que haja nenhuma sobreposição com outros que já tenham sido colocados antes include stdioh include stdlibh posicionamento de um trominó no tabuleiro typedef struct tPos int i j a posição da aresta do dominó int giro giro 0 trominó tem a forma giro 1 trominó tem a forma giro 2 trominó tem a forma giro 3 trominó tem a forma tromino sem giro é um L posicionamento Resolve o quebra cabeças d dimensão do tabuleiro um número múltiplo de 2 ij posição onde falta o quadrado do tabuleiro Retorna um array contendo os posicionamentos dos trominós no tabuleiro posicionamento resolveTrominoint d int i int j COMPLETE AQUI Se for necessário defina funções auxiliares int ps42 1 1 11 11 11 Coloca o trominó especificado por p na posicao ij do tabuleiro tab d é a dimensão do tabuleiro ou seja o número de quadrados numa fila ou coluna Retorna zero se parte ou todo o trominó ficam fora do tabuleiro ou se o trominó está sendo colocado em cima de parte ou toda uma peça colocada previamente int colocaposicionamento p int d int tab int i int j if pi d pj d pi pspgiro0 d pj pspgiro1 d pi i pj j pi pspgiro0 i pj j pi i pj pspgiro1 j tabpipj 1 tabpi pspgiro0pj 1 tabpipj pspgiro1 1 return 0 else tabpipj 1 tabpi pspgiro0pj 1 tabpipj pspgiro1 1 return 1 d dimensão do tabulueiro ij quadrado faltante no tabuleiro pos array com os trominós a ser colocados com posicao e giro cada um nt tamanho do array pos int verificaint d posicionamento pos int i int j int tabuleiro int mallocdsizeofint for int i0 id i tabuleiroi int callocd sizeofint int nt dd3 quantidade de trominós para preencher o tabuleiro for int k0 knt k if colocaposk d tabuleiro i j return 0 return 1 Função auxiliar Calcula xn int potint x int n int p 1 for int i 0 in i p x return p void main for int k0 k10 k int n rand 3 3 int d pot2n int i rand d int j rand d posicionamento pos resolveTrominod i j if verificad pos i j printfNAO exit1 printfSIM Entrada Não há entrada Saída A palavra SIM 3 Uma fazenda situada num terreno plano tem a forma de um polígono convexo de n vértices A fazenda está completamente cercada e possui uma porteira no meio de um dos lados do polígono João se encontra em algum ponto fora e à esquerda da fazenda e quer saber qual é o trajeto mais curto até a porteira João não poderá pular a cerca pois está eletrificada Projete um algoritmo razoavelmente eficiente para computar este trajeto Entrada 1 A primeira linha contém o número inteiro n correspondente à quantidade de vértices do polígono 2 As coordendas x e y de cada ponto do polígono que forma a cerca Ambos números são float e estão separados por espaço Cada ponto é listado em uma linha separada A listagem dos pontos não segue necessáriamente alguma ordem específica salvo que os dois primeiros pontos representam os extremos do lado em que se encontra o portão O portão está exatamente no meio deste lado 3 Finalmente uma linha com as coordenadas x e y correspondentes à posição de João Lembre que João se encontra à esquerda da fazenda ou seja sua coordenada x é menor que a coordenada x de qualquer ponto da fazenda Saída O trajeto mais curto até a cerca O trajeto está especificado pelos pontos que passa iniciando na posição inicial de João até chegar na porteira e passando possivelmente por vértices da cerca Cada ponto é listado em uma linha separada Exemplos Entrada Saída 5 0 0 1 1 05 05 05 12 0 1 1 2 10000 20000 10000 10000 05000 05000 5 0 0 05 05 05 12 0 1 1 1 1 1 10000 10000 02500 02500 5 0 0 1 1 05 05 05 12 0 1 1 05 10000 05000 00000 00000 05000 05000 4 O professor Bronny está ministrando pela primeira vez uma MOOC Massive Open Online Course Curso Online Aberto Massivo Neste modelo de curso o número de alunos pode chegar às centenas de milhares Uma das tarefas propostas no curso é a implementação de uma planilha eletrônica simples que deve poder ser testada com os dados dos alunos da própria turma Dentre os dados de cada aluno estão a idade e o sexo O professor Bronny achou que seria interessante poder ordenar os dados por idade e também dentro da mesma idade por sexo Escreva um programa com a melhor complexidade assintótica possível dentro do que você aprendeu no curso para fazer a ordenação que o professor Bronny precisa Entrada A primeira linha da entrada é composta por um número inteiro positivo N indicando o número de alunos no curso A seguir são apresentadas N linhas onde cada linha contém os dados de um aluno Os dados armazenados na planilha são primeiro nome último sobrenome idade sexo número de matrícula Os dados são apresentados sempre nesta ordem separados por um único espaço O primeiro nome e o último sobrenome são strings com no máximo 15 caracteres sem espaços A idade é um número inteiro positivo entre 10 e 120 O sexo é indicado por um único caractere que pode ser M masculino ou F feminino Finalmente o número de matrícula é um número com seis dígitos Saída A saída é dada por duas listagens dos dados dos alunos da turma Na primeira listagem os dados dos alunos são apresentados ordenados em ordem não decrescente de idade Em caso de empate os dados dos alunos devem ser apresentados na ordem em que foram lidos da entrada A seguir imprimise uma linha contendo apenas um símbolo seguida da segunda listagem em que os dados dos alunos são apresentados em ordem não decrescente de idade e em caso de empate primeiro os alunos do sexo feminino depois do sexo masculino Em caso de um novo empate a listagem segue a ordem de entrada Exemplo Entrada Saída 6 joao santos 22 M 123456 maria joaquina 55 F 123457 jose sampaio 48 M 123458 mario silva 98 M 123459 adriana nascimento 48 F 123460 katia valenca 22 F 123461 joao santos 22 M 123456 katia valenca 22 F 123461 jose sampaio 48 M 123458 adriana nascimento 48 F 123460 maria joaquina 55 F 123457 mario silva 98 M 123459 katia valenca 22 F 123461 joao santos 22 M 123456 adriana nascimento 48 F 123460 jose sampaio 48 M 123458 maria joaquina 55 F 123457 mario silva 98 M 123459