エラトステネスの篩(ふるい)

エラトステネスの篩(ふるい)

エラトステネスの篩(ふるい)は、効率よく 素数 を求めることができるアルゴリズムです。

指定された範囲の中から2で割り切れる数、3で割り切れる数、・・・・と割り切れる数を順に除外する方法です。

これを繰り返すと最後には 素数 だけが残ることになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import math

def get_prime(n):
if n <= 1: # 1以下の場合
return [] # 空リストを返す
prime = [2] # 素数リストを 2 だけで作成
limit = int(math.sqrt(n)) # 検索する上限を設定(nの平方根)

data = [i for i in range(3, n, 2)] # 奇数のリストを作成
while limit >= data[0]: # 上限≧奇数の先頭の場合
prime.append(data[0]) # 素数リストに奇数の先頭を追加
# 奇数リストのうち、先頭の数で割り切れないものでリストを作成
data = [j for j in data if j % data[0] != 0]

return prime + data # 素数リストと奇数のリストを合わせて返す

print(get_prime(100)) # 100までの素数を求める

[実行結果]

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

高速に素数を求めることができました。

プライオリティキュー

プライオリティキュー

プライオリティキュー を使って、下記の問題を解いてみます。

[問題]

車で 距離L の道を移動します。車にはもともとガソリンが P はいっています。

この車では距離1走るとガソリンが1消費されます。ガソリンが0になると車は停止し移動は失敗します。

途中には N箇所 のガソリンスタンドがあり、各ガソリンスタンドは道のスタート地点からそれぞれ 距離Ai の地点にあり Bi だけガソリンを補給することができます。

車の燃料タンクにはいくらでもガソリンを補給できます。

車は最後まで移動できるでしょうか。最後まで移動できる場合は 最小の補給回数 を、移動できない場合は -1 を出力してください。

[条件]

・ガソリンスタンド数Nは、1以上10000以下です。
・目的とする移動距離Lと初期ガソリン量は、1以上1000000以下です。
・スタート地点から各ガソリンスタンドまでの距離Aiは、1以上目的とする移動距離L以下です。
・各ガソリンスタンドで補給できるガソリン量Biは、1以上100以下です。

[解き方]

車で走るときには、ガソリンスタンドの場所に来た時にしかガソリンを補給できません。

しかし ガソリンスタンドの場所に来た時、それ以降いつでも一度だけガソリンを補給できる権利を手に入れる というように考えることもできます。

後で補給したくなった時に、すでに通過したガソリンスタンドで補給していたことにします。

できるだけ少ない回数の補給にしたいので、燃料が0になるまで走ってから補給をすることにします。

燃料が0になったときに使うべきガソリンスタンド(ガソリン量)は、明らかに最も大きいガソリン量です。

これを効率的に行うために、大きい数字から順に取り出せる プライオリティキュー を使います。


通常のリスト型から max関数 で一番補給量の多いものを取得し、取得したら remove関数 でその要素を削除することで プライオリティキュー の機能を実現します。

[Google Colaboratory]

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
32
33
34
35
36
#------------入力例1-----------------
L = 25 # 距離[L]
P = 10 # 初期ガソリン量[P]
# 各ガソリンスタンド(4か所)までの 距離[Ai] と ガソリン補給量[Bi]
stands = [{'A':10,'B':10}, {'A':14,'B':5}, {'A':20,'B':2}, {'A':21,'B':4}]
#-------------------------------------
cnt = 0 # 補給回数
pos = 0 # 現在の位置(スタート地点からの距離)
tank = P # 現在の保有ガソリン量
lst = [] # ガソリンを補給できる権利(通り過ぎたガソリンスタンドで補給できたはずのガソリン量)

# 目的とする移動距離をガソリンスタンド管理データ[stands]に追加(補給はしないのでガソリン量は0)
stands.append({'A':L,'B':0})

for stand in stands: # 移動箇所(各スタンド+目的移動距離)分ループでまわす
d = stand['A'] - pos # このポイントまでの距離

