<a href="https://nichidaibunrigojokai.swiki.jp/index.php?cmd=related&page=%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E5%85%A5%E9%96%80%28%E6%9D%91%E4%B8%8A%E9%9B%85%E5%BD%A6%29">プログラミング入門(村上雅彦)</a> の変更点
Top > プログラミング入門(村上雅彦)
|
プログラミング入門(村上雅彦) の変更点
''■[[プログラミング入門>プログラミング入門（学科専門）]]''
#contents
|BGCOLOR(#555):COLOR(White):200|520|c
|BGCOLOR(#fc2):COLOR(Black):''分類''|''数学科選択／数学科教員選択''|
|区分|[[数学科]]科目|
|履修形態|一般(人数過多の場合は抽選)|
|履修条件|二年生以上|
|単位数|2|
|講師|[[村上雅彦]]|
|学位等|学士（理学）|
*概要 [#Gaiyou]
&color(Red){「プログラミング入門」という名前の科目は複数ある。必ず数学科のものを履修すること。};
[[数学科]]と[[教職課程（数学科）>教職コース/教職課程]]の選択科目
プログラミングの基本となる条件分岐，繰り返し，配列（リスト），文字列についての講義が行われる。
Pythonを用いてプログラムを作成し計算を行う。（授業では[[PyTry>https://pro-ktmr.github.io/pytry/pytry/]]を使う。）
#br
教科書は北村祐稀の『JOI公式テキスト Pythonで問題解決 情報オリンピックに出てみよう』(実教出版 2022年 第1版)
必ず必要（初めの数講は[[立ち読み版>https://www.jikkyo.co.jp/material/dbook/R4JOI20220909/?pNo=1]]で可。）
#br
評価はLMSに毎回提出する演習の取り組み度合いでする。(100%)
対面授業に参加できない場合は対面授業の場合と同じく、設定されている曜日・時限にZoomで参加し、
CanvasLMSから演習ファイルを提出するように。
#br
困った時は[[Gemini>https://gemini.google.com/app?utm_source=app_launcher&utm_medium=owned&utm_campaign=base_all]]に聞くべし。
#br
この科目は文理学部(理学)のディプロマポリシー DP3,4,5 及びカリキュラムポリシー CP3,4,5 に対応している。
*講師の印象 [#Inshou]
*令和八年度(2026年度) [#h81d5434]
#style(class=submenuheader){{
**前期
}}
#style(class=submenu){{
|BGCOLOR(#555):COLOR(White):200|520|c
|BGCOLOR(#fc2):COLOR(Black):授業形態|対面授業|
|日程/教室|土曜日 三限目/3209教室(三号館二階九番教室)|
初めの数講は[[立ち読み版>https://www.jikkyo.co.jp/material/dbook/R4JOI20220909/?pNo=1]]で可。
[[著者のサポートサイト>https://pro-ktmr.github.io/joi-text/]]では、問題リスト（解答例付き）などが見られる。
また、[[公式Youtube>https://www.youtube.com/playlist?list=PLLGAP7yC96VH9djJcpmPz3JPplcxg9t2k]]が用意されている。
#br
//このページでは教科書がなくても問題ないように
この授業では著者が作った[[PyTry>https://pro-ktmr.github.io/pytry/pytry/]]を使う。
//***関数一覧 [#v8648eaa]
***基本 [#v8648edd]
#region(文字入力)
''文字入力''
PyTry(パイトライ)では直接文字を書けない。
関数を使って出力する。
-例①
print("テスト")
-例②
text = "テスト"
print(f"{text}")
#br
出力されない文字を書く場合は# を使う。
# この文章は出力されない。
print("テスト") # この文章は出力されない。
#br
#br
:Hello Worldの出力|
-print("")関数のみを用いる場合
print("Hello World")
-変数を使う場合
message = "Hello World"
print(message)
-f-strings（フォーマット済み文字列）を使う場合
name（他の単語でも構わない。）で文字列を設定し、print(f"{name}")で出力。
fはフォーマット(format)のf。
name = "World"
print(f"Hello {name}")
#endregion
***計算 [#v8648edb]
#region(計算)
''計算''
|計算記号|説明|例|h
|+|足し算|print(5 + 5)|
|-|引き算|print(5 - 5)|
|*|掛け算|print(5 * 5)|
|**|冪乗(aのb乗)|print(5 ** 5)|
|/|割り算|print(5 / 5)|
|//|割り算の商|print(5 // 5)|
|%|割り算の余り|print(5 % 5)|
#br
input()関数などを使う場合
|関数|説明|h
|input()|画面に入力欄を出し、入力された内容を文字列として受け取る。|
|int()|受け取った文字列を整数（Integer）に変換する。|
|float()|少数の計算に使う。|
input()で認識させた文字列をコンピューター側に計算可能な数値として認識させるには、int()を使う。
int()内に数字以外を入れるとエラーを起こす。例：int("こんにちは")
#br
-例
|CENTER:ソースコード|CENTER:入力欄|CENTER:出力欄|h
|100|100|100|c
|a = int(input())&br;b = int(input())&br;answer = a + b&br;print(answer)|100&br;200&br; &br; |300&br; &br; &br; |
aやbの数値はあらかじめ入力欄の同じ行に書いておく。
#br
>''baseとexponentを使った冪乗''
|関数|説明|h
|base|底|
|exponent|指数|
base = 3
exponent = 4
result = base**exponent
print(result)
# 3の4乗の計算
>''少数の計算''
float()とは、データを浮動小数点数に変換するための関数
#br
|例|結果と解説|h
|print(float("3.14"))|3.14が出力|
|print(float(5)) |5.0が出力（自動的に .0 がつく。）|
|print(int(3.99))|3が出力（intに入れると、小数の部分は切り捨てられる。）|
-例
|CENTER:ソースコード|CENTER:入力欄|CENTER:出力欄|h
|200|200|200|c
|num_str = input()&br;num_float = float(num_str)&br;print(num_float * 2)|1.5&br; &br; |3.0&br; &br; |
#endregion
***条件分岐 [#v8513bd8]
#region(条件分岐)
''条件分岐''
Pythonでは、if、elif、elseを使う。
（elifはelse ifの略）
|記号|意味|例|h
|==|等しい|a == b|
|!=|等しくない|a != b|
| > |より大きい|a > b|
| < |より小さい|a < b|
|>=|以上|a >= b|
|<=|以下|a <= b|
（※ = は代入なので注意）
#br
条件式の後ろには必ず「:」を付ける。
条件を満たしたときに実行したい処理は、半角スペース4つ分右にずらして書く。
この下げられたブロックが「その条件のときに実行される命令」になる。
#br
>''コード''
# 判定したい数値
score = 75
if score >= 80:
# 条件1：80点以上のとき
print("評価: A")
elif score >= 60:
# 条件2：80点未満で、60点以上のとき
print("評価: B")
else:
# どの条件にも当てはまらないとき（60点未満）
print("評価: C")
#br
「AかつB」「AまたはB」のように、複数の条件を組み合わせるにはandとorを使う。
|~and|両方の条件を満たすときだけ実行（かつ）|
|~or|どちらか一方でも条件を満たせば実行（または）|
>''コード''
if age >= 20 and has_ticket == True:
print("入場できます")
if day == "土曜日" or day == "日曜日":
print("お休みです")
#endregion
***繰り返しfor・繰り返しwhile [#mefadbc0]
|>|使い分け|h
|~for|処理する回数やデータ（リストなど）が決まっている時|
|~while|終了する条件だけが決まっている時|
#region(繰り返しfor)
''繰り返しfor''
for文は、「リストの中身を1つずつ取り出す」時や「〇回繰り返す」というように回数が決まっている場合に使う。
>''リストの要素を順番に取り出す場合''
-コード
fruits = ["りんご", "バナナ", "ぶどう"]
for item in fruits:
print(f"好きな果物: {item}")
-結果
好きな果物: りんご
好きな果物: バナナ
好きな果物: ぶどう
>''指定した回数だけ繰り返す場合''
繰り返したい場合は range(回数) を使う。
# 0から4まで（計5回）繰り返す
for i in range(5):
print(f"{i + 1}回目の実行")
#br
range(5) は 0, 1, 2, 3, 4 という数字を生成するため、1回目から表示したい場合は i + 1 とする。
#endregion
#region(繰り返しwhile)
''繰り返しwhile''
while文は、「条件が成り立っている間（Trueの間）ずっと繰り返す」処理である。
何回繰り返すか事前に決まっておらず、特定の条件を満たしたら終了したい場合に使う。
>''コード''
count = 1
# countが 3 以下の間、ずっと繰り返す
while count <= 3:
print(f"カウント: {count}")
count = count + 1 # 1ずつ増やす（これがないと無限ループになる。）
print("終わり！")
-結果
カウント: 1
カウント: 2
カウント: 3
終わり！
while文で条件が永遠に True のままだと、プログラムが止まらなくなる「無限ループ」が起こる。
必ず繰り返し内で条件が変化するコード（count = count + 1 など）を書くべし。
> ''繰り返しを制御する便利コマンド''
|~break|繰り返しをその場で強制終了して抜ける。|
|~continue|今回の処理を飛ばして、次の繰り返しに進む。|
>> breakの例
# （数字が 3 になったら終了）
for i in range(1, 6):
if i == 3:
print("3になったので中断します")
break
print(i)
-結果
1
2
3になったので中断します
#endregion
***リスト・多次元リスト [#uf8467dd]
|~1次元|1本の直線（例: [1, 2, 3]）|
|~2次元|平面・表（例: [[1, 2], [3, 4]]）|
|~3次元|立体・複数の表をまとめたもの（例: ビルの各階の部屋ごとのデータなど）|
#region(リスト)
''リスト''
リストは、複数のデータを1列に並べてまとめて管理する箱（配列）である。
リストの要素は0,1,2,3...と番号を振られる。
>''1次元リストの例''
numbers = [10, 20, 30]
print(numbers[0])
-結果
10
[0]なので最初の要素が現れる。
[1]の場合だと、結果は20になる。
#br
多次元リストとは、リストの中に、さらにリストが入っている構造のこと。
>''2次元リストのコード''
# 3行3列の2次元リスト（テストの点数表）
# 国語, 数学, 英語
scores = [
[80, 70, 90], # 0行目（A君の点数）
[65, 85, 75], # 1行目（B君の点数）
[90, 95, 100] # 2行目（C君の点数）
]
# B君（1行目）の数学（1列目）の点数を取り出す
print(scores[1][1]) # 結果: 85
# A君（0行目）の英語（2列目）の点数を取り出す
print(scores[0][2]) # 結果: 90
>''2次元リストと繰り返し処理（for文の入れ子）のコード''
board = [
["〇", "✕", "〇"],
["✕", "〇", "✕"],
["〇", "〇", "✕"]
]
# 行（横の並び）を取り出す
for row in board:
# 行の中の各マス目（列）を取り出す
for cell in row:
print(cell, end=" ")
print() # 改行
-結果
〇 ✕ 〇
✕ 〇 ✕
〇 〇 ✕
print(cell, end=" ")とは、改行せずに、横にスペースを挟みながら表示する為のコードである。
Pythonの print() は、通常自動的に改行される仕組みになってるが、それを変更したいときに end を使う。
#br
>''3次元リストの要素取り出し例''
cube = [
[ [1, 2], [3, 4] ],
[ [5, 6], [7, 8] ]
]
print(cube[0][1][0])
-結果
3
print(cube[0][1][0])は、この場合、
[0]で[ [1, 2], [3, 4] ]を、[1]で[3, 4]を、[0]で3を指定する。
つまりここでは、結果は3になる。
#endregion
***多重ループ [#ob814c3b]
#region(range()の使い方)
''range()の使い方''
range()は、連続した数字のリスト(連番)を自動で作ってくれる関数。
>''range(終了数)''
0から「指定した数字-1」までの連番を作る。
例えばrange(5)は「5まで」ではなく「5個の数字（0, 1, 2, 3, 4）」を作る。指定した数字自身は含まれない。
for i in range(5):
print(i, end=" ")
-結果
0 1 2 3 4
>''range(開始数, 終了数)''
始める数字を指定する。
「開始数 から 終了数 - 1 まで」
for i in range(1, 6):
print(i, end=" ")
-結果
1 2 3 4 5
>''range(開始数, 終了数, 増え幅)''
ここでは1から10-1まで、2ずつ増やして作る（奇数だけ取り出す）場合を考える。
for i in range(1, 10, 2):
print(i, end=" ")
-結果
1 3 5 7 9
増え幅に負の数を指定すると、数字を減らしていくことも出来る。
range(5, 0, -1)
#br
>''リストの中身をインデックス（番号）で処理する場合''
リストの要素を「何番目か」という番号（インデックス）を使って順番に扱いたい時、len()と組み合わせて使うのが定番。
fruits = ["りんご", "バナナ", "ぶどう"]
# len(fruits) は 3 なので、 range(3) つまり 0, 1, 2 になる
for i in range(len(fruits)):
print(f"{i + 1}番目の果物は {fruits[i]} です")
-結果
1番目の果物は りんご です
2番目の果物は バナナ です
3番目の果物は ぶどう です
#endregion
#region(多重ループ)
''多重ループ''
多重ループとは、ループ（繰り返し処理）の中に、更にループが入っている構造のことである。
繰り返し処理とは、繰り返しfor・繰り返しwhileのこと。
#br
特にループが2重になっているものを2重ループと呼び、2次元リストを出力する処理などでよく使われる。
#br
ループは外側と内側に分けられる。
内側のループが完全に終わって初めて、外側のループが次の段階に進む。
>''コード''
九九の表を作る。
# 外側のループ（1の段 〜 3の段）
for i in range(1, 4):
# 内側のループ（x 1 〜 x 3）
for j in range(1, 4):
print(f"{i * j}", end=" ")
print() # 段が終わったら改行
-結果
1 2 3
2 4 6
3 6 9
#endregion
***ソート [#vce014a5]
#region(ソート)
''ソート''
ソート(Sort)とは「バラバラに並んでいるデータを、決まりに従って順番に並べ替える処理」のこと。
>''sort()''
小さい順(昇順)に並べ替える。
numbers = [5, 2, 8, 1, 4]
numbers.sort()
print(numbers)
-結果
[1, 2, 4, 5, 8]
>''sorted()''
元のリストはそのまま残しつつ、並べ替えた新しいリストを作る。
numbers = [5, 2, 8, 1, 4]
# 新しいリストとして受け取る
new_numbers = sorted(numbers)
print(numbers) # 元のまま
print(new_numbers) # 並べ替えたもの
-結果
[5, 2, 8, 1, 4]
[1, 2, 4, 5, 8]
通常は小さい順(昇順)に出力されるが、引数に reverse=True を指定すると、大きい順(降順)になる。
numbers.sort(reverse=True)
new_numbers = sorted(numbers, reverse=True)
#br
>''文字列の並べ替え''
文字列をアルファベット順や五十音順に並び替える。
また、key引数を使うと文字列の短い順に並び替えられる。
長い順に並び替える時はsort(, reverse=True)を使う。
words1 = ["banana", "apple", "cherry"]
words2 = ["banana", "apple", "cherry"]
words1.sort()
words2.sort(key=len)
print(words1)
print(words2)
-結果
['apple', 'banana', 'cherry']
['apple', 'banana', 'cherry']
>''応用''
-文字列の並べ替え（アルファベットの逆順）
words = ["apple", "orange", "banana", "kiwi"]
sorted_words = sorted(words, reverse=True)
print(sorted_words) # ['orange', 'kiwi', 'banana', 'apple']
-文字列を1文字ずつ分解して降順(大きい順)に並べ替え
text = "python"
sorted_text = sorted(text, reverse=True)
print(sorted_text) # ['y', 't', 'p', 'o', 'n', 'h']
# 文字列に戻したい場合は "".join() だけにする。
result = "".join(sorted_text)
print(result) # "ytponh"
#endregion
***関数の定義と再帰関数・組み込み関数 [#o8937e13]
#region(関数の定義)
''関数の定義''
Pythonではオリジナルの関数を作れる。
>''関数の基本構文''
def 関数名(引数1, 引数2, ...):
# ここに実行したい処理を書く
return 戻り値
|~def|「ここから関数を定義する」という宣言|
|~関数名|関数につける名前（変数と同じく、分かりやすい名前を付ける。）|
|~&ruby(ひきすう){引数};|関数に渡す入力データ（不要なら省略可）|
|~return（返り値）|関数の処理結果として呼び出し元に返すデータ（不要なら省略可）|
#br
-例
def add(a, b):
result = a + b
return result # 計算結果を呼び出し元に返す
# 関数を実行し、戻り値を変数に受け取る
total = add(5, 3)
print(total)
#endregion
#region(再帰関数)
''再帰関数''
再帰関数とは、「関数の中で、自分自身を呼び出す関数」のこと。
>''関数の基本構文''
def 関数名(引数):
# ① ベースケース（終了条件）
if 終了条件:
return 戻り値
# ② 再帰ステップ（自分自身を呼び出す）
return 関数名(小さくした引数)
|~ベースケース（終了条件）|自分自身の呼び出しを止める条件（これがないと無限に呼び出してプログラムがクラッシュする。）|
|~再帰ステップ|問題を小さくしながら自分自身を呼び出す処理|
>''具体例''
階乗（n!）の計算を考える。
例えば、5!(5の階乗)は5×4!である。そして4!は4×3!である。
つまり、以下のようになる。
def factorial(n):
# ① ベースケース: 1 以下になったら計算を止めて 1 を返す
if n <= 1:
return 1
# ② 再帰ステップ: n * (n - 1 の階乗) nが5の場合は 5×4!
return n * factorial(n - 1)
print(factorial(5))
#endregion
#region(組み込み関数)
''組み込み関数''
組み込み関数とは、Pythonにあらかじめ標準で用意されている関数のこと。
Pythonには60種類以上の組み込み関数が存在する。
以下は特に使うものである。
|関数|役割|例|h
|print()|指定した文字や変数の内容を画面に表示します。|print("こんにちは")|
|input()|入力内容を文字列として受け取る。||
|int()|文字列を数字として受け取る。||
|float()|数字を浮動小数点として受け取る。||
|str()|数字を文字列として受け取る。||
|len()|リストの要素数や文字列の文字数を数えて返す。|print(len(要素))|
|range()|指定した範囲の連番データを自動で生成する。|for i in range(5):|
|sorted()|要素を小さい順(昇順)などに並べ替えた新しいリストを作って返す。|sorted(numbers, reverse=True)|
>''補足：要素の計算''
|~abs(数や引き算)|絶対値を返す。|
|~max(データ)|最大値を返す。|
|~min(データ)|最小値を返す。|
|~sum(データ)|合計値を計算する。|
scores = [70, 85, 90, 60, 95]
print(max(scores)) # 結果: 95 （最高点）
print(min(scores)) # 結果: 60 （最低点）
print(sum(scores)) # 結果: 400 （合計点）
score_a = 85
score_b = 92
# 引く順番を気にせず「差」を取得できる
difference = abs(score_a - score_b)
print(f"2人の点数の差は {difference} 点です。")
# 出力結果: 2人の点数の差は 7 点です。
#endregion
***計算量 [#d743ad24]
#region(計算量)
''計算量''
計算量とは「プログラムの実行にどれくらいの時間やメモリ（処理コスト）がかかるか」を表す指標のこと。
データ量が大きくなった時に、プログラムが重くならずに耐えられるかを評価・予測する為に使われる。
#br
大きく分けて2種類ある。
|~時間計算量（Time Complexity）|処理にかかる時間（ステップ数）がどれくらい増えるか|
|~空間計算量（Space Complexity）|使うメモリの量がどれくらい増えるか|
#br
入力データの量（データ数）をNとしたとき、O(N)（ビッグオー）という記号を使って大まかに表す。
厳密な処理秒数ではなく「データ数Nが増えた時に、処理時間がどう増えるか」という増え方（オーダー）に着目する。
|オーダー|名称|処理時間(目安)|h
|O(1)|定数時間|一瞬|
|O(logN)|対数時間|ほとんど増えない。|
|O(N)|線形時間|データ量に比例して増える。|
|O(NlogN)|応対数時間|O(N)より少し増えるが、実用的に非常に高速。|
|O(N2)|2乗時間|データが10倍になると処理時間は100倍になる。|
|O(2N)|指数時間|データが少し増えるだけで爆発的に重くなる。|
#endregion
***探索 [#b31d328c]
#region(探索)
''探索''
>''全探索（線形探索）''
解の候補となり得る全てを一つずつ順番に確認する。
必ず正解にたどり着くが、データ量が大きくなると処理に膨大な時間がかかる。
-リストの中から「7」があるか探索
numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 7]
for num in numbers:
if num == 7:
print("見つかりました！")
break
>''二分探索''
データがあらかじめ昇順にソート(整理)されていることが前提条件となる検索手法。
中央の値を見て、探したい値より大きいか小さいかで検索範囲を毎回半分に絞り込む。
-ソート済みのリストから「7」を探す場合
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 7
left = 0
right = len(numbers) - 1
while left <= right:
mid = (left + right) // 2 # 中央の数字
if numbers[mid] == target:
print(f"位置 {mid} で見つかりました！")
break
elif numbers[mid] < target:
left = mid + 1 # 右半分に絞り込む
else:
right = mid - 1 # 左半分に絞り込む
>''深さ優先探索（DFS）''
迷路や木構造(ツリー)において、行けるところまで進み、行き止まりになったら1つ戻って別の道を試す手法。
再帰関数やスタックを使うのが一般的。
-再帰関数を使った深さ優先探索
def dfs(node, visited):
visited.append(node) # 訪問済みにする
for next_node in graph[node]:
if next_node not in visited:
dfs(next_node, visited) # さらに奥へ進む（再帰呼び出し）
>''幅優先探索（BFS）''
開始地点から「距離が1の場所をすべて調べる→距離が2の場所をすべて調べる」というように、近い順に放射状に探索を広げていく。
キュー（先入れ先出しのリスト）を使う。
最短経路を求めたい場合に最適。最初に見つかった経路が確実に最短経路になる。
-キュー(queue)を使った幅優先探索
from collections import deque
queue = deque([start_node])
visited = {start_node}
while queue:
node = queue.popleft() # 先頭から取り出す
for next_node in graph[node]:
if next_node not in visited:
visited.add(next_node)
queue.append(next_node) # 次の探索候補に追加
#endregion
***累積和 [#g59bbd53]
#region(累積和)
''累積和''
配列などのデータの「先頭からの合計値」をあらかじめ計算して保持しておくアルゴリズム・データ構造である。
毎回sum()やfor文で計算するより楽。
>''コード''
A = [3, 1, 4, 1, 5, 9, 2]
N = len(A)
# 1. 累積和配列 S の構築 (長さ N + 1)
S = [0] * (N + 1)
for i in range(N):
S[i + 1] = S[i] + A[i]
# S は [0, 3, 4, 8, 9, 14, 23, 25] となる
# 2. 区間和を高速に求める関数 (インデックス L から R まで)
def get_range_sum(L, R):
return S[R + 1] - S[L]
# 例: インデックス 1 から 3 までの和 (A[1] + A[2] + A[3] = 1 + 4 + 1 = 6)
print(get_range_sum(1, 3)) # 出力: 6
# 例: インデックス 0 から 5 までの和
print(get_range_sum(0, 5)) # 出力: 23
#endregion
***抽象データ型 [#v5f88196]
#region(抽象データ型)
''抽象データ型''
抽象データ型(ADT=Abstract Data Type)とは、データ構造を定義する際に、
「内部でどうコード記述されているか」を切り離し、「外部からどんな操作ができるか」のみを定義した概念的なモデルのこと
|~データ型の利用者側（外部）|「どんな操作ができるか」だけを知っていればよい。|
|~データ型の提供者側（内部）|「どのようにデータを保持し、操作を実現するか」を実装する。|
#br
|ADT名|コード|操作・仕様|h
|スタック (Stack)|push(x)|データを上に追加|
|~|pop()|最後に追加したデータを取り出す。（LIFO: 後入れ先出し）|
|キュー (Queue)|enqueue(x)|データを末尾に追加|
|~|dequeue()|最も古いデータを取り出す。（FIFO: 先入れ先出し）|
|辞書/連想配列(Map)|put(key, value)|キーと値を紐づけて保存|
|~|get(key)|キーに対応する値を取得|
#endregion
***ビット演算 [#d54230ed]
#region(ビット演算)
''ビット演算''
ビット演算とは、データをコンピュータの最小単位であるビットとして直接操作する計算のこと。
通常の計算よりも処理が極めて早い。
|演算子|名称|例|仕組み|h
|&|論理積 (AND)|a & b|両方のビットが1なら1|
|||論理和 (OR)|a | b|どちらかのビットが1なら1|
|^|排他的論理和 (XOR)|a ^ b|2つのビットが異なっていれば1|
|~|反転 (NOT)|~a|ビットの0と1を反転する。|
|<<|左シフト|a << n|ビットを左にn個ずらす。（2n倍になる。）|
|>>|右シフト|a >> n|ビットを右にn個ずらす。（2nで割った商になる。）|
>''コード''
-10（二進数: 1010）と 12（二進数: 1100）を使った計算
|~左シフト(<<)|全体を左にずらし、空いた右端に0を詰める。|10 << 1|1010を左に1つずらすと、10100（20）⇨2倍になる。|
|~右シフト(>>)|全体を右にずらし、溢れた右端を捨てる。|10 >> 1|1010を右に1つずらすと、101（5）⇨2で割った商になる。|
-奇数・偶数の判定（高速化）
最下位ビットが 1 なら奇数、0 なら偶数。
余りを求める % 2 よりも早い。
n = 7
if n & 1:
print("奇数です") # 7 (0111) & 1 (0001) -> 1
else:
print("偶数です")
-ビットフラグの管理（状態のON/OFF）
複数の状態を1つの整数でまとめて管理できる。
# 各状態をビットの位置で定義
READ = 1 << 0 # 0001 (1)
WRITE = 1 << 1 # 0010 (2)
EXEC = 1 << 2 # 0100 (4)
# 権限の付与 (OR演算で追加)
permission = READ | WRITE # 0011 (3)
# 権限の確認 (AND演算でチェック)
if permission & WRITE:
print("書き込み権限があります")
if not (permission & EXEC):
print("実行権限はありません")
-フラグの反転
XOR(^)を使うと、同じ値を掛けるたびに 0 と 1（ON と OFF）が切り替わる。
state = 0
state ^= 1 # state は 1 になる
state ^= 1 # state は 0 に戻る
>''ビット全探索''
N個の要素から「選ぶ (1) / 選ばない (0)」の組み合わせ（部分集合）を、
整数データの二進数フラグ（0 〜 2^N - 1）に見立ててすべて列挙する手法である。
-コード（部分集合の全列挙）
items = ['A', 'B', 'C']
n = len(items)
# 2^n 通りのパターン（0 から 2^n - 1 まで）をループ
for i in range(1 << n):
subset = []
# 各要素（j番目のビット）が選ばれているか判定
for j in range(n):
if (i >> j) & 1: # i の j 番目のビットが 1 かどうか
subset.append(items[j])
print(f"パターン {i:2d} (二進数: {i:0{n}b}) : {subset}")
--結果
items = ['A', 'B', 'C']
n = len(items)
# 2^n 通りのパターン（0 から 2^n - 1 まで）をループ
for i in range(1 << n):
subset = []
# 各要素（j番目のビット）が選ばれているか判定
for j in range(n):
if (i >> j) & 1: # i の j 番目のビットが 1 かどうか
subset.append(items[j])
print(f"パターン {i:2d} (二進数: {i:0{n}b}) : {subset}")
#endregion
***グラフ [#pe8a3dc3]
#region(グラフ)
''グラフ''
Pythonにおけるグラフとは、点と線でデータの関係性を表したデータ構造のこと。
頂点は要素を表し、辺は要素間の関係を表す。
>''隣接リスト''
各頂点からどの頂点へ辺が伸びているかをリストや辞書で管理する。
# 辞書を使った隣接リストの例
# 1 -> [2, 3]
# 2 -> [1, 4]
# 3 -> [1, 4]
# 4 -> [2, 3]
graph = {
1: [2, 3],
2: [1, 4],
3: [1, 4],
4: [2, 3]
}
# 頂点 1 に隣接している頂点を確認する
print(graph[1]) # 出力: [2, 3]
>''隣接行列''
2次元リスト（行列）を使い、1（辺あり）と 0（辺なし）で接続を表す。
# 頂点数 4 の無向グラフの隣接行列
# 行・列ともに頂点 0~3 (実際は1~4に対応させることも多い)
matrix = [
[0, 1, 1, 0], # 頂点1からの接続 (2, 3へ接続)
[1, 0, 0, 1], # 頂点2からの接続 (1, 4へ接続)
[1, 0, 0, 1], # 頂点3からの接続 (1, 4へ接続)
[0, 1, 1, 0] # 頂点4からの接続 (2, 3へ接続)
]
# 頂点1と頂点2の間に辺があるか判定 (計算量 O(1))
print(matrix[0][1] == 1) # 出力: True
#endregion
***貪欲法 [#n4ff32ef]
#region(貪欲法)
''貪欲法''
貪欲法とは、最適化問題を解く際に、将来のことは考えず、その段階で最も最良に見える選択肢を繰り返し選んでいくという手法である。
>''硬貨でお釣りを払う場合''
620円を支払う時、その場で選べる最大の額面の硬貨から順番に貪欲に選んでいく。
（硬貨には五百円玉、百円玉、五十円玉、十円玉、五円玉、一円玉がある。）
def min_coins(amount):
# 日本の硬貨の種類（大きい順）
coins = [500, 100, 50, 10, 5, 1]
count = 0
for coin in coins:
# その硬貨で支払える枚数を貪欲に取得
num = amount // coin
count += num
amount -= coin * num # 残り金額を更新
return count
print(f"枚数: {min_coins(620)}枚") # 出力: 4枚
|>|貪欲法が使える条件|h
|~貪欲選択構造|目の前の「局所的な最適選択」を繰り返しても、全体の最適解を崩さないこと。|
|~部分構造最適性|全体の最適解が、途中の部分問題の最適解で成り立っていること。|
貪欲法で解けるか確信が持てない問題は、数学的証明（交換論法など）を行うか、失敗に備えて動的計画法を検討する。
#endregion
***動的計画法 [#jfbdc7ca]
#region(動的計画法)
''動的計画法''
動的計画法とは、大きくて複雑な問題を小さな部分問題に分割し、
その部分問題の計算結果を記録しながら再利用することで、無駄な再計算を避けて高速に解く手法である。
#br
貪欲法は局所的な最善を選んで突き進むため失敗する場合があるが、
動的計画法は過去のあらゆる状態の最小・最大コストを記録して確実に最適解を求める。
>''動的計画法の例''
フィボナッチ数列 Fn = Fn₋₁ + Fn₋₂ を求める。
単純な再帰関数で解く場合、同じ計算を何度も行ってしまうことがある。
def fib_dp(n):
if n <= 1:
return n
# 1. 計算結果を記録する配列（DPテーブル）を用意
dp = [0] * (n + 1)
dp[1] = 1
# 2. 小さい問題から順番に埋めていく（ボトムアップ処理）
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
print(fib_dp(50)) # 出力: 12586269025
#endregion
***ダイクストラ法 [#u7f39f31]
#region(ダイクストラ法)
''ダイクストラ法''
開始地点から他全ての頂点または特定のゴールまでの最短経路（最小コスト）を求める。
辺に距離や移動時間など(コスト)があるグラフに対して使える。
但しマイナスのコストがある場合、誤った計算をしてしまう。
>''段階''
+開始地点の距離を 0、それ以外の全頂点の距離を ∞（無限大）に設定する。
+「未確定の頂点リスト」を作る。
+未確定の頂点の中から、開始地点からの距離が最も小さい頂点uを選び、距離を確定とする。
+頂点uから直接行ける隣接頂点vについて、以下の比較を行う。
(開始地点から u までの距離) + (u から v へのコスト) < (現在の v の暫定距離)
+上記が成り立つ場合、より短い経路が見つかったため v の暫定距離を小さい値で上書きする。
+全ての頂点が「確定」するまで、段階3〜5を繰り返す。
最も距離が短い頂点を探す処理に優先度付きキュー（heapq）を利用すると、計算量を抑えられる。
>''コード''
import heapq
def dijkstra(graph, start, num_nodes):
# 各頂点までの最短距離を保持する配列 (初期値は無限大)
distances = [float('inf')] * (num_nodes + 1)
distances[start] = 0
# 優先度付きキュー [(距離, 頂点)]
queue = [(0, start)]
while queue:
current_dist, current_node = heapq.heappop(queue)
# キューから取り出した距離が、現在の記録より大きければスキップ (探索済み)
if current_dist > distances[current_node]:
continue
# 隣接する頂点の距離を更新
for next_node, weight in graph[current_node]:
distance = current_dist + weight
# より短い経路が見つかった場合
if distance < distances[next_node]:
distances[next_node] = distance
heapq.heappush(queue, (distance, next_node))
return distances
# --- グラフの設定 ---
# 頂点数 4 の重み付き有向グラフ
# 頂点: [行き先, コスト]
graph = {
1: [[2, 4], [3, 1]], # 1 -> 2 (コスト4), 1 -> 3 (コスト1)
2: [[4, 2]], # 2 -> 4 (コスト2)
3: [[2, 2], [4, 5]], # 3 -> 2 (コスト2), 3 -> 4 (コスト5)
4: []
}
# 頂点 1 からの最短距離を計算
result = dijkstra(graph, start=1, num_nodes=4)
for node in range(1, 5):
print(f"頂点 1 から 頂点 {node} への最短距離: {result[node]}")
-結果
頂点 1 から 頂点 1 への最短距離: 0
頂点 1 から 頂点 2 への最短距離: 3 (1 -> 3 -> 2 の順で通ると 1+2=3)
頂点 1 から 頂点 3 への最短距離: 1
頂点 1 から 頂点 4 への最短距離: 5 (1 -> 3 -> 2 -> 4 の順で通ると 1+2+2=5)
#endregion
***素集合データ構造 [#jfbdc7cc]
#region()
'' ''
#region(素集合データ構造)
''素集合データ構造''
素集合データ構造とは、互いに共通の要素を持たない「いくつかの集合」を管理するためのデータ構造である。
|~find(x)|要素 x が属する集合の親を探す。2つの要素 x, y が同じ集合にあるかは find(x) == find(y) で判定できる。|
|~union(x, y)|要素 x の集合と、要素 y の集合を1つに統合する。|
各集団を木（Tree）構造として表現する。また、各要素は親の番号を保持する。
>''コード''
class UnionFind:
def __init__(self, n):
# 各要素の親を管理 (初期状態は自分自身が親)
self.parent = list(range(n))
# 木の深さ(ランク)を管理
self.rank = [0] * n
def find(self, x):
# 自分が根でないなら、親の根を探しつつ「経路圧縮」を行う
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
# それぞれの根を取得
root_x = self.find(x)
root_y = self.find(y)
# 既に同じグループなら何もしない
if root_x == root_y:
return
# 「ランクによる併合」：低い方の木を高い方の木に繋ぐ
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
else:
self.parent[root_y] = root_x
if self.rank[root_x] == self.rank[root_y]:
self.rank[root_x] += 1
def same(self, x, y):
# 2つの要素が同じグループに属しているかチェック
return self.find(x) == self.find(y)
# --- 使い方例 ---
uf = UnionFind(6) # 0~5 の 6つの要素を用意
uf.union(0, 1)
uf.union(2, 3)
print(uf.same(0, 1)) # 出力: True (同じグループ)
print(uf.same(0, 2)) # 出力: False (別グループ)
uf.union(1, 3) # 0-1のグループと 2-3のグループを結合
print(uf.same(0, 2)) # 出力: True (1と3を介して同じグループになった)
#endregion
}}
*コメント [#comment]
#pcomment(,reply,20,)
|
