EstruturasdeDados 5Como visto no Captulo 3, tipos de dados elementares sao caracterizadospelofatoqueseusvaloressaoatomicos,istoe,naoadmitemdecomposi cao.Ostiposdedadosnumerico,caracterelogicoestaoentreostiposdedadoselementares suportados pela maioria das linguagens de programa cao. Entre-tanto,seosvaloresdeum tipodedadosadmitemdecomposi caoemvaloresmais simples, entao o tipo de dados e dito complexo ou estruturado, ao invesdeelementar, eaorganiza caodecadacomponenteeasrelacoesentreelesconstituioquechamamosdeestruturadedados.NesteCaptulo, estudaremosasestruturasdedadosmaiselementares,tais como vetores, matrizes e registros, mas que nos permitiraoresolverproblemasmaiscomplexosdoqueaquelesvistosateagora.5.1 VetoresConsidereoseguinteproblema:Calculeamediaaritmeticadasnotasde5alunosdeumadisci-plina e determine o n umero de alunos que tiveram notasuperior`amediacalculada.Comovocebemsabe,ocalculodamediaaritmeticadasnotasde5alunosdeumadisciplinapodeserresolvidoatravesdeumaestruturaderepeti caocomoaquesegue:...soma 0para i de 1 at e 5 fa ca705.1. Vetores UFMSleia notasoma soma +notafimparamedia soma/5...Entretanto, seseguirmoscomestetrechodealgoritmo, comodeterminare-mos quantos alunos obtiveram nota superior `a media calculada?Isto porquenaotemosasnotasdecadaumdos5alunosdepoisqueotrechoacimaforexecutado. Logo,devemosoptarporoutrocaminho,quepodeserestequesegueabaixo://algoritmoparacalcularamediade5notaseescrever//quantosalunosobtiveramnotasuperior`amediaalgoritmocalculamediaenotassuperiores//declara caodeconstantesevariaveisinteirosoma,media,nota1,nota2,nota3inteironota4,nota5,num//leituradasnotasleianota1,nota2,nota3,nota4,nota5//calculoasomadasnotassoma nota1 +nota2 +nota3 +nota4 +nota5//calculodamediamedia soma/5//calculodasnotassuperiores`amedianum 0senota1 > mediaentaonum num+ 1msesenota2 > mediaentaonum num+ 1msesenota3 > mediaentaonum num+ 1mse715.1. Vetores UFMSsenota4 > mediaentaonum num+ 1msesenota5 > mediaentaonum num+ 1mse//escreveon umerodealunoscomnotasuperior`amediaescreveon umerodealunoscomnotasuperior`amediae: ,nummalgoritmoComopodemosconstatar, naofomoscapazesdeutilizarumaestruturaderepeti caoparacalcularquantasnotaseramsuperiores `amedia,mesmoem-borahouvesse5estruturascondicionaisidenticas, amenosdavariavelcomovalor danota, pararealizar ocalculodesejado. Nocasodoproblemaacima, esta redundancia nao chega a ser um fardo, mas se tivessemos 100,1000,oumesmo1000000denotas,estasolu caoseriainviavel, umavezqueteramosdeescrever, respectivamente, 100, 1000ou1000000deestruturascondicionaissemelhantes,umaparacadanota. Felizmente,paraproblemascomoeste,temosuma forma ecazde solu cao,que utilizauma estrutura dedadosdenominadavetor.5.1.1 DenindoumaEstruturadeDadosVetorAestruturadedadosvetoreumaestruturadedadoslinearutilizadaparaarmazenar umalistade valores domesmotipo. Umdadovetor edenidocomotendoalgumn umeroxodecelulasidenticas. Cadacelulaarmazenaum,esomenteum,dos valoresdedadosdovetor. Cadaumadascelulasdeumvetorpossuiseuproprioendere co,ou ndice,atravesdoqualpodemosreferencia-la. Porexemplo, aprimeiraceluladeumvetorpossuindice1,aquartapossui ndice4,eassimpordiante.Aodenirmosumvetor, estamosnaverdadeespecicandoaestruturadedadosdeumnovotipodedados, otipodedadosvetor, poisestetipo,aocontrariodostiposprimitivos, naoestaprontoparausoe, portanto,deveserdenido explicitamentedentrodo algoritmo. Temostambemque adeni caodeumaestruturadedados epartedaespecica caodeum tipodedadoscomplexo,que,comosabemos,tambemconsistenaespecica caodasopera coes sobre o conjunto de valores do tipo. Entretanto,no momento,ve-remos a deni cao de tipos complexos como composta apenas da especica caodaestruturadedados.725.1. Vetores UFMSNospodemosdenirumvetoratravesdaespecica caodeumidenti-cadorparaumtipovetor,suasdimensoeseotipodedadosdosvaloresqueelepodearmazenar. Isto efeitodaseguinteforma:denatipovetor[li..ls]deonde denatipoevetorsaopalavras-chave; tipodoselementos eonomedotipodoselementosdovetor; nomedotipoeumidenticadorparaotiposendodenido; lielssaorespectivamenteoslimitesinferioresuperiordovetor.Porexemplo, paracriarmosumvetorde5elementosinteiroschamadovetornotas,fazemos:denatipovetor[1..5]deinteirovetornotasOn umerodeelementos(celulas)deumvetoredadoporls li + 1eondicedoprimeiroelemento(celula) e li, dosegundoeli+ 1, eassimpordiante. Istosignicaquedoisvetores aebcomvaloreslielssejam1e5e7e11, respectivamente, possuemomesmon umerodeelementos:5 = 51+1 = 117+1; entretanto,o primeiro elemento de a possui ndice1,enquantooprimeiroelementodebpossui ndice7.5.1.2 DeclarandoeManipulandoVariaveisdoTipoVetorPara declararmos uma variavel de um tipo vetor, procedemos exatamenteda mesma forma que para um tipo simples. Por exemplo, considere a cria caodeumavariaveldenominadanotasdotipovetornotas:vetornotasnotasEstadeclara caosignicaqueestamoscriandoumavariavelnotasqueedotipo vetornotas,ouseja,um vetordeinteiroscom5posi coesde ndices1a 5. Umavez declarada a variavel notas, podemos atribuir qualquerconjuntode5valoresnumericos`avariavel. Entretanto, istonaoefeitodaformamaisnatural,talcomo735.1. Vetores UFMSnotas (1, 0, 1, 33, 10)massimindividualmente;ouseja,umvalorporvezacadaceluladovetor.Para tal, usamos o nome da variavel, ondice da celula e uma sintaxe propria.Por exemplo, notas[0] 1, atribui o valor 1 `a celula de ndice 1 do vetor.Deforma geral,as celulas,e naoa variaveldo tipo vetorcomoum todo,eque sao utilizadasem qualquer opera caoenvolvendoa variavel,sejam elasleitura, escrita, atribui cao, expressao, e assim por diante. No caso particulardovetornotas, acelulade ndiceidenotas, notas[i], podeserusadaemqualquer parte de um algoritmo em que uma variavel inteira possa ser usada.Istosignicaquepodemostercomandostaiscomoleianotas[1],escrevanotas[1]enotas[2] notas[1] + 1.5.1.3 ProblemaseSolucoesEnvolvendoVetoresVamosiniciarestasubse caoresolvendode forma ecazo problema esta-belecidonoinciodesteCaptulo:1. Calculeamediaaritmeticadasnotasde5alunosdeumadisciplinaedetermineon umerodealunosquetiveramnotasuperior`amediacalculada.//algoritmoparacalcularamediade5notaseescrever//quantosalunosobtiveramnotasuperior`amediaalgoritmocalculamediaenotassuperiores//declara caodeconstantesdenaLI1denaLS5//declara caodetiposdenatipovetor[LI..LS]derealvetornotas//declara caodevariaveisvetornotasnotasrealsoma,mediainteironum,i//leecalculaamediadasnotassoma 0745.1. Vetores UFMSparaideLIateLSfa caleianotas[i]soma soma +notas[i]mpara//calculodamediamedia soma/(LS LI + 1)//calculodasnotassuperiores`amedianum 0paraideLIateLSfa casenotas[i] > mediaentaonum num+ 1msempara//escreveon umerodealunoscomnotasuperior`amediaescreveon umerodealunoscomnotasuperior`amediae: ,nummalgoritmo2. Escrevaumalgoritmoquedeclareumavariavel deumtipovetorde10 elementos inteiros,leia 10 valores para esta variavel e entaoescrevaomaioreomenorvalordovetoresuasrespectivasposi coesnovetor.//algoritmoparalerumvetorde10elementosedepoisescrever//omaioreomenorelementoesuasrespectivasposi coesalgoritmoencontramenormaior//declara caodeconstantesdenaLI1denaLS10//criaumtipovetorden umerosdenatipovetor[LI..LS]deinteirovetor10//declara caodevariaveisvetor10ninteiroi,maior,menor,pmenor,pmaior//le10n umerosearmazena-osemumvetorparaideLIateLSfa caescrevaEntrecomoelemento,i LI + 1,dovetor: 755.1. Vetores UFMSleian[i]mpara//determinamenoremaioresuasposi coesmenor n[LI]maior n[LI]pmenor 1pmaior 1paraideLI + 1ateLSfa casemenor > n[i]entaomenor n[i]pmenor i LI + 1senaosemaior< n[i]entaomaior n[i]pmaior i LI + 1msemsempara//escreveomenoreomaiorvaloresuasposi coesescrevaOmenorvalore: ,menorescrevaAposi caodomenorvalore: ,pmenorescrevaOmaiorvalore: ,maiorescrevaAposi caodomaiorvalore: ,pmaiormalgoritmo3. O Departamento de Computa cao e Estatstica (DCT) da UFMS desejasaber se existem alunos cursando, simultaneamente, as disciplinas Pro-grama caodeComputadoreseIntrodu cao`aCienciadaComputa cao.Para tal, estao disponveis os n umeros de matrcula dos alunos de Pro-grama cao de Computadores (no maximo 60) e de Introdu cao `a CienciadaComputa cao(nomaximo80).Escreva um algoritmo que leia cada conjunto de n umeros de matrculados alunos e escreva as matrculas daqueles que estao cursando as duasdisciplinas ao mesmo tempo. Considere que cada conjunto de n umerosdematrculaencerrecomamatrculainvalida9999, deformaqueoalgoritmosaibaquandooconjuntoden umerosjafoilido.//algoritmoparadeterminareescreverasmatrculaiguaisdeduas//deduasdisciplinas//algoritmodeterminamatrculasiguais765.1. Vetores UFMS//declara caodeconstantesdenaLI1denaLSPC60denaLSICC80//declara caodetiposdenatipovetor[LI..LSPC]deinteirovetorpcdenatipovetor[LI..LSICC]deinteirovetoricc//declara caodevariaveisvetorpcvpcvetoriccviccinteiroi,j,k,l,num//leasmatrculasdosalunosdePrograma caodeComputadoresi LI 1leianumenquantonum = 9999fa cai i + 1vpc[i] numleianummenquanto//leasmatrculasdosalunosdeIntrodu cao//`aCienciadaComputa caoj LI 1leianumenquantonum = 9999fa caj j + 1vicc[j] numleianummenquanto//vericaseexistemmatrculasiguais. Seexistirem,escreve//asmatrculasiguais.parakdeLIateifa cal LIenquantol jfa casevpc[k] = vicc[l]entaoescrevavpc[k]l j + 1senao775.1. Vetores UFMSl l + 1msemenquantomparamalgoritmo4. Escrevaumalgoritmoquerecebeuminteiro0< n 100eumvetordenn umeros inteiroscujaprimeiraposi cao e1einverteaordemdoselementosdovetorsemusaroutrovetor.//algoritmoparainverteraordemdoselementosdeumvetorsem//utilizarvetorauxiliaralgoritmoinverte//declara caodeconstantesdenaLI1denaLS100//criaumtipovetorden umerosdenatipovetor[LI..LS]deinteirovetint//declara caodevariaveisvetintvinteiroi,temp//entradadedadosleianparaide1atenfa caleiav[i]mpara//trocaoselementoscomseussimetricosparaide1atenDIV2fa catemp v[i]v[i] v[n i + 1]v[n i + 1] tempmpara//sadadosresultadosparaide1atenfa caescrevav[i]785.2. Matrizes UFMSmparamalgoritmo5.2 MatrizesOsvetores queestudamos ateentaosaotodosunidimensionais. Mas,podemos declararemanipular vetorescommais de uma dimensao,osquaisdenominamosmatrizes. Porexemplo, podemosdenirumaestruturadedadosmatriz4por5(umatabelacom4linhase5colunas), denominadatabela,escrevendoasseguinteslinhas:denaLI11denaLS14denaLI21denaLS25denatipovetor[LI1..LS1]deinteirocolunadenatipovetor[LI2..LS2]decolunatabelaNesteexemplo,coluna eumtipovetorden umeros,isto e,umtipocujaestruturadedadoseumvetorunidimensional,comoestamosacostumadosacriar. Entretanto,tabelaeumtipovetordecoluna,ouseja,umtipocujaestruturadedadoseumvetorbidimensional (umamatriz), poiscadaumdeseuselementosedotipovetorden umerosdotipocoluna!Uma forma alternativa para denir o tipo tabela acima (e preferida pelosdesenvolvedoresdealgoritmo)easeguinte:denaLI11denaLS14denaLI21denaLS25denatipovetor[LI1..LS1, LI2..LS2]deinteirotabelaTantoemumaformadedeni caoquantonaoutra, asconstantesLI1,LS1, LI2eLS2estabelecemon umerodeelementos databela. Istoe,LS1 LI1 + 1en umerodelinhasdatabela,enquantoLS2 LI2 + 1,on umerodecolunas.795.2. Matrizes UFMSUma vez denido o tipo tabela, podemos declarar uma variavel deste tipoda mesma maneira que declaramos variaveis dos demais tipos. Por exemplo,alinhaabaixodeclaraumavariaveldenominadamatdotipotabela:tabelamatApartirda,podemosmanipularavariavelmatutilizandodois ndices,em vez de apenas 1, para referenciar cada elemento desta matriz. O primeirondiceidenticaaposi caodoelementonaprimeiradimensao, enquantoosegundoidenticaaposi caodoelementonasegundadimensao. Seimagi-narmosmatcomoumatabela, entaooprimeiro ndicecorresponde`alinhada tabela em que o elemento se encontra, enquanto o segundo, ` a coluna. Porexemplo,suponha quedesejemosatribuirovalor0atodososelementosdamatrizmat. Istopodeserfeitocomoseguintetrechodecodigo:...paraideLI1ateLS1fa caparajdeLI2ateLS2fa camat[i, j] 0mparampara...Observe que um aninhamento de la cos foi utilizado para varrer toda amatriz. O la co mais externo e responsavel por variar o ndice que representaaposi caodoelementonaprimeiradimensaodamatriz, enquantoola comais internoeutilizadoparavariar ondicequerepresentaaposi caodoelementonasegundadimensaodamatriz. Asintaxemat[i, j]eusadaparareferenciarmosoelementodalinhaiecolunajdamatrizmat.5.2.1 ProblemaseSolucoesEnvolvendoMatrizes1. Escrevaumalgoritmoquedeclareumavariaveldeumtipomatrizde4por5elementosnumericos, leiavaloresparaestavariavel eescrevaasomadoselementosdecadalinhadamatriz, bemcomoasomadetodososelementos.//algoritmoparadeterminareescreverasomadoselementosdaslinhas//deumamatriz4por5easomadetodososelementosdamatrizalgoritmosomaporlinhaedelinhasdematriz805.2. Matrizes UFMS//declara caodeconstantesdenaLI11denaLS14denaLI21denaLS25//declara caodetiposdenatipovetor[LI1..LS1, LI2..LS2]deinteirotabela//declara caodevariaveistabelamatinteiroi,j,somalin,somatot//leituradoselementosdamatrizparaideLI1ateLS1fa caparajdeLI2ateLS2fa caescrevaentrecomoelemento,i LI1 + 1,e,j LI2 + 1,damatrizleiamat[i, j]mparampara//somaelementosporlinhaetotalizasomatot 0paraideLI1ateLS1fa ca//calculaasomadalinhai LI1 + 1somalin 0parajdeLI2ateLS2fa casomalin somalin +mat[i, j]mpara//exibeasomadalinhai LI1 + 1escrevaAsomadoselementosdalinha,i LI1 + 1,: ,somalin//acumulaasomadaslinhasparaencontrarasomatotalsomatot somatot +mat[i, j]mpara//exibeasomatotalescrevaAsomadetodososelementose: ,somatotmalgoritmo815.2. Matrizes UFMS2. DadasduasmatrizesAnmeBmp, comn 50, m 50ep 50.ObteramatrizmatrizCmpondeC= AB.//algoritmoparamultiplicarduasmatrizesalgoritmoprodutodematrizes//deni caodeconstantesdenaLI1denaLS50//deni caodetiposdenatipovetor[LI..LS, LI..LS]deinteiromatriz//declara caodevariaveismatrizA,B,Cinteiroi,j,k,n,m,p//entradadedadosleian,m,pparaide1atenfa caparajde1atemfa caleiaA[i, j]mparamparaparaide1atemfa caparajde1atepfa caleiaB[i, j]mparampara//Calculodamatrizprodutoparaide1atenfa caparajde1atepfa caC[i, j] 0parakde1atemfa caC[i, j] A[i, k] B[k, j] +C[i, j]mparamparampara//escritadamatrizCparaide1atenfa ca825.3. Registros UFMSparajde1atepfa caescrevaC[i, j]mparamparamalgoritmo5.3 RegistrosUmregistroeumaestruturadedadosqueagrupadadosdetiposdis-tintos ou, mais raramente, do mesmo tipo. Um registro de dados e compostopor um certo n umero de camposdedado, que sao itens de dados individu-ais. Porexemplo, suponhaquedesejemoscriarumalgoritmoparamanterumcadastrodosempregadosdeumadadacompanhia. Nestecadastro, te-mososseguintesdadosparacadaempregado: Nomedoempregado. CPFdoempregado. Salariodoempregado. Seoempregadopossuiounaodependentes.Entao, cada chadeste cadastro pode ser representada por umregistroque contemos campos nome, CPF, salario e indica cao de existencia dedependentes. Nestecaso, anaturezadoscamposebemdiversicada, poisnome pode ser representado por umacadeia, CPFe salario por valoresnumericoseexistenciadedependentesporumvalorlogico.5.3.1 DenindoumaEstruturadeRegistroAsintaxeparadeni caodeumnovotiporegistroeaseguinte:denatiporegistro< tipodocampo1>< campo1>< tipodocampo2>< campo2>...< tipodocampon>< campon>mregistro835.3. Registros UFMSondenomedotipoeonomedotiporegistrocujaestruturaestasendocriada,campoieonomedoi-esimocampodoregistroetipodocampoieotipodoi-esimocampodoregistro.Comoexemplo, vamoscriarumregistropararepresentarumachadocadastrodeempregadosdadocomoexemploanteriormente:denatiporegistrocadeianomeinteiroCPFrealsalariologicotemdepmregistroregcha5.3.2 CriandoeManipulandoVariaveisdeRegistrosUmavezque um tiporegistrotenhasidodenido, podemos criartantasvariaveis daquele tipo quanto desejarmos, assim como fazemos com qualqueroutro tipo complexovisto ateentao. Porexemplo,para criarmos treschasdeempregadoparaonossoexemplodocadastro,escrevemos:regchacha1,cha2,cha3Cadaumadessastresvariaveiseumregistrodotiporegchae, portanto,cada uma delas possui quatro campos de dado: nome, CPF, salario e temdep.Assimcomovariaveisdevetoresematrizes, variaveisregistrossaoma-nipuladas atravesde suas partes constituintes. Em particular,uma variavelregistro e manipulada atraves de seus campos. Entao, se desejarmos atribuirumvaloraumavariavel registro, temosdeefetuaraatribui caodevaloresparaseuscamposconstituintes,umdecadavez. Comoexemplo,considereaseguinteatribui caodoconjuntodevaloresBeltranodeTal,123456789,1800000efalso`avariavelficha1:ficha1.nome BeltranodeTalficha1.CPF 123456789ficha1.salario 180.00ficha1.temdep falsoApartirdesteexemplo, podemosvericar queoacessoacadacampodeumavariavelregistroerealizadoatravesdaescritadonomedavariavel845.3. Registros UFMSregistroseguidodeumponto(.)que, porsuavez,eseguidopelonomedocampo.5.3.3 VetoresdeRegistrosRegistros nosfornecemumaformadeagrupardadosdenaturezadis-tinta. Entretanto, criarmos uma unicavariavel deumregistrocomplexonaoparecesermuitodiferentedecriarmosumavariavel paracadacampodoregistroetrata-lasindividualmente. Istoe, criaruma unicavariavel deumregistrocomplexonaonos ajudariaaresolver nossos problemas maisfacilmentedoquecomoqueaprendemosantes. Agrandefor cadosregis-trosresidenousodelescombinadocomvetores. Por exemplo, umgrupode100empregadosiriarequererumconjuntode100variaveisregistros, oquepodeserconseguidoatravesdacria caodeumvetorde100elementosdotiporegistroemquestao!Umvetorderegistrosecriadodamesmaformaquecriamosvetoresdequalquerdostiposqueaprendemosateentao. Suponha,porexemplo, quedesejemoscriarumvetorde100elementosdotiporegcha. Istoefeitodaseguinteforma:denaLI1denaLS100denatiporegistrocadeianomeinteiroCPFrealsalariologicotemdepmregistroregchadenatipovetor[LI..LS]deregchavetcadAgora,considereadeclara caodeumavariaveldotipovetcad:vetcadcadastroParamanipularumregistroindividual dovetorcadastro, utilizamosonome da variavel vetor e ondice do elemento correspondente ao registro quequeremosacessar,comofazemoscomumvetordequalqueroutrotipo. Daemdiante, procedemoscomoaprendemosnaSubse cao5.3.2. Porexemplo,855.3. Registros UFMSsequisermos atribuir oconjuntodevalores SicranodeTal, 987654321,540, 00everdadeiroaoprimeiroregistrodecadastro, fazemos:cadastro[1].nome SicranodeTalcadastro[1].CPF 987654321cadastro[1].salario 540, 00cadastro[1].temdep verdadeiro5.3.4 RegistrodeTiposComplexosAssim como combinamos vetores e registros para criar vetores de registro,podemos ter umregistro de cujoumoumais campos sao de umoutrotipoderegistroouvetores. Suponha, porexemplo,quequeremosadicionarumcampoaonossoregistroregchapararepresentaracontabancariadoempregado. Estecampopodeser umoutroregistrocontendoos camposnomedobanco, n umerodaagenciaen umerodacontabancaria. Vejamoscomocariaanovadeni caoderegcha:denatiporegistrocadeiabancointeiroagenciainteironumccmregistroregbancodenatiporegistrocadeianomeinteiroCPFrealsalariologicotemdepregbancocontamregistroregchaOfatodocampocontaderegbancoserumoutroregistrofazcomqueamanipula caodestecamposejarealizada, tambem, atravesdesuaspartesconstituintes. Entao,secriarmosumavariavelchadotiporegcha,temosdemanipularocampocontadechacomosegue:ficha.conta.banco BancodePra caficha.conta.agencia 666ficha.conta.numcc 4555865.3. Registros UFMS5.3.5 UmProblemaEnvolvendoRegistrosSuponhaque voce tenhasidocontratado pelaCopeve paraconstruirparte de umprogramaparacalcular on umerode acertos emprovadoscandidatosaovestibulardaUFMS.Paratal,vocedeveraescreverum algo-ritmo que lera os dados de cada candidato e o gabarito das provas, calcularao n umero de acertosde cadacandidato em cada prova e escreverao n umerodeacertosdoscandidatosemcadaprova.Considerearespostaacadaquestaodeprovacomosendoumdoscincocaracteresa,b,c,dee.Vamos iniciar aconstru caodasolu cao deste problemapeladeni caodostiposeestruturasdedadosnecessarios. Deacordocomadescri caodoproblema, temos umgabarito, queerepresentadopor umamatriz, eumregistroquecontemumamatrizeumvetor. Cadacandidatopossuiumtalregistro. Logo,o conjunto de todos os candidatos pode ser representado porumvetorderegistros.Oalgoritmoedadoaseguir://algoritmoparacalcularon umerodeacertosde//candidatosaovestibularalgoritmovestibular//deni caodeconstantesdenaNUMQUEST 40denaNUMPROVAS 5denaNUMCAND 5000//deni caodetiposdenatipovetor[1..NUMPROVAS]deinteirovetacdenatipovetor[1..NUMQUEST, 1..NUMPROVAS] decaractermatgabdenatiporegistrointeirocodigomatgabXvetacAmregistroregcanddenatipovetor[1..NUMCAND]deregcandvetcand//declara caodevariaveis875.3. Registros UFMSmatgabG//matrizcontendoogabaritovetcandcandidato//vetorderegistroscontendoosdadosdoscandidatosinteiroi,j,k,n,soma//leituradamatrizdegabaritoparajde1ateNUMPROV ASfa caparaide1ateNUMQUESTfa caescrevaRespostadaquestao,i,daprova,jleiaG[i, j]mparampara//leituradaquantidadedecandidatosescrevaQuantidadedecandidatosleian//leituradosdadosdoscandidatosparakde1atenfa caescrevaCodigodocandidato:leiacandidato[k].codigoparajde1ateNUMPROV ASfa caparaide1ateNUMQUESTfa caescrevaRespostadaquestao,i,daprova,jleiacandidato[k].X[i, j]mparamparampara//Calculodosacertosdecadacandidatoparakde1atenfa caparajde1ateNUMPROV ASfa casoma 0paraide1ateNUMQUESTfa caseG[i][j] = candidato[k].X[i][j] entaosoma soma + 1msemparacandidato[k].A[j] somamparampara//Sadadosresultadosparakde1atenfa ca885.3. Registros UFMSescrevaCodigo:,candidato[k].codigoparajde1ateNUMPROV ASfa caescrevacandidato[k].A[j], acertosnaprova,jmparamparamalgoritmoBibliograaO textodeste captulofoi elaborado a partir dos livros abaixorelaciona-dos:1. Farrer,H.et. al. AlgoritmosEstruturados. EditoraGuanabara,1989.2. Shackelford, R.L. Introduction to Computing and Algorithms. Addison-WesleyLongman,Inc,1998.89ListadeexercciosVetores1. Dadauma seq uenciade n n umeros, imprimi-la em ordem inversa `adeleitura.2. Deseja-se publicar o n umero de acertos de cada aluno em uma prova emformadetestes. Aprovaconstade30questoes, cadaumacomcincoalternativasidenticadasporA,B,C,DeE.Paraissosaodados:ocartaogabarito;o cartaode respostas de cada aluno, contendoo seu n umeroesuasrespostas.3. Tentandodescobrir se umdadoeraviciado, umdonode cassinoolan counvezes. Dadososnresultadosdoslan camentos,determinaron umerodeocorrenciasdecadaface.4. Um jogador viciado de cassino deseja fazer um levantamento estatsticosimples sobre uma roleta. Para isso, ele fez n lan camentos nesta roleta.Sabendoqueumaroletacontem37n umeros(de0a36), calcular afreq uenciadecadan umero destaroletanosnlan camentosrealizados.5. Dadosdoisvetoresxey,amboscomnelementos, determinaropro-dutoescalardessesvetores.6. Saodadosdoisn umerosinteirospositivospeq, sendoqueon umerodedgitosdepemenorouigualaon umerodedgitosdeq. Vericarsep eumsubn umerodeq.Exemplos:p = 23,q= 57238,p esubn umerodeq;p = 23,q= 258347,pnao esubn umerodeq.7. Sao dadas as coordenadas reais x e yde um ponto, un n umero naturalneascoordenadasreaisdenpontos, com1 n 100. Deseja-secalcular e imprimir sem repeti cao os raios das circunferencias centradasnoponto(x, y)quepassemporpelomenosumdosnpontosdados.Exemplo:90Listadeexerccios UFMS___(x, y) = (1.0, 1.0);n = 5;Pontos:(1.0, 1.2), (1.5, 2.0), (0.0, 2.0), (0.0, 0.5), (4.0, 2.0)Nesse caso ha tres circunferencias de raios 1.12, 2.01e 3.162.Observa coes:(a) Adistanciaentreospontos(a, b)e(c, d)e_(a c)2+ (b d)2.(b) Dois pontos estao namesmacircunferencia se estao `amesmadistanciadocentro.8. Dadasduascadeias(umacontendoumafraseeoutracontendoumapalavra),determineon umerodevezesqueapalavraocorrenafrase.Exemplo:ParaapalavraANAeafrase:ANAEMARIANAGOSTAMDEBANANA.Temosqueapalavraocorre4vezesnafrase.9. Dadaumaseq uenciadenn umerosreais, determinarosn umerosquecompoemaseq uenciaeon umerodevezesquecadaumdelesocorrenamesma.Exemplo:n = 8Seq uencia: 1.7, 3.0, 0.0, 1.5, 0.0, 1.7, 2.3, 1.7Sada:1.7 ocorre 3 vezes3.0 ocorre 1 vez0.0 ocorre 2 vezes1.5 ocorre 1 vez2.3 ocorre 1 vez10. Dizemos que uma seq uencia de n elementos, com n par, e balanceadaseasseguintessomassaotodasiguais:asomadomaiorelementocomomenorelemento;asomadosegundomaior elementocomosegundomenorelemento;asomadoterceiromaior elementocomoterceiromenorelemento;eassimpordiante. . .Exemplo:91Listadeexerccios UFMS212361615eumaseq uenciabalanceada, pois16 + 2=15 + 3 = 12 + 6.Dadosn(npar)eumaseq uenciadenn umerosinteiros, vericarseessaseq uenciaebalanceada.11. Dadosdoisn umerosnaturaismeneduasseq uenciasordenadascomm e n n umeros inteiros, obter uma unica seq uencia ordenada contendotodososelementosdasseq uenciasoriginaissemrepeti cao.Sugest ao: imagineumasitua caoreal, porexemplo, doischariosemumabiblioteca.12. Dadas duas seq uencias com n n umeros inteirosentre 0 e 9, interpreta-dascomodoisn umerosinteirosdenalgarismos, calcularaseq uenciaden umerosquerepresentaasomadosdoisinteiros.Exemplo:n = 8,1aseq uencia 8 2 4 3 4 2 5 12aseq uencia + 3 3 7 5 2 3 3 71 1 6 1 8 6 5 8 813. Calcule o valor dopolinomiop(x) =a0+a1x+. . .+anxnemkpontos distintos. Sao dados os valores de n(graudo polinomio),dea0, a1, . . . an(coecientes reais dopolinomio), dekedos pontosx1, x2, . . . , xn.14. Dadoopolinomiop(x) = a0 +a1x +. . . anxn,isto e,osvaloresdenedea0, a1, . . . , an, determineoscoecientesreaisdaprimeiraderivadadep(x).15. Dadosdoispolinomiosreaisp(x) = a0 +a1x +. . . +anxneq(x) = b0 +b1x +. . . +bmxmdeterminaroprodutodessesdoispolinomios.16. Chama-seseq uenciadeFareyrelativa`anaseq uenciadefra coesracionaisirredutveis, dispostasemordemcrescente, comdenomina-dorespositivosenaomaioresquen.Exemplo:Sen=5, ostermosdaseq uenciadeFarey, taisque0 1,sao:01, 15, 14, 13, 25, 12, 35, 23, 34, 45, 11.925.4. Matrizes UFMSPara gerarmos os termos de uma seq uencia de Farey tais que 0 1, podemosutilizaroseguinteprocesso. Come camoscomasfra coes01e11, eentre cadaduas fra coes consecutivasijekm, introduzimosafra caoi+kj+meassimsucessivamenteenquantoj+ m n. Quandonaoformaispossvel introduzirnovasfra coesteremosgeradostodosostermosdaseq uenciadeFareyrelativaan, taisque0 1.Utilizandoometododescrito, determineostermos, 0 1, daseq uenciadeFareyrelativaan,comninteiropositivo.Sugest ao: gereosnumeradoreseosdenominadoresemdoisvetores.17. Dadaumaseq uenciax1, x2, . . . , xkden umeros inteiros, veriqueseexistemdoissegmentosconsecutivosiguaisnestaseq uencia, istoe,seexistemiemtaisquexi, xi+1, . . . , xi+m1= xi+m, xi+m+1, . . . , xi+2m1.Imprima,casoexistam,osvaloresdeiem.Exemplo:Naseq uencia7, 9, 5, 4, 5, 4, 8, 6existemi = 3em = 2.18. Dada uma seq uencia x0, x1, . . . , xk1 de k n umeros inteiros, determinarumsegmentodesomamaxima.Exemplo:Na seq uencia5, 2, 2, 7, 3, 14, 10, 3, 9, 6, 4, 1,a soma dosegmentoe33.5.4 Matrizes1. SejaaseguintematrizA:175 225 10 9000 37 47598 100 363 432 156 1840 301 302 6381 1 0402 4211 7213 992 442 732121 3 2 1 9000 2000(a) Quantoselementosfazempartedoconjunto?(b) Qualoconte udodoelementoidenticadoporA[4, 5]?(c) Qualoconte udodavariavelxaposaexecu caodocomandox =A[3, 2] +A[4, 1]?935.4. Matrizes UFMS(d) OqueaconteceriacasofossereferenciadooelementoA[5, 1] emumprogramaemlinguagemC?(e) Somar os elementosda quarta coluna (A[1, 3] +A[1, 3] +A[2, 3] +A[3, 3] +A[4, 3]).(f) Somaroselementosdaterceiralinha(A[2, 1] +A[2, 1] +A[2, 2] +A[2, 3] +A[2, 4] +A[2, 5]).2. Dada uma matriz real B, de 100 linhas e 200 colunas, escrever um pro-gramaquecalculeosomatoriodos elementosda quadragesimacolunaequecalculeosomatoriodatrigesimalinha.3. DadasduasmatrizesAeB,dedimensoesn m,fazerumprogramaquecalculeamatrizCnm= A+B.4. FazerumprogramaquedadaumamatrizAnm,determineAt.5. DadaumamatrizrealAcommlinhasencolunaseumvetorrealVcomnelementos,determinaroprodutodeAporV .6. Um vetor real x com n elementos e apresentado como resultado de umsistemadeequa coeslinearesAx = bcujoscoecientessaorepresenta-dos em uma matrizrealAmne osladosdireitos das equa coesem umvetorreal b de m elementos. Vericarse o vetorx erealmente solu caodosistemadado.7. Dadasduas matrizesreaisAmneBnp,calcularoproduto de AporB.8. DadaumamatrizrealAmn,vericarseexistemelementosrepetidosemA.9. Seja A2610uma matriz fornecida, cujo conte udo e a popula cao dos 10municpios mais populosos dos 26 estados brasileiros (A[i, j] representaapopula caodoj-esimomunicpiodoi-esimoestado). Determinaron umerodomunicpiomaispopulosoeon umerodoestadoaqueper-tence. Considerando que a primeira coluna sempre contem a popula caodacapital doestado, calcularamediadapopula caodascapitaisdos26estados.10. Deseja-se atualizar as contas correntes dos clientes deumaagenciabancaria.E dado o cadastro de n clientes contendo,para cada cliente,on umerodesuacontaeoseusaldo; ocadastroestaordenadopelon umerodaconta. Emseguida, e dadoo n umeromde opera coesefetuadasno dia e,paracada opera cao,o n umero da conta,uma letraCouDindicandoseaopera caoedecreditooudebitoeovalordaopera cao. Emitiroextratoatualizadodosclientes.945.4. Matrizes UFMS11. Deseja-se fazer aemissaodafolhade pagamentode umaempresa.Paracadaumdosnfuncionariossaodadasasseguintesinforma coes:Codigo Descri caoNOME NomedofuncionarioSAL SalariodofuncionarioHED HorasextrasdiurnasHEN HorasextrasnoturnasND N umerodedependentesFAL FaltasemhorasDE DescontoseventuaisREF Gastoscomrefei coesfeitasnaempresaVAL ValesretiradosduranteomesParacadafuncionario,emitirasseguintesinforma coes:Nome,Salario,HorasExtras=HED SAL/160+HEN 1,2 SAL/160,SalarioFamlia=ND 0,05 SalarioMnimovigente,SalarioBruto=Salario+HorasExtras+SalarioFamlia.eosdescontosefetuados:INSS=0,08 SAL,Faltas=FAL SAL/160,Refei coes,Vales,DescontosEventuais,ImpostodeRenda=0,08 SalarioBruto.enalmenteoseuSalarioLquido:SalarioLquido=SalarioBruto-Descontos.12. Dizemos que uma matriz inteira Ann e uma matrizdepermuta caoseem cadalinha e emcadacoluna houvern 1elementosnulos e um unicoelemento1.Exemplo:Amatrizabaixoedepermuta cao____0 1 0 00 0 1 01 0 0 00 0 0 1____955.4. Matrizes UFMSObserveque__2 1 01 2 00 0 1__nao edepermuta cao.DadaumamatrizinteiraAnn,vericarseA edepermuta cao.13. DadaumamatrizAmn,imprimiron umerodelinhaseon umerodecolunasnulasdamatriz.Exemplo:m = 4en = 4____1 0 2 34 0 5 60 0 0 00 0 0 0____tem2linhasnulase1colunanula.14. Dizemosqueumamatrizquadradainteiraeumquadradomagico1seasomadoselementosdecadalinha,asomadoselementosdecadacolunaeasomadoselementosdadiagonalprincipalesecund ariasaotodasiguais.Exemplo:Amatriz__8 0 74 5 63 10 2__eumquadradomagico.Dada uma matriz quadrada inteira Ann, vericar se A e um quadradomagico.15. (a) ImprimirasnprimeiraslinhasdotriangulodePascal2.11 11 2 11 3 3 11 4 6 4 11 4 10 10 5 1...1O primeiro registro conhecido de um quadrado magico vem da China e data do segundoseculoantesdeCristo.2Descobertoem1654pelomatematicofrancesBlaisePascal.965.4. Matrizes UFMS(b) Imprimir as nprimeiras linhas dotriangulode Pascal usandoapenasumvetor.16. UmjogodepalavrascruzadaspodeserrepresentadoporumamatrizAmnondecadaposi caodamatrizcorrespondeaumquadradodojogo, sendo que 0 indica um quadrado branco e 1 indica um quadradopreto. Indicarnamatrizasposi coesquesaoinciodepalavrashori-zontaise/ouverticaisnos quadrados correspondentes (substituindo oszeros), considerando que uma palavra deve ter pelo menos duas letras.Paraisso,numereconsecutivamentetaisposi coes.Exemplo:Dadaamatriz______0 1 0 1 1 0 1 00 0 0 0 1 0 0 00 0 1 1 0 0 1 01 0 0 0 0 1 0 00 0 1 0 0 0 1 1______asadadeveraser______1 1 2 1 1 3 1 45 6 0 0 1 7 0 08 0 1 1 9 0 1 01 10 0 11 0 1 12 013 0 1 14 0 0 1 1______17. UmamatrizD88pode representaraposi caoatualde um jogode da-mas, sendoque0indicaumacasavazia, 1indicaumacasaocupadaporumape cabrancae 1indicaumacasaocupadaporumape capreta. Supondo que as pe cas pretas estaose movendo no sentido cres-centedas linhas da matrizD, determinaras posi coesdas pe caspretasque:(a) podemtomarpe casbrancas;(b) podemmover-sesemtomarpe cas;(c) naopodemsemover.18. Umcampeonatode futebol foi disputadopor ntimes identicadospelos seus nomes. Para cada time sao considerados os seguintes dados:PG n umerodepontosganhos(3porvitoria,1porempatee0porderrota);GM n umerodegolsmarcados;GS n umerodegolssofridos;S saldodegols(GM-GS);V n umerodevitorias;GA goal averageoumediadegols(GM/GS).975.4. Matrizes UFMS(a) Dados os resultados de mjogos, imprima uma tabela com todos osdados (PG, GM, GS, S, V, GA, igual `aquela que sai no jornal) dosntimes. Cadaresultadoerepresentadonaforma(t1, t2, n1, n2)cujainterpreta caoeaseguinte: nojogot1 t2oresultadofoin1n2.Exemplo:SaoPaulo,Milan,3,2Palmeiras,Crici uma,1,2...(b) Comosmesmosdadosdoitem(a), imprimaaclassica caodostimes no campeonato (do primeiro para o ultimo). A classica caoepelon umerodepontosganhos(PG)eemsegundolugarpelosaldodegols (S). Sehouver empate segundoos dois criterios,classiqueostimesenvolvidoscomoquiser.(c) Um grupo de t torcedores organizou um bol aosobre os resultadosdos mjogos. Cadaresultadocertovale 5pontos (inclusive oplacar) ou3pontos (apenas ovencedor ouempate). Comosdados doitem(a) emais os palpites quesaocompostos dempares de n umeros inteiros(p1, q1), (p2, q2), . . . , (pm, qm),onde o i-esimoparrepresentaopalpitedoi-esimojogo,descubraonomedoganhadordobolao.19. OselementosaijdeumamatrizinteiraAnnrepresentamoscustosdetransportedacidadeiparaacidadej. Dadosnitinerarios, cadaumcomkcidades,calcularocustototalparacadaitinerario.Exemplo:____4 1 2 35 2 1 4002 1 3 87 1 2 5____Ocustodoitinerario03133210 ea03+a31+a13+a33+a32+a21+a10= 3+1+400+5+2+1+5=417.20. Considere n cidades numeradas de 0 a n1 que estao interligadasporumaseriedeestradasdemao unica. Asliga coesentreascidadessaorepresentadaspeloselementos deumamatrizquadradaLnn, cujoselementoslijassumemovalor1ou0,conformeexistaounaoestradadiretaquesaiadacidadeiechegue`acidadej. Assim, oselementosdacolunajindicamasestradasquechegam`acidadej. Porconve caolii= 1.Aguraabaixomostraumexemploparan = 4.985.4. Matrizes UFMS(a) Dadok, determinarquantasestradassaemequantaschegam`acidadek.(b) Aqualdascidadeschegaomaiorn umerodeestradas?(c) Dadok, vericarsetodasasliga coesdiretasentreacidadekeoutrassaodemaodupla.(d) Relacionarascidadesquepossuemsadasdiretasparaacidadek.(e) Relacionar,seexistirem:i. Ascidadesisoladas, istoe, asquenaotemliga caocomne-nhumaoutra;ii. Ascidadedasquaisnaohasada,apesardehaverentrada;iii. Ascidadesdasquaishasadasemhaverentrada.(f) Dadaumaseq uenciademinteiroscujosvaloresestaoentre0en1, vericarse e possvel realizaro roteiro correspondente. Noexemplodado, oroteirorepresentadopelaseq uencia23210,comm = 5,eimpossvel.(g) Dados k e p, determinar se e possvel ir da cidade kpara a cidadeppelas estradas existentes. Voce consegue encontrar omenorcaminhoentreasduascidades?99Modularizacao 6Osalgoritmosquetemosconstrudoateentaosaomuitosimples, poisresolvemproblemassimpleseapresentamapenasoscomponentesmaisele-mentares dos algoritmos: constantes, variaveis, expressoes condicionais eestruturasdecontrole. Entretanto, amaioriadosalgoritmos resolvepro-blemas complicados, cujasolu caopodeser vistacomoformadadevariassubtarefas oum odulo, cadaqual resolvendoumaparteespeccadopro-blema.Nestetopico,veremoscomo escreverum algoritmoconstitudode variosmodulos ecomoestes modulos trabalhamemconjuntopararesolver umdeterminadoproblemaalgortmico.6.1 OQueePorQue?Umm odulonadamaisedoqueumgrupodecomandosqueconstituium trecho de algoritmo com uma fun cao bem denida e o mais independentepossveldasdemaispartesdoalgoritmo. Cadamodulo,duranteaexecu caodoalgoritmo, realizaumatarefaespeccadasolu caodoproblemae, paratal, pode contar com o auxlio de outros modulos do algoritmo. Desta forma,aexecu caodeumalgoritmocontendovariosmodulospodeservistacomoumprocessocooperativo.A constru cao de algoritmos compostos por modulos, ou seja, a constru caodealgoritmosatravesdemodulariza caopossuiumaseriedevantagens: Tornaoalgoritmomaisfacil deescrever. O desenvolvedorpodefocalizar pequenas partes de umproblemacomplicadoe escrever asolu cao para estas partes, uma de cada vez,ao inves de tentarresolveroproblemacomoumtododeumasovez.1006.2. Componentesdeummodulo UFMS Tornaoalgoritmomais facil deler. Ofatodoalgoritmoestardivididoemmodulospermitequealguem, quenaosejaoseuautor,possaentenderoalgoritmomaisrapidamenteportentarentenderosseusmodulosseparadamente,poiscomocadamodulo emenoremaissimples doqueoalgoritmomonolticocorrespondenteaoalgoritmomodularizado, entendercadaumdelesseparadamenteemenoscom-plicadodoquetentarentenderoalgoritmocomoumtododeumasovez. Elevaonveldeabstra cao.E possvel entender o que um algoritmofazpor saber apenasoqueos seusmodulos fazem, semquehajaanecessidade de entender os detalhes internos aos modulos. Alem disso,seosdetalhesnosinteressam,sabemosexatamenteondeexamina-los. Economiadetempo, espa coeesfor co. Freq uentemente, neces-sitamosexecutarumamesmatarefaemvarioslugaresdeummesmoalgoritmo. Umavezqueummodulofoi escrito, elepode,comovere-mosmaisadiante, serchamadoquantasvezesquisermosedeondequisermos no algoritmo, evitando que escrevamos a mesma tarefa maisdeumaveznoalgoritmo,oquenospouparatempo,espa coeesfor co. Estendealinguagem. Uma vez que um modulo foi criado, podemosutiliza-loemoutros algoritmos semque eles sejammodicados, damesmaformaqueusamososoperadores leiaeescrevaemnossosalgoritmos.Amaneiramais intuitivade proceder `amodulariza cao de problemase realizadaatraves dadeni caode ummoduloprincipal, queorganizaecoordena o trabalho dos demais modulos, e de modulos especcos para cadauma das subtarefas do algoritmo. O modulo principal solicita a execu cao dosvariosmodulosemumadadaordem,osquais, antesdeiniciaraexecu cao,recebemdados domoduloprincipal e, aonal daexecu cao, devolvemoresultadodesuascomputa coes.6.2 ComponentesdeummoduloOsmodulosqueestudaremosdaquiemdiantepossuemdoiscomponen-tes: corpoeinterface. Ocorpodeummodulo eogrupodecomandosquecompoeotrechodealgoritmocorrespondenteaomodulo. J aainterfacedeummodulopodeservistacomoadescri caodosdadosdeentradaedesadadomodulo. Oconhecimentodainterfacedeummodulo etudooqueenecessarioparaautiliza caocorretadomoduloemumalgoritmo.1016.3. FerramentasparaModulariza cao UFMSAinterface deummoduloedenidaemtermos deparametros. Umparametroe umtipoespecial devariavel queovalor de umdadosejapassadoentreummoduloequalqueralgoritmoquepossausa-lo. Existemtrestiposdeparametros: parametrosdeentrada,quepermitemquevaloressejampassadosparaummoduloapartirdoalgoritmoquesolicitousuaexecu cao; parametrosdesada,quepermitemquevaloressejampassadosdomoduloparaoalgoritmoquesolicitousuaexecu cao;e parametrosdeentradaesada, que permitem tanto a passagem devaloresparaomoduloquantoapassagemdevaloresdomoduloparaoalgoritmoquesolicitousuaexecu cao.Quando criamos um modulo, especicamos o n umero e tipos de parametrosque ele necessita. Isto determina a interface do modulo. Qualquer algoritmoqueuse um modulodeveutilizarosparametrosquesaoespecicadosnain-terfacedomoduloparasecomunicarcomele.6.3 FerramentasparaModularizacaoHadoistiposdemodulos: fun cao: uma fun cao e um modulo que produz um unico valor de sada.Elapodeservistacomoumaexpressaoque eavaliadaparaum unicovalor,suasada,assimcomoumafun caoemMatematica. procedimento: umprocedimentoeumtipodemodulousadoparavariastarefas,naoproduzindovaloresdesada.As diferen cas entre as deni coes de fun caoe procedimentopermitemdeterminar se um modulo para uma dada tarefa deve ser implementado comoumafun caoouprocedimento. Porexemplo,seum moduloparadeterminaro menor de dois n umeros e necessario,ele deve ser implementado como umafun cao, pois ele vai produzir um valor de sada. Por outro lado, se um moduloparadeterminaromaioreomenorvalordeumaseq uenciaden umeroserequerido, eledeveserimplementadocomoumprocedimento, poiselevaiproduzirdoisvaloresdesada.Vamosconsiderarqueaprodu caodeumvalordesadaporumafun caoe diferente da utiliza cao de parametros de sada ou de entrada e sada. Vere-mos mais adiante que os parametros de sada e de entrada e sada modicam1026.4. CriandoFun coeseProcedimentos UFMSo valor de uma variavel do algoritmo que a chamou, diferentemente do valordesadaproduzidoporumafun caoqueseraumvaloraserusadoemumaatribui caoouevolvidoemalgumaexpressao.6.4 CriandoFuncoeseProcedimentosAmdeescrevermos umafun caoouprocedimento, precisamos cons-truirasseguintespartes: interfaceecorpo. Comoditoantes, ainterfaceeumadescri caodosparametrosdomodulo, enquantocorpoeaseq uenciadeinstru coesdomodulo. Ainterfacedeumafun caotemaseguinteformageral:fun cao()onde nomeeumidenticador unicoquerepresentaonomedafun cao; listadepar ametrosformaiseumalistadosparametrosdafun cao; tipoderetornoeotipodovalorderetornodafun cao.Porexemplo:fun caorealquadrado(realr)Logoaposadescri caodainterfacepodemosdescreverocorpodoalgo-ritmo. Paradelimitaroscomandosquefazempartedafun cao, utilizamosmfun cao.Ocorpodeumafun caoeumaseq uenciadecomandos quecompoeafun caoe quesempre nalizacomumcomandoespecial denominadoco-mandoderetorno. Ocomandoderetorno edaseguinteformaretornaondevalor deretornoeovalor desadaproduzidopelafun cao. Porexemplo:retornax1036.4. CriandoFun coeseProcedimentos UFMSVejamosumexemplodeumafun cao. Suponha quedesejemosconstruirumafun caoparacalcularoquadradodeumn umero. On umerodeveserpassadoparaafun cao, quecalcularaoseuquadradoeodevolveraparaoalgoritmoque a solicitou. Vamosdenominar estafun cao de quadrado,comomostradoaseguir://fun caoparacalcularoquadradodeumn umerofun caorealquadrado(realr)//declara caodevariaveisrealx//calculaoquadradox r r//retornaoquadradocalculadoretornaxmfun caoAinterfacedeumprocedimentotemaseguinteformageral:procedimento()onde nome e um identicador unico que representa o nome do procedimento; listadepar ametros formaiseumalistadosparametros doprocedi-mento.Porexemplo,procedimentolern umero(refrealval)O corpo de um procedimento e uma seq uencia de comandos que nao pos-suicomandoderetorno,poisapenasfun coespossuemtaltipodecomando.Paradelimitaroscomandosquefazempartedoprocedimento, utilizamosmprocedimento.Vejamos um exemplo de um procedimento. Suponha que desejemos cons-truirumprocedimentoparalerumn umeroepassaron umerolidoparao1046.5. ChamandoFun coeseProcedimentos UFMSalgoritmoquesolicitouaexecu caodoalgoritmoatravesdeumparametrode sada. Denominemos este procedimento de lern umero,como mostrado aseguir://procedimentoparalerumn umeroprocedimentolern umero(refrealval)//Solicitaaentradadon umeroescrevaEntrecomumn umero:leiavalmprocedimentoAqui, val eoparametrodesadaqueconteraovalor deentradaqueserapassadoparaoalgoritmo que solicitar aexecu cao doprocedimentolern umero. Apalavra-chaveref, queantecedeonomedavariavel nalistadeparametrosformaisdoprocedimento, eutilizadaparadenirval comoparametrodesadaouentradaesada.6.5 ChamandoFuncoeseProcedimentosFun coeseprocedimentosnaosaodiferentesapenasnaformacomosaoimplementados, mas tambem na forma como a solicita cao da execu cao deles,ousimplesmentechamada,deveserrealizada. Achamadadeumafun caoeusadacomoumvalorconstantequedeveseratribudoaumavariaveloucomopartedeumaexpressao, enquantoachamadadeumprocedimentoerealizadacomoumcomandoaparte.Comoexemplo, considereumalgoritmoparalerumn umeroeexibiroseuquadrado. Estealgoritmodeveutilizaroprocedimentolern umeroeafun caoquadrado, vistosantes, paraleron umeroeobteroseuquadrado,respectivamente. Oalgoritmosegueabaixo://algoritmoparacalculareexibiroquadradodeumn umero//fornecidocomoentradaalgoritmocalculaquadrado//declara caodevariaveisrealnum,x//leumn umero1056.6. PassagemdeParametros UFMSlern umero(num)//calculaoquadradodon umerolidox quadrado(num)//escreveoquadradoescrevaOquadradodon umero e:,xmalgoritmoNoteadiferen cadachamadadoprocedimentolern umeroparaacha-madadafun caoquadrado. Nachamadadoprocedimento, temosumains-tru caoporsi so. Poroutrolado,achamadada fun cao ocupaolugarde umvalorouexpressaoemumainstru caodeatribui cao. Istoporqueachamadaquadrado(num)esubstitudapelovalorderetornodafun cao.Tantonachamadadoprocedimentolern umeroquantonachamadadafun caoquadrado, temos umparametro: avariavel num. Nachamadadoprocedimentolern umero,num eumparametrodesada,comodenidonainterfacedoprocedimento, e, portanto, aposaexecu caodoprocedimento,num contera o valor lido dentro do procedimento. Ja na chamada da fun caoquadrado, numeumparametrodeentrada, comodenidonainterfacedafun cao,e,assimsendo,ovalordenum epassadoparaafun cao.Avariavel numedenominadaparametroreal. Umparametrorealespecicaumvalor passadoparaomodulopeloalgoritmoqueochamououdomoduloparaoalgoritmoqueochamou. Osparametrosformaissaoaqueles da declara cao do modulo. A lista de parametros reais deve concordaremn umero,ordemetipocomalistadeprametrosformais.6.6 PassagemdeParametrosOsvaloresdosparametrosreaisdeentradasaopassadosporummeca-nismo denominado c opia, enquanto os valores dos parametros reais de sadaeentradaesadasaopassadospor um mecanismodenominadoreferencia.Omecanismodepassagempor copiafuncionadaseguinte forma. Ovalordoparametroreal (umaconstanteouovalordeumavariavel ouex-pressao) de entrada e atribudo ao parametro formal quando da chamada doprocedimento/fun cao. Porexemplo,nachamada1066.7. EscopodeDadoseCodigo UFMSx quadrado(num)ovalordavariavel numeatribudoaoparametroformalrdafun caoqua-drado.Nomecanismodepassagemporreferencia,quandodachamadadopro-cedimento/fun cao, oparametroformalpassaacompartilharamesmaareadearmazenamentodeparametroreal, assim, qualquer altera caonovalordoparaemtroformal feitapeloprocedimento/fun caoacarretaraumamo-dica caonoparametroreal quandodoterminodoprocedimento/fun cao.Sendoassim,quandoachamadalern umero(num)eexecutada,a variavelreal num e a variavelformal val(que estaprecedidadapalavrachaveref)compartilhamumamesmaareadearmazenamento,assim,numevalcontemomesmovalor. Quando efeitaaleituradodadoearmazenadaemval,estaatualiza caoafetaraovalordenum. Aoterminodoprocedimentoavariavelnumconteraovaloratualizado.Devemosobservarqueosparametrosreaisdesadaedeentradaesadadevem obrigatoriamenteser variaveis, uma vez que nao faz sentido modicarovalordeumaconstanteoudeumaexpressao.6.7 EscopodeDadoseCodigoOescopodeummodulo(ouvariavel) deumalgoritmoeaparteoupartesdoalgoritmoemqueomodulo(ouvariavel)podeserreferenciado.Quandoiniciamosoestudodemodulariza caoenatural nosperguntarmosqual e o escopo de um dado modulo e das constantes ou variaveis nele presen-tes. Emparticular,oescopodeummodulodeterminaquaiss aoosdemaismodulosdoalgoritmoquepodemchamar-lheequaiselepodechamar.Osmodulosdeumalgoritmosaoorganizadospornveis. Noprimeironvel,temosapenasoalgoritmoprincipal. Aquelesmodulosquedevemseracessadospeloalgoritmoprincipal devemserescritosdentrodelee, nestacondi cao,sao ditospertencerem aosegundo nvel. Os modulos escritosden-tro de modulos de segundo nvel sao ditos modulos de terceiro nvel. E assimsucessivamente. Porexemplo://algoritmoparacalcularoquadradodeumn umerofornecido//comoentrada1076.7. EscopodeDadoseCodigo UFMSalgoritmocalculaquadrado//moduloparacalculodoquadradodeumn umerofun caorealquadrado(quadrador)//declara caodevariaveisrealx//calculaoquadradox r r//passaparaoalgoritmochamadorovalorobtidoretornaxmfun cao//moduloparalerumn umeroprocedimentolern umero(refrealval)//solicitaumn umeroaousuarioescrevaEntrecomumn umero: leiavalmprocedimento//declara caodeconstantesevariaveisrealnum,x//leumn umerolern umero(num)//calculaoquadradox quadrado(num)//escreveoquadradoescrevaOquadradodon umero e: ,xmalgoritmoAqui,desejavamosqueafun caoquadradoeoprocedimentolern umerofossem chamados pelo modulo principal e, por isso, escrevemos tais modulosdentrodomoduloprincipal, nosegundonvel dahierarquiamodular do1086.8. ProblemaseSolu coes UFMSalgoritmo.A regra para determinar o escopo de um modulo e bastante simples: ummodulo Xescrito dentro de um modulo A qualquer pode ser acessado apenaspelomoduloAouporqualquermoduloescritodentrodeAoudescendente(diretoounao)dealgummodulodentrodeA.Como exemplo, considere umalgoritmo no qual o modulo principalcontemoutrosquatromodulos, S1, S2, F1, F2. Porsuavez, S1contemmaisdoismodulos, S3eF3; eF2contemosmodulosS4eF4. Estasi-tua cao e ilustrada por um diagramana Figura??. De acordocom as regrasdeescopodescritasanteriormente, omoduloF3sopodeserchamadoporS1eS3,enquantoomoduloF1podeseracessadoportodososmodulos.Variaveispodemserlocaisouglobais. Umavariavel (constante)editalocal aummodulose elae declaradanaquele modulo. Por exemplo, avariavel xdafun caoquadradoe umavariavel local aestafun cao. Umavariavel e dita global a ummodulo quando ela nao esta declarada nomodulo, mas podeser referenciadaapartir dele. Nestecurso, considera-remosquevariaveissaosemprelocais, istoe, nenhummodulopoderarefe-renciarumavariaveldeclaradaemoutromodulo.6.8 ProblemaseSolucoesNesta se cao, veremos tres problemas envolvendo fun coes e procedimentosesuasrespectivassolu coes.1. Escreva umalgoritmo paraler dois n umeros e exibir omenor dosdois. A verica caode qual deles e o menor deve ser realizadapor umafun cao.//algoritmoparaoencontrareexibiromenordedoisn umerosalgoritmoencontramenordedois//moduloparaencontraromenordedoisn umerosfun caointeiromenordedois(inteiroa,b)//declara caodevariaveisinteiromenormenor asea > bentaomenor b1096.8. ProblemaseSolu coes UFMSmseretornamenormfun cao//declara caodeconstantesevariaveisinteirox,y,z//ledoisn umerosescrevaEntrecomdoisn umeros: leiax,y//obtemomenordosdoisz menordedois(x, y)//escreveomenordosdoisescrevaOmenordosdois e: ,zmalgoritmo2. Escreva um algoritmo para ler tres n umeros e exibir o maior e o menordostres. Aobten caodomaioredomenorn umerodeveserrealizadaporumprocedimento.//algoritmoparaoencontrareexibiromenoreomaiordetres//n umerosalgoritmoencontraminmax//moduloparaencontraromenoreomaiordetresn umerosprocedimentominmax(inteiroa,b,c,refinteiromin,max)//encontraomaiordostressea bea centaomax asenaoseb centaomax bsenaomax cmsemse1106.8. ProblemaseSolu coes UFMS//encontraomenordostressea bea centaomin asenaoseb centaomin bsenaomin cmsemsemprocedimento//declara caodeconstantesevariaveisinteirox,y,z,menor,maior//letresn umerosescrevaEntrecomtresn umeros: leiax,y,z//obtemomenoreomaiordostresminmax(x, y, z, menor, maior)//escreveomenoreomaiordostresescrevaOmenordostrese: ,menorescrevaOmaiordostrese: ,maiormalgoritmo3. Escreva um algoritmo para ler tres n umeros e escreve-los em ordem naodecrescente. Utilize, obrigatoriamente, umprocedimentoparatrocarovalordeduasvariaveis.//algoritmoparalertresn umeroseescreve-losemordem//naodecrescentealgoritmoordenatres//moduloparatrocarovalordeduasvariaveisprocedimentotroca(refinteiroa,b)//declara caodevariaveisinteiroaux1116.8. ProblemaseSolu coes UFMS//trocaosvaloresaux aa bb auxmprocedimento//declara caodeconstantesevariaveisinteirol,m,n//leostresn umerosescrevaEntrecomtresn umeros: leial,m,n//encontraomenorepoeemlsel > moul > nentaosem nentaotroca(l, m)senaotroca(l, n)msemsesem > nentaotroca(m, n)mseescrevaOsn umerosemordemnaodecrescente: ,l,m,nmalgoritmoNeste algoritmo,os parametros do procedimento trocasao parametrosdeentradaesada, poisparatrocarosvaloresdosparametrosreaisdentrode umprocedimento, estes valores devemser copiados paraosparametrosformaiseasmudan casnosparametrosformaisdevemserreetidasnosparametrosreais,umavezqueasvariaveisprecisamretornardoprocedimentocomosvalorestrocados.BibliograaO textodeste captulofoi elaborado a partir dos livros abaixorelaciona-dos:1126.8. ProblemaseSolu coes UFMS1. Farrer,H.et. al. AlgoritmosEstruturados. EditoraGuanabara,1989.2. Shackelford, R.L. Introduction to Computing and Algorithms. Addison-WesleyLongman,Inc,1998.113ListadeExerccios1. Para se determinar o n umero de lampadas necessarias para cada comodode uma residencia, existem normas que fornecem o mnimo de potenciade ilumina caoexigidapor metroquadrado (m2) conformea utiliza caodestecomodo. Suponha quesoseraousadaslampadasde60W.Sejaaseguintetabela:Utiliza cao Classe Potencia/m2quarto 1 15saladeTV 1 15salas 2 18cozinha 2 18varandas 2 18escritorio 3 20banheiro 3 20(a) Fa ca um modulo (fun cao ou um procedimento) que recebe a classedeilumina caodeumcomodoesuasduasdimensoesedevolveon umerodelampadasnecessariasparaocomodo.(b) Fa ca umalgoritmo que leia umn umeroindeterminadode in-forma coes,contendocadaumaonomedocomododaresidencia,sua classe de ilumina cao e as suas duas dimensoes e, com base nomoduloanterior, imprimaaareadecadacomodo, suapotenciadeilumina caoeon umerototal delampadasnecessarias. Alemdisso, seu algoritmo deve calcular o total de lampadas necessariaseapotenciatotalparaaresidencia.2. Acomissaoorganizadoradeumrallyeautomobilsticodecidiuapurarosresultadosdacompeti caoatravesdeumprocessamentoeletronico.Umdos programas necessarios paraaclassica cao das equipes e oqueemiteumalistagemgeraldodesempenhodasequipes,atribuindopontossegundodeterminadasnormas.(a) Escreva um modulo (fun cao ou procedimento) que calcula os pon-tosdecadaequipeemcadaumadasetapasdorallye, seguindooseguintecriterio. Sejaovalor absolutodadiferen caentreotempo-padraoeotempodespendidopelaequipenumaetapa(fornecidoscomoparametros):114ListadeExerccios UFMS < 3minutos atribuir100pontos`aetapa3 5minutos atribuir80pontos`aetapa > 5 atribuir80 55pontos`aetapa(b) Fa caumalgoritmoqueleiaostempos-padrao(emminutosdeci-mais) para as tres etapas da competi cao, leia um n umero indeter-minado de informa coes, contendo para cada equipe o seu n umerode inscri cao e os tempos (em minutos decimais) despendidos paracumprir astresetapase,utilizandoo modulo anterior,calculeospontosobtidosporcadaequipeemcadaetapa, asomatotal depontosporequipe,eaequipevencedora.3. (a) Fa caumafun caoquantosdiasquerecebeodia,omeseoanodeumadataeretornaumvalorquecontemon umerodediasdoanoateadatafornecida.(b) Fa caumalgoritmoquerecebenparesdedatas, ondecadapardeve ser fornecido no formato dia1, mes1, ano1, dia2, mes2,ano2, veriqueseasdatasestaocorretasemostreadiferen ca,emdias,entreessasduasdatas. Utilizeafun caoanteriorparaocalculodototaldediasdecadadata.4. (a) Escrevaumafun caoquerecebedoisn umerosinteirospositivosedeterminaoprodutodosmesmos, utilizandooseguintemetododemultiplica cao:i. dividir,sucessivamente,oprimeiron umeropor2,atequeseobtenha1comoquociente;ii. paralelamente,dobrar,sucessivamente,osegundon umero;iii. somar os n umeros da segunda coluna que tenham um n umeromparnaprimeiracoluna. Ototal obtidoeoprodutopro-curado.Exemplo: 9 69 6 64 122 241 48 4854(b) Escrevaumprogramaqueleianparesden umerosecalculeosrespectivosprodutos,utilizandoafun caoanterior.5. Umn umeroaeditoserpermutac aodeumn umerobseosdgitosdeaformamumapermuta caodosdgitosdeb.Exemplo:5412434 e uma permuta cao de 4321445,mas nao e uma per-muta caode4312455.115ListadeExerccios UFMSObserva c ao: considere que o dgito 0 (zero)nao aparecenosn umeros.(a) Fa ca uma fun cao contadgitos que, dados um inteiro n e um inteirod,0 < d 9,devolvequantasvezesodgitodapareceemn;(b) Utilizandoafun caodoitemanterior,fa caum algoritmoqueleiadoisn umerosaeberespondasea epermuta caodeb.6. Umn umerob editosersuxodeumn umeroaseon umeroformadopelos ultimosdgitosdeasaoiguaisab.Exemplo:a b567890 890 suxo1234 1234 suxo2457 245 naoesuxo457 2457 naoesuxo(a) Construaumafun caosuxoquedadosdoisn umerosinteirosaebvericaseb eumsuxodea.(b) Utilizandoafun caodoitemanterior, escrevaumalgoritmoqueleia dois n umeros inteiros ae b e verica se omenor deles esubseq uenciadooutro.Exemplo:a b567890 678 b esubseq uenciadea1234 2212345 a esubseq uenciadeb235 236 Umnao esubseq uenciadooutro7. Umaseq uenciadenn umerosinteirosnaonuloseditam-alternanteseeconstitudapor msegmentos: oprimeirocomumelemento, osegundo com dois elementos e assim por diante ate a m-esima,com Melementos. Alem disso, os elementos de um mesmo segmento devem sertodos pares ou todos mpares e para cada segmento,se seus elementosforem todos pares (mpares), os elementos do segmento seguinte devemsertodos mpares(pares).Porexemplo:Aseq uencia comn =10 elementos: 8 37 2104 513411 e 4-alternante.Aseq uenciacomn = 3elementos: 728 e2-alternante.A seq uencia com n = 8 elementos: 1 124 2135 126 nao e alternante,poiso ultimosegmentonaotemtamanho4.116ListadeExerccios UFMS(a) Escreva uma fun cao blocoque recebe comoparametro um inteiron e len inteirosdo teclado,devolvendoum dos seguintes valores:0, seosnn umeroslidosforempares;1, seosnn umeroslidosforem mpares;-1, seentreosnn umeroslidoshan umeroscomparidadesdiferentes.(b) Utilizandoafun caodoitemanterior,escrevaumalgoritmoque,dadosuminteiron(n 1)eumaseq uenciadenn umerosintei-ros, vericaseelaem-alternante. Oalgoritmodeveimprimirovalordemoudarumarespostadizendoqueaseq uencianaoealternante.8. Considereasseguintesformulasderecorrencia:___F1= 2;F2= 1;Fi= 2 Fi1 +Gi2i 3.___G1= 1;G2= 2;Gi= Gi1 + 3 Fi2i 3.Podemosentaomontaraseguintetabela:i 1 2 3 4 5 . . .Fi2 1 3 8 24 . . .Gi1 2 8 11 20 . . .Esteexerccioestadivididoemtrespartes.(a) Soparaversevoceentendeuasformulas,qualeovalordeF6eG6?(b) Fa caum procedimento de nome valor que recebe um inteiro K 1edevolveFkeGk.Exemplo:Parak= 2,oprocedimentodeveretornarosvalores1e2. Parak=3, afun caodevedevolverosvalores3e8.Parak= 4,afun caodevedevolverosvalores8e11.Observa c ao: naoutilizevetoresnesteexerccio.(c) Fa caumalgoritmoqueleuminteiron > 2eimprimeosvaloresFn2 + Gn+200eFn+200 + Gn2. Seualgoritmodeveobrigatori-amenteutilizaroprocedimentodoitemanterior.9. Umconjuntopodeserrepresentadoporumvetordaseguinteforma:V [0] eotamanho do conjunto;V [1], V [2], . . .saooselementosdo con-junto(semrepeti coes).(a) Fa ca uma fun cao intersec c ao que dados dois conjuntos de n umerosinteiros A e B, constroi um terceiro conjunto C que e a intersec caode Ae B. Lembre-se deque emC[0]a sua fun caodeve colocarotamanhodaintersec cao.117ListadeExerccios UFMS(b) Fa caum algoritmoque leiaum inteiron 2euma seq uenciadenconjuntosden umerosinteiros(cadaumcomnomaximo100elementos)econstruaeimprimaovetorINTERquerepresentaaintersec caodosnconjuntos.NOTE que NAO eprecisolertodos os conjuntos de uma so vez. Vocepode ler os dois primeiros conjuntos e calcular a primeira instersec cao.Depois,leiaoproximoconjuntoecalculeumanovaintersec caoentreesseconjuntolidoeoconjuntodaintersec caoanterior, eassimpordiante.10. (a) Escrevaumafun caoquerecebecomoparametrosumvetorrealAcomnelementoseumvetorBcommelementos, ambosre-presentandoconjuntos, evericaseAestacontidoemB(A B).(b) Utilizando a fun cao anterior verique se dois conjuntos sao iguais(A = BseesomenteseA BeB A).11. (a) Escrevaumafun caoquetrocaoconte udodeduasvariaveis.(b) Escrevaumafun caoquerecebedoisinteiros, iej, umamatrizrealAmnetrocaalinhaipelalinhaj. Utilizeoprocedimentodoitemanterior.12. Dizemos que uma matriz Ann e um quadradolatino de ordem n se emcadalinhaeemcadacolunaaparecemtodososinteiros1, 2, 3, . . . , n(ouseja,cadalinhaecoluna epermuta caodosinteiros1, 2, . . . , n).Exemplo:____1 2 3 42 3 4 14 1 2 33 4 1 2____Amatrizacimaeumquadradolatinodeordem4.(a) Escreva uma fun c ao que recebe como parametro um vetor inteiroV comnelementosevericaseemV ocorremtodososinteirosde1an.(b) Escrevaumafun caoque recebe como parametros umamatrizinteira Anne umndice je verica se na coluna jde A ocorremtodososinteirosde1an.(c) Utilizando as fun coes acima, verique se uma dada matriz inteiraAnneumquadradolatinodeordemn.118Ponteiros 7A memoria do computador e constituda de muitas posi coes (geralmentemilhoes), cadaqual podearmazenar umpeda codedado. Cadaposi caode memoriae denominadacelula. Estas posi coes saomuitosimilares `asvariaveisquetemosutilizado, comumadiferen ca: aoescrevernossosalgo-ritmos,criamos nossas variaveissimplesmente dando nome aelas,enquantoquenocomputadorestascelulasexistemsicamente.Estas celulas dememoriasaonumeradas seq uencialmente. Quandooprocessador do computador precisa acessar uma celula de memoria, ele a re-ferencia pelo seu n umero, que tambem conhecemos comoendere co. Quandoumalgoritmoeescritoemumalinguagemdeprograma caoparaserusadoemum computador,cadaidenticadordevariavelusado noalgoritmoeas-sociadocomoendere codaceluladememoriaqueseraalocadaparaaquelavariavel. Nas linguagens de programa cao modernas, o programador nao pre-cisasepreocuparcomisto. Noambientedalinguagemdeprograma caoemantida uma lista dos identicadores usados pelo programador e que associaautomaticamenteestescomosendere cosdascelulasdememoria.Umponteiroeumacelulaquearmazenaoendere codeoutraceluladedados. Olhando o valor do ponteiro, o computador determina onde olhar namemoria pelo valor do dado apontado pelo ponteiro. De fato, um ponteiro eum tipo especial de variavelcujo conte udo e um endere co de memoria. VejaumexemplonaFigura7.89008900 8900 ppFigura7.1: Ponteiroparmazenandooendere co8900esuarepresenta caoesquematicaUsaremosaseguintenota caoparadeclararumavariaveltipoponteiro119UFMStipododadoEstecomandodeclaraumavariavel denomeidenticador queapontapara uma celula armazenando umdado tipodado. Por exemplo, na de-clara caointeirop,qas variaveis p e q sao do tipo ponteiro para inteiro, isto e, ambas poderaoapontarparaumavariavel dotipointeiro. Comoaquantidadedecelulasde memoria utilizada por um tipo varia conforme o tipo, a variavelponteiroapontaparaaprimeiraposi caoepelotipoelesabequantascelulasapartirdaquelaposi caocontemodado.Para podermos entender a base de ponteiros, consideraremos a Figura 7,onde mostramos as variaveis p e qe seu respectivo conte udos, bem como suarepresenta caoesquematica. Nestagura, mostramosduasvariaveispeq,ambossaovariaveisdotipoponteiro,isto earmazenamendere cos,eambasapontamparaumavariavelinteiraquearmazenaovalor4.44 300 300ppqqFigura7.2: Arepresenta caoesquematicadosponteirospeqeseusrespec-tivosconte udo: oendere co300Assim, o algoritmo pode acessar o valor n umerico 4 referenciando o valorapontado por p ou referenciando o valor apontado por q. Isto e feito atravesdooperadorunario. Aoreferenciarmosumponteiroestamosseguindooponteiroevendoparaondeeleaponta. Comopeumponteiroparaotipointeiro, istoe armazenaovalor doendere codememoriaondeestevalorinteirose encontra,precisamosde um mecanismo para que elepossa alteraro valor da celula de memoria para onde aponta. Assim p 9 altera o valordavariavelparaaqualpaponta. Nestecaso,ovalordavariavel apontadapor q foi tambemalterada, umavez queambos apontamparaomesmoendere co.NaFigura7mostramosoqueocorreseatribuirmosovalor9`avariavelapontadaporp: estaremosmudandotambemovaloroqualqaponta.120UFMS9p qFigura 7.3: Altera cao do conte udo para onde p aponta acarreta mudan ca noconte udoparaondeqapontaAvariavel ponteirocontemumendere co. Paraalterar ovalor deumponteirodevemosatribuirumnovovaloraele. Porexemplo, quandomu-damosovalordeqparafaze-loapontarparaamesmacelulaqueraponta,utilizaremososeguintecomando:q rEstecomandosignicaquenos mudamosovalor deq deformaqueeleapontaparaoendere codememoriaparaoquelraponta. Istotemomesmosignicadodecopieoendere coarmazenadoemrparaq.AFigura7.4(a)mostraoqueaconteceraseavariavelqapontarparaavariavel inteiraapontadaporr. Oalgoritmopoderaobterovalorarmaze-nadonelareferenciandotantorquantoq.9 3 pqr93pqrFigura7.4: ManipulandoponteirosSeagoraquisermosqueraponteparaaposi caoparaaqual paponta,usaremosocomandor p.Devemosnotarqueqnaosoreferencioudiferentesvaloresmastambemar-mazenoudiferentescelulasdememoria(Figura7).93 p qrFigura7.5: ManipulandoponteirosSe um ponteiro nao estiver apontando para nenhuma celula, diremos queseuvalorenulo. Ovalornulonaoeamesmacoisaquenenhumvalor. Ao121UFMSinvesdisso, eleeumvalorparticularquesignicaqueesteponteironaoestaapontandoparanada.Atribumosovalornuloparaumavariavel apontadorratravesdose-guintecomando:r nuloNaFigura7desenhamosumponteironulocomoumaterramento(ele-tricidade).9 3 pqrFigura7.6: OponteirorapontandoparanuloAoreferenciarmosumponteiroeledeveestar apontandoparaalgumacelula. Assim,nestecontexto, oseguintecomandoeincorretor 5umavezquernaoapontaparanenhuma posi caodememoria. Paracorrigiristopoderamosfazerr pr 5eteramosperapontandoparaoendere codememoriacujovalore5(Figura7).53 p q rFigura7.7: Resultadodepoisdoscomandosr per 5Se quisermos obter oendere code memoriade umavariavel devemosutilizar o operador unario &. Assim se tivermos uma variavel do tipo inteiroval,contendoovalor7,oresultadodocomandop &valeaatribui caodoendere codevariavalval `ap(Figura7).1227.1. TiposBase UFMS573p q rvalFigura7.8: Atribui caodoendere codeumavariavel tipointeiroparaumponteirpp7.1 TiposBaseAte opresente momento, consideramos quecadavariavel ocupaumaregiaodamemoriaenaonospreocupamoscomaquantidadedememoriaocupadapor cadaumdos tipos. Vimos queumponteiroapontaparaaprimeiraposi caodememoriaquecontemodado. Parasabermosquantasposi coes de memoria, a partir da inicial, contem o valor armazenado devemosolharotipobasedavariavelponteiro.Cadalinguagemde programa cao dene umaquantidade de memoriautilizadapor cadaumde seus tipos basicos. Oconceito de ponteiros eimplementado em linguaguem de programa cao considerando esta quantidadedememoria, tantoparaefeitodealoca caoquantoparamovimenta caodeponteiros. Nestetextoutilizaremosaseguinteconven caoTipo UnidadesdeMemoriacaracter 1logico 1inteiro 2real 4O objetivo de xarmos uma quantidade de memoria que os diversos tiposutilizamseravistomaisadiante.7.2 OperacoescomPonteirosPodemosutilizarduasopera coescomponteiros: somaesubtra cao. De-vemos lembrar queponteiros armazenamendere cos dememoriaondeumdado de um determinado tipo base esta armazenado. Assim estas opera coes1237.3. PonteiroseVetores UFMSlevamemcontaaquantidadede memorianecessariaparaarmazenarotipobase. Porexemplo, seconsiderarmosumponteiropqueapontaparaumavariaveldotipointeiroarmazenadanoendere co200,aatribui caop p + 1faracomquepaponteparaaprimeriaposi caodememoriaaposointeiro.Comoconvencionamos queuminteiroutilizaduasunidades dememoria,oconte udodepsera202(enao201!). Omesmoraciocniovaleparaaopera caodesubtra cao. Seovalorinicialdepfor200,ocomandop p 1faracomqueovalordepseja198.Cadavezqueovalor deumponteiroeincrementadoeleapontaparaoproximoelementodeseutipobase. Cadavezqueumponteiroedecre-mentadoelaapontaparaoelementoanterior. Emambososcasosleva-seem consider cao a quantidade utilizadapelo tipo base. Veja Figura 7.2comoexemplo.0204020302020201019901980200Figura7.9: Memoriaocupadaporuminteiroeseusrespectivosendere cosAsopera coesaritmeticasdeponteirosacimasomentepodemserfeitasentreponteiroseinteiros(constante,variaveisouexpressoes). Nenhuma ou-traopera caoepermitidacomponteiros.7.3 PonteiroseVetoresNestase caovamos considerar os ponteiros demaneirasimilar aoqueocorrenalinguagemC. Quandoutilizamos somentoonomedeumvetor1247.4. Aloca caoDinamicadeMemoria UFMSestamos, defato, referenciandooendere codaprimeiraposi caodovetor.Assim, seconsiderarmosumvetorAquecontemelementosdotipointeiroeumavariavelpdotipoponteiroparainteiro,aatribui caop Aevalidaenestecasoparmazenaraoendere codaprimeiraposi caodovetorA. Diantedistoeconsiderandoasopera coesaritmeticasdeponteirospodemos verque p +1 sera um apontadorpara a proxima posi caodo vetor.Alemdisso, seconsiderarmosqueAcome cacom ndice1, A[5] e(p + 4)acessamomesmoelemento,nestecasooquintoelementodovetor.Observamosque(p + 4) ediferentedep + 4,umavezqueooperadortemprecedenciasobreosdemais.Vimosduasformasdeacessaroselementosdeumvetor: usandoain-dexa caodamatrizouusandoaartimeticadeponteiros. Surgeaquestao:qualdelasutilizar?7.4 AlocacaoDinamicadeMemoriaRelembremosdasse coesanterioresque, quandofazemosasdeclara coesdevariaveis, estamosfazendoaloca caoestaticadememaria, ouaindaqueestamosalocandomemariaemtempodecompila cao. Quandoexecutamosumprograma, aeleedestinadoumblocodememoriadisposto, emgeral,comoilustradonaFigura7.4.Ocodigo doprogramagerado pelocompilador e ligador e carregadonapartemaisbaixadoblocodememoria. ASvariaveisglobaiseaoutrasvariaveis temporarias criados pelo compilador ocupam uma area de memoriaimediatamenteacimadaareadecodigo. Orestantedoblocodememoriae divididoemduas areas: pilhae heap. Apilhae usadaparaarmaze-nar variaveis locais, parametros, valores de retornoe outras informa coesnecessariasdurantechamadasamodulosrealizadasnoprograma. Apilhaeaheapsaocolocadas emposi coes opostasnaarearestantedoblocodememoria, ecadaumadelascrescedetamanhoemdire coeesopostas(umaemdire caooaos endere cos mais altos eoutraemdire caooaos endere cosmaisbaixos), detal formaquecadaumadelaspossamudardetamanhosemafetaruma`aoutra. O unicoproblemaqueocorreequandoaquanti-dade de memoria livre no bloco de memoria nao e suciente para comportarocrescimentodapilhaedaheap.Em muitas situa coes,a quantidade de memoria que um programa neces-1257.4. Aloca caoDinamicadeMemoria UFMSPilhaHeapVariaveisPrograma000000Baixa111111AltaFigura7.10: Organiza caodaMemoriasita nao e conhecida em tempo de compila cao. Considere o seguinte exemplobastantesimplesqueilustraessasitua cao. SejaSumconjuntoden umerosinteiros. Deseja-seum programa para determinar os elementos de Sque saomaioresque a mediaaritmeticados inteirosemS. Saodados de entradadoprograma: aquantidadedeelementosemSeoselementosdeS. Parare-solver este problema e necessario que os elementos de Ssejam armazenados.Oproblemaaquiequedesconhecemos, emtempodecompila cao, aquan-tidadedememoriaqueseranecessariaparaarmazenarS(essainforma caososeraconhecidaemtempodeexecu cao). Ateentao, temosresolvidoessetipodeproblema,considerandoaexistenciadeumlimitantesuperiorparaotamanhodeSeentaoalocandomemoriagrandeosucienteparacom-portaromaiortamanhoesperadopara S. Porexemplo,seolimitanteparaotamanhodeSe100, usamosumvetordetamanho100paraarmazenaroselementosdeS. Obviamente, seotamanhodeSformenorque100oprogramateriaalocadomaismemoriadoquenecessitava.Aaloca caodinamicadememoriaresolveesteproblema. Elaconsistenoprocessodealocar memoriaemtempodeexecu caoconformeaneces-sidadedoprograma. Aheapeamemoriareservadaparaser usadapelaaloca caodinamica. Paraqueaquantidadedememoriadisponvelnaheapnao sobreponha a area de pilha, e recomendado que a memoria alocada dina-micamente seja liberada pelo programa `a medida que nao e mais necessaria.Asseguintesopera coessaousadaspeloalgoritmoparaaloca caoelibera cao1267.4. Aloca caoDinamicadeMemoria UFMSdememoriadinamica: Aloque(p,n)p e um ponteiro e n e a quantidade de memoria, em unidades relativasaotipobasedep, aser alocadadinamicamente. Aloqueiraalocarnposi coesconsecutivasdememoria,cadaumadelasdotamanhone-cessarioparaarmazenarumvalordotipobasedep, eatribuirapoendere coinicialdamemoriaalocada. Podeocorrerfalhanaaloca cao,quando a quantidade de memoria requerida nao pode ser alocada. Nes-sescasos, Aloqueatribui ovalornuloap. Ovalordepsempredeveservericadoapos umachamadaaAloque,paraque haja garantiadequehouvesucessonaaloca cao. Libere(p)p eumponteiro. Libereiraliberaramemoriaanteriormentealocada,cujo endere co inicial estaarmazenado em p. O espa co de memoria de-salocado (liberado) torna-se livre para ser usado por futuras chamadasaAloque.Desta forma, podemos evitar o desperdcio de memoria alocando exatamenteaquantidadedememoriaque oprogramanecessita. Emnossoexemploan-terior, podemos usar umponteiroparainteironolugar dovetor de 100posi coese,entao, aposlerotamanhodeSefetuarumachamadaaAloquepara alocaraquantidade de memorianecessariaparaarmazenaroselemen-tosdeS. Essaideiaestailustradanoseguintealgoritmo:AlgoritmoExemplointeirop,n,i,somarealmedialeianAloque(p,n)if p =nulothenescrevaNaohamemoriasucienteelsesoma 0foride0aten 1doleia(p +i)//omesmoquep[i]soma soma+(p +i)endformedia soma/nforide0aten 1doif (p +i)>mediathenescreva(p +i)1277.5. PonteirosparaPonteiros UFMSendifendforendifLibere(p)Fimalgoritmo7.5 PonteirosparaPonteirosUmponteiroparaponteiroecomosevoceanotasseemsuaagendaon umerodotelefone de umaempresaque fornecesse n umerode telefonesresidenciais. Quando voceprecisardo telefonede uma pessoavoceconsultasuaagenda, depoisconsultaaempresaeelateforneceon umerodesejado.Entenderponteiroparaponteirorequerconhecimentodeponteiro. Chama-se nvel de indire cao ao n umero de vezes que temos que percorrer para obteroconte udodavariavel nal. As variaveis dotipoponteirotemnvel deindire caoum. As variaveis dotipoponteiroparaponteirotemnvel deindire caodois. Setivermosumavariavel queeumponteiroparaponteiroparainteiro, paraobtermosovalordointeiroprecisamosfazerdoisnveisdeindire coes.89008900 9100910091008900 9100ppFigura7.11: Exemploondep eumponteiroparaponteiroPodemos declarar um ponteiro para um ponteiro com a seguinte nota cao:tipodado identicadoronde: identicador e o conte udo da variavel apontada e identicadoreoconte udoponteirointermediario.AlgoritmoExemplo2inteiroa,b,p,ppa 2b 3p &a//precebeendere codeapp &p//ppapontaparaoponteiropousejaapp 5//arecebevalor5(duasindire coes)pp &b//ppapontaparabpp &6//brecebevalor5Fimalgoritmo1287.5. PonteirosparaPonteiros UFMSRessaltamos que ponteiro para inteiro e ponteiro para ponteiro parainteirotemnveisdeindire coesdiferentes. Emnosso, exemplo, oconte udodep eumendere codeuminteiroeoconte udodepp eumendere codeumponteiroparainteiro. Emoutraspalavrassaotiposdiferentes. Assimumcomandodaformapp pnao evalido.Um fato interessante e que o n umero de indire coes e, teoricamente,inde-terminadoedepende dalinguagemdeprograma caoon umero deindire coespermitidas,noentantoalogicapermaneceamesma. Assimpodemosfazeraseguintedeclara caointeiropQuesignicaqueoponteiroparaponteiroppossuiseisindire coes.129AlgoritmosdeOrdenacao 8Umdos problemas mais tradicionais daareadecomputa caoeopro-blemadaordena cao. Nesseproblema, dadaumaseq uenciaden umeros,precisamoscoloca-laemumacertaordem(numericaoulexicograca). Napratica,osn umerosaseremordenadosraramentesaovaloresisolados. Emgeral, cadaumdelesfazpartedeumacole caodedados(registro). Cadaregistrocontemumachave, queeovaloraserordenado, eorestantedoregistro consiste em dados satelites. Assim, na pratica, quando permutamososn umeros,tambemdevemospermutarosdadossatelites. Porconsiderar-mosapermuta caodosdadossatelitesumaopera caomecanica, suporemosqueaentradadoproblemaconsistesomenteden umeros.Denindo o problema da ordena cao formalmente, temos: dada umaseq uencia de n n umeros a1, a2, . . . , an, encontrar uma permuta cao a1, a2, . . . , an

