Algoritmos e Complexidade: Exercícios Resolvidos, Notas de estudo de Mecatrônica

Baixe Algoritmos e Complexidade: Exercícios Resolvidos e outras Notas de estudo em PDF para Mecatrônica, somente na Docsity! Lista de Exer  ios 1 { PMR 2300 | 1o. semestre 2005Prof. Fabio CozmanLinguagem Java, Analise de Algoritmos, Re urs~ao, Bus a sequen ial e binaria e Ordenamento(sele ~ao, inser ~ao e uni~ao)1. Qual String e impressa pelo programa:publi lass What {publi stati void f(int x) {x = 2;}publi stati void main(String args[℄) {int x = 0;f(x);System.out.println("Hey: " + x);}}2. Considere o seguinte exemplo de altera ~ao de um arranjo passado por referên ia para um metodo hamado doIt:publi stati void doIt(int h[℄) {int k[℄ = new int[2 * h.length℄;for (int i=0; i<h.length; i++) {k[i℄ = h[i℄;k[i+h.length℄ = h[i℄;}h = k;k[0℄ = 2;}Esse odigo ontem um erro. Rees reva-o de forma a garantir que o arranjo h na hamada da fun ~aoe modi ado (seu tamanho e onteudo s~ao dupli ados, e seu elemento 0 re ebe o valor 2).3. Es reva um pequeno metodo em Java que re eba dois arranjos a e b de tamanho igual, ontendovalores do tipo double, e retorne o produto es alar de a e b.4. Elabore um programa re ursivo que al ule o Mnimo Divisor Comum de dois inteiros usando oseguinte algoritmo, onhe ido omo algoritmo de Eu lides: Divida o numero maior pelo menor epegue o resto; ent~ao divida o divisor pelo resto e assim su essivamente ate que o resto seja zero |o quo iente da ultima divis~ao e o divisor omum. Por exemplo, tome 928 e 100: dividimos 928 por100, obtemos resto 28; dividimos 100 por 28, obtemos resto 16; dividimos 28 por 16, obtemos resto12; dividimos 16 por 12, obtemos resto 4; dividimos 12 por 4 e obtemos resto zero | o resultado e 4.5. Es reva uma lasse hamada Complexo que opera sobre numeros omplexos. O onstrutor basi odeve ser:Complexo( double a, double b ).Um segundo onstrutor deve ser providen iado para riar o numero real a:Complexo( double a ).Codi que os metodos add(Complexo ), subtra t(Complexo ),multiply(Complexo ) e divide(Complexo ).6. Considere que vo ê omprou uma bibliote a ontendo a lasse Complexo, ujo manual indi a:1 publi lass Complexo:publi Complexo(double a, double b);publi Complexo add(Complexo );publi Complexo subtra t(Complexo );publi Complexo multiply(Complexo );publi Complexo divide(Complexo );Vo ê deseja riar uma lasse omo Complexo, porem om metodos adi ionais que permitem somar,subtrair, dividir e multipli ar por um numero real:publi Complexo add(double d);publi Complexo subtra t(double d);publi Complexo multiply(double d);publi Complexo divide(double d);Codi que uma lasse SuperComplexo que ontem toda a fun ionalidade indi ada anteriormente us-ando o esquema de hierarquias de Java.7. Es reva um algoritmo re ursivo que transforme um numero inteiro de imal em um numero binario.8. Considere a fun ~ao f(n) de nida re ursivamente omo segue: f(0) = 0; f(n) = f(n=2) se n e par;f(n) = 1 + f(n 1) se n e impar. Codi que essa fun ~ao em Java e obtenha o valor de f(100).9. Considere o seguinte algoritmo:int exer i io1(int x) {if (x < 5)return(3*x);elsereturn(2 * exer i io1(x-5) + 7);}Qual e o resultado de exer i io1(4) e exer i io1(20)? Desenhe a arvore de hamadas re ursivaspara ada aso.10. Considere o seguinte algoritmo:int exer i io2(int x, int y) {if (x > y)return(-1);else {if (x == y)return(1);elsereturn(x * exer i io2(x+1, y) + exer i io2(2*x,y))}}Qual e o resultado de exer i io2(10,4), exer i io2(4,3), exer i io2(4,7)? Desenhe a arvorede hamadas re ursivas para ada aso.11. Dado o fragmento de odigo abaixo, desenhe a arvore de re urs~ao para f(1; 10) e obtenha o valor deretorno. 2 (a) Qual a omplexidade do programa em nota ~ao BigOh no pior aso? Justi que.(b) Suponha que a ter eira linha seja removida; qual a omplexidade do programa resultante emnota ~ao BigOh, no pior aso? Justi que.( ) Suponha que a sexta linha seja substituda porSystem.out.println( j + k ). Qual a omplexidade do programa resultante em nota ~aoBigOh no pior aso? Justi que.(d) Suponha que a quarta e quinta linhas sejam substitudas porfor (j = i; j<a.length; j++)for (k = j; k<b.length; k++)Qual a omplexidade do programa resultante em nota ~ao BigOh no pior aso? Justi que.23. Considere uma bus a sequen ial de um elemento X em um arranjo de N elementos. Normalmenteassumimos que ada ompara ~ao utilizada na bus a tem um usto xo. Suponha porem que ada ompara ~ao exija uma bus a binaria no arranjo de N elementos. Qual e a omplexidade da bus ade X em nota ~ao BigOh no pior aso?24. Para o odigo a seguir, indique o tre ho rti o do programa (isto e, as linhas que se repetem maisvezes). Determine o valor da variavel sum ao nal. Indique a omplexidade no pior aso em nota ~aoBigOh. Justi que.int sum = 0;for (int i=0; i<n; i++)for (int j = 0; j<(n*i); j++)for (int k=0; k<j; k++)sum++;DICA: O resultado e O N5
, pois o valor de sum atinge N5=6N4=4N3=6 +N2=4.25. Para o odigo a seguir, indique o tre ho rti o do programa. Determine o valor da variavel sum ao nal. Indique a omplexidade no pior aso em nota ~ao BigOh. Justi que.int sum = 0;for (int i=0; i<n; i++)sum++;for (int i=0; i<n; i++)for (int j=0; j<(i*i); j++)if ((j%i) == 0)for (int k=0; k<j; k++)sum++;DICA: O resultado e O N4
, pois o valor de sum atinge N4=8 5N3=12 + 3N2=8 11N=12. Estevalor e obtido pela express~ao N1Xi=0 1 + N1Xi=1 i1Xj=0 ij1Xk=0 1:Note o efeito da opera ~ao % na omplexidade do programa.26. Demonstre que o seguinte programa leva a um loop in nito para n maior que 2.publi boolean verify(int x, int y, int z, int n) {boolean flag = false;int auxX, auxY, auxZ;while (flag == false) { 5 auxX = 1; auxY = 1; auxZ = 1;for (int i=0; i<n; i++) {auxX *= x;auxY *= y;auxZ *= z;}if (auxX + auxY == auxZ)flag = true;n++;}}DICA: Esse problema e extremamente simples! Veri que a express~ao matemati a produzida para ada valor de n, e argumente que a express~ao n~ao tem solu ~ao usando um resultado onhe ido emmatemati a.27. Considere os seguintes metodos:publi ube(int n) {aux = 0;for (int i=1; i<=n; i++)aux += i*i*i;return(aux);}publi square(int n) {aux =0;for (int i=1; i<=n; i++)aux += i;return(aux * aux);}(a) Indique a omplexidade dos dois metodos em nota ~ao BigOh.(b) Demonstre que os dois metodos retornam o mesmo valor.( ) Es reva um metodo que retorna o mesmo valor em tempo O (1).28. Considere o seguinte teorema ( onhe ido omo Teorema do Limite Superior): um politopo om Nverti es em D dimens~oes tem KND=2 fa es para uma onstante K > 0 e para qualquer N maior queum erto M . A partir desse teorema, prove que a ordena ~ao e impress~ao das fa es de um politopo om N verti es em 4 dimens~oes pode ser feita em O N2 logN
. Justi que a partir da de ni ~ao danota ~ao BigOh.DICA: Lembre-se que um politopo e um objeto geometri o de nido por hiperplanos em um espa o om D dimens~oes (para D = 2, temos poliedros).29. Considere um programa om dois metodos. O primeiro metodo re ebe um numero N e produz umarranjo a de tamanho N !, onde ada elemento do arranjo e uma permuta ~ao do arranjo b igual a[1; 2; :::; N ℄ (existem N ! permuta ~oes de uma lista om N elementos). Suponha que a seja ordenadode alguma forma, e o segundo metodo realiza uma bus a binaria em a. Prove que a omplexidadedo segundo metodo e O (N logN), usando a aproxima ~ao de Stirling:N ! = p2N(N=e)N (1 +O (1=N)):30. Considere os dois programas abaixo: 6 int doIt1(int a[℄) {int n = a.length;int sum = 0;for (int i=0; i<=n; i++)for (int j=0; j<=i; j++)sum += a[i℄ * a[j℄;return(sum);}int doIt2(int a[℄) {int n = a.length;int sum = 0;int sum2 = 0;for (int i=0; i<=n; i++) {sum += a[i℄;sum2 += a[i℄ * a[i℄;}return( (sum * sum + sum2)/2 );}(a) Determine a omplexidade de ada metodo no pior aso em nota ~ao BigOh.(b) Prove que os dois metodos retornam o mesmo resultado. (Di a: Use indu ~ao nita em n, otamanho do vetor a. Note que os dois metodos retornam o mesmo resultado para n = 1,assuma que os resultados s~ao iguais para n generi o e prove que s~ao iguais para (n+ 1).)31. Considere o seguinte metodo:publi void doIt(int a[℄, int b[℄) {Ordena.ordena(a);for (int i=0; i<b.length; i++) {int aux = BinarySear h.sear h(a, b[i℄);for (int j=aux; j<a.length; j++)System.out.println(a[j℄);}}onde: void ordena(int a[℄) e um metodo de lasse (da lasse Ordena) que faz o ordenamento doarranjo a). int sear h(int a[℄, int x) e um metodo de lasse (da lasse BinarySear h) que faz bus abinaria do elemento x no arranjo a e retorna o ndi e de x em a. a e b s~ao arranjos de tamanho maximo N . todos os elementos de b est~ao em a (os elementos de b podem ser repetidos).Qual a omplexidade em nota ~ao BigOh no pior aso em fun ~ao de N para (justi que!):(a) metodo ordena implementado om ordena ~ao por inser ~ao.(b) metodo ordena implementado om mergesort.32. Vo ê foi hamado por uma empresa para analisar um blo o fundamental de programas de ontrolede uxo de aixa. Vo ê identi ou que o seguinte metodo e hamado muito frequentemente:7