C++講座 第3回?

algorithmとエラトステネスの篩です. 2008-05-28にやった内容です.

ここに書いてあるソースは全くチェックしてないのでコンパイルできないかも.

algorithm

algorithmには色々なアルゴリズムが入っていますが, 今回はsortとreverseを使います.

algorithmを使うためには.

#include <algorithm>

としてください.

sort

sort(ここから,ここまで);

「ここから」の部分と「ここまで」の部分にはイテレータを渡します. とりあえずソートしたい場合は,begin()とend()を渡すことが多いと思います.

前にやったことの復習です.前回はintでしたが, 今回は文字列のソートをしてみます.

#include <string>
#include <vector>
#include <algorithm>
#include <stdio.h>
using namespace std;
int main(){
  vector<string> v;
  v.push_back("safii");
  v.push_back("sango");
  v.push_back("key");
  v.push_back("muroi");

  //  ソートする
  ・・・

  // イテレータを使って表示
  ・・・

  return 0;
}

先に「イテレータを使って表示」を書いてみましょう.

vector<string>::iterator it;
for (it=v.begin();it!=v.end();++it) {
  printf("%s\n",(*it).c_str());
}

気をつけなければいけないのは,printfはC言語の関数なので, string型を表示できないことです. 「*it」はstring型なので,printfで表示できません. そこで,「c_str()」メソッドでC言語の「char*」を得ます.

C++の入出力機能を使えばstring型でもなんでも表示できるのですが, それはまた後日.

表示できたら次に「ソートする」のところを書いてみます.

sort(v.begin(), v.end());

これだけです.intをソートしたときと全く同じですね. algorithmのsort()はイテレータさえ渡せばソートしてくれます.

reverse

使い方はsortと同じなので, さっきの'sort'を'reverse'に置き換えるだけです.

reverse(v.begin(), v.end());

これだけでは,つまらないので,文字列自体をreverseしてみます.

C言語の文字列はcharの配列でしたが,C++のstringもやはり内部では vectorと同じように配列を使っています. …ということは,文字列についてもイテレータが使えます.

string s="sango";

このとき,begin()とend()は,

s.begin() ← 先頭の's'を指す
s.end() ← 末尾の'o'の後ろ指す

となっています.

string s="sango";
reverse(s.begin(), s.end());
printf("%s\n",s.c_str());

どういう結果が出たでしょうか? もちろん,sortとかもできます.

algorithmには,sortやreverse以外にも色々入っているので 調べてみてください.良く使うのはsortくらいですが….

エラトステネスの篩

ICPCで素数を使った問題が出ることがあります. ある範囲内の素数の一覧が欲しいときは,エラトステネスの篩(ふるい)が便利です.

配列を用意して,素数で無いと分かったものから消していきます.

1は素数で無いので,最初に消す.

x2345678910
11121314151617181920
21222324252627282930
31323334353637383940

次に,2を見ます.2には「x」がついてないので,素数です. この時点で,2の倍数は素数で無いことが分かるので2の倍数全てに「x」をつけます.

x23x5x7x9x
11x13x15x17x19x
21x23x25x27x29x
31x33x35x37x39x

次に3が出てきます.そして,3の倍数を全て「x」にします.

x23x5x7xxx
11x13xxx17x19x
xx23x25xxx29x
31xxx35x37xxx

4は「x」なので,次に5が出てきます.

x23x5x7xxx
11x13xxx17x19x
xx23xxxxx29x
31xxxxx37xxx

このように配列を操作していけば,素数だけが残ります.

もっと…

上の例は,改善の余地があります.

例えば,「2」以外の偶数は明らかに素数ではないので最初から無かったことに すれば配列の大きさや比較の回数を減らすことが出来ます.

全ての素数は必要ないけど,ある数「x」が素数かどうか判定したいこともあります. このときは,2~√xまでの全ての整数で割ってみて,割り切れなければ 素数ということができます.

ただ,「x」がとても大きい(数十~数百桁ある)ときは,この方法では いつまでたっても計算が終わりません. 暗号に使われる素数は2進数で数千ビットあるのが普通です. そんなときはラビン法等の確率的判定を行いましょう. 確率的判定は「たぶん素数」ということが確認できますが, 複数回繰り返すことで「まず間違いなく素数」であると確認することができます.

Texts

total: 1567  / today: 1  / yesterday: 1  / now: 1

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2015-09-22 (火) 17:40:46 (1247d)