Debate: Ensino da Programação

1. Primeiro Programa

O módulo começa por este capítulo, onde de forma sucinta se introduz o conceito de programa, linguagem de programação, e linguagem imperativa. O estudante realiza aqui o seu primeiro programa, o “olá mundo”, sendo explicadas todas as suas componentes e é indicada a secção de instalação do compilador localmente. Atualmente este passo não é essencial, já que o estudante pode utilizar o HackerRank para a realização de todos os exercícios, não sendo necessária qualquer instalação. A instalação era sempre um ponto que necessitava de muita interação e esforço por parte de alguns estudantes, tendo sido eliminada com a solução online.

2. Variáveis

Este capítulo introduz o conceito de variável num programa, como algo que guarda informação e que utiliza memória. Como suporte a este conceito, utiliza-se um programa de troca de valor entre duas variáveis. É aqui introduzida a primeira execução passo a passo, de modo a que o estudante verifique que uma variável mantém sempre o valor até que exista nova atribuição, e possa compreender a sua diferença relativamente à variável na matemática. Realça-se ainda a introdução neste capítulo de dados num programa, bem como a possibilidade de existirem erros de qualidade de código, sendo listados três.

3. Condicionais

Aqui temos como principal conceito a introduzir a possibilidade de execução alternativa de instruções num só programa. Não menos importante é a utilização de expressões lógicas para decidir entre as instruções alternativas, sendo dado um exemplo entre número par ou ímpar como primeiro exemplo de instruções alternativas. Novamente a execução passo-a-passo e entrada de dados é utilizada para clarificar o que o programa faz, mediante cada tipo de entrada de dados, e são listados os diferentes tipos de operadores lógicos e operadores numéricos. O exemplo central é determinar se um ano é bissexto, permitindo assim a utilização de diferentes operadores. Em termos de qualidade de código, introduz-se entre outros, o conceito de indentação do código.

4. Ciclos

Este é o último capítulo deste primeiro módulo, em que se introduz a possibilidade de uma linha de código ser executada mais que uma vez, abrindo assim as portas para uma outra dimensão dos programas, em que com um esforço limitado em escrever o programa, este pode realizar um número arbitrário de instruções, ao contrário do que se verificava até então. O exemplo de base é a soma dos primeiros N números ao quadrado, sem utilizar um ciclo, e depois a solução utilizando o ciclo. Introduz-se apenas o ciclo “while”, de modo a simplificar e manter a proximidade com o condicional introduzido anteriormente. A execução passo a passo evidencia a situação em que existem mais passos na execução do programa do que instruções, o que até aqui não ocorria, introduzindo-se o conceito de variável iteradora. Em termos de erros de qualidade, evidencia-se aqui o das instruções parecidas seguidas, sendo normalmente evidência de falha na identificação de um ciclo.

AFs pré-programação

Existem dois tipos de atividades formativas (AFs): AFs de pré-programação e AFs de programação. As AFs de pré-programação existem apenas neste primeiro módulo, e centram-se nos três conceitos essenciais do módulo: variável, condicional e ciclo. Os testes têm base de dados de perguntas, permitindo repetir o teste, e podem servir de base para identificar problemas que podem tornar espinhosa a tentativa de realização das AFs de programação. Quando o estudante tem problemas em avançar em exercícios muito simples de programação, este é o tipo de exercício que é necessário realizar de modo a verificar se tem os meios mínimos suficientes para iniciar-se no mundo da programação.

Exercícios 1

• Exercícios Verdes:

Olamundosizeof

Soma

HMS

Produto

Arranjos

• Exercícios Azuis:

SomaDigitos

Fibonacci

Combinacoes

Euler

Trocos

Primo

• Exercícios Vermelhos:

TriplaSoma

PI

FormulaResolvente

Exercícios 1

Após os quatro capítulos e a realização das AFs de pré-programação, o estudante tem o seguinte conjunto de exercícios, cujos enunciados estão no manual e podem ser visualizados / realizados no HR. Exercícios 1: http://hr.gs/uabproge1

Estes exercícios são realizados no HR, e estão muito apoiados em termos de execuções de exemplo. Ao submeter o código no HR o estudante tem de imediato uma lista de casos de teste bem-sucedidos e falhados, existindo no caso dos testes falhados os dados de entrada e saída, podendo ver a diferença entre o que era esperado e o ocorrido.

5. Funções

