0votos

Palíndromo de mayor tamaño preferible Javascript pyton o sage en Haskell

por josejuan hace 3 años

No conozco ninguna solución más que la búsqueda exhaustiva. Mi solución (que ya publiqué en http://www.glc.us.es/~jalonso/exercitium/mayor-capicua-producto-de-dos-numeros-de-n-cifras ) intenta descomponer directamente los palíndromos desde el mayor al menor hasta encontrar. Encuentra para factores menores de 10^7 (palíndomo menor que 10^14) en unos 9 segundos.

Hallar el mayor número palíndromo múltiplo de 2 números menores o iguales que 10^7

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
{- 
 
    Decrementando 
  
        999..997 
        999..996 
        999..995 
        ... 
  
    obtenemos capicuas `C` de mayor a menor. 
  
    `factores` busca dos factores de `C` de `N` dígitos 
    (puede mejorarse usando las potencias repetidas). 
 
PS C:\MTO\tmp> .\maxpal2.exe 7 
(99956644665999,(9998017,9997647)) 
 
PS C:\MTO\tmp> Measure-Command { .\maxpal2.exe 7 } 
 
 
Days              : 0 
Hours             : 0 
Minutes           : 0 
Seconds           : 8 
Milliseconds      : 945 
Ticks             : 89451442 
TotalDays         : 0,000103531761574074 
TotalHours        : 0,00248476227777778 
TotalMinutes      : 0,149085736666667 
TotalSeconds      : 8,9451442 
TotalMilliseconds : 8945,1442 
 
-} 
import System.Environment 
import Data.Numbers.Primes (primeFactors) 
import Control.Applicative ((<|>)) 
 
mayorCapicuaP :: Integer -> (Integer, (Integer, Integer)) 
mayorCapicuaP n = 
    let p = 10^n - 1 
        q = 10^(n - 1) 
        factores c = 
            let rs = reverse $ primeFactors c 
                s _ _ [] = Nothing 
                s u w rs | u > p     = Nothing 
                         | q <= u && 
                           q <= v && 
                           v <= p    = Just (u, v) 
                         | otherwise = s (u * head rs) w (tail rs) <|> 
                                       s u (w * head rs) (tail rs) 
                         where v = w * product rs 
            in  if head rs > p then Nothing else s 1 1 rs 
        e (h:hs) = case factores c of 
                     Just  r -> (c, r) 
                     Nothing -> e hs 
                   where s = show h 
                         c = read (s ++ reverse s) 
    in  e [p - 2, p - 3..] 
 
main = getArgs >>= print . mayorCapicuaP . head . map read 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.