Resolução de Exercícios de Laboratório (Aula 7) – Algoritmos e Estruturas de Dados
Sugestão de Resolução de Exercícios de Laboratório – Introdução ao Algoritmos e Estruturas de Dados (IAED), Instituto Superior Técnico
1. (Radix) Considere a aplicação do algoritmo radixLSD ao seguinte vector:
<48372, 62309, 83861, 91874, 18913, 33829, 47812, 95954, 52377, 22394, 56108, 60991>
Qual é o terceiro número da sequência, após o algoritmo ter considerado três digitos?
2. (Radix) Considere o seguinte vector de números inteiros sem sinal de 6 bits: <32, 1, 34, 9, 6, 2, 20, 18, 10>
Qual o conteúdo do vector após o primeiro passo do algoritmo de ordenação radix sort MSD, em que em cada passo os elementos são ordenados considerando 2 bits (ou seja, byte = 2 bits) ?
Nota: considere que o algoritmo é baseado numa versão estável do algoritmo counting sort. O algoritmo deve apenas processar os 6 bits menos significativos de cada número, independentemente dos números poderem ser guardados em palavras com maior número de bits.
3. (Radix) Considere o exercicio anterior, mas onde o vector de inteiros de entrada é o seguinte: <16, 15, 50, 32, 5, 35, 9, 48, 1>
4. (Radix) Considere a seguinte sequência de números inteiros sem sinal, que se encontram representados por palavras de 6 bits: <12, 9, 7, 10, 16, 23, 48, 24, 5, 1>
Qual será o quarto elemento da sequência, após dois passos do algoritmo radixLSD, considerando que em cada passo são analisados 2 bits (i.e. byte = 2 bits) ?
5. (Aritmética de ponteiros) Implemente duas versões da função strlen, uma em que utiliza índices e outra em que aplique aritmética de ponteiros.
Recorde a implementação do tipo de dados Complexo da 4ª Aula de laboratório.
#include <stdlib.h>
/* strlenI
* Versao com indices
*/
int strlenI(char* str){
int i=0;
while(str[i] != ' ') i++;
return i;
}
/* strlenP
* Versao com aritmetica de ponteiros
*/
int strlenP(char* str){
int i=0;
while(*(str+i) != ' ') i++;
return i;
}
int main(){
char str1[] = {'H', 'E', 'L', 'L', 'O', ',', ' ', 'W', 'O', 'R', 'L', 'D',' '};
printf("%sn", str1);
printf("strlen: %d / %dn", strlenI(str1), strlenP(str1));
return 0;
}
6. (Estruturas) Implemente uma função complexo soma(complexo a, complexo b) que recebe dois números complexos como argumento e devolva a soma dos dois.
#include <stdlib.h>
typedef struct Complexo {
int real, img;
} complexo;
complexo leComplexo(){
complexo c;
scanf("%d+%di", &(c.real), &(c.img));
return c;
}
void imprimeComplexo(complexo c){
printf("%d+%din", c.real, c.img);
}
complexo soma(complexo a, complexo b){
complexo res;
res.real = a.real + b.real;
res.img = a.img + b.img;
return res;
}
int main(){
complexo c1, c2;
c1 = leComplexo();
c2 = leComplexo();
imprimeComplexo(soma(c1,c2));
return 0;
}
7. (Ponteiros) Altere a função desenvolvida no exercício anterior por forma a que esta não devolva o resultado da soma mas que o resultado da soma venha no primeiro argumento da função.
#include <stdlib.h>
typedef struct Complexo {
int real, img;
} complexo;
complexo leComplexo(){
complexo c;
scanf("%d+%di", &(c.real), &(c.img));
return c;
}
void imprimeComplexo(complexo c){
printf("%d+%din", c.real, c.img);
}
void soma(complexo* a, complexo* b){
(*a).real = (*a).real + (*b).real;
(*a).img = (*a).img + (*b).img;
}
int main(){
complexo c1, c2;
c1 = leComplexo();
c2 = leComplexo();
soma(&c1, &c2);
imprimeComplexo(c1);
return 0;
}
8. (Ponteiros) Altere a função desenvolvida no exercício anterior por forma a que a função devolva um ponteiro para um número complexo que tem o resultado da soma.
#include <stdlib.h>
typedef struct Complexo {
int real, img;
} complexo;
complexo leComplexo(){
complexo c;
scanf("%d+%di", &(c.real), &(c.img));
return c;
}
void imprimeComplexo(complexo c){
printf("%d+%din", c.real, c.img);
}
complexo* soma(complexo* a, complexo* b){
complexo* c = (complexo*) malloc(sizeof(complexo));
(*c).real = (*a).real + (*b).real;
(*c).img = (*a).img + (*b).img;
return c;
}
int main(){
complexo c1, c2;
complexo* c3;
c1 = leComplexo();
c2 = leComplexo();
c3 = soma(&c1, &c2);
imprimeComplexo(*c3);
free(c3);
return 0;
}