Neste primeiro capítulo é introduzido o conceito de função, com base na ideia de mandar executar um bloco de código de qualquer parte do código. Fornece-se um exemplo em que duas linhas de código são repetidas em duas zonas do código, sendo a solução a construção de uma função para conter as instruções duplicadas, e assim chamar a função nos dois locais em que as instruções são necessárias. A execução passo a passo acompanha os exemplos de modo a procurar clarificar esta questão. É de seguida introduzido o termo abstração, para realçar a vantagem das funções, que consiste na abstração funcional, em que ao implementar uma função o programador apenas precisa saber o que a função tem de fazer, e ao utilizar a função é necessário saber apenas o que a função faz. Desta forma pode-se atacar problemas arbitrariamente grandes, prestando atenção a cada momento apenas a uma pequena parte deste. Em termos de erros de qualidade são referidos alguns, sendo o mais relevante as instruções parecidas não seguidas, reveladores de uma falha na identificação da necessidade de uma função.

6. Mais Ciclos e Condicionais

Este é um capítulo em que não são introduzidos novos conceitos, apenas formas alternativas de na linguagem C de se escrever ciclos e condicionais. Nos ciclos são introduzidos o “for” e “do-while”, fornecendo-se alguns exemplos, e o “switch”. Aqui realça-se que o ciclo “for” prevê a utilização da variável iteradora, ficando o código mais bem organizado.

7. Vetores

7. Vectores

Neste capítulo é introduzido a importante estrutura de dados vetor, sendo a única estrutura de dados introduzida neste módulo e a primeira que permite ter um conjunto de variáveis. São dados alguns exemplos de evidência da necessidade de ter as variáveis agrupadas, nomeadamente na necessidade de calcular uma média. A não utilização de vetores iria inviabilizar a utilização de um ciclo, o que conduziria ao erro de código duplicado seguido. Introduz-se também o conceito de string, como sendo um conjunto de caracteres. São dados como exemplo algumas funções do string.h. Introduz-se aqui também a leitura dos argumentos do programa e matrizes. Como erros de qualidade realça-se o erro de variáveis com nomes quase iguais, tendo como origem provavelmente a falha de identificação de um vetor.

8. Procedimentos

Embora o conceito de procedimento seja um conceito ligado com o da função, tem a diferença de que o procedimento faz algo, não retornando nada e não podendo ser utilizado numa expressão, enquanto que uma função calcula algo e pode ser utilizado numa expressão. São dados exemplos, nomeadamente o procedimento “Troca” que troca os valores entre duas variáveis, e é introduzida a passagem de argumentos por referência. Este conceito faz uso do apontador, mas de forma leve, de modo a suportar a passagem de argumentos por referência. Os apontadores ficam para o módulo III, no contexto da memória dinâmica. É introduzido também o conceito das variáveis globais, acessíveis a todas as funções, embora sendo algo desaconselhado. São aqui introduzidas as variáveis estáticas internas às funções, acompanhadas de exemplos de utilização. São dados vários erros de qualidade, entre os quais as funções muito grandes, sendo normalmente um indicador de que faltam abstrações funcionais.

9. Recursão

Neste último capítulo do módulo é introduzido o conceito da recursão, que aplica a abstração funcional à própria função. É dado o exemplo da função fatorial recursiva, sendo comparada com a versão iterativa, e as torres de Hanoi, em que não é comparada com nenhuma alternativa, sendo realçada a simplicidade para resolver um problema que de outra forma seria de grande complexidade.

Exercícios 2

• Exercícios Verdes:

Argumentos

Inverte

Rand

Find

Maximo

MDC

Sort

RemoveDups

• Exercícios Azuis:

SomaNumeros

Trocos2

JogoDados

Baralhar

MergeSort

BinarySearch

NumeracaoRomana

PokerDados

• Exercícios Vermelhos:

StrReplace

NDamas

DoisDados

Calendario

EditDistance

Exercícios 2

Após os capítulos, inicia-se um bloco grande de exercícios, cujos enunciados estão no manual e podem ser visualizados / realizados no HR. Exercícios 2: http://hr.gs/uabproge2

Tal como no módulo anterior, o grau de dificuldade é crescente, procurando-se aqui propor como exercícios exemplos clássicos e funções de alta reutilização, permitindo por um lado que o estudante utilize o seu código nas atividades de avaliação, e por outro dar exemplos do que são boas abstrações funcionais, as que levam a que a função possa vir a ser reutilizada tanto no próprio programa como em outros programas. Entre os exercícios destacam-se as funções de ordenação e procura, bem como função para baralhar um conjunto de elementos e remover duplicados.

