Differences between revisions 7 and 8
Revision 7 as of 2018-10-12 06:58:51
Size: 3974
Comment:
Revision 8 as of 2018-10-14 21:38:29
Size: 3673
Comment:
Deletions are marked like this. Additions are marked like this.
Line 17: Line 17:

 ||<|2>演習(8) ||<|2>基本課題(8a)||<|2>【関数定義】||<|1>[[https://ja.wikipedia.org/wiki/試し割り法|試し割り法]]による素数判定||
 ||<|1> [[../BP_008a|BP_02_008a_judge_prime_number_by_trial_division.py|target="_blank"]]||
Line 91: Line 88:



----

基本問題(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 ]

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

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


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

*

*

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

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

   1 def is_prime_number( x ):
   2     last = int( x ** 0.5 )
   3     for i in range( 2, last + 1 ):
   4         if is_divisor( i, x ):
   5             return( False )
   6     return( True )
  • ここで,is_divisor()関数は,単に,約数かどうか判定する以下の2 行の関数ですが,関数にするまでもないですね.

   1 def is_divisor( d, x ):
   2     return( 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 )

   1 #!/usr/bin/env python
   2 # -*- coding: utf-8 -*-
   3 # ==============================================================================
   4 # * Copyright (c) 2018 IIJIMA, Tadashi
   5 # *       (IIJIMA Laboratory, Dept. of Science and Technology, Keio University).
   6 # ==============================================================================
   7 # ソフトウェア工学[02] 基本課題[02]-(008a)  BP_02_008a_judge_prime_number_by_trial_division.py
   8 # BP(Basic Problem) 02-008a: 試し割による素数判定
   9 #        2018-10-03 飯島 正 (iijima@ae.keio.ac.jp)
  10 # ==============================================================================
  11 # dはxの約数である
  12 def is_divisor( d, x ):
  13     return( x % d == 0 )
  14 # ==============================================================================
  15 # 2 ~ √xの間に,約数が存在しないなら,xは素数
  16 def is_prime_number( x ):
  17     last = int( x ** 0.5 )
  18     for i in range( 2, last + 1 ):
  19         if is_divisor( i, x ):
  20             return( False )
  21     return( True )
  22 # ==============================================================================
  23 # ===== 【メイン・プログラム】  =====
  24 # ----- オープニングメッセージ -----
  25 print( "試し割り法によって,素数か否かを判定する関数: " )
  26 print( "  50以下の素数列を表示するために使ってみる. " )
  27 print( "  指定の数以下の素数を列挙するには,「エラトステネスの篩」を使う方が効率がよいが," )
  28 print( "  その実装は,リストを取り上げてから,後日,行う" )
  29 
  30 # ----- 計算と実行結果の表示 -----
  31 for i in range( 2, 50 ):
  32     if is_prime_number( i ):
  33         print( i, end=", " )
  34 print()
  35 # ==============================================================================

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