Differences between revisions 8 and 10 (spanning 2 versions)
⇤ ← Revision 8 as of 2018-10-14 21:38:29 →
Size: 3673
Editor: TadashiIijima
Comment:
← Revision 10 as of 2018-10-16 13:56:30 → ⇥
Size: 408
Editor: TadashiIijima
Comment:
Deletions are marked like this. Additions are marked like this.
Line 5: Line 5:
#acl AdminGroup:read,write,delete,revert,admin TadashiIijima:read,write,delete,revert,admin IijimaStaffGroup: IijimaGroup: IijimaObogGroup: GuestGroup: Known: All: #acl AdminGroup:read,write,delete,revert,admin TadashiIijima:read,write,delete,revert,admin IijimaStaffGroup: IijimaGroup: IijimaObogGroup: GuestGroup: Known: All:read
Line 17: Line 17:

 * 解答は基本的に，下記 6 行です．
  * 2～√xまでの整数で順に割ってみて，割り切れたら，(1と)自分自身以外に約数があることを意味する．
   * 逆に言えば，割り切れる整数が，その範囲内に存在しなければ，素数であることを意味する
  * x**0.5は，平方根です．したがって，mathモジュールのsqrt()関数を使ってもかまいません
  * 与えられた整数以下の素数を列挙するのであれば，[[https://ja.wikipedia.org/wiki/エラトステネスの篩|エラトステネスの篩(ふるい)]]を使うのがよいでしょう
   * 後日，リストを取り上げてからやりましょう

{{{#!highlight python
def is_prime_number( x ):
    last = int( x ** 0.5 )
    for i in range( 2, last + 1 ):
        if is_divisor( i, x ):
            return( False )
    return( True )
}}}

 * ここで，is_divisor()関数は，単に，約数かどうか判定する以下の2 行の関数ですが，関数にするまでもないですね．

{{{#!highlight python
def is_divisor( d, x ):
    return( x % d == 0 )
}}}

 * なので，もうすこし短く書けそうです．

{{{#!highlight python
def is_prime_number( x ):
    for i in range( 2, int( x ** 0.5 + 1 ) ):
        if x % d == 0 :
            return( False )
    return( True )
}}}

{{{#!highlight python
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# ==============================================================================
# * Copyright (c) 2018 IIJIMA, Tadashi
# * (IIJIMA Laboratory, Dept. of Science and Technology, Keio University).
# ==============================================================================
# ソフトウェア工学[02] 基本課題[02]-(008a) BP_02_008a_judge_prime_number_by_trial_division.py
# BP(Basic Problem) 02-008a: 試し割による素数判定
# 2018-10-03 飯島 正 (iijima@ae.keio.ac.jp)
# ==============================================================================
# dはxの約数である
def is_divisor( d, x ):
    return( x % d == 0 )
# ==============================================================================
# 2 ～　√xの間に，約数が存在しないなら，xは素数
def is_prime_number( x ):
    last = int( x ** 0.5 )
    for i in range( 2, last + 1 ):
        if is_divisor( i, x ):
            return( False )
    return( True )
# ==============================================================================
# ===== 【メイン・プログラム】　 =====
# ----- オープニングメッセージ -----
print( "試し割り法によって，素数か否かを判定する関数： " )
print( "　　50以下の素数列を表示するために使ってみる．　" )
print( " 指定の数以下の素数を列挙するには，「エラトステネスの篩」を使う方が効率がよいが，" )
print( " その実装は，リストを取り上げてから，後日，行う" )

# ----- 計算と実行結果の表示 -----
for i in range( 2, 50 ):
    if is_prime_number( i ):
        print( i, end=", " )
print()
# ==============================================================================
}}}

基本問題(8)

Contents

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

*

概要

[ edit ]

*

ヒント

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

[ edit ]

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

    • 関数定義

    • print()関数

      • キーワードパラメータsepは区切り文字列，キーワードパラメータendは行末文字列です．

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

[ edit ]

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

    • 素数かどうかの判定には，試し割り法を使いましょう

      • dがxの約数かどうかを判定する関数is_divisor( d, x )と，xが素数かどうかを判定するis_prime_number(x)を定義しましょう
      • 2～√xまでの整数で順に割ってみて，割り切れたら，「(1と)自分自身以外に約数がある」ことを意味します．
        • 逆に言えば，割り切れる整数が，その範囲内に存在しなければ，「素数である」ことを意味します

      • 平方根は，x**0.5で求められます．

      • 与えられた整数以下の素数を列挙するのであれば，エラトステネスの篩(ふるい)を使うのがよいでしょう

        • 後日，リストを取り上げてからやりましょう
*

実行例

[ edit ]

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

fig-01

*

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

[ edit ]

  • 解答は基本的に，下記 6 行です．

    • これが試し割り法です．

      • 2～√xまでの整数で順に割ってみて，割り切れたら，「(1と)自分自身以外に約数がある」ことを意味します．
        • 逆に言えば，割り切れる整数が，その範囲内に存在しなければ，「素数である」ということになります．
      • x**0.5は，平方根です．したがって，mathモジュールのsqrt()関数を使ってもかまいません
    • 「与えられた整数以下の素数を列挙する」のであれば...

      • エラトステネスの篩(ふるい)を使うのがよいでしょう

      • 「エラトステネスの篩(ふるい)」は，後日，リストを取り上げてから(前提科目では既に使っていますが)，やりましょう 

def is_prime_number( x ):
    last = int( x ** 0.5 )
    for i in range( 2, last + 1 ):
        if is_divisor( i, x ):
            return( False )
    return( True )
  • ここで，is_divisor()関数は，単に，約数かどうか判定する以下の2 行の関数です 

   1 def is_divisor( d, x ):
   2     return( x % d == 0 )
  • もちろん，以下のようにも書けますが，ちょっと冗長ですね．
    • 条件を表す論理式を，if文やwhile文の条件判断のところに書く例を見慣れているので，以下のように書く人も割と多いでしょう．
      • ですが，論理式の評価結果（計算結果）は論理値です．論理値を返す関数なら，そのままそれを返してしまえばよいですよね．
      • 上記のように書いてもよいということを一度見ておけば，今後も安心して使えますよね． 

   1 def is_divisor( d, x ):
   2     if x % d == 0:
   3         return( True )
   4     else:
   5         return( False )
  • is_divisor()は，関数にするまでもないですね．
    • is_prime_number()関数に組み込んでしまえば，下記のように，もうすこし短く書けそうです．
    • でも，私の個人的意見としては，is_divisor()を関数として独立させる方が好みです

      • x % d == 0という条件式が何を意味しているかを，関数名で明確に示しているからです．

      • もちろん，これは単なる個人的好みなので，皆さんに押し付けるつもりはありません
        • ですから，試験などではどちらの形でも構いません（加点も減点もありませんので心配しないでくださいね） 

   1 def is_prime_number( x ):
   2     for i in range( 2, int( x ** 0.5 + 1 ) ):
   3         if x % d == 0 :
   4             return( False )
   5     return( True )
*

高度な話題 (授業中，もしくは授業後に順次公開します)

[ edit ]

  • ⇒ 高度な話題へのリンク: 授業の流れを阻害しないように別ページにします

    • (後日の回の授業内容にはなる可能性がありますが，この回の授業内容には含めません)．
    • に関するものです．

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

*

*

SoftEng: Python/Prog/Practice/Basic/02/BP_008a (last edited 2018-10-28 14:44:43 by TadashiIijima)