Projeto de Algoritmos e Resolução de Problemas

Pensamento computacional 计算思维 é o conjunto de ferramentas mentais para analisar um problema e projetar uma solução que um computador possa executar. Duas principais são abstração e decomposição.

Abstração

Abstraction 抽象 significa manter as características essenciais de um problema e ignorar detalhes irrelevantes, fornecendo um modelo mais simples.

Exemplos:

• um mapa de rede de trens mantém as estações e linhas, mas ignora a geografia.
• uma class em programação orientada a objetos mantém apenas os atributos e métodos que o sistema precisa.
• uma função oculta uma parte do trabalho atrás de um nome.

Um modelo completo de qualquer problema real seria muito grande para raciocinar, então a abstração é essencial.

O avaliador pede o objetivo da abstração e seus benefícios. Objetivo: produzir um modelo mais simples de um problema que contenha apenas os detalhes necessários para resolvê-lo. Benefícios: o problema fica mais fácil de entender e programar; o programa é menor e mais rápido de escrever e testar; o mesmo modelo pode ser reutilizado para problemas semelhantes. Quando solicitado a produzir um modelo abstrato de um sistema, liste apenas os dados e ações que a tarefa exige. Para uma grade escolar, isso significa as aulas, salas, professores e períodos; não significa a cor das salas ou a idade dos professores.

Decomposição

Decomposição 分解 significa dividir um grande problema em subproblemas menores, cada um mais fácil de resolver e tratado individualmente.

1. encontre as partes principais da tarefa.
2. divida cada uma em subtarefas menores.
3. continue até que cada uma seja pequena o suficiente para ser projetada diretamente.
4. resolva as tarefas pequenas e combine-as.

Para controle de estoque: "gerenciar estoque" → "registrar vendas", "registrar entregas", "produzir relatórios" → ("registrar vendas") "consultar produto", "diminuir contagem de estoque", "salvar a transação". A decomposição torna grandes problemas gerenciáveis, permite que uma equipe divida o trabalho e gera código modular — cada módulo se torna uma procedura 过程 ou função.

"Explique por que a decomposição é usada" é uma questão de três pontos com formato fixo. Dê três benefícios separados: cada subproblema 子问题 é pequeno o suficiente para ser projetado, codificado e testado independentemente; diferentes programadores podem trabalhar em diferentes módulos 模块 ao mesmo tempo; um módulo já existente (ou uma rotina de biblioteca) pode ser reutilizado, e um erro é mais fácil de encontrar porque está contido em um único módulo. Um diagrama estrutural (tópico 12) é o diagrama de uma decomposição: o programa no topo, seus módulos abaixo, e os dados passados entre eles.

Um algoritmo 算法 é uma solução expressa como uma sequência de passos definidos. Cada passo é unívoco 无歧义 (um único significado), determinístico 确定性 (mesma entrada → mesma saída), finito (os passos terminam) e efetivo (cada um pode ser executado). Um algoritmo diz o que fazer, independente da linguagem de programação usada para implementá-lo.

Ao iniciar um algoritmo, liste todas as peças de dados em uma tabela de identificadores 标识符表 — seu identificador 标识符 (o nome da variável 变量), tipo de dado 数据类型 e descrição. A tabela do exame tem exatamente estas três colunas:

Use nomes descritivos (ItemCost, não x): um identificador começa com uma letra, não contém espaços e é escrito da mesma forma toda vez que aparece. Tipos comuns são INTEGER, REAL, STRING, CHAR, BOOLEAN, DATE, além de arrays. A tabela força você a nomear todas as peças de dados antes de escrever o código, e uma questão "complete a tabela de identificadores" dá um ponto por cada tipo de dado ou descrição correta, então escreva o tipo exatamente como o guia de pseudocódigo faz.

Pseudocódigo 伪代码 é uma maneira estruturada e independente de linguagem para descrever algoritmos.

1. Sequência

Passos são executados um após o outro (sequência 顺序):

INPUT Name
INPUT Age
OUTPUT "Hello", Name

2. Seleção

Uma escolha de quais passos executar, baseada em uma condição (seleção 选择):

IF Age >= 18 THEN
    OUTPUT "Adult"
ELSE
    OUTPUT "Minor"
ENDIF

Para mais opções, use CASE OF ... ENDCASE.

3. Iteração

Repetir um bloco (iteração 迭代, um laço 循环):

FOR i ← 1 TO 10
    OUTPUT i
NEXT i

Um loop WHILE testa a condição antes de cada passagem (pode rodar zero vezes); um loop REPEAT...UNTIL testa depois de cada passagem (sempre roda pelo menos uma vez).

WHILE Total < 100 DO
    INPUT Value
    Total ← Total + Value
ENDWHILE

REPEAT
    INPUT Mark
UNTIL Mark >= 0 AND Mark <= 100

