<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> をテンプレートにして作成
右端に[+]の印が付いた帯は、タップまたはクリックをすると、閲覧できます。
[
ホーム
|
リロード
|
新規
]
サイト内検索
:
[
差分チェッカー
]
[
アップローダー
]
【楽天スーパーDEAL】毎日更新・最大50%ポイントバック!!(広告)
Tweet
プログラミング入門(村上雅彦)
をテンプレートにして作成
開始行:
''■[[プログラミング入門>プログラミング入門(学科専門)]]''
#contents
|BGCOLOR(#555):COLOR(White):200|520|c
|BGCOLOR(#fc2):COLOR(Black):''分類''|''数学科選択/数学科...
|区分|[[数学科]]科目|
|履修形態|一般(人数過多の場合は抽選)|
|履修条件|二年生以上|
|単位数|2|
|講師|[[村上雅彦]]|
|学位等|学士(理学)|
*概要 [#Gaiyou]
&color(Red){「プログラミング入門」という名前の科目は複数...
[[数学科]]と[[教職課程(数学科)>教職コース/教職課程]]の...
プログラミングの基本となる条件分岐,繰り返し,配列(リス...
Pythonを用いてプログラムを作成し計算を行う。(授業では[[P...
#br
教科書は北村祐稀の『JOI公式テキスト Pythonで問題解決 情報...
必ず必要(初めの数講は[[立ち読み版>https://www.jikkyo.co....
#br
評価はLMSに毎回提出する演習の取り組み度合いでする。(100%)
対面授業に参加できない場合は対面授業の場合と同じく、設定...
CanvasLMSから演習ファイルを提出するように。
#br
困った時は[[Gemini>https://gemini.google.com/app?utm_sour...
#br
この科目は文理学部(理学)のディプロマポリシー DP3,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/materia...
[[著者のサポートサイト>https://pro-ktmr.github.io/joi-tex...
また、[[公式Youtube>https://www.youtube.com/playlist?list...
#br
//このページでは教科書がなくても問題ないように
この授業では著者が作った[[PyTry>https://pro-ktmr.github.i...
//***関数一覧 [#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"{...
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("こん...
#br
-例
|CENTER:ソースコード|CENTER:入力欄|CENTER:出力欄|h
|100|100|100|c
|a = int(input())&br;b = int(input())&br;answer = a + b&b...
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...
#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|どちらか一方でも条件を満たせば実行(または)|
>''コード''
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回目...
#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() は、通常自動的に改行される仕組みになって...
#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,...
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
>''リストの中身をインデックス(番号)で処理する場合''
リストの要素を「何番目か」という番号(インデックス)を使...
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', 'app...
-文字列を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()|指定した文字や変数の内容を画面に表示します。|pri...
|input()|入力内容を文字列として受け取る。||
|int()|文字列を数字として受け取る。||
|float()|数字を浮動小数点として受け取る。||
|str()|数字を文字列として受け取る。||
|len()|リストの要素数や文字列の文字数を数えて返す。|print...
|range()|指定した範囲の連番データを自動で生成する。|for i...
|sorted()|要素を小さい順(昇順)などに並べ替えた新しいリス...
>''補足:要素の計算''
|~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)''
迷路や木構造(ツリー)において、行けるところまで進み、行き...
再帰関数やスタックを使うのが一般的。
-再帰関数を使った深さ優先探索
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]...
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 なら奇数、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}) : {subse...
--結果
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}) : {subse...
#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から直接行ける隣接頂点vについて、以下の比較を行う。
(開始地点から u までの距離) + (u から 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_no...
return distances
# --- グラフの設定 ---
# 頂点数 4 の重み付き有向グラフ
# 頂点: [行き先, コスト]
graph = {
1: [[2, 4], [3, 1]], # 1 -> 2 (コスト4), 1 -> 3 (コ...
2: [[4, 2]], # 2 -> 4 (コスト2)
3: [[2, 2], [4, 5]], # 3 -> 2 (コスト2), 3 -> 4 (コ...
4: []
}
# 頂点 1 からの最短距離を計算
result = dijkstra(graph, start=1, num_nodes=4)
for node in range(1, 5):
print(f"頂点 1 から 頂点 {node} への最短距離: {resul...
-結果
頂点 1 から 頂点 1 への最短距離: 0
頂点 1 から 頂点 2 への最短距離: 3 (1 -> 3 -> 2 の順で...
頂点 1 から 頂点 3 への最短距離: 1
頂点 1 から 頂点 4 への最短距離: 5 (1 -> 3 -> 2 -> 4 の...
#endregion
***素集合データ構造 [#jfbdc7cc]
#region(素集合データ構造)
''素集合データ構造''
素集合データ構造とは、互いに共通の要素を持たない「いくつ...
|~find(x)|要素 x が属する集合の親を探す。2つの要素 x, 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,)
終了行:
''■[[プログラミング入門>プログラミング入門(学科専門)]]''
#contents
|BGCOLOR(#555):COLOR(White):200|520|c
|BGCOLOR(#fc2):COLOR(Black):''分類''|''数学科選択/数学科...
|区分|[[数学科]]科目|
|履修形態|一般(人数過多の場合は抽選)|
|履修条件|二年生以上|
|単位数|2|
|講師|[[村上雅彦]]|
|学位等|学士(理学)|
*概要 [#Gaiyou]
&color(Red){「プログラミング入門」という名前の科目は複数...
[[数学科]]と[[教職課程(数学科)>教職コース/教職課程]]の...
プログラミングの基本となる条件分岐,繰り返し,配列(リス...
Pythonを用いてプログラムを作成し計算を行う。(授業では[[P...
#br
教科書は北村祐稀の『JOI公式テキスト Pythonで問題解決 情報...
必ず必要(初めの数講は[[立ち読み版>https://www.jikkyo.co....
#br
評価はLMSに毎回提出する演習の取り組み度合いでする。(100%)
対面授業に参加できない場合は対面授業の場合と同じく、設定...
CanvasLMSから演習ファイルを提出するように。
#br
困った時は[[Gemini>https://gemini.google.com/app?utm_sour...
#br
この科目は文理学部(理学)のディプロマポリシー DP3,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/materia...
[[著者のサポートサイト>https://pro-ktmr.github.io/joi-tex...
また、[[公式Youtube>https://www.youtube.com/playlist?list...
#br
//このページでは教科書がなくても問題ないように
この授業では著者が作った[[PyTry>https://pro-ktmr.github.i...
//***関数一覧 [#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"{...
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("こん...
#br
-例
|CENTER:ソースコード|CENTER:入力欄|CENTER:出力欄|h
|100|100|100|c
|a = int(input())&br;b = int(input())&br;answer = a + b&b...
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...
#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|どちらか一方でも条件を満たせば実行(または)|
>''コード''
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回目...
#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() は、通常自動的に改行される仕組みになって...
#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,...
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
>''リストの中身をインデックス(番号)で処理する場合''
リストの要素を「何番目か」という番号(インデックス)を使...
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', 'app...
-文字列を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()|指定した文字や変数の内容を画面に表示します。|pri...
|input()|入力内容を文字列として受け取る。||
|int()|文字列を数字として受け取る。||
|float()|数字を浮動小数点として受け取る。||
|str()|数字を文字列として受け取る。||
|len()|リストの要素数や文字列の文字数を数えて返す。|print...
|range()|指定した範囲の連番データを自動で生成する。|for i...
|sorted()|要素を小さい順(昇順)などに並べ替えた新しいリス...
>''補足:要素の計算''
|~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)''
迷路や木構造(ツリー)において、行けるところまで進み、行き...
再帰関数やスタックを使うのが一般的。
-再帰関数を使った深さ優先探索
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]...
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 なら奇数、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}) : {subse...
--結果
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}) : {subse...
#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から直接行ける隣接頂点vについて、以下の比較を行う。
(開始地点から u までの距離) + (u から 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_no...
return distances
# --- グラフの設定 ---
# 頂点数 4 の重み付き有向グラフ
# 頂点: [行き先, コスト]
graph = {
1: [[2, 4], [3, 1]], # 1 -> 2 (コスト4), 1 -> 3 (コ...
2: [[4, 2]], # 2 -> 4 (コスト2)
3: [[2, 2], [4, 5]], # 3 -> 2 (コスト2), 3 -> 4 (コ...
4: []
}
# 頂点 1 からの最短距離を計算
result = dijkstra(graph, start=1, num_nodes=4)
for node in range(1, 5):
print(f"頂点 1 から 頂点 {node} への最短距離: {resul...
-結果
頂点 1 から 頂点 1 への最短距離: 0
頂点 1 から 頂点 2 への最短距離: 3 (1 -> 3 -> 2 の順で...
頂点 1 から 頂点 3 への最短距離: 1
頂点 1 から 頂点 4 への最短距離: 5 (1 -> 3 -> 2 -> 4 の...
#endregion
***素集合データ構造 [#jfbdc7cc]
#region(素集合データ構造)
''素集合データ構造''
素集合データ構造とは、互いに共通の要素を持たない「いくつ...
|~find(x)|要素 x が属する集合の親を探す。2つの要素 x, 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,)
ページ名: