17. In Python implementiertes Referenzproblem für das Offline-Schreiben in Echtzeit

Klicken Sie hier, um Details zum Problem anzuzeigen. http://nabetani.sakura.ne.jp/hena/ord17scheherazade/ http://qiita.com/Nabetani/items/dabe8ec57e0313229552

#!/usr/bin/env python
# -*- coding:utf8 -*-

def is_palindrome(data, base):
    digits = []
    while data > 0:
        digits.append(data % base)
        data /= base
    return digits == digits[::-1]

def solve(data):
    bases = [base for base in xrange(2, data) if is_palindrome(data, base)]
    return ','.join(map(str, bases)) if bases else '-'

def test(data, correct):
    answer = solve(int(data))
    print 'xo'[answer == correct], data, correct, answer

0, test( "17301", "5,38,100,218,236,5766,17300" );
1, test( "2", "-" );
2, test( "1", "-" );
3, test( "3", "2" );
4, test( "4", "3" );
5, test( "5", "2,4" );
6, test( "6", "5" );
7, test( "10", "3,4,9" );
8, test( "101", "10,100" );
9, test( "1001", "10,25,76,90,142,1000" );
10, test( "10001", "10,24,30,42,80,100,136,10000" );
11, test( "1212", "22,100,201,302,403,605,1211" );
12, test( "123412", "62,100,205,215,30852,61705,123411" );
13, test( "5179", "5178" );
14, test( "4919", "4918" );
15, test( "5791", "5790" );
16, test( "5498", "2748,5497" );
17, test( "453", "150,452" );
18, test( "134", "66,133" );
19, test( "8489", "27,652,8488" );
20, test( "1234", "22,616,1233" );
21, test( "5497", "41,238,5496" );
22, test( "4763", "19,35,432,4762" );
23, test( "3974", "17,27,1986,3973" );
24, test( "3521", "44,55,502,3520" );
25, test( "5513", "20,38,53,148,5512" );
26, test( "8042", "23,29,60,4020,8041" );
27, test( "7442", "37,60,121,3720,7441" );
28, test( "4857", "25,1618,4856" );
29, test( "22843", "49,69,91,141,430,22842" );
30, test( "194823", "84,121,21646,64940,194822" );
31, test( "435697", "160,169,235,626,1822,435696" );
32, test( "142", "3,7,70,141" );
33, test( "886", "5,14,442,885" );
34, test( "3102", "7,65,93,140,281,516,1033,1550,3101" );
35, test( "17326", "11,28,99,105,8662,17325" );
36, test( "32982", "13,72,238,477,716,1433,5496,10993,16490,32981" );
37, test( "36", "5,8,11,17,35" );
38, test( "37", "6,36" );
39, test( "251", "8,250" );
40, test( "252", "5,10,17,20,27,35,41,62,83,125,251" );
41, test( "253", "12,14,22,252" );
42, test( "6643", "2,3,9,81,90,510,948,6642" );
43, test( "5040", "71,79,83,89,104,111,119,125,139,143,167,179,209,239,251,279,314,335,359,419,503,559,629,719,839,1007,1259,1679,2519,5039" );

Ich habe irgendwie eine Regel aus dem Ausgabeergebnis gefunden und versucht, die Verarbeitung zu beschleunigen.

def reverse(number, base):
    r = 0
    while number > 0:
        r = r * base + (number % base)
        number /= base
    return r

def solve(number):
    if number < 3: return '-'
    bases = []
    prev = 0
    for div in xrange(1, number):
        base = (number - 1) / div
        if base == 1 or base == prev: break
        if number == reverse(number, base): bases.append(base)
        prev = base
    for base in xrange(base - 1, 1, -1):
        if number == reverse(number, base): bases.append(base)
    return ','.join(map(str, bases[::-1]))
Ausführungszeit
Vor dem Beschleunigen 2.122s
Nach dem Beschleunigen 0.255s

Dank Cielavenir wurde festgestellt, dass die Grenze √ (Nummer -1) ist, also habe ich versucht, den Beschleunigungsprozess zu organisieren. http://qiita.com/cielavenir/items/3d2bea62d301a2309884

def palindrome(number, base):
    forward, reverse = number, 0
    while number > 0:
        reverse = (reverse * base) + (number % base)
        number /= base
    return forward == reverse

def solve(number):
    if number < 3: return '-'
    pre = number - 1
    root = int(pre ** 0.5)
    bases = [base for base in xrange(2, pre / root) if palindrome(number, base)]
    bases += [pre / div for div in xrange(root, 0, -1) if palindrome(number, pre / div)]
    return ','.join(map(str, bases))

