忍者ブログ
CUDA+GPGPU、C++、C#などのプログラムについての備忘録がわり
[63] [62] [61] [60] [59] [58] [57] [56] [55] [54] [53
Posted by - 2019.10.17,Thu
×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

Posted by サンマヤ - 2013.04.08,Mon
ブログ記事再開の第1弾は、Pythonです。

いままで、C++やDelphi、C#といった言語を使ってきましたが、
Pythonが大きく異なる点は、型チェックが実行時にのみあるというところです。
まあ、スクリプト言語(インタープリター)なので当たり前ですが。

今回は、簡単なプログラムを作ってみたいと思います。


さて、プログラムのテーマなのですが、
リストなどを簡単に扱えるということで、素数を列挙するプログラムを書いてみたいと思います。

素数を見つけるアルゴリズムは、「エラトステネスのふるい」です。
とはいっても、当たり前の方法です。

目標:Nまでの素数を見つける

1.2からNまでの整数を全部書き出した表をつくる
2.表のうち、一番小さいものは素数(最初は2)
3.表から、その素数で割れるものは全部消す
4.表に数が残っていれば、2番に戻る

小さい順に素数をみつけていき、それで割れる数を消していくってことですね。

実に単純な方法ですが、それ以上に効率のいい方法というのもなさそうです。
(素数にいわゆる「規則性」みたいなものはないので)

最初に作ったプログラムリスト。
prime1.py
 1 #! c:/python27/python.exe
 2 
 3 
 4 def PrimeNumber():
 5     number_list = range(2,10000)
 6     number_list.reverse()
 7     prime_list = []
 8 
 9     while len(number_list)>0:
10         a = number_list.pop()
11         prime_list.append(a)
12         for x in reversed(number_list):
13             if x % a == 0:
14                 number_list.remove(x)
15     print "prime numbers are\n"
16     print prime_list
17 
18 
19 if __name__ == "__main__":
20     PrimeNumber()
21 
1行目は、スクリプト言語のお作法で、インタープリターのパスを指定しています。
4行目からがメインとなる関数の定義です。
まず、2から10000までの整数をいれたリストを作ります。
その後、リストを逆順にしているのは、リストは末尾から取り出すのが効率がいいので、
手順2を行うのに都合がいいのです。
そして、prime_listは素数のリストで、最初は空です。
while文以降は、数のリストが空っぽになるまで以下の処理を続けろ、という意味。
ここで、Pythonの特徴のひとつに、「ブロックはインデントで決まる」というのが使われます。
C言語系なら{}、Pascalならbegin-endなど、
たいていの言語では処理の構造を示す記号が決められています。
ところが、Pythonではインデントですべてが決められます。
これはコーディングの見た目が統一されるという意味で合理的かもしれません。

ループの中では、まず最初にリストの末尾から数字を取り出し、素数のリストに加えます。
次に、取り出した素数で割れる数字をリストから消します。
逆順に取り出しているのは、繰り返し処理の中でリストの要素を削除するという操作を行うとき、
その副作用がリストの繰り返し処理にどのような影響を与えるかわからなかったからです。

以上でアルゴリズムは終了ですが、
最後のところの処理でかなり処理コストがかかりそうです。
というのも、末尾から調べていくので、removeを実行した際に、
先頭から探して該当要素を消すとなると、その検索に時間がかかりそうだからです。

というわけで、次回はこの点を改良するとともに、
関数プログラミング的な要素を取り入れた変更を加えてみたいと思います。
PR
Comments
Post a Comment
Name :
Title :
E-mail :
URL :
Comments :
Pass :   Vodafone絵文字 i-mode絵文字 Ezweb絵文字
カレンダー
09 2019/10 11
S M T W T F S
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31
フリーエリア
最新コメント
[11/19 矢野 忠]
[02/25 山本義和]
[07/08 hirota]
[07/06 hirota]
[02/05 矢野 忠]
最新トラックバック
プロフィール
HN:
サンマヤ
性別:
非公開
職業:
プログラマ
趣味:
ゲーム
バーコード
ブログ内検索
カウンター
忍者アナライズ
Template by mavericyard*
Powered by "Samurai Factory"
忍者ブログ [PR]