dessaseq uenciatalquea1 a2 . . . an.A seguir descrevemos alguns dos algoritmos simples de ordena cao. Nessadescri cao,assumiremosquejaexisteumtipodenominadovetnumquede-ne um vetorde inteiroscujolimiteinferior e1elimitesuperior e100. Emoutraspalavras,omitiremosnosalgoritmosaseguirumalinhadotipodenatipovetor[1..100]deinteirovetnum8.1 Bubble-sortO algoritmobubble-sortconsiste em passar seq uencialmente varias vezespelos elementos a1, a2, . . . , anda seq uencia de tal forma que, a cada passo, oelementoajsejacomparadocomoelementoaj+1. Seaj> aj+1,entaoelessaotrocados.Algoritmobubblesort1308.2. Insertion-sort UFMSinteiroi,j,n,tempvetnumaleianforide1atendoleiaa[i]endforforide1aten 1doforjde1aten 1doif a[j] > a[j + 1]thentemp a[j]a[j] a[j + 1]a[j + 1] tempendifendforendforFimalgoritmo8.2 Insertion-sortParacompreensaodoalgoritmoInsertion-sort, imagine aseguinte si-tua cao: vocetem um conjuntode cartasem sua maoesquerda e coma maodireitatentaordenarascartas. Aideiaecolocarcadacarta, daesquerdaparaadireita, emsuaposi caocorreta, fazendoinser coes. Nestealgoritmo,acadapasso,oelementoakeinseridoemsuaposi caocorretaAlgoritmoinsertionsortinteiroi,j,c,nvetnumaleianforide1atendoleiaa[i]endforforide2atendoc a[i]j i 1whilej> 0Ea[j] > cdoa[j + 1] a[j]j j 1endwhilea[j + 1] cendforFimalgoritmo1318.3. Selection-sort UFMS8.3 Selection-sortOmetododeordena caoporsele caotemoseguinteprincpiodefuncio-namento: pegueomaiorelementodaseq uenciaetroque-ocomoelementoqueestana ultimaposi cao. Aseguir, repitaessaopera caoparaosn 1elementos. Ouseja, encontreomaior elementoentreeles ecoloque-onapen ultimaposi cao. Depois, repitaaopera caoparaos n 2elementos eassimsucessivamente. Aonal daexecu cao, aseq uenciaestaraemordemnao-decrescente.Algoritmoselectionsortinteiroimax,max,i,jvetnumaleianforide1aten doleiaa[i]endforforidenate2passo 1domax a[1]imax 1forj 2ateidoif a[j] > maxthenmax a[j]imax jendifendfora[imax] a[i]a[i] maxendforFimalgoritmo132Umpoucosobrecomplexidadedealgoritmos 9Ate agora, estivemos interessados apenas noquesitocorretudedeumalgoritmo. Ouseja, dadoumproblemaespecco, focalizamos as nossasaten coesapenasnodesenvolvimentoeestudodealgoritmosqueresolvesseoproblema,semnospreocuparmoscomasuaeciencia.Parapodermosclassicarumalgoritmocomoecienteounao, precisa-mosdenirprecisamenteumcriterioparamedirmosasuaeciencia. Essecriterio e o seu tempo de execu cao,que pode ser medido por meio da imple-menta caoeexecu caodoalgoritmoutilizando-sevariasentradas distintas.Apesardevalida, essaestrategiaexperimentalapresentavariosproblemas.O principal deles eofatodelaserdependente da maquina (softwaree hard-ware) em que o algoritmo esta sendo executado. Precisamos entao encontrarumaformademedirotempodeexecu caoquenospermitacomparardoisalgoritmos independentemente damaquinaonde estaosendoexecutados.Uma forma de se fazerisso e contandoo n umero de opera coesprimitivas doalgoritmo. Dentreasopera coesprimitivasestao: atribuirumvaloraumavariavel, executarumaopera caoaritmetica, chamarummodulo,comparardoisn umeros,avaliarumaexpressaoeretornardeumafun cao.Em um ambiente computacional,cada opera cao primitiva corresponde auma ou mais instru coes de baixo-nvel,as quais possuem tempo de execu caoque depende da maquina, embora seja constante. Desde que on umerodeinstru coesdebaixonvel correspondentes acadaopera caoprimitivaeconstante, edesdequecadaopera caoelementarpossuitempodeexecu caoconstante, os tempos de execu cao de duas opera coes primitivas quaisquer di-ferementresiporumfatorconstante. Issonospermiteconsiderarotempodeexecu caodecadaopera caoprimitivacomosendoomesmo, oqueim-plicapodermosnosconcentrar apenasnaquantidadeefreq uenciadetaisopera coes.Tomemosentaocomoexemplooseguintealgoritmoqueleumvetorde133UFMSinteiroa,comn 1posi coes,uminteiroxeprocuraporxdentrodeA.1: Algoritmobusca2: denatipovetor[1..10]deinteirovetnum3: inteiroi,j,x,n4: logicoachou5: vetnuma6: achou F7: i 18: leian,x9: forjde1atendo10: leiaa[j]11: endfor12: whileachou = FEi ndo13: if x = a[i]then14: achou V15: else16: i i + 117: endif18: endwhile19: if achou = V then20: escrevaOelementodevalor,x,estanaposi cao,i,dovetor.21: else22: escrevaOelementodevalor,x,naoseencontranovetor23: endif24: FimalgoritmoNessealgoritmo, aslinhas6e7contemumaopera caoprimitiva(atri-bui caodovalorfalso`avariavelachouedovalor1`avariaveli). Alinha9e umla co para..fa ca que se repete exatamente nvezes. Naprimeiraitera caodessela co, temos umaopera caodeatribui cao(j 1),que corresponde aumaopera caoprimitiva. Noinciode cadaumadasitera coes desse la co, acondi caojn, que tambemcorrespondeaumaopera caoprimitiva,eavaliadaumavez. Comoessaavalia caoefeitan + 1vezes, acondi caoj ncontribuicomn + 1opera coesprimitivas. Aonalde cada itera cao,temos duas opera coes primitivas: uma soma (j +1) e umaatribui cao(j j+ 1). Comoessasduasopera coesestaodentrodola co,elas se repetem n vezes. Uma outra opera cao que se encontra dentro do la coeaindexa cao(a[i])necessariadurantealeituradovetor. Essaindexa caocorrespondeaumasomaqueserepetenvezes. Comtudoisso, ola coemquestaocorrespondea4n + 2opera coesprimitivas.Alinha12determinaoinciodeumla coqueserarepetido,nomnimo,umavez e, nomaximo, nvezes. Noinciode cadaitera cao desse la co,134UFMSacondi caoachou=FEi 0ele-mentos(nos)L1, L2, . . . , Lncomasseguintespropriedadesestruturais,quedecorremunicamentedasposi coesrelativasdeseusnos:1. L1eoprimeirono;2. para1 < k n,onoLkeprecedidopelonoLk1;3. Lneo ultimono.Emnossosestudosassumiremosquecadano eformadoporvarioscam-pos, quearmazenamascaractersticas doselementosdalista. Umdessescamposconstitui oquechamamosdechavedono. Oconceitodecampochaveedeextremaimportanciapoiseleconstitui oprincipal objetoaser13610.2. Aloca caoseq uencial UFMSmanipuladopelosalgoritmossobrelistas. Paraseevitarambig uidades,ire-mossuporquetodasaschavessaodistintas.Asopera coesmaisfreq uentesemlistassaoabusca,i nser caodeumno,eremo caodeum nodalista. Alemdessasopera coesvalemencionaroutrasderelativaimportanciacomoacombina caodeduasoumaislistaslinearesemuma unica, aordena caodosnos, adetermina caodotamanhodalista,etc.Podemos citar casos particulares delistas combasenas opera coes deinser caoeremo cao. Seasinser coeseremo coes saorelizadassomenteemumextremo, alistaechamadapilha. Seasinser coessaorelizadasemumextremo,easremo coesemoutro,alista echamadaf ila.Existemduasformasdearmazenarosnosdeumalistanocomputador: aloca caoseq uencial: osnossaoarmazendosemposi coesconsecutivasdamemoria; aloca caoencadeada: osnossaoarmazendosemposi coesnaoconsecu-tivasdamemoria.Amelhor maneiradearmazenar listas lineares depende, basicamente,das opera coesmais freq uentes a serem executadas sobre ela. Naoexiste,emgeral, uma unicarepresenta caoqueatende, demaneiraeciente, todasasopera coesacimamencionadas.10.2 Alocacaoseq uencialAmaneiramaissimplesdemanterumalistanocomputador ealocandoposi coesconsecutivasdamemoriaacadaumdeseusnos(vetor). Assim,poderamos denir uma lista L,comno maximo1000nos de um certotipo,utilizandoosseguintescomandosdenossalinguagemalgortmica:denaMAX1000denatiporegistrointeirochavetipo1campo1tipo2campo2. . .tipomcampommregistrotiporegistro13710.2. Aloca caoseq uencial UFMSdenatipovetor[1..MAX]detiporegistrolistalistaLNotenaslinhas acimaquetiporegisto eum tipoquedene um registroque possui um n umero qualquer de campos, sendo um deles o campo chave.Em nosso exemplo,ele esta denido como inteiro,mas pode ser de qualquertipoelementarconhecido.Armazenadadeformaseq uencial, aseguintefun caopodeserutilizadaparaabusca, pormeiodachave, deumelementonalistaL. Elarecebecomoparametroumavariaveldo tipo lista (um vetor),achavexe otama-nho nda lista. Eladevolveo ndicena listaondeo elementose encontraou-1casooelementonaoestejanalista.fun caointeiroBuscaListaSeq(listaL,inteirox,inteiron)inteiroii 1whileL[i].chave = xEi ndoi i + 1endwhileif i = n + 1thenretorneielseretorne-1endifmfun caoAfun caoacimaexecuta, nomnimo,8(quandooelementoencontra-senaprimeiraposi caodovetor)e, nomaximo1+3(n+1)+2n+2+1=5n+6opera coesprimitivas.Sobreosprocedimentosdeinser cao(insereumnovoregistrononaldalista)eremo cao(removeumregistrodalistacujachaveex)emumalistalinearalocadaseq uencialmente, elesencontram-sedetalhadasabaixo. Notequeambos seutilizamdafun caoBuscaListaSeq. Afun caodeinser caoinsereumnovoresgitraprocedimentoInser cao(listaL,tiporegistronovo,refinteiron)if n < MAXthenif BUSCAListaSeq(L,novo.chave)=-1thenL[n + 1] novon n + 1elseescrevaElementojaexistenalistaendif13810.2. Aloca caoseq uencial UFMSelseimprimalistacheia(overow)endifmprocedimentoO procedimento acima executa, no mnimo, 1 opera cao primitiva (quandoalistaestacheia)e, nomaximo1+2+2=5opera coesprimitivas(notequeon umerodeopera coesprimtivasrealizadasporesseprocedimentonaodependeden).procedimentoRemo cao(listaL,inteirox,refinteiron)inteiroktiporegistrovalorif n > 0thenk BUSCAListaSeq(L,x)if k = 1thenvalor L[k]foridekaten 1doLk Lk + 1endforn n 1elseimprimaElementonaoseencontranalistaendifelseimprimaunderowendifmprocedimentoAfun caoacimaexecuta, nomnimo, 1opera caoprimitiva(quandoalistaestavazia)e,nomaximo1+2+1+1+1+n+2(n-1)+2(n-1)+1=5n+3opera coesprimitivas.10.2.1 PilhaseFilasEmgeral, oarmazenamentoseq uencial delistaseempregadoquandoas estruturas sofrempoucas inser coes eremo coes aolongodotempo, ouquandoinser coes eremo coes naoacarretammovimentacaodosnos. Esse ultimocasoocorrequandooselementosasereminseridoeremovidosestaoemposi coeespeciaisdalista, comoaprimeiraoua ultima. Issonosleva`adeni caodepilhaselas.13910.2. Aloca caoseq uencial UFMS10.2.1.1 PilhasUmapilha euma listalineartalque asopera coesdeinser caoeremo caosaorealizadasemum unicoextremo.Emgeral, aimplementa c aodeumapilhasefazpormeiodeumregis-troPcontendodoiscampos: P.topo,uminteiroindicandoaquantidadedeelementosna pilha,e um vetorP.L, de tamanhoMAX,contendoosP.topoelementos. Assim,poderamosdenirumapilha,comnomaximo1000nosdeumcertotipo, utilizandoosseguintescomandosdenossalinguagemal-gortmica:denaMAX1000denatiporegistrointeirochavetipo1campo1tipo2campo2. . .tipomcampommregistrotiporegistrodenatipovetor[1..MAX]detiporegistrolistadenatiporegistrotipo1campo1listaLmregistrotipopilhatipopilhaPOs seguintes procedimento podementao ser utilizados parainserir eremoverelementosdeumapilha, respectivamente. Quandofalamosnessaestruturadedados, ecomumnosreferenciarmos`asopera coesdeinser caoeremo caodeelementoscomoempilharedesempilharprocedimentoEmpilha(reftipopilhaP,tiporegistronovo)if P.topo = MAXthenP.topo P.topo + 1P.L[P.topo] novoelseimprimaoverowendifmprocedimentoO procedimento acima executa, no mnimo, 1 opera cao primitiva (quandoapilhaestacheia)e,nomaximo,5opera coesprimitivas.fun caotiporegistroDesempilha(reftipopilhaP,removido)tiporegistroremovido14010.2. Aloca caoseq uencial UFMSif P.topo = 0thenremovido P.L[P.topo]P.topo P.topo 1elseimprimaunderowendifmfun caoAfun caoacimaexecuta, nomnimo, 1opera caoprimitiva(quandoapilhaestavazia)e,nomaximo,5opera coesprimitivas.10.2.1.2 FilasUma la e uma lista linear tal que as opera coes de inser cao sao realizadasemumextremoeasderemo caosaorealizadasnooutroextremo.Em geral,a implementa caode uma la se faz por meio de um registro Fcontendo tres campos: F.inicio, um inteiro indicando o incio da la, F.fim,um inteiro indicando o m da la,e um vetorF.L,de tamanho MAX,con-tendoosF.inicio F.fim+ 1elementosdala. Assim,poderamosdeniruma la, com no maximo 1000nos de um certo tipo, utilizando os seguintescomandosdenossalinguagemalgortmica:denaMAX1000denatiporegistrointeirochavetipo1campo1tipo2campo2. . .tipomcampommregistrotiporegistrodenatipovetor[1..MAX]detiporegistrolistadenatiporegistrointeiroiniciotipo1fimlistaLmregistrotipofilatipofilaFOsseguintesprocedimentopodemserutilizadosparainserir(enleirar)eremover(desinleirar)elementosdeumala.Noteque,aposqualqueropera cao,deve-sesempreteroponteiroinicioindicandooinciodalaefimonal dala. Issoimplicaincrementar14110.2. Aloca caoseq uencial UFMSinicioquandodeumainser c aoefimquandodeumaremo caodala. Issofaz com que a la se mova,dando a falsa impressao de memoria esgotada.Paraeliminaresseproblema,consideram-seosnnosalocadoscomoseelesestivessem em crculo, com F.L[1] seguindo F.L[n]. No algoritmo de inser caoem uma la, a variavel auxiliar provarmazena provisoriamente a posi cao dememoriacalculadadeformaarespeitaracircularidade,sendoqueoindcefimemovimentadosomenteseaposi caoforpossvel. Os ndicesinicioefimsaoambosinicializadoscomzero.procedimentoEnleira(reftipofilaF,tiporegistronovo)prov (F.fimMODMAX) + 1if prov = F.iniciothenF.fim provF.L[F.fim] novoif F.inicio = 0thenF.inicio = 1endifelseimprimaoverowendifmprocedimentoO procedimento acima executa, no mnimo, 4 opera cao primitiva (quandoalaestacheia)e, nomaximo, 9opera coesprimitivas(quandooprimeiroelementoestasendoinserido).fun caotiporegistroDesenleira(reflaF)tiporegistrorecuperadoif F.inicio = 0thenrecuperado F.L[F.inicio]if F.inicio = F.fimthenF.inicio 0F.fim 0elseF.inicio (F.inicioMODMAX) + 1endifretornerecuperadoelseimprimaoverowendifmfun caoA fun cao acima executa,no mnimo, 1 opera cao primitiva (quando a laestavazia)e,nomaximo,7opera coesprimitivas(quandoo unicoelementoestasendoremovido).14210.2. Aloca caoseq uencial UFMS10.2.2 UmexemplodeaplicacaodeumapilhaDentreas varias aplica c oes deumapilha, existeumadegrandeinte-ressenaareadecompiladores. Suponha quequeremosdecidirseumadadaseq uenciadeparenteses estabemformadaounao. Umaseq uenciadessetipo editabemformadaquandoosparentesesecolchetessefechamperfei-tamente. Por exemplo, a seq uencia ( ( ) [ ( ) ] ) esta bem formada, enquantoqueaseq uencia([)]naoestabemformada.Vamosentaoescrever umalgoritmoqueleiaumvetor decaracteres scontendoaseq uenciade parentesesecolchetesedetermine aseaseq uenciaestabemformadaounao.algoritmodenatipovetor[1..1000]decaracteresvetcaracdenatiporegistrointeirotopovetcaracLmrgistrotipopilhavetcaracstipopilhaPlogicotempinteiroi,ntemp VP.topo 0leianforide1atenfa cadoleias[i]endfori 1whilei nANDtemp = V doif s[i] =)thenif P.topo = 0ANDP.L[P.topo] =(thenP.topo P.topo 1elsetemp = Fendifelseif s[i] =]thenif P.topo > 1ANDP.L.[P.topo 1] =[thenP.topo P.topo 1elsetemp Fendifelse14310.2. Aloca caoseq uencial UFMSP.topo P.topo + 1P.L[P.topo] s[i]endifendifi i + 1endwhileif temp = V thenescrevaAseq uenciaebemformada!elseAseq uencianao ebemformada!endifmalgoritmo144ListadeExercciosponteiros1. Escrevaumalgoritmoqueleiaumvetor Adenn umerosinteiros eordene esse vetor. O vetor deve ser alocado dinamicamente e ordenadoutilizandoapenasanota caodeponteiros.2. Escrevaumalgoritmoqueleiadois vetores Ae Bcomnn umerosinteiros, ecrieumvetorCresultadodasomadeAeB. Osvetoresdevem ser alocados dinamicamente e todas as opera coes envolvendo osseuselementosdevemserfeitasutilizandoanota caodeponteiros.3. Escreva o algoritmo para uma fun cao que recebe como par ametros doisvetoresdeinteirosAeBeretorneumterceirovetorCtalque: Ceadiferen caentreXeY ; CeoprodutoentreXeY ; Ceaintersec caoentreXeY ; CeauniaodeXcomY .Ordenacao1. Umalgoritmodeordena caoe ditoestavel senaoalteraaposi caorelativadeelementoscommesmovalor. Porexemplo, seovetordeinteirosvtiverdoiselementosiguaisa222,primeiroum azuledepoisumvermelho, umalgoritmodeordena caoestavel mantemo222azulantesdo vermelho. Combasenessadeni cao,paracadaum dosalgo-ritmos vistos em sala de aula (bolha, sele cao,inser cao), determine se oalgoritmo e estavel ou nao. Em caso armativo, escreva sim.Em casonegativo,escrevanaoeforne ca uma seq uenciade n umeros (entradaparaoalgoritmo)quecomproveofatodoalgoritmonaoserestavel.2. SejaSumaseq uenciadenn umerostalquecadaelementorepresentaumvotodiferenteparapresidentedocentroacademicodocursodeBachareladoemAnalisedeSistemasdaUFMS.Ovotoeumn umerointeiro que representa, de forma unica, o estudante escolhido para145ListadeExerccios UFMSocargo. Escreva umalgoritmo que recebaSe ncomo entradaedetermineon umeroquerepresentaocandidatomaisvotado.dica: ordeneaseq uenciaListas1. Escrevaummoduloque, dados comoparametros umalistaalocadaseq uencialmenteL,oseutamanhoneumvalorx,devolvaon umerodeelementosdalistacujachavepossuivalormaiorouigualax.2. Escrevaummoduloque, dadoscomoparametros umalistaORDE-NADAalocadaseq uencialmenteL, oseutamanhoneumelementonovo cujo valorda chave e x, insira novo dentro da lista(logicamente,alistadevepermanecerordenadaaposainser cao).3. Escrevaummoduloque, dadoscomoparametros umalistaORDE-NADAalocadaseq uencialmenteL, oseutamanhoneovalorx, re-movaoelementocujovalordachaveex.4. Escrevaummoduloque, dados comoparametros umalistaalocadaseq uencialmenteLeoseutamanhon,invertaaordemdoselementosdessalista.5. Escrevaummoduloque,dadoscomoparametrosduaslistasalocadasseq uencialmenteL1eL2eotamanhodecadalista,(men,respecti-vamente), devolvaumaterceiralistaL3resultadodacombina caodaslistasL1eL2.6. Escrevaummoduloque, dadoscomoparametrosduaslistasORDE-NADASalocadasseq uencialmenteL1eL2eotamanhode cadalista,(me n, respectivamente),devolvauma terceiralistaL3,tambemOR-DENADA,resultadodacombina caodaslistasL1eL2.Pilhas1. Utilizandoumapilha(easfun coesEmpilhaeDesempilhaasso-ciadas), escrevaumalgoritmoqueleiaumaseq uenciadecaracterese