Recommended Posts

17. In Python implementiertes Referenzproblem für das Offline-Schreiben in Echtzeit
Das 15. Offline-Echtzeit-Schreiben eines Referenzproblems in Python
Das 14. Referenzproblem beim Schreiben in Echtzeit in Python
Das 18. Offline-Echtzeit-Schreiben eines Referenzproblems in Python
Das 16. Offline-Echtzeit-Schreiben eines Referenzproblems zur Lösung mit Python
Das 19. Offline-Echtzeit-Schreiben eines Referenzproblems zur Lösung mit Python
20. Offline-Echtzeit So schreiben Sie Probleme in Python
Das 16. Offline-Echtzeit-Schreibproblem wurde mit Python gelöst
Das 15. Offline-Problem beim Schreiben in Echtzeit wurde mit Python gelöst
Das 18. Offline-Echtzeit-Schreibproblem in Python
Das 19. Offline-Echtzeit-Schreibproblem in Python
17. Offline-Echtzeit So lösen Sie Schreibprobleme mit Python
Beim 15. Offline-Echtzeitversuch habe ich versucht, das Problem des Schreibens mit Python zu lösen
Das 14. Referenzproblem beim Offline-Schreiben in Echtzeit mit Python
Teil 1 Ich habe die Antwort auf das Referenzproblem geschrieben, wie man in Python in Echtzeit offline schreibt
13. Offline-Echtzeit So lösen Sie Schreibprobleme mit Python
Das 10. Referenzproblem beim Schreiben in Echtzeit. Implementierungsbeispiel von Python.
Offline-Echtzeit zum Schreiben eines Python-Implementierungsbeispiels für das E15-Problem
Das 11. Referenzproblem beim Schreiben in Echtzeit. Implementierungsbeispiel von Python.
Antwort auf "Offline in Echtzeit, wie man ein F02-Problem schreibt"
Teil 1 Ich habe ein Beispiel für die Antwort auf das Referenzproblem geschrieben, wie man in Python in Echtzeit offline schreibt
Antwort auf "Offline-Echtzeit, wie man ein F01-Problem schreibt"
Antwort auf "Offline-Echtzeit, wie man ein E13-Problem schreibt"
Offline-Echtzeit zum Schreiben eines E14 Python-Implementierungsbeispiels
So schreiben Sie offline in Echtzeit Lösen von E05-Problemen mit Python
Das zwölfte Offline-Echtzeit-Schreibreferenzproblem. Implementiert von Python
Wie schreibe ich Ruby to_s in Python
Offline in Echtzeit, wie man ein Implementierungsbeispiel für E11 Ruby und Python schreibt
So schreiben Sie offline in Echtzeit Lösen von E04-Problemen mit Python
Ich habe versucht, das Problem von F02 zu lösen, wie man mit Python offline in Echtzeit schreibt
Verwendung der C-Bibliothek in Python
So schreiben Sie den richtigen Shebang in Perl-, Python- und Ruby-Skripten
Tipps zum Schreiben werden in Python kurz abgeflacht
So erhalten Sie die Dateien im Ordner [Python]
So rufen Sie den n-ten größten Wert in Python ab
So erhalten Sie den Variablennamen selbst in Python
Grundlegende Informationen Schreiben Sie das Problem mit dem Herbst 2018-Algorithmus in Python
So ermitteln Sie die Anzahl der Stellen in Python
So schreiben Sie in Python die Verkettung von Zeichenfolgen in mehrere Zeilen
Wie Sie das aktuelle Verzeichnis in Python in Blender kennen
Ich möchte in Python schreiben! (3) Verwenden Sie Mock
Verwendung des in Lobe in Python erlernten Modells
[Python] So geben Sie Listenwerte der Reihe nach aus
Wie man in Python entwickelt
So schreiben Sie eine benutzerdefinierte Validierung in Django REST Framework
[Python] So überprüfen Sie, ob der Schlüssel im Wörterbuch vorhanden ist
So debuggen Sie eine Standard-Python-Bibliothek in Visual Studio
Verwendung der Methode __call__ in der Python-Klasse
[Python] Wie schreibe ich eine if-Anweisung in einen Satz?
So erhalten Sie den letzten (letzten) Wert in einer Liste in Python
[Python] Wie man PCA mit Python macht
Wie man nüchtern mit Pandas schreibt
So sammeln Sie Bilder in Python
Verwendung von SQLite in Python
Im Python-Befehl zeigt Python auf Python3.8
So erhalten Sie die Python-Version
Wie man MySQL mit Python benutzt
So verpacken Sie C in Python