Programação de Computadores

Instituto de Computação UFFDepartamento de Ciência da Computação

Otton Teixeira da Silveira Filho

Conteúdo

● Alguns Conceitos sobre Linguagens

● Conceito de Algoritmo

● Pseudocódigo

● Tipos de Variáveis

● Operadores

● Estruturas de Controle

● Estruturas de Dados

● Subprogramação

Exercício

Determine se um número é capicua

Exercício

Melhor dizer o que é um número capicua...

Exercício

Um número é capicua (ou número palíndromo) se o seu reverso é ele próprio.

Exemplos:

● 121

● 3516153

● 2002

● 111111111111

Exercício

Precisamos de um algoritmo...

Exercício

Observe que nenhum programa deste material tem por finalidade ser eficiente, inteligente ou referência de qualidade de desenvolvimento

A intenção está no aprendizado de construção de algoritmos, implementação de algoritmos e apresentar conceitos e elementos de Python

Exercício

Criemos um algoritmo possível para determinar se um número é capicua

O primeiro algoritmo usará o fato que aqui verificaremos se um número é capicua na base 10

Exercício

...

Exercício

Repare que a entrada se dá como cadeia de caracteres. No final das contas, ser número não importaria aqui.

Exercício

Agora tentemos outro algoritmo que se baseia que numeros int são representados como usa sucessão de algarismos

Exercício

...

Exercício

Repare que a entrada se dá como cadeia de caracteres. No final das contas, ser número não importaria aqui.

Novamente este programa não faz uma filtragem da entrada. Modifique este programa para que só admita como entrada uma cadeia de caracteres que contenha apenas algarismos.

Exercício – Constante de Kaprekar

Faça um programa em Python no qual será solicitado que se entre com um número de quatro algarismos sendo que pelo menos dois algarismos diferentes, podendo haver complementação de zeros à esquerda.

i) Ordene os algarismos em ordem crescente e em ordem decrescente, colocando estes valores em duas variáveis

ii) Subtraia da variável de maior valor a de menor valor

iii) Se o valor da subtração for 6174, pare e imprima quantos passos foram dados. Caso não, volte ao passo ii.

Exercício

Melhor dar um exemplo:

Escolhamos 1726 que gera 7621 e 1267

Exercício

Melhor dar um exemplo:

Escolhamos 1726 que gera 7621 e 1267

● 7621 – 1267 = 6354 que gera 6543 e 3456

● 6543 – 3456 = 3087 que gera 8730 e 0378

● 8730 – 0378 = 8352 que gera 8532 e 2358

● 8532 – 23 58 = 6174

se você insistir e gerar 7641 e 1467

● 7641 – 1467 = 6174

Exercício

Determine os números primos menores ou iguais a n usando o Crivo de Eratóstenes.

Crivo de Eratóstenes

Vejamos um exemplo para n = 20

i) Escreva os números de 1 a 20

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

ii) corte da lista os múltiplos de 2

1, 2, 3, x, 5, x, 7, x, 9, x, 11, x, 13, x, 15, x, 17, x, 19, x

ii) corte da lista múltiplos de 3

1, 2, 3, x, 5, x, 7, x, x, x, 11, x, 13, x, x, 17, x, 19, x

iii) como o número 4 já foi cortado, cortemos os múltiplos de 5

1, 2, 3, x, 5, x, 7, x, x, x, 11, x, 13, x, x, 17, x, 19, x

Crivo de Eratóstenes

iv) como o número 6 já foi cortado, cortemos os múltiplos de 7

1, 2, 3, x, 5, x, 7, x, x, x, 11, x, 13, x, x, 17, x, 19, x

v) paramos pois os múltiplos do próximo número não cortado, 11, é maior que 20

Crivo de Eratóstenes

Repare que estamos matando um bocado de coisas que já estão mortas

Crivo de Eratóstenes

Uma forma de implementar está em preenchermos um vetor com o valor igual ao seu índice e “matarmos“ os valores múltiplos de cada valor no vetor partindo de 2. Observe que

● Como os primeiros múltiplos serão os de 2, não tem sentido matar valores maiores que n/2

● Da mesma forma, não há sentido em matar valores múltiplos de 3 maiores que n/3 ou múltiplos de 4 maiores que n/4 e etc.

Crivo de Eratóstenes

Mas como “matamos“ os elementos que não são primos?

Uma possibilidade é atribuirmos ao elemento da lista um valor que não se encaixe no que um número primo é.

Crivo de Eratóstenes

...

Crivo de Eratóstenes

Vamos introduzir algumas modificações desta versão

Crivo de Eratóstenes

...

Crivo de Eratóstenes

Aqui fizemos uso de um controle de fluxo de repetição aplicado ao for, usando o continue que salta as instruções que se seguem sem interromper a laço de repetição

Além disto, usando o end no print() de tal forma que imprimimos os números primos separados por vírgula e um espaço em branco

Crivo de Eratóstenes

Repare que não fizemos uma leitura inteligente no programa pois permitimos valores inválidos por serem negativos ou nulos

Crivo de Eratóstenes

Repare que não fizemos uma leitura inteligente no programa pois permitimos valores inválidos por serem negativos ou nulos

No entanto, esta implementação segue o algoritmo como apresentado onde se “mata” o que já está “morto” e, pior, usa os valores “mortos” para “matar” múltiplos dele.

Crivo de Eratóstenes

Repare que não fizemos uma leitura inteligente no programa pois permitimos valores inválidos por serem negativos ou nulos

No entanto, esta implementação segue o algoritmo como apresentado onde se “mata” o que já está “morto” e, pior, usa os valores “mortos” para “matar” múltiplos dele.

● Aperfeiçoe este programa de forma que ele não use valores já “mortos” para “matar” seus múltiplos

Crivo de Eratóstenes

É claro que podemos ter várias implementações do mesmo algoritmo.

Crivo de Eratóstenes

É claro que podemos ter várias implementações do mesmo algoritmo.

Uma ideia está em usar uma lista de tipo bool inicialmente preenchido com True, ou seja, a princípio todos os valores representados seriam vistos como primos em potencial. A medida que aplicamos o Crivo de Eratóstenes, marcamos como False os números excluídos como primos

Crivo de Eratóstenes

...

Crivo de Eratóstenes

Repare novamente no uso do continue associado ao for.