Escolher o loop vale um ponto: FOR quando você sabe quantas vezes (um loop controlado por contador 计数循环); WHILE quando o loop pode não rodar de todo (um loop pré-condição 前测循环); REPEAT ... UNTIL quando deve rodar pelo menos uma vez, como na validação de entrada (um loop pós-condição 后测循环). Uma resposta "descreva a construção de iteração" nomeia a construção, diz onde a condição é testada e dá a consequência (zero vezes ou pelo menos uma vez).

Operações comuns

• atribuição 赋值: x ← 5 (uma seta; = é para comparação).
• entrada/saída: INPUT variable, OUTPUT expression.
• comparações =, <>, <, >, <=, >=; lógica AND, OR, NOT.
• aritmética + - * /, mais DIV (divisão inteira) e MOD (resto).
• strings: LENGTH, LEFT, RIGHT, MID, e & para concatenação 拼接 (juntar).

O pseudocódigo que o exame espera

Toda resposta de pseudocódigo é avaliada contra o guia de pseudocódigo publicado pela Cambridge. Escreva estas formas exatamente:

RAND(100) gera um número real de 0 até (mas não incluindo) 100. INT(RAND(100)) + 1 gera um inteiro de 1 a 100.

Dois hábitos valem pontos em todas as questões: declare toda variável que usar, com o tipo da sua tabela de identificadores, e inicialize 初始化 todo contador 计数器 e total (Count ← 0, Total ← 0) antes do loop que o altera.

Entrada → Processamento → Saída

Todo programa segue este formato:

INPUT Length
INPUT Width
Area ← Length * Width
OUTPUT "Area = ", Area

Listar entradas e saídas primeiro deixa o algoritmo mais limpo.

Exemplo resolvido. Escreva pseudocódigo que insere 100 inteiros e outputa quantos deles, e a soma desses, estão entre 10 e 20 inclusos.

Tabela de identificadores: Count : INTEGER (contador de loop), Value : INTEGER (o inteiro inserido), InRange : INTEGER (quantos estavam no intervalo), Total : INTEGER (soma deles).

DECLARE Count, Value, InRange, Total : INTEGER
InRange ← 0
Total ← 0
FOR Count ← 1 TO 100
    INPUT Value
    IF Value >= 10 AND Value <= 20 THEN
        InRange ← InRange + 1
        Total ← Total + Value
    ENDIF
NEXT Count
OUTPUT InRange, Total

Se a questão pedir para "identificar duas construções e dizer como cada uma é usada", responda no mesmo formato: iteração, o loop FOR, repete a entrada 100 vezes; seleção, a instrução IF, adiciona um valor apenas quando está no intervalo.

Exemplo resolvido. Um programa escolhe um número secreto inteiro de 1 a 100. O usuário chuta até acertar; após cada chute errado, o programa diz "Muito baixo" ou "Muito alto", e no final ele outputa quantos palpites foram feitos.

Tabela de identificadores: Secret : INTEGER (o número a ser adivinhado), Guess : INTEGER (a entrada do usuário), Tries : INTEGER (quantos palpites até agora).

DECLARE Secret, Guess, Tries : INTEGER
Secret ← INT(RAND(100)) + 1
Tries ← 0
REPEAT
    INPUT Guess
    Tries ← Tries + 1
    IF Guess < Secret THEN
        OUTPUT "Too low"
    ELSE
        IF Guess > Secret THEN
            OUTPUT "Too high"
        ENDIF
    ENDIF
UNTIL Guess = Secret
OUTPUT "You took ", Tries, " guesses"

Um loop REPEAT ... UNTIL é a escolha certa porque o usuário deve chutar pelo menos uma vez. Os pontos são para: o número aleatório no intervalo correto, um loop que termina em um chute correto, o contador que começa em zero e aumenta dentro do loop, as duas mensagens sob as condições certas, e a saída final.

Exemplo resolvido. Outputar dois números inteiros aleatórios diferentes, cada um entre $-10$ e $10$ inclusos.

Há 21 valores possíveis, então INT(RAND(21)) gera de 0 a 20 e subtraindo 10 desloca para o intervalo $-10$ a $10$. O segundo número deve ser gerado novamente até diferir do primeiro:

DECLARE First, Second : INTEGER
First ← INT(RAND(21)) - 10
REPEAT
    Second ← INT(RAND(21)) - 10
UNTIL Second <> First
OUTPUT First, Second

O mesmo algoritmo pode ser escrito de três formas.

• inglês estruturado 结构化英语 — linguagem natural com indentação e palavras-chave fixas; bom para uma descrição de alto nível.
• flowchart 流程图 — um diagrama com formas padrão:

• pseudocódigo — a notação de palavras-chave acima; mais próximo do código.

Você deve ser capaz de converter entre qualquer par: cada IF é um losango de decisão, cada laço é uma seta de retorno, e uma sequência são retângulos empilhados.

