Algorithms and pseudocode · Algoritmos e pseudocódigo
| English | Português |
|---|---|
| algorithm/ˈælɡərɪθəm/ | algoritmo |
| sequence/ˈsiːkwəns/ | sequência |
| deterministic/dɪˌtɜːmɪˈnɪstɪk/ | determinista |
| identifier table/aɪˈdentɪfaɪə ˈteɪbl/ | tabela de identificadores |
| variable/ˈveərɪəbl/ | variável |
| data type/ˈdeɪtə taɪp/ | tipo de dado |
| pseudocode/ˈsuːdəʊkəʊd/ | pseudocódigo |
| assignment/əˈsaɪnmənt/ | atribuição |
| loop/luːp/ | laço |
| count-controlled loop/kaʊnt kənˈtrəʊld luːp/ | laço controlado por contagem |
| pre-condition loop/priː kənˈdɪʃn luːp/ | pré-condição do laço |
| post-condition loop/pəʊst kənˈdɪʃn luːp/ | pós-condição do laço |
| iteration/ˌɪtəˈreɪʃn/ | iteração |
| selection/sɪˈlekʃn/ | seleção |
| flowchart/ˈfləʊtʃɑːt/ | fluxograma |
| stepwise refinement/ˈstepwaɪz rɪˈfaɪnmənt/ | refinamento passo a passo |
The most expensive hyphen in history
- On 22 July 1962 the Mariner 1 rocket, bound for Venus, was blown up 293 seconds after launch.
- The cause was one missing bar over a symbol in the guidance equations. The computer followed the written steps exactly, and the written steps were wrong.
- A computer never fills in what you meant. Every step you give it must have exactly one meaning.
- That is why this lesson is about writing steps a machine can follow: algorithms 算法.
O hífen mais caro da história
- Em 22 de julho de 1962, o foguete Mariner 1, rumo a Vênus, foi destruído 293 segundos após o lançamento.
- A causa foi uma barra faltante sobre um símbolo nas equações de orientação. O computador seguiu os passos escritos exatamente, e os passos escritos estavam errados.
- Um computador nunca preenche o que você quis dizer. Cada passo que você lhe dá deve ter exatamente um significado.
- É por isso que esta aula é sobre escrever passos que uma máquina possa seguir: algoritmos 算法.
What an algorithm is
- An algorithm is a solution to a problem expressed as a sequence of defined steps.
- Each step is unambiguous (one meaning), deterministic 确定性 (same input → same output), finite (the steps end) and effective (each step can actually be done).
- It says what to do, independent of any programming language, and every one follows input → process → output.
Every algorithm has the same shape: input, process, output
O que é um algoritmo
- Um algoritmo é uma solução para um problema expressa como uma sequência de passos definidos.
- Cada passo é não ambíguo (um significado), determinístico 确定性 (mesmo entrada → mesma saída), finito (os passos terminam) e efetivo (cada passo pode realmente ser executado).
- Ele diz o que fazer, independente de qualquer linguagem de programação, e todos seguem entrada → processo → saída.
Todo algoritmo tem a mesma forma: entrada, processo, saída
An algorithm is "deterministic". This means: · Um algoritmo é "determinístico". Isso significa:
Deterministic = same input → same output every time. (Finite = the steps end; unambiguous = one meaning per step.) · Determinístico = mesma entrada → mesma saída toda vez. (Finito = os passos terminam; inequívoco = um significado por passo.)
Worked example: the identifier table
- Before writing code, list every piece of data in an identifier table 标识符表: its variable 变量 name, its data type 数据类型 and a description.
- A shop's stock program stores
"Fruit",20/02/2025,12.67andTRUE. The exam asks for a name and a type for each. Category : STRING(a category of stock),DateSold : DATE(when it was sold),ItemCost : REAL(the cost),InStock : BOOLEAN(is it in stock?).- One mark per row for the name and the type, so write the type exactly as the pseudocode guide does:
INTEGER,REAL,STRING,CHAR,BOOLEAN,DATE.
An identifier table names every piece of data before you write code
Exemplo resolvido: a tabela de identificadores
- Antes de escrever código, liste todas as peças de dados em uma tabela de identificadores 标识符表: seu nome de variável 变量, seu tipo de dado 数据类型 e uma descrição.
- Um programa de estoque de loja armazena
"Fruit",20/02/2025,12.67eTRUE. A prova pede um nome e um tipo para cada um. Category : STRING(uma categoria de estoque),DateSold : DATE(quando foi vendido),ItemCost : REAL(o custo),InStock : BOOLEAN(está em estoque?).- Uma marca por linha para o nome e o tipo, então escreva o tipo exatamente como o guia de pseudocódigo faz:
INTEGER,REAL,STRING,CHAR,BOOLEAN,DATE.
Uma tabela de identificadores nomeia todas as peças de dados antes de escrever o código
In an identifier table, the data type for a value such as 12.67 (a cost) is ____. · Em uma tabela de identificadores, o tipo de dado para um valor como 12.67 (um custo) é ____.
A number with a decimal part is a REAL. INTEGER is for whole numbers, STRING for text, BOOLEAN for TRUE/FALSE and DATE for a date. · Um número com parte decimal é um REAL. INTEGER é para números inteiros, STRING para texto, BOOLEAN para VERDADEIRO/FALSO e DATE para data.
The three constructs
IF … THEN … ELSE … ENDIF
- Assignment 赋值 stores a value with an arrow,
Total ← Total + Value;=is for comparison.DIVis whole-number division andMODthe remainder, so17 MOD 5 = 2.
The three building blocks of any algorithm
Os três construtores
SE … ENTÃO … SENÃO … FIM_SE
- Atribuição 赋值 armazena um valor com uma seta,
Total ← Total + Value;=é para comparação.DIVé divisão inteira eMODo resto, então17 MOD 5 = 2.
INPUT Age # sequence
IF Age >= 18 THEN
# selection
ENDIF
OUTPUT "Adult"
ELSE
OUTPUT "Minor"
ENDIF
FOR Count <- 1 TO 10 # iteration
OUTPUT Count
NEXT Count
Os três blocos fundamentais de qualquer algoritmo
Selection: follow the IF / ELSE branches · Seleção: siga os ramos DO / SE NÃO
Drag the score and watch which branch runs. Selection tests each condition in turn and takes the FIRST one that is true — that is how IF … ELSE IF … ELSE works. · Arraste a pontuação e observe qual ramo é executado. A seleção testa cada condição por sua vez e toma a PRIMEIRA que for verdadeira — é assim que funciona O SE ... SENÃO SE ... SENÃO.
Match each of the three programming constructs to what it does. · Combine cada uma das três construções de programação com o que ela faz.
Every algorithm is built from just three constructs — sequence, selection and iteration. · Todo algoritmo é construído a partir de apenas três construções — sequência, seleção e iteração.
In this pseudocode, which symbol means assignment (store a value)? · Neste pseudocódigo, qual símbolo significa atribuição (armazenar um valor)?
Assignment uses ← (e.g. x ← 5); = is reserved for comparison. · Atribuição usa ← (ex. x ← 5); = é reservado para comparação.
What is the value of 17 MOD 5? · Qual é o valor de 17 MOD 5?
MOD gives the remainder: $17 = 3 \times 5 + 2$, so 17 MOD 5 = 2. (17 DIV 5 = 3.) · MOD dá o resto: $17 = 3 \times 5 + 2$, então 17 MOD 5 = 2. (17 DIV 5 = 3.)
Which loop?
FOR … NEXTwhen you know how many times: a count-controlled loop 计数循环.WHILE … ENDWHILEtests the condition before each pass, so the body may run zero times: a pre-condition loop 前测循环.REPEAT … UNTILtests after each pass, so the body always runs at least once: a post-condition loop 后测循环. Validating an input is the classic case.- A "describe the iteration construct" answer names the loop, says where the condition is tested, and gives the consequence.
A WHILE loop tests before the body runs; a REPEAT … UNTIL loop tests after it
Qual loop?
FOR … NEXTquando você sabe quantas vezes: um loop controlado por contagem 计数循环.WHILE … ENDWHILEtesta a condição antes de cada passagem, então o corpo pode ser executado zero vezes: um loop de pré-condição 前测循环.REPEAT … UNTILtesta depois de cada passagem, então o corpo sempre é executado pelo menos uma vez: um loop de pós-condição 后测循环. Validar uma entrada é o caso clássico.- Uma resposta "descreva o construtor de iteração" nomeia o loop, diz onde a condição é testada e dá a consequência.
Um loop WHILE testa antes do corpo rodar; um loop REPEAT … UNTIL testa depois dele
How does a WHILE loop differ from a REPEAT...UNTIL loop? · Como um loop WHILE difere de um loop REPEAT...UNTIL?
WHILE checks first (can run 0 times); REPEAT...UNTIL checks after, so it always runs at least once. · WHILE verifica primeiro (pode rodar 0 vezes); REPEAT...UNTIL verifica depois, então sempre roda pelo menos uma vez.
A FOR loop is count-controlled (it repeats a fixed number of times), while a WHILE loop is condition-controlled (it repeats until a condition changes). · Um loop FOR é controlado por contagem (repete um número fixo de vezes), enquanto um loop WHILE é controlado por condição (repete até uma condição mudar).
Use FOR when you know how many passes; use WHILE/REPEAT when you loop until something becomes true. · Use FOR quando souber quantas passagens serão necessárias; use WHILE/REPEAT quando looping até algo se tornar verdadeiro.
Worked example: from words to pseudocode
- Task: input 100 integer values, add up only the positive ones, and output the total.
- Plan the data first:
Count,TotalandNextNumber, allINTEGER. Then the three constructs do the rest.
- The follow-up asks you to identify the constructs: iteration (the
FORloop repeats the input 100 times), selection (theIFdecides whether a value is added) and sequence (the statements run in order).
Exemplo resolvido: de palavras para pseudocódigo
- Tarefa: input 100 valores inteiros, some apenas os positivos e output o total.
- Planeje os dados primeiro:
Count,TotaleNextNumber, todosINTEGER. Então os três construtores fazem o resto.
DECLARE Count, Total, NextNumber : INTEGER
Total <- 0
FOR Count <- 1 TO 100
INPUT NextNumber
IF NextNumber > 0 THEN
Total <- Total + NextNumber
ENDIF
NEXT Count
OUTPUT Total
- A questão seguinte pede para você identificar os construtores: iteração (o loop
FORrepete o input 100 vezes), seleção (oIFdecide se um valor é adicionado) e sequência (os comandos rodam em ordem).
Spotting constructs in an extract
- A favourite question shows five pseudocode extracts and asks you to tick which of assignment, selection, iteration each one uses.
Result ← CalculateTotal()is an assignment.WHILE IsClosedis iteration.REPEAT … INPUT Value … UNTIL Sales[4] > Valueis iteration and assignment (INPUTstores a value). IF Sales[Current] <= 150 THEN Discount ← TRUE ENDIF- Look at every line of the extract, not only the first one. A row may need two ticks.
Identificando construtores em um trecho
- Uma pergunta favorita mostra cinco trechos de pseudocódigo e pede para marcar quais usam atribuição, seleção, iteração cada um.
Result ← CalculateTotal()é uma atribuição.WHILE IsClosedé iteração.REPEAT … INPUT Value … UNTIL Sales[4] > Valueé iteração e atribuição (INPUTarmazena um valor). IF Sales[Current] <= 150 THEN Discount ← TRUE FIM_SE- Olhe para cada linha do trecho, não apenas a primeira. Uma linha pode precisar de duas marcações.
Which constructs does this extract use? REPEAT … INPUT Value … UNTIL Total > 100. Select all · todos that apply. · Quais construções este extrato utiliza? REPEAT … INPUT Value … UNTIL Total > 100. Selecione todos os que se aplicam.
REPEAT … UNTIL is iteration, and INPUT Value stores a value, which counts as assignment. There is no IF or CASE, so no selection — the UNTIL condition controls the loop, it does not choose between branches. · REPEAT … UNTIL é iteração, e INPUT Value armazena um valor, o que conta como atribuição. Não há SE ou CASO, então não há seleção — a condição UNTIL controla o loop, não escolhe entre ramos.
Flowcharts
- A flowchart 流程图 documents the same algorithm as a picture. Ovals are
STARTandEND, rectangles are processes, parallelograms areINPUT/OUTPUT, and a diamond is a decision. - A diamond is where selection happens, and a flow line that goes back up the chart is a loop.
- The exam asks both ways: pseudocode from a flowchart, and a flowchart from pseudocode or structured English. Every symbol you draw should map to one line of pseudocode.
Each flowchart symbol maps to one kind of pseudocode statement
Fluxogramas
- Um fluxograma 流程图 documenta o mesmo algoritmo que um desenho. Elipses são
STARTeEND, retângulos são processos, paralelogramos sãoINPUT/OUTPUT, e um losango é uma decisão. - Um losango é onde ocorre a seleção, e uma linha de fluxo que volta para cima no diagrama é um laço.
- A prova pede nos dois sentidos: pseudocódigo de um fluxograma, e um fluxograma de pseudocódigo ou inglês estruturado. Cada símbolo desenhado deve corresponder a uma linha de pseudocódigo.
Cada símbolo de fluxograma corresponde a um tipo de instrução de pseudocódigo
In a flowchart, what does a diamond represent? · Em um fluxograma, o que representa um losango?
Diamonds are where selection happens, and a diamond whose flow line goes back up the chart is a loop test. Rectangles are processes, parallelograms input/output, ovals START and END. · Losangos são onde ocorre a seleção, e um losango cuja linha de fluxo volta para cima no diagrama é um teste de loop. Retângulos são processos, paralelogramos entrada/saída, ovais INÍCIO e FIM.
Worked example: the guessing game
- The program picks a random integer from 1 to 100, then asks for guesses until the user gets it. The user must guess at least once, so the loop is a
REPEAT … UNTIL.
- Follow the flowchart: one decision diamond for the loop test, two for the hints, and every flow line ends up back at
INPUT Guessor atEND.
The guessing game as a flowchart: the loop returns to the input until the guess matches
Exemplo resolvido: o jogo de adivinhar
- O programa sorteia um inteiro aleatório de 1 a 100 e depois pede palpites até que o usuário acerte. O usuário deve palpitar pelo menos uma vez, então o loop é um
REPEAT … UNTIL.
DECLARE Target, Guess : INTEGER
Target <- INT(RAND(100)) + 1
REPEAT
INPUT Guess
IF Guess < Target THEN
OUTPUT "Too low"
ELSE
IF Guess > Target THEN
OUTPUT "Too high"
ENDIF
ENDIF
UNTIL Guess = Target
OUTPUT "Correct"
- Siga o fluxograma: um losango de decisão para o teste do laço, dois para as dicas, e cada linha de fluxo termina voltando para
INPUT Guessou emEND.
O jogo de adivinhar como um fluxograma: o laço retorna à entrada até que o palpite corresponda
Why is REPEAT … UNTIL the right loop for the guessing game? · Por que REPEAT … UNTIL é o loop certo para o jogo de adivinhação?
A post-condition loop always runs its body once before testing, which matches a game that needs at least one guess. A WHILE loop would need a guess before the loop just to have something to test. · Um loop pós-condição sempre executa seu corpo uma vez antes de testar, o que corresponde a um jogo que precisa de pelo menos um palpite. Um loop WHILE precisaria de um palpite antes do loop apenas para ter algo para testar.
Stepwise refinement
- Stepwise refinement 逐步求精 means starting from an outline and expanding each step into more detailed steps, again and again, until every step can be written directly as pseudocode.
- "Process an order" → "get the items", "calculate the total", "take payment" → "calculate the total" becomes "for each item, add price × quantity; apply any discount".
- Each level is a refinement of the one above, and the finished levels together are the design. "Describe stepwise refinement" wants the outline, the expansion and the stopping rule.
Refine each step until it can be coded directly
Refinamento passo a passo
- Refinamento passo a passo 逐步求精 significa começar de um esboço e expandir cada passo em passos mais detalhados, repetidamente, até que cada passo possa ser escrito diretamente como pseudocódigo.
- "Processar um pedido" → "obter os itens", "calcular o total", "receber o pagamento" → "calcular o total" torna-se "para cada item, somar preço × quantidade; aplicar qualquer desconto".
- Cada nível é um refinamento do nível acima, e os níveis finais juntos formam o projeto. "Descrever refinamento passo a passo" quer dizer o esboço, a expansão e a regra de parada.
Refine cada passo até que possa ser codificado diretamente
Put the stages of stepwise refinement in order. · Coloque as etapas do refinamento passo a passo em ordem.
Outline first, then refine level by level; you stop when a step is one line of pseudocode. · Esboce primeiro, depois refine nível por nível; você para quando um passo é uma linha de pseudocódigo.
Logic statements
- Parts of a solution are defined by logic statements: conditions built from comparisons (
=,<>,<,>,<=,>=) joined byAND,ORandNOT. - A valid mark:
Mark >= 0 AND Mark <= 100. A discount applies if the customer is a member or spends over 50:IsMember OR Total > 50. NOT (Mark < 40)says the same thing asMark >= 40. Write the statement, then test it with a value on each side of the boundary.
Comparisons joined by AND, OR and NOT build the conditions an algorithm needs
Declarações lógicas
- As partes de uma solução são definidas por declarações lógicas: condições construídas a partir de comparações (
=,<>,<,>,<=,>=) unidas porAND,OReNOT. - Uma nota válida:
Mark >= 0 AND Mark <= 100. Um desconto se aplica se o cliente for membro ou gastar mais de 50:IsMember OR Total > 50. NOT (Mark < 40)diz a mesma coisa queMark >= 40. Escreva a declaração, depois teste-a com um valor de cada lado da fronteira.
Comparações unidas por AND, OR e NOT constroem as condições que um algoritmo precisa
NOT (Mark < 40) is true for exactly the same values of Mark as Mark >= 40. · NOT (Mark < 40) é verdadeiro exatamente para os mesmos valores de Mark que Mark >= 40.
Negating "less than 40" gives "40 or more". Test the boundary: Mark = 40 makes Mark < 40 false, so NOT of it is true, and 40 >= 40 is also true. · Negar "menor que 40" resulta em "40 ou mais". Teste o limite: Mark = 40 torna Mark < 40 falso, então NÃO dele é verdadeiro, e 40 >= 40 também é verdadeiro.
Marks that slip away
←assigns and=compares.IF Total = 0is a test;Total = 0on its own line earns nothing.- Every construct closes:
ENDIF,ENDWHILE,UNTIL,NEXT,ENDCASE. A missing closer breaks the structure mark. - Declare before you use, and initialise a running total to
0. WHILEmay never run,REPEATalways runs once. Choose the loop that matches the task, and say why if asked.
Marcas que escapam
←atribui e=compara.IF Total = 0é um teste;Total = 0em sua própria linha não ganha pontos.- Todo constructo fecha:
ENDIF,ENDWHILE,UNTIL,NEXT,ENDCASE. Um fechador ausente quebra a nota de estrutura. - Declare antes de usar, e inicialize um total acumulador para
0. WHILEpode nunca rodar,REPEATsempre roda uma vez. Escolha o laço que combina com a tarefa, e diga por quê se perguntado.
You've got it
- an algorithm's steps are unambiguous, deterministic, finite, effective; plan the data in an identifier table
- three constructs: sequence, selection (
IF/CASE), iteration (FOR/WHILE/REPEAT);WHILEtests before,REPEATafter - a flowchart and pseudocode describe the same algorithm; stepwise refinement expands an outline until it can be coded
- conditions are logic statements: comparisons joined with
AND,OR,NOT
Entendeu?
- os passos de um algoritmo são não ambíguos, determinísticos, finitos, eficazes; planeje os dados em uma tabela de identificadores
- três constructos: sequência, seleção (
IF/CASE), iteração (FOR/WHILE/REPEAT);WHILEtesta antes,REPEATdepois - um fluxograma e pseudocódigo descrevem o mesmo algoritmo; refinamento passo a passo expande um esboço até que possa ser codificado
- condições são declarações lógicas: comparações unidas com
AND,OR,NOT