0

何らかの理由で、以下の出力は 0 になります。非常に大きな文字列 (100,000 文字) を使用しており、500,000,000,000 など、1000 億単位の大きな整数を探しています。私がしなければならない特別なことはありますか？目標は、pi の最初の 100,000 桁で 1,2,3 のサブシーケンスの数を見つけることです。私は以下がアルゴリズム的に正しいことを知っています。「コードが正しい」だけではありません。

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)
4

3 に答える 3

4

最も簡単で最速の方法は、おそらく次のとおりです。

subSeqTotal = pi100k.count("123")
于 2011-06-01T02:02:32.493 に答える
3 
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')

于 2011-06-01T01:40:41.747 に答える
0

これらの解決策はどれも正しくないようです。サブシーケンスを正しく検索しているとは思いません。

このアルゴリズムを使用して、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 で試してみましたが、うまくいかないようでした。

于 2011-12-28T03:06:57.380 に答える