Questão FC373195
Considere v um vetor de inteiros, contendo a sequência de valores {1,4,7,9,10,12}. Uma chamada à função teste, foi realizada por meio da instrução r \(\leftarrow\) teste(v,6,10), s
Algoritmos e Lógica de Programação
FCC · 2019
Considere v um vetor de inteiros, contendo a sequência de valores {1,4,7,9,10,12}. Uma chamada à função teste, foi realizada por meio da instrução r \(\leftarrow\) teste(v,6,10), sendo 6 o tamanho do vetor e 10 o valor que se deseja localizar no vetor.
função teste(a[], n, x:inteiro):inteiro
início
retorne opera(a, 0, n+1, x);
fim_função
funcão opera(a[], p, r, x:inteiro): inteiro
var q:inteiro
início
se(p=r-1)
então retorne r
senão
q \(\leftarrow\)(p+r)/2;
se (a[q] < x)
então retorne ..I..
senão retorne ..II..
fim_se
fim_se
fim_função
Para que a função teste retorne o valor 4, que é a posição do valor 10 no vetor (considerando que o primeiro índice do vetor é zero) as lacunas I e II devem ser correta e respectivamente preenchidas por
- opera(a, r, q, x) e opera(a, q, p, x)
- opera(a, q, r, x) e opera(a, p, q, x)
- q e (p+r).
- ((a+p)*(q-x)/2) e ((a+q)*(r-x)/2)
- opera(a, p, q, x) e opera(a, q, r, x)
Mostrar resposta e comentário
Gabarito
B
Comentário do professor
A alternativa correta implementa a busca binária. A função teste chama inicialmente opera(a,0,n+1,x), ou seja, com \(r=n+1=7\). Em cada chamada calcula-se \(q=(p+r)/2\) (truncando para inteiro) e decide-se qual metade manter.
Quando a[q] < x, o elemento procurado está na metade à direita, logo deve-se chamar opera(a, q, r, x) (novo limite inferior = q). Quando a[q] ≥ x, está na metade esquerda ou em q, então chama-se opera(a, p, q, x) (novo limite superior = q).
Aplicando ao vetor {1,4,7,9,10,12}: primeiro \(q=3\) (a[3]=9<10) → opera(a,3,7,10); depois \(q=5\) (a[5]=12≥10) → opera(a,3,5,10); depois \(q=4\) (a[4]=10≥10) → opera(a,3,4,10). Finalmente \(p=3, r=4\) satisfaz \(p=r-1\) e retorna r=4, posição correta de 10.
Conteúdo do catálogo FC Concursos · Atualizado em