Números automórficos

[Bruno Oliveira]

OK, de qualquer maneira obrigado pela brevidade da resposta , fico então á espera de algum feedback e algumas dicas de como tornar o programa mais pitónico .

[Ivo_Timóteo]

Código: Seleccionar Todos

>>> Python + Maths == Functional Paradigm
True

Olhando assim por alto, como é que sabes que os 10 primeiros vão estar antes de 10000000? Vais andar a fazer trabalho a mais

Código: Seleccionar Todos

for x in range(1,10000000,1):

Eu ainda não sei muitas das operações sobre listas que fazem com que os programas fiquem ainda mais bonitos... Mas seguindo um aproach com uma certa orientação funcional, podes chegar a algo deste tipo:

Código: Seleccionar Todos

def N_automorficos(n):
    a = []
    i = 1
    while 1:
        if len(a) == n:
            return a
        if automorfico(i):
            a += [i]
        i += 1

print N_automorficos(10)

Sim, eu sei que tem ali um while
Acho que este codigo não deve gerar nenhumas duvidas

Depois só tens de definir a função automorfico

Código: Seleccionar Todos

def automorfico(n):
    if (n**2)%(10**numDigitos(n)) == n:
        return 1
    else:
        return 0

Tem () a mais mas ajuda a ler

finalmente, a numDigitos(n):

Código: Seleccionar Todos

def numDigitos(n):
    if(n<10):
        return 1
    else:
        return 1+numDigitos(n/10)

[RicardoCampos]

Acho que este codigo não deve gerar nenhumas duvidas

Não gera dúvidas, mas gera os números automórficos

[jap]

Desculpem não ter respondido logo, mas acabei por ficar sem qualquer acesso à net nos últimos dois dias...

Ora aqui vai a minha resolução (pitónica) para o problema:

Código: Seleccionar Todos

#!/usr/bin/env python
"""
Automorphic numbers
"""

if __name__ == "__main__":

    nmax = 10
    auto_numbers = []
    n,nauto = 1,0
   
    while nauto < nmax:
        if str(n*n).endswith(`n`):
            auto_numbers.append(n)
            nauto += 1
        n += 1
   
    print auto_numbers


OK, o que é uma resolução pitónica?

É um jargão muito usado pelos utilizadores de Python: código pitónico é aquele que utiliza ao máximo a expressividade e as potencialidades do Python, e também algumas das suas idiossincrasias...

Um código não pitónico é aquele em que se vislumbra que o programador pensou no algoritmo em C, Java ou outra linguagem e simplesmente o transcreveu para Python...

Uma das características mais fantásticas do Python é conhecida por "batteries included", o que significa que estão à disposição do utilizador um grande número de ferramentas de alto nível para lidar com inúmeros problemas comuns (por exemplo estruturas de dados como listas e dicionários, ferramentas para tratamento de strings, expressões regulares, acesso à net, etc). Assim fica muito mais fácil resolver problemas como este!

Gostaram de

Código: Seleccionar Todos

str(n*n).endswith(`n`)

?

[jap]

Vou então dar algumas dicas de Python, usando o meu programazito como exemplo.

As primeiras linhas de código

Código: Seleccionar Todos

#!/usr/bin/env python
"""
Automorphic numbers
"""

if __name__ == "__main__":

podem, na realidade ser omitidas!

Passo a explicar.

A primeira linha

Código: Seleccionar Todos

#!/usr/bin/env python

é um comentário. Tudo o que se segue numa linha ao sinal # é ignorado pelo interpretador de Python, e portanto podem usar este sinal para introduzir comentários no vosso código.
O comentário que eu escrevi é um comentário algo especial. Nada diz ao Python, que o ignora, mas é útil para quem correr este programa num sistema UNIX (ou derivado, como o Linux). É completamente inútil no Windows, mas também não faz mal estar lá. O que é que significa para um sistema UNIX? Bem, neste sistema operativo quando executam este ficheiro como uma "shell script" o sistema lê a primeira linha de texto e fica a saber que tem de procurar o programa python para interpretar o ficheiro. Mas, como disse, isto é uma característica do UNIX e nada tem a ver com o Python, que simplesmente ignora esta linha porque começa com um #.

As 3 linhas seguintes,

"""
Automorphic numbers
"""

são o que em Python se designa por uma "doc string". É de bom tom pitónico iniciar sempre um programa com uma doc string, que explique a quem lê o programa o que ele faz. É uma espécie de documentação do programa. Uma doc string pode ter quantas linhas quiserem, desde que esteja entre duas linhas com """. Exemplo de uma doc string mais completa:

Código: Seleccionar Todos

"""
Automorphic numbers
jap@ 1/12/2008
version 1.0.0.0
Use at your own risk!