while tank - d < 0: # 現在のガソリン量でスタンドまでたどり着けるかどうか
# ガソリンが足りない場合
if len(lst) > 0: # ガソリン補給の権利があるかどうか
x = max(lst) # 一番補給量の多いものを取得(プライオリティキー機能として)
lst.remove(x) # 一番補給量の多いものを削除(プライオリティキー機能として)
tank += x # ガソリンを補給
cnt += 1 # ガソリン補給回数をカウントアップ
else: # ガソリン補給ができない
cnt = -1 # 移動失敗
break

if cnt < 0: # 移動失敗したので終了
break
else: # 移動成功
tank -= d # タンクのガソリンを移動距離分減らす
pos = stand['A'] # 現在位置をガソリン位置まで移動
lst.append(stand['B']) # 到達したガソリンスタンドのガソリン補給可能量を権利としてリストに追加

print(cnt)

[実行結果]

2

1つめのと2つ目のガソリンスタンドでガソリンを補充すると目的の距離まで走ることができ、かつ最小の補給回数なので 2 が解となります。

OpenPyXL㉕ (グラフを作成)

グラフを作成

openpyxl.chart で定義されているクラスを使うと、ワークシートのデータから グラフ を作成することができます

グラフ を作成する手順は次のようになります。

  1. グラフオブジェクトの生成
    グラフの種類に対応したオブジェクトを作成します。
  2. グラフタイトル等の設定
    グラフオブジェクトのプロパティを使って、グラフの棒や線のスタイル、グラフのタイトル、縦軸と横軸のタイトルを設定します。
  3. データ用のReferenceオブジェクトの生成
    グラフのデータが入力されているセル範囲を指定します。
  4. カテゴリデータ用のReferenceオブジェクトの生成
    カテゴリデータは入力されているセル範囲を指定します。
  5. グラフオブジェクトへのデータ用Referenceオブジェクトの追加
    グラフオブジェクトにデータ用Referenceオブジェクトを追加します。
  6. グラフオブジェクトへのカテゴリのReferenceオブジェクトの追加
    add_dataメソッドで、グラフオブジェクトにカテゴリのReferenceオブジェクトを追加します。
  7. 位置を指定してグラフを配置
    add_chartメソッドにグラフオブジェクト、グラフを配置する基準にするセル番地を指定して、ワークシートにグラフを配置します。

下記のサンプルソースでは、BarChartコンストラクタ を使って棒グラフを作成しています。

[Google Colaboratory]

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import openpyxl
from openpyxl.chart import BarChart, Series, Reference

book = openpyxl.Workbook() # ブックを生成
sheet = book.active # アクティブなシートを取得

rows = [
('月', '商品1', '商品2'), # タイトル行
(1, 320, 435), # 12行のレコードデータ
(2, 130, 530),
(3, 440, 60),
(4, 550, 770),
(5, 260, 410),
(6, 370, 640),
(7, 580, 630),
(8, 625, 430),
(9, 720, 230),
(10, 580, 340),
(11, 670, 450),
(12, 605, 755),
]
for row in rows: # 行数のぶんだけ繰り返す
sheet.append(row) # ワークシートに追加する

#### 列ごとに棒グラフを作成 ####
chart1 = BarChart() # 棒グラフのオブジェクトを生成
chart1.type = 'col' # 列ごとにタテ棒を表示する
chart1.style = 10 # グラフのスタイルを設定
chart1.title = '年間売上' # メインタイトル
chart1.y_axis.title = '売上高' # タテ軸のタイトル
chart1.x_axis.title = '月' # ヨコ軸のタイトル

# データが入力されているセル範囲
data = Reference(sheet, # 対象のワークシート
min_col=2, # 開始列
min_row=1, # 開始行
max_col=3, # 終端列
max_row=13 # 終端行
)

# カテゴリデータのセル範囲
cats = Reference(sheet, # 対象のワークシート
min_col=1, # 開始列
min_row=2, # 開始行
max_row=13) # 終端行

# BarChartオブジェクトにデータを追加
chart1.add_data(data, titles_from_data=True)

# BarChartオブジェクトにカテゴリを追加
chart1.set_categories(cats)

