Переполнение строки Python? - PullRequest
Новая
       22

Переполнение строки Python?

0 голосов
/ 01 июня 2011

По какой-то причине, приведенное ниже приводит к выводу 0. Я использую очень большую строку (100 000 символов) и ищу большое целое число из сотен миллиардов, например, 500 000 000 000. Есть ли что-то особенное, что мне нужно сделать? Цель состоит в том, чтобы найти число подпоследовательностей 1,2,3 в первых 100 000 цифр числа пи. Я знаю, что приведенное ниже является алгоритмически правильным. Это просто не «код-правильно». 

pi100k = "3.14159[100,000 digits of pi]"
subSeqInit = 0
subSeqPair = 0
subSeqTotal = 0

for c in pi100k:
    if c == 1:
        subSeqInit = subSeqInit + 1
    elif c == 2 and subSeqInit > 0:
        subSeqPair = subSeqPair + 1
    elif c == 3 and subSeqTotal > 0:
        subSeqTotal = subSeqTotal + 1

print(subSeqTotal)

Ответы [ 3 ]

4 голосов
/ 01 июня 2011

Самый простой и быстрый способ, вероятно, таков: 

subSeqTotal = pi100k.count("123")
3 голосов
/ 01 июня 2011 
pi100k = "3.14159[100,000 digits of pi]"
subSeqInit = 0
subSeqTotal = 0

for c in pi100k:
    if c == '1':
        subSeqInit = 1
    elif c == '2' and subSeqInit == 1:
        subSeqInit = 2
    elif c == '3' and subSeqTotal == 2:
        subSeqTotal = subSeqTotal + 1
        subSeqInit = 0

print(subSeqTotal)

Python неявно преобразует строковые символы в целые числа.Кроме того, ваш алгоритм неверен, то, что я описал выше, будет работать лучше.

РЕДАКТИРОВАТЬ:

Вы можете сделать это намного короче, используя модуль регулярных выражений 

import re
subSeqTotal = len(re.findall('123',pi100k))\

РЕДАКТИРОВАТЬ 2: Как отметил MRAB, лучше всего использовать pi100k.count('123')

0 голосов
/ 28 декабря 2011

Кажется, ни одно из этих решений не является правильным. Я не думаю, что они ищут подпоследовательность правильно.

Я решил это рекурсивно в C, с этим алгоритмом: 

/* global cstring for our pi data */
const char *g_numbers = 3.14........[100,000 digits];

/* global to hold our large total : some compilers don't support uint64_t */
uint64_t  g_total = 0;


/* recursively compute the subsequnces of 1-2-3 */
void count_sequences(const char c, unsigned int index)
{
    while (index < 100000){
        switch (g_numbers[index]){
            case '1': if (c == '1') count_sequences('2', index+1); break;
            case '2': if (c == '2') count_sequences('3', index+1); break;
            case '3': 
                      if (c == '3'){
                        g_total++;
                        count_sequences('3', index+1);
                        return;
                      }
            default: break;
        }
        index++;
    }
}

Извините, я не могу раздать решение Python - но я надеюсь, что это поможет. Это не должно быть слишком сложно для переделки. Я попробовал данные ответы на Python, и они, похоже, не сработали.

...