0

私は Koeing アクセラレーテッド C++ を練習しており、自分の答えを検証したいと考えています。net には解決策がないため、ここに投稿して、私の解決策について専門家の意見を聞くことにしました。人々が私がここに投稿することを好むかどうかはわかりません. そうでない場合は、お知らせください。今後は行いません。また、これは宿題ではなく、私の C++ スキルを次のレベルに引き上げたいという純粋な願望です。

問題:辞書にあるすべての回文を見つけるプログラムを作成してください。次に、最長の回文を見つけます。

これまでに行ったこと-> 回文をテストする関数を定義し、すべての単語をリストに保存しました。以下にコードを掲載しました。

私が立ち往生している場所: ベクトルよりもリストデータ構造を使用するという私の選択が良いかどうかに関係なく、アドバイスが必要ですか? 第二に、最も長い単語を表示する方法に行き詰まっています。最長の長さは表示できますが、最長の単語は表示できません。

以下の私の試み

    bool palindromeTest( const std::string& input )
{
   typedef std::string::size_type strSize;
    strSize i = 0;
    strSize j = input.size() - 1  ;
    while( i < input.size() )
    {
        if ( input[i] != input[j])
        {
            return false;
        }
        i++;
        j--;
    }

    return true;
}



int main()
{

    // stores all words in a list or vector
    std::list< string> listDict;
    std::string readWord;
    std::ifstream readFile( "/Users/apple/palidndrome-ch5-10/dict.txt" );
    if( ! readFile )
    {
        std::cout <<" failed to open file" << std::endl;
        return 0;
    }
    while( readFile >> readWord )
    {
        listDict.push_back( readWord );
    }

     std::string::size_type maxLen = 0 ;
     std::string longestWord = " "; // to store longest palindrome


     // print all the palindrome words and also which is longest palindrome.

    for( std::list<std::string>::const_iterator it = listDict.begin(); it != listDict.end(); ++it )
    {

        if( palindromeTest( *it )  )
        {
            std::cout <<" the word -> " << *it << " is palindrome" << std::endl;
            // find max len of palindrome;
            maxLen = max( maxLen, it->size() );
            longestWord = *it ;// need to change code here ?? no idea how

        }

    }

    std::cout <<" the maximum len is = " << maxLen << std::endl;
    std::cout << " the word with maximum length is  " << longestWord ; // something is wrong here


    return 0;
}
4

2 に答える 2

1

まずはパリンドロームテスト。文字列内のすべての文字を 2 回チェックしていますが、これは不要です。この特定のケースでは、その特定の操作の時間が 2 倍になるだけなので問題にはなりませんが、いくつかの同様の操作ではセマンティクスが変更されます (reverse概念的に回文のテストに非常に似ていると考えてください)。0チェックを改善するには、 toからループ カウンターを使用するか、input.size()/22 つのポインター/イテレーターを使用して、それらが途中で一致するまで実行します。input.size()/2また、最大まで反復すると、奇数サイズの文字列についてテストされていない文字が残ることに注意してください。しかし、それは問題ありません。

シーケンシャル コンテナが必要な場合はstd::vector<>、 ではなく ,を常にデフォルトにする必要がありますstd::list<>。最大値を手動で見つけるには、maxこの要素が以前の最大値よりも大きいかどうかを確認し、最大値と文字列 (または文字列自体) の位置の両方を更新するテストの呼び出しを変更する必要があります。std::set<std::string>この特定のケースで、繰り返し回数が多い場合は、繰り返しを避けるために、順次コンテナーではなく、連想コンテナー ( ) を使用することも検討できます。ただし、単語を完全にメモリに保存しない方がよいでしょう。

イテレータと、標準ライブラリのイテレータのヘッダーの使い方を学ぶ必要があります。たとえば、読み取りループは次のように変換できます。

std::vector<std::string> words;
std::copy( std::istream_iterator<std::string>( readFile ),
           std::istream_iterator<std::string>(),
           std::back_inserter( words );

回文のチェックは、std::equalアルゴリズムの呼び出しにすることができます。

bool isPalindrome( std::string const & str ) {
   return std::equal( str.begin(), str.begin()+str.size()/2,
                      str.rbegin() );
}

適切なファンクターを提供することにより、アルゴリズムを使用して最長の回文を見つけることもできます。

std::vector::const_iterator max = std::max_element( words.begin(), words.end(), []( std::string const & lhs, std::string const & rhs ) { return lhs.size () < rhs.size(); });

(C++11 のラムダを使用すると、C++03 では、同じ比較を実行するファンクターを作成する必要があります。これには定型コードが必要ですが、それほど複雑になることはありません)

Antimony が指摘しているように、この結果のみが必要な場合は、すべての単語をメモリに保持する必要はありません。その場合、各単語を読み取ったとおりにテストし、最長の回文である場合にのみ保存できます。今。これは、標準のアルゴリズムで簡単に実装できるわけではなく、独自のループをロールするだけで簡単になります。

学習目的では、おそらく本 (C++03 を対象とする) に従うことをお勧めしますが、C++11 での簡単な解決策は次のとおりです。

std::string longestPalindrome( std::istream& stream ) {
   std::string longest;
   std::for_each( std::istream_iterator<std::string>(stream),
                  std::istream_iterator<std::string>(),
                  [&longest]( std::string const & word ) {
                      // if is longest palindrome so far
                      if (std::equal( word.begin(),
                                      word.begin()+word.size()/2,
                                      word.rbegin() 
                          && word.size() > longest.size())) 
                      {
                         longest = word;
                      }
                  });
   return longest;
}
int main() {
   std::ifstream readFile( "/Users/apple/palidndrome-ch5-10/dict.txt" );
   if ( !readFile ) {
      std::cerr << "failed to open file\n";      // [*]
      exit(1);
   }
   std::string longest = longestPalindrome( readFile );
   std::cout << "The longest palindrome is: '" << longest << "'\n";
}

[*]: 本当に必要でない限り、std::endl. 2 つの違いは、ストリームstd::endlもフラッシュする (書き込みを強制する) ことであり、特に理由なくパフォーマンスに影響を与えます。いつフラッシュする必要があるかについては、基本的に、ユーザーにクエリを実行する場合など、出力が今生成されることを確認する必要がある場合:

std::cout << "Enter a number: " << std::flush; // Ensure that the user gets the message
                                               // before we lock waiting for an answer:
std::cin >> number;

そしてこの場合でも、（改行が必要な場合）「\n」をダンプする方がstd::flush明確std::endlであり、（フラッシュが意図的であることが明確ではない場合、果てしなく使用するコードが多すぎるためstd::endl...

于 2012-07-15T04:22:17.333 に答える
1

ここではベクトルとリストの両方が同じように機能しますが、ベクトルの方が効率的です。

変更することで、最も長い単語を見つけることができます

maxLen = max( maxLen, it->size() );
            longestWord = *it ;// need to change code here ?? no idea how

に

if (it->size() >= longestWord.size()) {longestWord = *it;}

(longestWord.size() を呼び出すだけなので、実際には maxlen を追跡する必要はありません。)

于 2012-07-15T03:19:50.577 に答える