Python
昨日、作成した2分探索木のプログラムを使って、 最悪の場合の2分探索木と 平衡2分探索木 が作られていく様子を見ていきたいと思います。 プログラム例(r05a_ap_pm3.py) 最悪の場合 107行目以降を以下のように変更します。 関数insertを使って、1から順番に7…
令和5年度秋期 応用情報技術者試験(AP)の午後問題3は、 2分探索木(AVL木) に関する問題でした。2分探索木については、何度か出題されてますが、木の回転が出題されたのは初めてかもしれませんね。 学生時代に作った記憶がありますが、復習のつもりで取り組ん…
「Boot camp for Beginners」を完走したので、次は、「競プロ典型 90 問 - AtCoder」に取り組んでみたいと思います。 「012 - Red Painting（★4）」を幅優先探索で解いてみたのですが、TLEx9という結果となりました。解説を読んでみると、Union-Findアルゴリ…
ついにというか、ようやくというか「Boot camp for Beginners」の300問解き終わりました。 高校の教科書にPythonが掲載されたことを機にPythonを少しでも習得しようとはじめたのですが、Beginnersとはいえ最後までやり切ると気持ちがいいですね。お陰様でPyt…
以前、『アルゴリズムC〈第3巻〉グラフ・数理・トピックス』のp34で紹介されている「合併-発見アルゴリズム」をPythonで作ってみたのですが、 合併-発見(Union Find)アルゴリズム - Mae向きなブログ 「D - Friend Suggestions」を解くときに、同じグループに…
以前、「順列を求める - Mae向きなブログ」で自前で順列を求める関数を作ってみたのですが、「[C#] 順列を求める next_permutation() 代わりを実装する方法 │ Web備忘録」に順列を列挙する面白いアルゴリズムが紹介されていましたので、Pythonで作ってみまし…
イオンモール 総賃貸面積(大きさ・広さ)でランキング No. 店舗名 総賃貸面積(㎡) 1 イオンモール幕張新都心 128,000 2 mozo wondercity（モゾ ワンダーシティ） 101,000 3 イオンレイクタウンmori 99,000 4 イオンモール広島府中 98,000 5 イオンモール岡山 …
令和5年度春期 応用情報技術者試験(AP)の午後問題3は、 多倍長整数の演算(カラツバ法) に関する問題でした。 多倍長整数の加減算については、学生時代の課題で取り組んだ記憶があるのですが、乗算についてはこんな手法があるんですね。 問題を解くだけでも勉…
30個ほどのWordファイルをそれぞれPDFに変換し、ひとつのPDFファイルとして結合する必要が出てきたので、Pythonを使って自動化してみました。 事前準備として、Word文書のファイル名を00_foo.docx, 01_foo.docx, … としておきます。 word2pdf.py まず、複数…
C++を使って紹介されているパズルを、「アルゴリズム力」と「Python力」を鍛えるために、Pythonで書き換えながら読んでみました。 プログラム学習にパズルを題材にするというのは、いいですね。面白くて楽しい経験を通して、結果としてアルゴリズム力が養わ…
『パズルで鍛えるアルゴリズム力』の第3章で紹介されている「ドミノタイリング」をPythonで書いてみました。 3_4_domino_solver.py BipartiteMatchingモジュールは、「二部マッチング問題を解くためのクラス - Mae向きなブログ」で作成したものを使用。 実行…
『パズルで鍛えるアルゴリズム力』の第3章で紹介されている「二部マッチング問題を解くためのクラス」をPythonで書いてみました。 bipartite_matching.py 実行 『パズルで鍛えるアルゴリズム力』のp273 図3-62 を解いてみました。 % python bipartite_matchi…
『パズルで鍛えるアルゴリズム力』の第3章で紹介されている「編集距離」をPythonで取り組んでみました。 3_3_edit_distance_solver.py 実行 % python 3_3_edit_distance_solver.py First String: ROOF Second String: SOFT ↘︎ ↘︎ ↓ ↘︎ → 3 文字列ROOFとSOFT…
『パズルで鍛えるアルゴリズム力』の第3章で紹介されている「4x4オセロ」をPythonで取り組んでみました。 学べるアルゴリズム ネガマックス探索 α-β探索 3_2_othello_solver.py 実行 % python 3_2_othello_solver.py -10 パズルで鍛えるアルゴリズム力作者:…
『パズルで鍛えるアルゴリズム力』の第3章で紹介されている「15パズル」をPythonで取り組んでみました。 「反復深化A*」アルゴリズム、面白いですね。 3_1_15puzlle_solver.py 実行 % python 3_1_15puzlle_solver.py 15puzzle input: 1 2 3 4 5 6 0 8 9 10 7…
『パズルで鍛えるアルゴリズム力』の第2章で紹介されている「油分け算」をPythonで取り組んでみました。 2_3_oil_solver.py 実行 10L, 7L, 3Lの壺を使って、10Lの壺に入った油10Lを10Lの壺に5L, 7Lの壺に5L, 3Lの壺に0Lの状態にするには、どのような手順で行…
『パズルで鍛えるアルゴリズム力』の第2章で紹介されている「迷路」をPythonで取り組んでみました。 2_3_meiro_solver.py 実行 % python 2_3_meiro_solver.py 8 8 .#....#G .#.#.... ...#.##. #.##...# ...###.# .#.....# ...#.#.. S....... ----- solution …
『パズルで鍛えるアルゴリズム力』の第2章で紹介されている「覆面算」をPythonで取り組んでみました。 2_2_fukumen_solver.py 実行 % python 2_2_fukumen_solver.py 3 SEND MORE MONEY The num of solutions: 1 9 5 6 7 1 0 8 5 1 0 6 5 2 % python 2_2_fuku…
『パズルで鍛えるアルゴリズム力』の第1章で紹介されている「虫食算」をPythonで取り組んでみました。 1_3_mushikui_solver.py 実行 % python 1_3_mushikui_solver.py Mushikuizan Input: 2 2 *1 2* **3 *4* **** The num of solutions: 1 1 th solution: 71…
『パズルで鍛えるアルゴリズム力』の第1章で紹介されている「小町算」をPythonで取り組んでみました。 1_2_komachi_solver.py 実行 TARGETを2023とすると、1通りしかないんですね。 % python 1_2_komachi_solver.py The number of solutions: 1 1 + 2 * 3 + …
『パズルで鍛えるアルゴリズム力』の第1章で紹介されている「テンパズル」をPythonで取り組んでみました。 1_1_ten_puzzle_solver.py 実行 % python 1_1_ten_puzzle_solver.py 1 th number: 3 2 th number: 4 3 th number: 7 4 th number: 8 target number: …
勾配降下法を使ってある問題に取り組んでいたのですが、うまくいかないので簡単な数式に立ち返って試してみました。 gradient_descent.py numpyは使ってません。 実行 % python gradient_descent.py 1.3333333335464594 -0.666666666566563 0.99937896531948…
以前、Zeller(ツェラー)の公式を使うと日付の曜日を求められることを、なんとのバイブルで知ったのですが、他にもフェアフィールドの公式というものがあるんですね。 プログラミングの繰り返し文の課題でよくある問題ですが、数式で求められるというのは驚き…
Lucasの定理を用いてを求めるPythonスクリプトを作ってみました。 lucas.py 7行目は、フェルマーの小定理 より、 を用いています。(p:素数) 実行 % python lucas.py 13 3 3 1 参考 Lucasの定理とその証明 | 高校数学の美しい物語
令和5年度大学入学共通テスト 情報関係基礎の第2問は暗号に関する問題でした。 大学入試の問題にソリティア帝国とかシャッフル王国が登場することが面白いですね。 以下は、暗号化のルールですが、暗号文中での対応する文字列は、復号するときに一意に定まる…
令和5年度大学入学共通テスト 情報関係基礎の第3問は綱渡りをしながら、各ロープに巻かれているリボンに触れることで特典を獲得して、できるだけ多くの得点を競うゲームでした。 具体的には、 ゲームのキャラクターは、1本目の55m地点から始める。 キャラク…
D - Change Usernames rootから辿っていって、ループがないかチェックしています。ただし、入力例2のような場合、rootが存在しないことになるので、最後にチェックをしています。 最初、以下のような結果となり悩んだのですが、原因は、再帰の上限回数に達し…
分割数のリストを求めるスクリプトを作ってみました。partition関数自体はわずか10行足らずなのですが、昔から再帰に苦手意識があって苦労しました。 partiton.py 実行 整数6を4つの和に分割しています。 % python partition.py 6 4 [1, 1, 1, 3] [1, 1, 2, …
『アルゴリズムC〈第3巻〉グラフ・数理・トピックス』のp34で紹介されている「合併-発見アルゴリズム」をPythonで作ってみました。 「合併-発見アルゴリズム」は、以下のような用途で使われているようです。 グラフにおいて、その具体的な道を求める必要はな…
現在、「SoftBank ウインターカップ2022 令和4年度 第75回全国高等学校バスケットボール選手権大会」開催中ですが、都道府県別の優勝回数を調べてみました。 男子 都道府県 優勝回数 秋田 20 宮城 8 福岡 7 京都 4 東京 4 宮崎 2 愛知 2 福井 1 大阪 1 山形 …
