Bem vindo ao curso de Introdução à Ciência da Computação destinado aos alunos regulares da Universidade de São Paulo e a todos os demais interessados em aprender não só a programar em Python mas também os conceitos básicos da Ciência da Computação! Aqui você irá aprender os principais conceitos introdutórios de Ciência da Computação e também aprenderá a desenvolver pequenos programas na linguagem Python. Este curso não possui pré-requisitos. Não é esperado que você tenha qualquer experiência prévia em programação, no entanto, se supõe que o aluno domine os conceitos básicos de matemática do ensino fundamental. O objetivo principal é desenvolver o raciocínio aplicado à formulação e resolução de problemas computacionais. O ato de programar é uma ferramenta útil para trabalhar esse raciocínio, bem como tornar mais concretos outros conceitos comuns em Ciência da Computação. Ao término do curso, o aluno estará capacitado para escrever pequenos programas em Python e prosseguir para a parte 2 do curso. Bom aprendizado! === Esse curso foi elaborado com o apoio dos Profs. José Coelho de Pina e Carlos Hitoshi Morimoto do Departamento de Ciência da Computação do IME-USP. Nelson Posse Lago, gerente técnico do CCSL-IME-USP, Athos Ribeiro e Yorah Bosse têm sido excelentes assistentes de ensino, ajudando a manter a qualidade do curso.
Exercício Resolvido
Loading...
來自 Universidade de São Paulo 的課程
Introdução à Ciência da Computação com Python Parte 1
1513 個評分
從本節課中
Repetições Encaixadas
Existem situações em que precisamos trabalhar com repetições de repetições. Vamos ver como isso funciona?
與講師見面
Fabio KonProfessor Titular
Departamento de Ciência da Computação - IME
[MÚSICA] Então vamos ver como
a gente descobre se número é primo por meio de programa Python.
Vamos supor que a gente tem o seguinte problema,
a gente quer fazer programa onde o usuário vai digitando vários números
e para cada número a gente vai dizendo se esse número é primo, ou não é primo.
Como a gente poderia fazer isso?
Vamos abrir aqui novo arquivo.
Teria que ser algo do tipo "iii",
supor número, o usuário vai
digitando números positivos,
então vou fazer: n recebe inteiro,
input, digite número inteiro.
Ele vai digitar aqui número inteiro, daí a gente vai fazendo o seguinte,
enquanto esse número inteiro digitado é maior que zero,
a gente faz o seguinte:
se o número é primo,
se o n é primo,
daí print
n é primo.
O tal ponto de exclamação para ficar bem feliz,
e caso contrário,
a gente imprime que n
não é primo.
Vou colocar uma carinha triste aqui, infelizmente o número não é primo.
[SEM_ÁUDIO] E a gente
vai repetindo isso, daí depois que faz para a gente lê mais outro número aqui.
Na verdade eu vou fazer assim, vou colocar para ler aqui logo no começo.
Não.
Vamos deixar daquele jeito, colocar no final,
senão vou ter que fazer teste a mais.
Assim já vai ficar pouquinho melhor.
Depois vocês podem tentar reorganizar,
aqui a gente começa com determinado número digitado pelo usuário,
daí enquanto esse número aqui for maior que zero, a gente vê, é primo?
Se for, a gente imprime que é primo, caso contrário,
a gente diz que não é primo e lê mais número ali do usuário e fica nesse
loop enquanto o usuário digita números maiores que zero.
Quando o usuário digitar número igual a zero ou negativo,
ele cai fora desse while.
Muito simples, resolvemos o problema?
Quase!
Eu simplesmente escondi para debaixo do pano, na verdade, para essa função é primo
a parte mais complicada que é exatamente definir se o número n é primo ou não.
Então, para isso, a gente vai ter que definir aqui uma função,
implementar essa função é primo.
Então, vou definir aqui a função: é primo, que ela recebe como
parâmetro número x aí qualquer, e ela vai ter que
devolver verdadeiro ou falso, de acordo com se aquele número é primo ou não.
Como é que a gente pode verificar se número é primo?
Método que a gente pode fazer é: ir dividindo ele por todos os números,
dois, três, quatro, até chegar no número x e ver se algum deles divide.
Se algum deles divide, o número maior que estritamente maior
que e menor que o próprio x, se algum deles divide, daí ele não é primo.
Dividir significa que o resto da divisão inteira é zero.
É divisor inteiro.
Então como é que a gente pode fazer isso?
Vamos chamar esses números de fatores, então eu vou começar com o fator dois,
e daí a gente vai vendo se cada desses números divide.
Vou fazer o seguinte, enquanto o resto da divisão do número,
não é n, é x dentro da função é primo, o valor é x.
Aqui x.
Enquanto o x, o resto da divisão de x pelo fator,
se for diferente de zero, então,
eu tenho que continuar indo para o próximo fator buscando por algum que divide.
Se for igual a zero,
já não é primo e eu posso cair fora do while e dizer: não é primo.
Então, eu vou continuar no while enquanto não encontrei
divisor e eu vou fazendo isso.
Eu vou fazer: enquanto o fator não
divide aqui, eu vou para o próximo fator,
quem sabe o próximo fator, [INAUDÍVEL] fator mais quem sabe o próximo divide.
Eu vou repetindo esse while aqui, mas note que se o número for primo,
ele vai ser sempre subindo, fator igual a fator mais.
Quando que eu paro?
Tem que ter outro critério de parada, então vou colocar no while: eu quero que
se repita enquanto não encontrei o divisor e também enquanto o número,
enquanto o fator é menor que o x.
Porque se o fator chegou lá no x, eu já posso parar.
Na verdade eu não preciso ir até o x, porque na pior das hipóteses,
qual é a divisão que pode dar o menor número possível?
É quando estou na metade do x, eu dividindo o x pela metade do x,
vai dar dois se for número par.
Se for número ímpar vai dar quase dois, não vai dar dois.
Então, eu posso ir só até x sobre dois.
Porque se até x sobre dois não encontrei fator,
não é depois do x sobre dois que eu vou encontrar outro fator, porque,
depois do x sobre dois, dividindo aquilo pelo x vai dar número menor que dois,
entre e dois, então, não vai ser número inteiro, então eu posso ir só
até essa condição de parada que fator é menor ou igual a x sobre dois.
Na verdade, depois vocês podem pensar mais se tem
número ainda menor que x sobre dois que a gente poderia ir só até ele.
Fica de lição de casa pensar pouco mais sobre isso.
Então, nesse while aqui a gente vai repetindo,
e a gente vai cair fora do while por dois motivos: ou porque essa
primeira parte aqui deu falso ou porque essa segunda parte deu falso.
Se a primeira parte foi falsa, ou seja,
se o x, resto de divisão do x pelo fator, se isso aqui é igual a zero,
daí, não é número primo, então, posso devolver falso.
Devolva falso porque se encontrou uma divisão que deu exata, divisor, então,
não é primo.
Então, tudo bem.
Aliás, aqui acho que a gente tem que ir até o x dividido por dois.
Menor ou igual a x sobre dois.
Nesse caso aqui devolve falso.
Caso contrário, deixa eu botar
tabs aqui, caso contrário,
else, return to, por quê?
Porque se eu cheguei até ao final desse while aqui e não encontrei
nenhum fator cuja divisão desse exata, significa que o número é primo.
Então, nesse caso aqui, eu devo devolver verdadeiro,
indicando que o número é primo.
Vamos ver se a coisa funciona agora.
Para isso eu vou mandar executar aqui.
Vamos compilar, ver se tem algum erro de compilação.
Salvar.
Eu vou chamar de primos.
Encontrei erro de compilação.
Aqui, às vezes eu esqueço esses dois pontos aqui na condição do while.
Ver se tem mais algum outro erro de compilação, ok, pode salvar.
Não tem.
Então: digite número inteiro.
Eu vou digitar o número dez.
Deu erro, vamos ver qual é que é o erro aqui.
O erro, ele falou que o nome é primo
não está definido, isso que deu na linha cinco.
Então, na linha cinco, que é esta linha aqui,
ele diz que não conhece a função: é primo.
Vamos definir a função é primo aqui cima, isso vai resolver o nosso problema.
Vamos compilar novamente.
Digite número inteiro: dez.
Isso resolveu aquele nosso problema.
Ou seja, eu estava usando a função é primo,
antes de ter definido, então, colocando a definição da função ali cima,
é primo, quando ele chega aqui a função é primo já está definida.
E ele disse: dez não é primo, o que está certo, dez não é primo,
porque a gente viu que dez é dois vezes cinco, tem esses dois divisores primos.
Digitar outro número, 20, 20 não é primo,
oito não é primo, nove não é primo, porque nove é três vezes três.
Sete, sete é primo!
Deu certo.
Seis não é primo, cinco é primo.
Quatro não é primo, três é primo.
Vamos ver uns números maiores aqui, 11, 11 é primo,
12 não é primo, 13 é primo, 14, 15, 16.
Vamos pegar aquele número grandão que eu tinha visto ali,
esse número aqui quando calculei a multiplicidade por fatores primos,
ele disse que esse aqui é dos fatores,
então vou ver se esse aqui realmente é número primo.
É número bem grandão: 654923 é número primo, primo grande.
Vamos ver se funciona para o dois, dois é caso meio problemático.
Diz que dois não é primo, aí depende da sua definição se, dois é primo.
Se dois é primo, a gente precisa tratar ele,
pelo menos esse meu algoritmo não está capturando o dois,
então a gente tem duas formas: uma forma complicada e uma forma simples.
A forma complicada é a gente alterar esse algoritmo de forma que para o dois,
ele acabe devolvendo true também.
Eu vou fazer agora uma forma mais simples e fica de lição de casa a forma mais
sofisticada.
A forma simples é simplesmente você colocar aqui: if x igual a dois,
return true.
Fazendo isso aqui e executando agora,
se eu der quatro,
não é primo, três é primo, dois é primo.
Ele está funcionando aqui para o dois, mas o dois eu estou tratando como caso
excepcional, caso separado, por isso eu introduzi esse if aqui.
Não é a forma mais elegante, a forma mais elegante é ter
algoritmo genérico que funcionasse para todos os casos,
mas teria que pensar mais para descobrir como fazer isso.
Então, parece que está funcionando, agora vocês já têm, já sabem como fazer o
programa para identificar se determinado número é primo ou não.
[MÚSICA]
[MÚSICA]
[MÚSICA]