# ワークシート上にグラフを追加
sheet.add_chart(chart1, # 対象のワークシート
'A15' # グラフエリアの左上隅をA16セルに合わせる
)

book.save('Test.xlsx') # ブックを保存

[Test.xlsx]

保存したExcelファイルを確認すると、棒グラフが作成されていることを確認できます。

しゃくとり法

しゃくとり法

しゃくとり法 というアルゴリズムを使って、下記の問題を解いてみます。

[問題]

1
2
3
長さ<b>n</b>の数列 <b>a1,a2,..</b> と整数<b>S</b>が与えられます。
連続する部分列で、その合計が<b>S</b>以上となるもののうち、<b>最小の長さ</b> を求めなさい。
解が存在しない場合は<b>0</b>を出力しなさい。

[条件]

1
2
3
・長さ<b>n</b>は <b>5以上 100000未満</b>
・数列の各要素は、<b>0より大きく10000以下</b>
・整数Sは <b>100000000未満</b>

この問題は、区間の先頭と末尾を 交互 に進めながら条件を満たす 最小の区間 を調べることで解くことができます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
a = [5,1,3,5,10,7,4,9,2,8]
S = 15

n = len(a) # 配列数
res = n + 1 # 最小区間の初期値(配列数+1)
s = 0 # 集計開始位置
t = 0 # 集計最終位置
total = 0 # 合計値

while True:
while t < n and total < S: # 集計最終位置が配列内かどうか、合計値がSより小さいかどうか
total += a[t] # 合計値を算出
t += 1 # 集計最終位置を1つうしろにずらす
if total < S:
break # 合計値が条件(整数S以上)に達していないので終了(集計最終位置が配列を超えた)
res = min(res, t - s) # 合計値が条件を満たしている部分列の長さが、より短い場合は更新
total -= a[s] # 合計値から先頭の要素をひく
s -= 1 # 集計開始位置を1つうしろにずらす

if res > n: # 配列数より大きいので解がなかった
res = 0 # 解がなかったため0を設定
print(res) # 解を出力

[実行結果]

1
2

配列の4番目から5番目の2要素(5,10)を足すと15を超えますので、出力結果の2は正解ということになります。

OpenPyXL㉔ (レコード単位で入力)

レコード単位で入力

レコード単位で複数のデータを入力するためには、Worksheetオブジェクトの appendメソッド を使います。

まずは1行分のレコードをタプルで定義し、これを1つのリストにまとめます。

そのあとリストに設定した1レコード分のデータ(タプル)をforループで取得し、appendメソッドの引数に設定します。(22~23行目)

[Google Colaboratory]

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
import openpyxl

rows = [
('月', '商品1', '商品2'), # タイトル行
(1, 320, 435), # 12行のレコードデータ
(2, 130, 530),
(3, 440, 60),
(4, 550, 770),
(5, 260, 410),
(6, 370, 640),
(7, 580, 630),
(8, 625, 430),
(9, 720, 230),
(10, 580, 340),
(11, 670, 450),
(12, 605, 755),
]

book = openpyxl.Workbook() # ブックを生成
sheet = book.active # アクティブなシートを取得

for row in rows: # 行数の数だけ繰り返す
sheet.append(row) # ワークシートに追加する

book.save('Test.xlsx') # ブックを保存

[Test.xlsx]

保存したExcelファイルを確認すると、リストに定義したデータがすべて入力されていることを確認できます。

OpenPyXL㉓ (行や列の固定表示)

行や列の固定表示

Excelには、ワークシートのセルをスクロールさせても特定の 行や列を固定で表示 する機能があります。

データが多い場合に見出しの行やれるを固定しておくと、スクロールしても常に見出しが表示されるので作業がしやすくなります。

Worksheetオブジェクトの freeze_panesプロパティ に任意のセル番地を代入するとセルが固定されるようになります。

次のサンプルコードでは、1行目を固定表示 にしています。

[Google Colaboratory]

1
2
3
4
5
6
7
import openpyxl

book = openpyxl.Workbook()
sheet = book.active

sheet.freeze_panes = 'A2'
book.save('Test.xlsx')

[Test.xlsx]

保存されたExcelファイルを開くと、1行目が 固定表示 になっていることを確認できます。

