基本問題(7)

[ edit ]

*


概要

*


ヒント

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

[ edit ]

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

[ edit ]

  • この課題の解き方 (問題解決のヒント) ....
    • 前に,「約数を列挙する」ために使った「試し割り法」を使いましょう.
      • 先に素数のリストをつくってから,素数のリストで試し割りをしてもよいのですが,その必要もないでしょう.
      • 先に素数のリストを作ってから実行する方法は,効率よく素数のリストを求める方法(エラトステネスの篩(ふるい))を取り上げた後で,やりましょう
*


実行例

[ edit ]

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

fig-01

*


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

[ edit ]

  • 解答例の核心部分,下記 13 行の関数です.

# ==== 【関数定義】 試し割り法で何回割れるかカウントする関数(2~√xまで試す) ==========================
def factoring( x ):
    last = int( x ** 0.5 ) + 1
    list_of_factors = []
    for i in range( 2, last ):
        count = 0
        while is_divisor( i, x ):
            count += 1
            x /= i
        if count != 0:
            # 1項目と2項目は意味が異なるので本当はリストではなくタプルの方がふさわしい → タプルは後日取り上げる
            # print( [i, count] )
            list_of_factors.append( [i, count] )
    if list_of_factors == []: # xが素数のとき,自分自身のみ
        list_of_factors = [[x,1]]
    return( list_of_factors )
*


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

[ edit ]

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

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# ==============================================================================
# * Copyright (c) 2018 IIJIMA, Tadashi
# *       (IIJIMA Laboratory, Dept. of Science and Technology, Keio University).
# ==============================================================================
# ソフトウェア工学[03] 基本課題[03]-(007a)  BP_03_007a_factoring
# BP(Basic Problem) 03-007a: 試し割り法による素因数分解
#        2018-10-17 飯島 正 (iijima@ae.keio.ac.jp)
# ==============================================================================
# ==== 【関数定義】 dはxの約数であるかどうか判定する関数(述語) =================================
def is_divisor( d, x ):
    return( x % d == 0 )
# ==============================================================================
# ==== 【関数定義】 試し割り法で何回割れるかカウントする関数(2~√xまで試す) ==========================
def factoring( x ):
    last = int( x ** 0.5 ) + 1
    list_of_factors = []
    for i in range( 2, last ):
        count = 0
        while is_divisor( i, x ):
            count += 1
            x /= i
        if count != 0:
            # 1項目と2項目は意味が異なるので本当はリストではなくタプルの方がふさわしい → タプルは後日取り上げる
            # print( [i, count] )
            list_of_factors.append( [i, count] )
    if list_of_factors == []: # xが素数のとき,自分自身のみ
        list_of_factors = [[x,1]]
    return( list_of_factors )
# ==============================================================================
# ==== 【関数定義】 素因数分解の結果を表示する ============================================
def print_factors( x, list_of_factors ):
    print( x, " = ", sep="", end="" )
    print( list_of_factors[0][0], "^", list_of_factors[0][1], sep="", end="" )
    for factor in list_of_factors[1:]: # 先頭要素以降のスライス(部分範囲リスト)
        print( " + ", factor[0], "^", factor[1], sep="", end="" )
# ==============================================================================
# ===== 【メイン・プログラム】 =====
# ----- オープニングメッセージ -----
print( "素因数分解: " )
print()

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

# ----- 計算と結果の表示 -----
list_of_factors = factoring(x)
print( x, "の素因数分解は: ", list_of_factors )
print()
print_factors( x, list_of_factors )
print()
# ==============================================================================
*
*

SoftEng: Python/Prog/Practice/Basic/03/BP_007a (last edited 2018-10-21 13:12:28 by TadashiIijima)