Publicité
+ Répondre à la discussion Actualité déjà publiée
Page 2 sur 2 PremièrePremière 12
Affichage des résultats 21 à 22 sur 22
  1. #21
    Expert Confirmé
    Homme Profil pro
    Inscrit en
    septembre 2006
    Messages
    2 389
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : septembre 2006
    Messages : 2 389
    Points : 2 806
    Points
    2 806

    Par défaut

    premier essai :

    Code :
    1
    2
    3
    4
    5
    6
    time palindrome.rb < /usr/share/dict/words  > /dev/null
    
    real	0m23.213s
    user	0m23.189s
    sys	0m0.022s
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    #!/usr/bin/env ruby
    
    while s = gets
    	r=s.reverse
    	l=s.length
    
    	palindromes=Array.new
    
    	i=0
    	while i<l-1 && palindromes.empty?
    		j = 0
    		while j<=i
    			s1=s[j,l-i]
    			r1=r[i-j,l-i]
    			if s1 == r1
    				palindromes << s1
    			end
    			j += 1
    		end
    		i += 1
    	end
    	if !palindromes.empty?
    		puts "Largest palindromes in #{s}"
    		palindromes.each do |p|
    			puts "\t#{p}"
    		end
    		puts "------------"
    	end
    end
    exemple de sortie :

    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    Largest palindromes found in aa
            aa
    ------------
    Largest palindromes found in aal
            aa
    ------------
    Largest palindromes found in aalii
            aa
            ii
    ------------
    Largest palindromes found in aam
            aa
    ------------
    Largest palindromes found in aardvark
            aa
    ------------
    Largest palindromes found in aardwolf
            aa
    ------------
    Largest palindromes found in Aaronitic
            iti
    ------------
    Largest palindromes found in aba
            aba
    ------------
    Largest palindromes found in Ababdeh
            bab
    ------------
    Largest palindromes found in Ababua
            bab
    ------------
    Largest palindromes found in abac
            aba
    ------------
    Largest palindromes found in abaca
            aba
            aca
    ------------
    Largest palindromes found in abacate
            aba
            aca
    ------------
    Largest palindromes found in abacay
            aba
            aca
    ------------
    Largest palindromes found in abacinate
            aba
    ------------
    Largest palindromes found in abacination
            aba
    ------------
    Largest palindromes found in abaciscus
            aba
    ------------
    …
    Largest palindromes found in computation
    	tat
    ------------
    Largest palindromes found in computational
    	tat
    ------------
    Largest palindromes found in computative
    	tat
    ------------
    Largest palindromes found in computativeness
    	tat
    	ene
    ------------
    Largest palindromes found in computus
    	utu
    ------------
    Largest palindromes found in Comsomol
    	omo
    ------------
    Largest palindromes found in comurmurer
    	rer
    ------------
    …
    Largest palindromes found in forrue
    	rr
    ------------
    Largest palindromes found in forsakenness
    	enne
    ------------
    Largest palindromes found in forsooth
    	oo
    ------------
    …
    Largest palindromes found in navarchy
    	ava
    ------------
    Largest palindromes found in Navarrese
    	ava
    	ese
    ------------
    Largest palindromes found in Navarrian
    	ava
    ------------
    Largest palindromes found in naveled
    	ele
    ------------
    …
    Largest palindromes found in premillenarianism
    	ll
    ------------
    Largest palindromes found in premillennial
    	ll
    	nn
    ------------
    Largest palindromes found in premillennialism
    	ll
    	nn
    ------------
    Largest palindromes found in premillennialist
    	ll
    	nn
    …
    Largest palindromes found in zymome
    	mom
    ------------
    Largest palindromes found in zymometer
    	mom
    	ete
    ------------
    Largest palindromes found in zymomin
    	mom
    ------------
    Largest palindromes found in zymosimeter
    	ete
    ------------
    Largest palindromes found in zymosis
    	sis
    ------------
    Largest palindromes found in zymotically
    	ll
    ------------
    Largest palindromes found in zymotoxic
    	oto
    ------------
    Largest palindromes found in Zyryan
    	yry
    ------------
    Largest palindromes found in Zyzzogeton
    	zz
    ------------
    le même palindrome apparaissant à différents endroits sera sorti plusieurs fois…
    si l'on veut une seule sortie : remplacer l'Array "palindromes" par un Hash…

    pour info, la même version compilée en C :
    Code :
    1
    2
    3
    4
    5
    6
    time ./palindrome < /usr/share/dict/words > /dev/null
    
    real	0m0.605s
    user	0m0.596s
    sys	0m0.006s
    si l'on veut les palindromes >= à une taille minimum c'est le "l-1" du "while i<l-1 && palindromes.empty?" qu'il faut paramétrer en "l - (longueur minimale désirée - 1)"

    si on ne stocke pas les résultats, mais qu'on les sort directement (tjs la version en C)
    Code :
    1
    2
    3
    4
    5
    6
    time ./palindrome < /usr/share/dict/words > /dev/null
    
    real	0m0.378s
    user	0m0.268s
    sys	0m0.014s

  2. #22
    Invité
    Invité(e)

    Par défaut

    Une expression J qui donne la liste des plus longs palindromes

    Code :
    1
    2
    3
    4
    ((#~((=>./)@:(#@>)))@:(#~((-:|.)@>))@:~.@:,@:({\~(1+i.@:#)))
    
    (#~((=>./)@:(#@>)))(#~((-:|.)@>))~.,({\~(1+i.@:#)) 'esope reste ici et se repose'
    'te ici et'
    Petite explication:
    si y est la chaine qu'on étudie

    1+i.#y
    est la suite 1 2 3 ... #y (#y : longueur de la chaine)
    n {/ y
    génère toutes les sous chaines de longueur n de y
    1+i.#y {/ y
    génère un tableau de toutes les sous chaines de y

    ({\~(1+i.@: #)) est l'expression fermée correspondante

    , met ce tableau "en ligne", et ~. en élimine les doublons
    ~.,({\~(1+i.@: #))
    est la liste de toutes les sous chaines uniques

    (-: |.) renvoie 1 si la chaine est un palindrome, 0 sinon
    (#~((-: |.)@ >))
    sélectionne les palindromes de la liste précédente

    (#@>) compte les lettres de chaque palindrome
    >./ donne le maximum d'une suite
    (=>./)@: (#@>) renvoie 1 si la longueur est égale à la longueur maximale rencontrée dans la suite

    (#~((=>./)@: (#@>))) sélectionne les palindromes maximaux

    Francois

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •