基本問題(9)

[ edit ]

Contents

  1. 基本問題(9)
    1. 概要
    2. ヒント
    3. この課題で使うPythonの機能 (学習のヒント)
    4. この課題の解き方 (問題解決のヒント)
    5. 実行例
    6. プログラム例: 本質的な部分 (授業中に順次公開します)
    7. プログラム例: 配布コード (授業中に順次公開します)
*

概要

[ edit ]

*

ヒント

この課題で使うPythonの機能 (学習のヒント)

[ edit ]

この課題の解き方 (問題解決のヒント)

[ edit ]

  • この課題の解き方 (問題解決のヒント) ....
    • 春学期の前提科目でも例題に取り上げていたようですね．
*

実行例

[ edit ]

  • 実行例(1) ... クリックすると拡大します

fig-01

*

プログラム例: 本質的な部分 (授業中に順次公開します)

[ edit ]

  • 解答例の核心部分は，下記の 10 行の関数です． 

# ==== 【関数定義】 エラトステネスの篩 ====================================================
def sieve_of_eratosthenes( n ):
    list_of_prime_numbers = [2]
    limit = int( n ** 0.5 )
    list_of_candidates = [i for i in range( 3, n+1, 2 )]
    while True:
        # print( list_of_candidates )
        prime_number = list_of_candidates.pop(0)
        list_of_prime_numbers.append( prime_number )
        if limit <= prime_number:
            return( list_of_prime_numbers + list_of_candidates )
        # 候補リストからpで割り切れないものだけドロップさせる(filtering out)
        list_of_candidates = filtering_out( list_of_candidates, prime_number )
  • ふるい落とす関数filtering_out()... 実質 6 行の関数 

# ==== 【関数定義】 篩にかける ========================================================
#    ※　list_of_candidates から prime_number，およびその倍数を取り除いたリストを返す
def filtering_out( list_of_candidates, prime_number ):
    result = list()
    for x in list_of_candidates:
        if is_not_divisor( prime_number, x ):
            result.append( x )
    return( result )

[ edit ]

  • 【高度な話題/別解】: ふるい落とす関数filtering_out()... 実質 2 行の関数
    • 内包リスト表現を用いた方法です ⇒ 後日，取り上げる予定です 

# ==== 【関数定義】 篩にかける ========================================================
#    ※　list_of_candidates から prime_number，およびその倍数を取り除いたリストを返す
def filtering_out( list_of_candidates, prime_number ):
    return( [ x for x in list_of_candidates if is_not_divisor( prime_number, x )] )
  • 【高度な話題/別解】: ふるい落とす関数filtering_out()... 実質 2 行の関数
    • 高階関数filter()を用いる方法 ⇒ 後日，取り上げる予定です 

# ==== 【関数定義】 篩にかける ========================================================
#    ※　list_of_candidates から prime_number，およびその倍数を取り除いたリストを返す
def filtering_out( list_of_candidates, prime_number ):
    return( list( filter( lambda x: is_not_divisor( prime_number, x ), list_of_candidates ) ) )

[ edit ]

  • 【高度な話題/別解】: ふるい落とす関数filtering_out()
    • 以下のようには書けません．
      • なぜでしょう？ ⇒ 後日(リスト処理の2周目くらい)，取り上げる予定ですが...
        • シーケンスからループしつつ，要素を削除するのは注意が必要です 

# ==== 【関数定義】 篩にかける ========================================================
#    ※　list_of_candidates から prime_number，およびその倍数を取り除く（）
for x in list_of_candidates:
    if is_divisor( prime_number, x ):
        list_of_candidates.remove( x )
  • 【高度な話題/別解】: ふるい落とす関数filtering_out()
    • 以下なら大丈夫？ ⇒ 後日(リスト処理の2周目くらい)，取り上げる予定です
      • [:]はスライスですが，全体をコピーすることに相当します
        • コピーしたものでループすることで問題が生じません!! 

# ==== 【関数定義】 篩にかける ========================================================
#    ※　list_of_candidates から prime_number，およびその倍数を取り除く（）
#    ※　[:]はスライスですが，全体をコピーすることに相当します ⇒ コピーしたものでループする
for x in list_of_candidates[:]:
    if is_divisor( prime_number, x ):
        list_of_candidates.remove( x )