This is a copyleft program to be shared by quarkonia.
"""

Notem que um comentário não é uma doc string e uma doc string não é um comentário. Um comentário é ignorado pelo programa (embora como está no código, possa ser usado para documentá-lo). Uma doc string faz parte do vosso programa, fica guardada na RAM do computador quando o programa corre, e podem aceder a ela (doc string) de dentro do programa! A sério! Veremos mais tarde como isto pode ser útil - trata-se de uma ferramenta de metaprogramação.

Por último (por hoje!) a linha

Código: Seleccionar Todos

if __name__ == "__main__":

também pode ser omitida, se preferirem. O que é que ela significa?

É para ser interpretada à letra: se quando o Python interpretar este ficheiro o programa que estiver a correr for o programa principal (que tem internamente o nome de __main__), então (e só então) executa o código que se segue a esta instrução. (A propósito os dois "underscores" que antecedem e precedem __name__ e __main__ têm um significado especial, mas não me vou alargar agora sobre isso - até porque esta linha pode ser omitida, certo? )

Como vocês verão em breve, os ficheiros de Python podem correr na forma de programa principal ou serem importados por outros programas (neste caso não são, obviamente, o programa principal). Se se habituarem a incluir esta linha "bizarra" poderão mais tarde utilizar estes ficheiros como módulos para serem importados de outros programas, o que, verão, é imensamente útil.

E chega por hoje de dicas pitónicas. Espero que tenha sido útil. Amanhã darei mais algumas, explicando o resto deste pequeno programa.

[Bruno Oliveira]

Óptima explicação prof.

Fico ansiosamente á espera da parte II, ah e já agora, fiquei surpreendido com

Gostaram de

Código: Seleccionar Todos

str(n*n).endswith(`n`)

?

Incrível, mas muito bom!

[RicardoCampos]

O que eu não entendo é o porquê de serem números automorficos.

Um automorfismo é um isomorfismo de um grupo para ele próprio...

[jap]

Aqui o adjectivo automórfico é para ser interpretado simplesmente na acepção de "com forma semelhante a ele próprio", não no sentido mais preciso e estrito que é usado em teoria de grupos..., I guess

[jap]

Ora vamos então à explicação do "core" do programa...

Código: Seleccionar Todos

    nmax = 10
    auto_numbers = []
    n,nauto = 1,0
   
    while nauto < nmax:
        if str(n*n).endswith(`n`):
            auto_numbers.append(n)
            nauto += 1
        n += 1
   
    print auto_numbers

Primeira observação: este bloco de código está identado 4 espaços para a direita; isto é necessário porque se trata de um bloco "if":

Código: Seleccionar Todos

if __name__ == "__main__":
    nmax = 10
    auto_numbers = []
    n,nauto = 1,0
   
    while nauto < nmax:
        if str(n*n).endswith(`n`):
            auto_numbers.append(n)
            nauto += 1
        n += 1
   
    print auto_numbers


A identação é muito importante (obrigatória em Python!). Podem usar 4 espaços, um "tab", ou um número diferente de espaços, mas é preciso identar o código!

Ora a primeira instrução do bloco que se segue ao if é um exemplo da instrução mais básica do python:

Código: Seleccionar Todos

nmax = 10

O que é que esta instrução faz? Esta instrução (simbolizada pelo sinal = que nada tem a ver com igualdade matemática) significa atribuir um nome a um objecto. O nome é o que está à esquerda do sinal e o objecto é o que está à direita. O que é um objecto? É um conjunto de dados que reside algures na memória do computador. Imaginem uma caixa com "coisas" lá dentro e uma grande etiqueta na caixa com o nome do conjunto dessas coisas. É que um objecto pode ser uma grande colecção de coisas muito díspares que residem na memória do computador mas que de alguma forma estão "agrupadas" numa caixa. Neste caso o que está dentro da caixa é o número 10, mas podia haver lá muito mais coisas. Bem, para dizer a verdade, o python quando cria a caixa para colocar lá dentro o número "10" coloca também lá dentro mais coisas, que não são visíveis na instrução acima, como por exemplo uma espécie de manual de instruções sobre como usar o que está dentro da caixa. Por exemplo no caso acima, no manual de instruções figuram o tipo do objecto (um número inteiro), e uma lista das operações que ele suporta.

Em python todos os objectos (números e outras "coisas") são colocados dentro de caixas, caixas essas que têm etiquetas com um "nome". Se, por alguma razão, a etiqueta for arrancada (isto pode acontecer!!! ) e a caixa ficar sem etiqueta, a caixa vai ser destruída (com o objecto lá dentro!) pelo "gestor do armazém de caixas de objectos" do python - esse gestor de armazém passa tipicamente a pente fino a memória do vosso computador (reservada ao python) à procura de caixas sem etiqueta, e destrói-as de imediato, libertando o espaço de memória. Chama-se a este gestor de armazém zeloso o "colector de lixo". É mesmo muito zeloso: entre cada passagem para limpeza de caixas sem nome decorrem apenas alguns milisegundos!



Em resumo:

a) Em python os dados e outras "coisas", que chamamos genericamente de objectos, são guardados dentro de "caixas"; é preciso dar um nome à caixa o que se faz com a instrução de atribuição (de nome) que tem a forma

Código: Seleccionar Todos

nome = objecto

b) Um objecto sem nome irá ser destruido implacavelmente pelo colector de lixo dentro dos próximos milisegundos!

c) Uma curiosidade: é possível dar dois ou mais nomes a um mesmo objecto, se acharem que isso pode ser útil.

Por exemplo a instrução

Código: Seleccionar Todos

jose = ze = "o meu colega de turma"

faz um duplo batismo do objecto que é a cadeia de caracteres "o meu colega de turma". Esta cadeia de caracteres pode ser referenciada, daqui para a frente, com um dos dois nomes, jose, ou ze.

Agora que já sabemos o que faz a primeira instrução que se segue ao if (cria um objecto com o nome nmax que referencia o número 10, que é o número máximo de números automórficos que pretendemos gerar), vejamos a segunda instrução:

Código: Seleccionar Todos

auto_numbers = []

Esta instrução cria um novo tipo de objecto, uma lista (vazia) que vai servir para guardar os números automórficos. Esta lista vai também ser guardada dentro de uma caixa com o nome auto_numbers.

E deixo o resto para amanhã, que o post já vai longo!

[Bruno Oliveira]

A partir desta altura vai começar a parte do código em que tenho algumas dúvidas, vamos a ver se as minhas conjecturas estarão certas!

[jap]

Vamos então ao núcleo do código...

Código: Seleccionar Todos

    while nauto < nmax:
        if str(n*n).endswith(`n`):
            auto_numbers.append(n)
            nauto += 1
        n += 1

Este núcleo consiste de um ciclo while que tem embutido lá dentro um bloco if.

Acho que o código é bastante auto-explicativo!

O valor de nauto, que é o nome do objecto que guarda o número de números automórficos que já se encontraram num dado instante da execução do programa, é inicialmente 0. Sempre que é encontrado um número automórfico, o valor de nauto é incrementado de 1. É o que faz a instrução

Código: Seleccionar Todos

nauto += 1

Na realidade se o objecto de nome xxx for um número inteiro a instrução

xxx += 1

faz com que o nome xxx passe a designar o número inteiro original incrementado de uma unidade.

No ciclo while o número n, que inicialmente é 1, é incrementado em cada iteração do ciclo de uma unidade ( n+=1 ), percorrendo todos os números, um a um, até que se encontre o número desejado de números automórficos.

Como é que se testa se o número n é automórfico? Esta é a parte gira.
O teste de automorfismo é

Código: Seleccionar Todos

str(n*n).endswith(`n`)

ou seja, multiplicamos n por n e convertemos esse número numa string. Todas as strings têm um conjunto de funções próprias que lhes podem ser aplicadas, os chamados métodos de string. Esssas funções são invocadas pela sintaxe "string.f", onde f é o método desejado. Felizmente as strings em Python têm o método ".endswith(substring)"! E qual é a terminação da string que buscamos? Procuramos que a string termine nos dígitos do próprio número n, não é? Então podemos resolver o problema de duas formas:

Código: Seleccionar Todos

str(n*n).endswith(str(n))

ou ainda

Código: Seleccionar Todos

str(n*n).endswith(`n`)

porque em python

Código: Seleccionar Todos

`objecto`

é o mesmo que

Código: Seleccionar Todos

str(objecto)

ou seja, converte o objecto numa string, se tal for possível.

Claro que podíamos ainda escrever

Código: Seleccionar Todos

`n*n`.endswith(`n`)

mas a versão que eu apresentei é a mais pitónica - mais tarde explicarei porquê!

Está tudo claro ou há dúvidas?

[Bruno Oliveira]

Está muito bom! Eu só tinha tido dúvidas na parte inicial, esta aqui tinha percebido .

A parte do

Código: Seleccionar Todos

  auto_numbers.append(n)

, é apenas para escrever os números automórficos que foram encontrados, na lista certo?

[jap]

Está muito bom! Eu só tinha tido dúvidas na parte inicial, esta aqui tinha percebido .

A parte do

Código: Seleccionar Todos

  auto_numbers.append(n)

, é apenas para escrever os números automórficos que foram encontrados, na lista certo?

Sim, se L for o nome de uma lista, a instrução

L.append(x)

acrescenta o objecto de nome x à lista L.

Claro que para que esta instrução funcione há que criar a lista L primeiro! Isto pode ser feito criando uma lista vazia e atribuindo-lhe o nome L. Uma lista vazia em Python é o objecto []. Então para criar, por exemplo uma lista de nomes podemos fazer,

Código: Seleccionar Todos

L = []
girlfrend='Maria'
buddy = 'Ze'
L.append(girlfriend)
L.append(buddy)

Claro que podes ainda fazer, neste exemplo específico

Código: Seleccionar Todos

L = []
L.append('Maria')
L.append('Ze')

ou, mais directamente, criar logo a lista dos amigos com a instrução

Código: Seleccionar Todos

L = ['Maria','Ze']

[Bruno Oliveira]

Então era como eu pensava .

Obrigado pela paciência que dispendeu com as excelentes explicações do código pitónico, prof