AFs Extra

Foram feitas três atividades formativas extra, para serem realizadas após os exercícios do módulo 2, com outras linguagens de programação orientadas para determinados fins. Linguagem R para o cálculo estatístico, o VBA para programação numa folha de calculo, e o Processing para produção de imagens. Para além de introduzirem as respetivas linguagens para quem tenha acabado de fazer este módulo, são solicitados alguns dos exercícios para as quais as linguagens trazem vantagem, pretendendo-se assim abrir o leque de possibilidades aos estudantes.

10. Memória

Este é o primeiro capítulo do terceiro módulo, onde se irá introduzir a necessidade de poder alocar memória de forma dinâmica, dependendo dos dados de entrada, e libertar a memória de forma precisa. Para tal irá falar-se do stack, heap, malloc, free, e apontadores. É um capítulo complexo, em que se procura falar dos termos introduzidos como forma de resolver um problema enunciado. Neste capítulo referem-se diversos erros com alocação de memória, como ler/alterar uma posição de memória não alocada, libertar um endereço de memória inválido, não libertar após alocar, etc. São indicadas boas práticas para evitar cair nesses erros.

11. Estruturas

Neste capítulo introduz-se as estruturas em C, que permitem agrupar variáveis de diferentes naturezas. Entre os exemplos está uma estrutura para data, agrupando o ano, mês e dia, bem como uma estrutura para guardar dados de uma pessoa. É naturalmente introduzido o typedef, e bem como o conceito de abstração de dados. Como exemplo de abstração de dados, cria-se uma estrutura de alta reutilização, TVetorInt, o qual implementa-se de uma forma, da qual se identifica um problema de eficiência. Após se alterar apenas as funções do tipo abstrato de dados, o programa que o utiliza, fica a funcionar mais rapidamente, não tendo o mesmo de ter alterações. Este capítulo não termina sem introduzir a importante estrutura de dados de listas ligadas. Assim os estudantes ficam com uma alternativa à utilização de vetores.

12. Ficheiros

Neste capítulo de ficheiros introduz-se o redireccionamento dos dados de entrada e saída na linha de comandos, nomeadamente para ficheiros, e apresentam-se as funções de ficheiros, em tudo iguais às funções de entrada e saída de dados, mas com o apontador para ficheiro. Os ficheiros stdin e stdout são também introduzidos, sendo dados exemplos com estruturas e com alocação dinâmica de memória, dos capítulos anteriores.

13. Truques

Neste capítulo são introduzidos os operadores binários, o operador ?, e a estrutura union. São dados exemplos de ganho de eficiência, sendo este ganho quantificado, e exemplos em que se vê alguma vantagem em utilizar o operador ? pela sua forma compacta, dentro de expressões, e da estrutura union.

Exercícios 3

Após os capítulos, inicia-se um bloco de exercícios, cujos enunciados estão no manual e podem ser visualizados / realizados no HR. Exercícios 3: http://hr.gs/uabproge3

Estes exercícios são em menor quantidade que no módulo anterior, seguindo a mesma lógica dos mais simples para os mais complexos. Vários exercícios são de listas, de modo a dar alguma experiência de utilização, podendo assim os estudantes utilizarem de facto esta estrutura de dados em alternativa a vetores.

• Exercícios Verdes:

Adiciona

More

Insere

InsertSort

Enesimo

• Exercícios Azuis:

Palavras

CifraCesar

More

BaseDeDados

MergeSort

Sort

• Exercícios Vermelhos:

Find

Histograma

Indicador

Critérios de Correção

Em termos de critérios de correção existem critérios divulgado antes do enunciado, os quais são detalhados após a correção, na mensagem de feedback.

No feedback global, em vez de uma resolução do e-fólio, deve existir para cada alínea um conjunto de situações que resultaram das opções dos estudantes, comentando relativamente a problemas e vantagens de cada opção. Deve-se mostrar uma solução considerada a mais simples. Desta forma, tira-se partido de muitos estudantes terem resolvido o mesmo problema, e assim pode-se analisar diferentes formas igualmente boas de resolver o mesmo problema, como por outro lado, analisam-se opções desaconselhadas com as respetivas explicações.