OpenPyXL㉒ (セル結合の解除)

セル結合の解除

Worksheetオブジェクトの unmerge_cellsメソッド を使うと、結合したセルを 解除 することができます。

引数には結合されたセルの 元のセル範囲 を指定します。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
import openpyxl

book = openpyxl.Workbook()
sheet = book.active

sheet.merge_cells('A1:A2') # セルを結合
sheet['A1'] = '結合1' # セルに入力
book.save('Test1.xlsx')

sheet.unmerge_cells('A1:A2') # 結合を解除
book.save('Test2.xlsx')

[Test1.xlsx] ➡ [Test2.xlsx]

2つのExcelファイルを開くと、結合されたセルが 解除 されていることを確認できます。

OpenPyXL㉑ (セル結合)

セル結合

Worksheetオブジェクトの merge_cellsメソッド を使うと、複数のセルを1つのセルに結合できます。

引数にセル範囲を指定すると、すべてのセルが 左上のセル に結合されます。

下記のサンプルコードでは、A1とA2を1つのセル に結合しています。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
import openpyxl

book = openpyxl.Workbook()
sheet = book.active

sheet.merge_cells('A1:A2') # セルを結合
sheet['A1'] = '結合1' # セルに入力
#sheet['A2'] = '結合2' # エラー(AttributeError: 'MergedCell' object attribute 'value' is read-only)

book.save('Test.xlsx')

結合したセルに値を設定する場合は、左上のセル(A1)を指定します。

左上のセル以外(A2)に値を設定しようとすると AttributeError が発生します。

[Test.xlsx]

保存したExcelファイルを開くと、A1とA2の セルが結合 されていることを確認できます。

OpenPyXL⑳ (セルの幅と高さを設定)

セルの幅と高さを設定

Worksheetオブジェクトには、セルの幅や高さ を保持するオブジェクトがあります。

  • column_dimensionsオブジェクト
    セルの幅を保持します。
    widthプロパティ でセル幅を設定します。
    0から409まで の整数、または小数を設定可。単位はポイント(pt)。
  • row_dimensionsオブジェクト
    セルの高さを保持します。
    heightプロパティ でセルの高さを設定します。
    0から255まで の整数、または小数を設定可。単位はポイント(pt)。

セルの幅と高さを設定するサンプルコードは下記のとおりです。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
import openpyxl
book = openpyxl.Workbook() # Workbookオブジェクトを生成
sheet = book.active # アクティブシートを取得

sheet['A1'] = '幅を設定' # A1セルに文字列を入力
sheet.column_dimensions['A'].width = 50 # A列の幅を30に設定
print('A列の幅 =>', sheet.column_dimensions['A'].width)

sheet['B2'] = '高さを設定' # B2セルに文字列を入力
sheet.row_dimensions[2].height = 80 # 2行目の高さを100に設定
print('2行目の高さ', sheet.row_dimensions[2].height)

book.save('Test.xlsx') # ファイル保存

[実行結果]

[Test.xlsx]

保存されたExcelファイルを開くと、セルの幅と高さ が変更されていることを確認することができます。

OpenPyXL⑲ (数式を入力)

数式を入力

Excelの数式を設定する場合は、数式を文字列 でセルに書き込みます。

sheet[‘A3’] = ‘=SUM(A1:A2)’

上記のように設定すると、ワークシートの A3セルA1からA2までの値を合計 して表示することができます。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
import openpyxl

book = openpyxl.Workbook() # Excelブックを生成
sheet = book.active # アクティブなワークシートを取得
sheet['A1'] = 50 # A1セルに値を入力
sheet['A2'] = 30 # A2セルに値を入力
sheet['A3'] = '=SUM(A1:A2)' # A3セルにSUM()関数を入力
print('A3セル', sheet['A3'].value) # A3セルの数式を確認

book.save('test.xlsx') # ブックを保存

[実行結果]

A3セルに ‘=SUM(A1:A2)’ という数式が設定されていることを確認できます。

[Test.xlsx]

保存されたExcelファイルを確認すると、A3セルに A1からA2までの合計値 が表示されています。