SE ... ENTÃO ... SENÃO ... FIM_SE

Refinamento passo a passo 逐步求精 começa com um esboço de alto nível e expande cada etapa até que seja pequena o suficiente para ser codificada. Para uma média de $n$ números:

Nível 1:

Read in the numbers
Compute the average
Output the average

Nível 2:

INPUT n
total ← 0
FOR i ← 1 TO n
    INPUT value
    total ← total + value
NEXT i
average ← total / n
OUTPUT average

C refinamento mantém a estrutura anterior e adiciona detalhes.

Uma questão de seis pontos sobre "aplicar refinamento passo a passo" fornece um esboço de alto nível e pede que cada etapa seja expandida em instruções concretas que um programador poderia codificar. Mantenha as etapas na mesma ordem, nomeie os dados que cada etapa lê ou produz, e pare quando cada linha for uma única entrada, atribuição, saída, laço ou condição. Por exemplo, "validar a senha" torna-se: digite a senha; verifique se seu comprimento é pelo menos 8; verifique se contém pelo menos um dígito; saia "aceita" se ambas as verificações forem bem-sucedidas, caso contrário saia "rejeitada".

Uma declaração lógica 逻辑语句 é uma condição Booleana 布尔 controlada por ramificações, construída a partir de comparações (x > 10), conectivos (AND, OR, NOT) e colchetes. Use-a como condição de IF, WHILE ou REPEAT...UNTIL:

WHILE attempts < 3 AND NOT loggedIn DO
    INPUT password
    IF password = correctPassword THEN
        loggedIn ← TRUE
    ELSE
        attempts ← attempts + 1
    ENDIF
ENDWHILE

Precedência 优先级 (maior para menor): NOT, depois AND, depois OR. Use colchetes quando tiver dúvidas. Erros comuns:

• a = 1 OR 2 está errado — escreva a = 1 OR a = 2.
• NOT a > 5 significa NOT (a > 5), ou seja, a <= 5.
• NOT (A AND B) é o mesmo que (NOT A) OR (NOT B) (Lei de De Morgan 德摩根定律) — útil para simplificar condições.

Transformar uma frase em uma declaração lógica é uma habilidade testada diretamente nos exames. "Um ingresso é gratuito para qualquer pessoa com menos de 5 ou mais de 65 anos" torna-se Age < 5 OR Age > 65. "Uma nota é válida se for um número inteiro de 0 a 100" torna-se Mark >= 0 AND Mark <= 100. "O laço para quando o arquivo termina ou dez registros foram lidos" torna-se UNTIL EOF(File) OR Count = 10. Escreva cada comparação por extenso: Age > 65 e Age < 5, nunca Age > 65 OR < 5.

Exemplo resolvido. Escreva uma tabela de identificadores e pseudocódigo para ler 10 números e exibir o maior. A tabela de identificadores nomeia cada variável com seu tipo de dado e propósito: Count : INTEGER (contador de laço), Num : REAL (o número acabado de ser lido), Max : REAL (maior até agora).

Max ← -999999
FOR Count ← 1 TO 10
    INPUT Num
    IF Num > Max THEN
        Max ← Num
    ENDIF
NEXT Count
OUTPUT Max

A decisão de design que carrega os pontos é inicializar Max: ela deve começar abaixo de qualquer entrada possível - ou, ainda mais seguro, ser definida como o primeiro número lido. Inicializá-la como 0 faz o algoritmo retornar incorretamente 0 para uma lista de números negativos, um bug que sua traçagem só expõe se os dados de teste incluírem um negativo.

Uma questão de definição é avaliada contra wording fixo. Aprenda estas exatamente, e dê apenas uma resposta.

• Defina um algoritmo como uma sequência inequívoca, finita e determinística de passos, independente da linguagem.
• Use as três construções corretamente — sequência, seleção, iteração — e mantenha uma tabela de identificadores com tipos de dados.
• Divida um problema por decomposição e abstração, depois refinamento passo a passo.
• Escreva pseudocódigo que realmente funcionaria: declare variáveis e siga o estilo de pseudocódigo do exame.

Erros comuns

• Usar = para atribuir um valor. Atribuição é ←; = é uma comparação.
• Esquecer ENDIF, ENDWHILE, ENDCASE ou NEXT. Toda construção fecha, e a palavra de fechamento é onde o ponto da construção é verificado.
• Não inicializar um total ou contador antes do laço, de modo que o algoritmo soma a um valor que nunca existiu.
• Usar um laço FOR quando o número de repetições é desconhecido. Ler até um valor sentinela ou um palpite correto precisa de WHILE ou REPEAT ... UNTIL.
• Escrever Age > 65 OR < 5. Cada lado de OR e AND deve ser uma comparação completa.
• Responder "explique por que a decomposição é usada" com um benefício escrito de três maneiras. Três pontos precisam de três benefícios diferentes.