Critérios de correção para os e-fólios (4 valores):

• (2 valores) Funcionalidade:

Resultado dos casos de teste recolhidos do HackerRank (HR).

No caso de existir código específico para um dado caso de teste, esse caso de teste não é contabilizado e é removido um caso de teste passado.

• (1 valor) Qualidade:

Avaliado de acordo com a lista Erros Comuns (capítulo 17 do manual). São apontados os três erros de qualidade principais. Um erro de gravidade elevada desconta 33%, um erro de gravidade média desconta 25% e um erro de gravidade baixa desconta 10% neste critério. No caso de ser realizada a alínea C e/ou D, considera-se que o estudante poderia realizar as alíneas A e B com qualidade máxima, pelo que as penalidades encontradas incidem apenas nas alíneas C e D, sendo a parte relativa às alíneas A e B consideradas como sendo realizadas à qualidade máxima.

• (0,25 valores) Relatório - dimensão/forma:

O relatório deverá ter uma dimensão entre 2 e 4 páginas, não contando com os anexos. O texto deve estar bem organizado e sucinto, devendo representar uma mais valia relativamente ao código. Não necessita de reproduzir o enunciado, nem deve conter código.

• (0,25 valores) Relatório - conteúdo:

O relatório deve indicar o que foi realizado, e o que ficou por realizar. Deve descrever e justificar caso tenha ponderado alternativas, as opções tomadas a nível de estrutura de dados adotada, e abstrações funcionais implementadas.

• (0,5 valores) Relatório - testes

Deve referir no relatório quais os testes realizados e respetivos resultados globais, e colocar em anexo informação relativa a todos os testes realizados. Os testes devem comprovar o bom funcionamento da aplicação na maior diversidade de casos possíveis, sendo necessário apresentar resultados de pelo menos 10 casos de teste para poder ter a totalidade deste critério. Os casos de teste para avaliação, não podem ser utilizados neste critério.

Enunciados 2010 - 2019

Enunciados

E-fólio A:

• Jogo do Risco
• Sueca
• Settles of Cattan
• Pontos e quadrados
• Poker
• Dominó
• Mine sweeper
• Black Jack
• Dominó de 4 lados

E-fólio B:

• jogo da Forca
• Simulador de corridas de automóveis
• BD actividades desportivas
• BD mundial de futebol
• BD estudante
• Encontrar palavras, com prefixo igual ao sufixo, e únicas.
• Expressões numéricas
• Supermercado
• Jogo de palavras

E-fólio Recurso (até 2016/17):

• contagens com urnas
• Erros de qualidade no código
• Desmultiplicar totoloto com e sem perdas
• Quadrados Mágicos
• Jogo da Vida
• Codificar ficheiro (simples troca de ordem)
• Master Mind

Resoluções, e-fólio A, alínea A

// Risco

int main()

{

int batalhoes=0, cavalaria=0, artilharia=0;

printf("Numero de batalhoes: ");

scanf("%d",&batalhoes);

/* descontar nos batalhões a artilharia e cavalaria, se possível */

if(batalhoes>0)

{

artilharia=batalhoes/10;

batalhoes-=artilharia*10;

cavalaria=batalhoes/5;

batalhoes-=cavalaria*5;

} else

batalhoes=0;

/* mostrar resultado, já que o número de tropas de infantaria

corresponde ao número de batalhões que não foram contabilizados

na arquilharia nem na cavalaria */

printf("%d Infantaria, %d Cavalaria, %d Artilharia",

batalhoes, cavalaria, artilharia);

}

// Sueca

void MostraCarta(int carta)

{

char numeros[]="23456DVR7A";

if(carta>=0 && carta<40)

printf("%c%c",numeros[carta%10],3+carta/10);

else

printf("**");

}

void main()

{

char str[255];

int carta;

printf("Introduza carta (0-39): ");

gets(str);

printf("Carta introduzida: ");

MostraCarta(atoi(str));

}

Exemplos de resoluções da primeira alínea do primeiro e-fólio.

Resoluções

// Domino

////////////////////////////////////////

// função base para responsta à alínea A

void PrintPeca(int esquerda, int direita) {

printf("[%d:%d]",esquerda,direita);

}

int main() {

srand(time(NULL));

PrintPeca(rand()%7,rand()%7);

}

//Settlers of Cattan

int LancaDoisDados()

{

return rand()%6 + rand()%6 + 2;

}

void main()