[ edit ]

  • 【異なる発想の別解(mark&sweep方式):リストの場合】: 本来の配列は，リストよりも添え字によるアクセスが非常に速いので，Python以外の配列をよく使う言語では，以下の解法の方が一般的です

    • mark&sweep方式...私は，このように名付けましたが，mark&sweepというのは元々，ガベージコレクタの実装方法の一つです．

      • 他にこのようには呼ぶ人は，まずいないと思いますので．注意してください (かえって混乱させてしまうかなぁ)． 

# ==== 【関数定義】 篩にかける ========================================================
#    ※　sieveリストに対し，prime_number，およびその倍数に，Falseマークを付ける
def mark_drop_numbers( sieve, prime_number, n ):
    for i in range( prime_number, n+1, prime_number ):
        sieve[i] = False


# ==== 【関数定義】 篩の中での先頭要素(最初にTrueが入っている要素の添え字)を見つける =====
#      ※前回見つけた素数から先をチェックすればよい
def top_of_sieve( sieve, prime_number ):
    top = prime_number
    while not sieve[top]:
        top += 1
    return( top )


# ==== 【関数定義】 篩を走査する（Trueが入っている要素の添え字を収集しリストで返す） =====
def sweep_sieve( sieve, n ):
    result = list()
    for i in range( 2, n+1 ):
        if sieve[i]:
            result.append( i )
    return( result )

  • 【異なる発想の別解(mark&sweep方式):辞書(dict)の場合】:

    • 辞書(dict)とは言っても順序が要りますね．

  • 【異なる発想の別解(mark&sweep方式):NumPyの配列の場合】:

*

プログラム例: 配布コード (授業中に順次公開します)

[ edit ]

  • 以下の解答例を配布します．
    • 本質部分は替えませんが，コメントやメインプログラム部分の実行例を，後々，分かり易く書き換える可能性はあります． 

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# ==============================================================================
# * Copyright (c) 2018 IIJIMA, Tadashi
# *       (IIJIMA Laboratory, Dept. of Science and Technology, Keio University).
# ==============================================================================
# ソフトウェア工学[03] 基本課題[03]-(009a)  BP_03_009a_sieve_of_eratosthenes.py
# BP(Basic Problem) 03-009a: エラトステネスの篩によって素数のリストを求める
#   ※ 篩にかける　⇒ ドロップさせる要素を除いたリストを作る (forループを使う)
#        2018-10-17 飯島 正 (iijima@ae.keio.ac.jp)
# ==============================================================================
# ==== 【関数定義】 dはxの約数であるかどうか判定する関数(述語) =================================
def is_divisor( d, x ):
    return( x % d == 0 )
# -----------------------------------------------------------------------------
def is_not_divisor( d, x ):
    return( x % d != 0 )
# ==============================================================================
# ==== 【関数定義】 篩にかける ========================================================
#    ※　list_of_candidates から prime_number，およびその倍数を取り除いたリストを返す
def filtering_out( list_of_candidates, prime_number ):
    result = list()
    for x in list_of_candidates:
        if is_not_divisor( prime_number, x ):
            result.append( x )
    return( result )
# ==============================================================================
# ==== 【関数定義】 エラトステネスの篩 ====================================================
def sieve_of_eratosthenes( n ):
    list_of_prime_numbers = [2]
    limit = int( n ** 0.5 )
    list_of_candidates = [i for i in range( 3, n+1, 2 )]
    while True:
        # print( list_of_candidates )
        prime_number = list_of_candidates.pop(0)
        list_of_prime_numbers.append( prime_number )
        if limit <= prime_number:
            return( list_of_prime_numbers + list_of_candidates )
        # 候補リストからpで割り切れないものだけドロップさせる(filtering out)
        list_of_candidates = filtering_out( list_of_candidates, prime_number )
# ==============================================================================
# ===== 【メイン・プログラム】 =====
# ----- オープニングメッセージ -----
print( "指定された正整数までの素数のリストを求める: " )
print( "　　　　※エラトステネスの篩を用いる" )
print()

# ----- パラメータの入力 -----
x = int( input( "正の整数を入力してください>>> " ) );
print()

# ----- 計算と結果の表示 -----
result = sieve_of_eratosthenes( x )
print( result )
# ==============================================================================
*
*

SoftEng: Python/Prog/Practice/Basic/03/BP_009a (last edited 2018-10-21 12:55:26 by TadashiIijima)