{

int i;

for(i=0;i<10;i++)

printf("%d ",LancaDoisDados());

}

// Poker

void MostraCarta(int carta)

{

char *naipes="opce", *numeros="234567890VDRA";

if(carta>=0 && carta<=51) {

// número

if(carta%13==8) // caso do 10, tem dois dígitos

printf("1");

printf("%c",numeros[carta%13]);

// naipe

printf("%c ",naipes[carta/13]);

}

}

main() // alínea A

{

int carta;

printf("Indique carta [0-51]: ");

scanf("%d",&carta);

MostraCarta(carta);

}

/* Jogo dos Pontos e Quadrados

*/

#define TAMANHO_MAXIMO 10

void Quadricula(int tamanho)

{

int i,j,ncasas;

for(i=0;i<tamanho+1;i++) {

if(i==0) {

// colocar a identificação das colunas

printf("\n ");

for(j=0;j<tamanho+1;j++)

printf("%c ",j+'0');

printf("\n");

}

// colocar a identificação das linhas

printf("%c ",i+'A');

for(j=0;j<tamanho;j++)

printf("+ ");

printf("+\n");

if(i<tamanho) {

printf(" ");

for(j=0;j<tamanho;j++)

printf(" ");

printf("\n");

}

}

}

void main()

{

int dimensao,jogador;

// leitura de dados iniciais

printf("\nJogo dos pontos e quadrados\nIndique dimensao [2-%d]: ", TAMANHO_MAXIMO-1);

scanf("%d",&dimensao);

if(dimensao<2)

dimensao=2;

else if(dimensao>TAMANHO_MAXIMO-1)

dimensao=TAMANHO_MAXIMO-1;

// desenhar o mapa de jogo

Quadricula(dimensao);

}

// Black Jack

/* Mostrar uma carta dado um número de 0 a 51 */

int main()

{

int valor;

char *naipe = "POCE";

char *numero = "A234567890VDR";

scanf("%d", &valor);

if (valor % 13 == 9)

printf("1");

printf("%c%c", numero[valor % 13], naipe[valor / 13]);

}

// Mine sweeper

int main() {

int N,M;

int i,j;

scanf("%d",&N);

scanf("%d",&R);

/* Mostre um tabuleiro de N linhas e M colunas */

for(i=0;i<N;i++) {

for(j=0;j<M;j++)

printf("+");

printf("\n");

}

}

/*

Dominó de 4 lados (ou em quadrado em que se juntam cantos), a colocar sempre em baixo num dos lados (a peça pode rodar).

A - pedir para imprimir a peça;

*/

void main()

{

int peca[4], i;

// entrada de dados, 4 números

for(i=0;i<4;i++)

scanf("%d", &(peca[i]));

printf("++++\n+%d%d+\n+%d%d+\n++++\n",

peca[0], peca[1], peca[3], peca[2]);

}

Critérios de Correção

Em termos de critérios de correção, sendo a prova realizada com papel e esferográfica, não se pode aplicar os mesmos critérios que nos e-fólios, em que os estudantes utilizaram o computador.

Critérios do Grupo I:

• 0,5 por cada erro detetado, até ao máximo de 3 valores (basta identificar 6 dos 7 erros).

• 0,5 por erro introduzido não existente (cancela um erro bem identificado)

• 0,3 por um erro identificado, mas não corrigido

• 0,2 erro detetado, mas corrigido de forma incorreta

Grupo II / III / IV

Critérios positivos (soma de 0 a 1,5 valores):

• + 0,5 - assinatura correta

• + 0,5 - retorno da função correto

• + 0,5 - lógica relativamente correta

Negativos (subtrai de 3 a 1,5)

• - 0,5 - erro no código (expressão numérica/lógica incorreta; instrução incorreta)

• - 0 - um só erro sintático (inclui troca de aspas por plicas e vice-versa)

• - 0,5 - dois ou mais erros sintáticos menores.

Enunciados 2010 - 2018

Enunciados

Época Normal:

• Número de palavras sem tags html
• Master mind
• Binpacking
• Números mágicos, número de divisores
• Poker de dados
• Cifra de César
• Contagens com urnas
• Gerar cartas válidas de BINGO

Época de Recurso:

• Normalizar texto
• Gerador de apostas totobola
• Listas, intersecção, ordenação
• Jogo do 24
• Merge sort
• Numeração romana
• Jogo da vida
• Jogo da Forca