関数などのルーチンが自分自身を呼び出して実行すること。
ある種の複雑な問題を解くコードをシンプルに記述できる場合があるが、再帰による入れ子の数に応じて占有するメモリが増加する上、実行速度も効率的とは言えず、非再帰的に記述できるならそうすべきである。 再帰によって簡潔に記述できる処理の例としては「ハノイの塔」と呼ばれるゲームの解法が有名。
これは弥生 Advent Calendar 2021 の7日目の記事です。 qiita.com PosgreSQL の WITH 共通テーブル式(Common Table Expression)は一時的なテーブルを定義するもの。 サブクエリを使って SQL がネストして深くなってしまうような場合に、便利だと思う。 PostgreSQL では WITH 句で CTE を書ける。 www.postgresql.jp こんな感じで、名前をつけた式を別の式から呼ぶことができる。便利。 WITH company_names AS ( SELECT company_name AS name FROM co…
どうも!LSSです!! もう4か月も前になりますか。 【JavaScript】続・自動生成迷路 - Little Strange Software というスクリプトを書いていました。 タイトル通り、自動的に迷路を生成するスクリプトでしたが、生成して表示するだけのものでした。 で、今回はそれに「最短正解ルート」を自動的に割り出し、表示する機能をつけてみました! 自動生成迷路 最短正解ルートの割り出しアルゴリズム コード あとがき 自動生成迷路 幅: 高さ: // ax=xmax || ay=ymax?0:parseInt(mztxt.substr(ax+ay*xmax,1)); mzw=(ax,…
非同期で再帰(UWP) 自分用:メモ: 非同期で再帰(UWP)の挙動が安定しない…。 この辺か??? devlights.hatenablog.com stackoverflow.com 自分でも書いてはみたが... var buf = new BlockingCollection<IStorageItem>(); var copyDirTask = Task.Run<Task>(async () => { await this.CopyFolderAsync(s, d, buf); buf.CompleteAdding(); }); List<AbstractStorage> result1…
ハノイの塔とは 仕組み ダウンロード ハノイの塔とは ハノイの塔は三本の柱と円盤から構成される塔で、常に小さいものが上に来るようにしながら、円盤を一枚ずつ移動させ。塔を他の柱に移すというものです。 単純な仕組みでありながら、円盤の数が増えると爆発的に作業量が増えるのが特徴です。 ja.wikipedia.org この前、授業でも紹介されて、これを解くアルゴリズムがあることを知ったので視覚化してみました。 見にくいですが、とりあえず作業量がとても多いのは伝わるかと思います。 仕組み 以下のような再帰的関数で実装できます。 移動先(from)と移動元(to)に当たらない柱(other)を、再帰呼び…
07/25(月) 午後0時半起床。午後1時からMulti-Universities Campの3回目。3日連続5hでもうヘトヘト。 "蔚来杯"2022牛客暑期多校训练营3_ACM/NOIP/NOI/CCPC/ICPC算法编程基础集训_牛客竞赛OJ これまでの2セットは結構簡単だったので舐めてかかっていたらボコボコにしてやられた。チームでAJHCFDの6完。僕はCとFを書いた。 Cは01234のみからなる文字列が与えられるので、自由な順序で連結して辞書順最小にせよという問題。有名な話で、という比較関数でソートすることで達成される。しかし制約がドヤバい。文字列の数が、文字列長の総和がであった。しか…
アルゴリズムとは アルゴリズムとは、問題を解決するための手順です。 コンピュータは、アルゴリズムに従って計算をしています。アルゴリズムが非効率なものであると、どんなに性能が良いコンピュータを使っていても計算量が多くなってしまいます。 より良いアルゴリズムとは より良いアルゴリズムとは、少ない計算回数で同じ結果を得ることがアルゴリズムです。 C++のキーポイント #include <bits/stdc++.h> と using namespace std; は毎回最初に書く C++のプログラムはmain関数から始まる cout << "文字列" << endl;で文字列を出力できる // や /…
どうもこんにちは。 今回もマクロで作ったマインスイーパーのコード解説をしていきます。 どんな感じのマインスイーパーになっているかはこちらからご確認ください。 programminghajimetemita.hatenablog.com 今回は前回の記事の続きになります。 マスを開く処理のうちの、空白マスを開いたときの処理です。 前回の記事はこちらからどうぞ。 programminghajimetemita.hatenablog.com では内容に入ります。 1.コードの内容 2.マインスイーパーの挙動 3.コードの内容解説 4.特に重要なコード 5.おわりに 1.コードの内容 まずは実際に記述…
「作って学ぶコンピュータアーキテクチャ」では、執筆時点ですでに500ページを超えてしまい、泣く泣く2章分を削除しています。 そのうちの一つである、「付録1. 関数呼び出しのバリエーションと高度な機能」を無償公開しました。 github.com この章は、本当は基本的な演算や機能の実装後に挿入したかった章で、以下の範囲をカバーしています。 関数の引数の構造体渡し 可変長引数のサポート 末尾再帰呼び出しの実装 結構昔に書いた原稿を、明らかにおかしなものとか、体裁を修正しただけなので正直ちゃんとしたチェックは入っていないのですが、ディスクの肥やしにしても勿体ないので、出版社の許可を取り公開します。 …
はじめに こんにちは、情報システム部サービス開発チームの金です。 Rubyのパターンマッチ機能、皆さんは使っていますか? Ruby2.7の実験的(experimental)新機能として発表されて久しいですが、Ruby3.0では一部についてexperimentalの警告が出なくなり、その後も新構文が続々と追加されています。 RailsでもActive Modelにパターンマッチを使えるようにするPRがマージされたりと、これから使う機会が増えそうな機能です。 ...が、私はまだ使ったことがありません。 何かを覚えるには実際に手を動かすのが一番ですよね。 聞くところによると、「パターンマッチ」は「再…
SECCON beginners CTF2022に参加したので、そのことを書いていきます。 主旨 CTFを解く時、あとから振り返ると「なんでここできたんだ?」みたいになりがちで一生ワナビーみたいな気分がして悔しいので、問題を見たときに何を考えていたのか、その考えの何が間違っていたのかを記録して復習することにしました。そこでwriteupというよりは考える過程を記録して復習の材料にしたり、アンチパターンにしたいと思います(テストの訂正ノートのようなものです)。考えていたことをいちいち書き起こしているのでやや冗長になっています。なお、自分が関心のあるジャンルはreverseとpwnでこれらの問題を…
目次 目次 挨拶・作成動機 0. はじめに、君らは計算機の力を信頼しすぎている 1. 入門者は計算機の力を信頼しすぎている 2. 適当なアルゴリズムは計算機の力を信頼しすぎている 2.1 理論的に解けることと現実的に解けないこと 2.2 時間計算量・空間計算量 3. 適当なコードは計算機の力を信頼しすぎている 3.1 オーバーヘッド 3.2 メモリの理論と現実 4. まとめ 挨拶・作成動機 どうも、Prokumaです。大学院生活はだいぶ慣れました。今の所楽しい院生活です。 僕はTwitter廃人なのでよくTwitterを見ていますし、その他のSNSも見ていますが、あまりにも計算機を信頼し切って…
サブフォルダも含め配下のフォルダパス全てを返すFunction 作ってみた いや、FileSystemObject使えよ、って話なんですけどね。 Dir関数使って作ったらどうなんのかな、と思って。 ソースコードを晒す 場当たり的に作ったやつなので、だいぶ恥ずかしいのですが、晒します。 リスト1 Public Function GetFolderPathAll( _ ByVal a_FolderPath As String) As String '配下の全てのフォルダのパスを、「>」で区切った文字列にして返す。 ' Dim ret As String ret = "" '対象のフォルダがなか…
問題 大事なところだけ抜粋すると、 を個の2つの組に分ける通り数答えよ。atcoder.jp 解法 2つの組というところがミソで、うまく数え上げることができなかった。 例えば、{ (1,2), (3,4) } と{ (2,1), (3,4)} は同じになる。 これを回避するには、各要素の右端の数字が小さいように並べれば良い。 以下プロコン部のプロの引用 最も小さい値aと任意の数字b(a≠b)とでペアを作っていくことで遷移の途中で同じ結果の集合が生成されるのを回避できる みたいなのはよくあるかもしれないです 確かに、各要素に何らかの順序関係を注入するとうまくいきそうな気がする。実装は最近良く見る…
文字列操作関数集その2 LAMBDA 関数を使った数式によるユーザー定義関数(カスタム関数)として、実用的でコピペで使えるサンプルコードをまとめていきたいと思います。 使い方は以下の記事を参照してください。 www.shegolab.jp 本記事では文字列操作関連のツールとしてよく使いそうな、検索、置換、変換等の機能を主に集めました。
PHPerKaigi 2022の翌日、4/12にPHPerKaigi参加者用のDiscordで発生したやり取りをきっかけとしてPHPStan本体にコンストラクタ直接実行を検知するためのPRを出しました。 github.com PHPerKaigiは実は4日目もあった!?と感じる程の盛り上がりがPRを出すまでにあったので、その一連の流れをまとめます。 #phperkaigi #a 4日目セッションテーマ: 外部からの手動 ->__construct() コールを PHPStan 拡張を書いて滅ぼそうぜワークショップ— wip (@mpyw) 2022年4月12日 突然 #phperkaigi の…
登録日: 2022-04-15 更新日: 2022-05-01 前回、「Python」の開発で使われるIDE の「PyCharm」コードエディタをインストールして日本語化 しました。 - 残念ながら、Python の学習のために追加した「EduTools」プラグインは日本語化の対象外 でした。 英語のままでは学習が進まないので、まずは基本的なコース の「Introduction to Python」(Python の基本)を翻訳してみました。その備忘録です。 - - ホストOS : Xubuntu 20.04.4 LTS ゲストOS : Lubuntu 22.04 LTS ←(今回の作業) -…
はじめに こんにちは、BRANU開発部でバックエンドエンジニアを担当している遠藤です。 近年、面接内でコーディングテストを取り入れている企業が増えております。 その中で、ソートアルゴリズムは頻繁に質問される分野になるかと思います。 そこで今回は、簡単にではありますがソートアルゴリズムの一部についてご紹介させていただきます。 環境 Windows10 Ruby ソートの種類 バブルソート 選択ソート 挿入ソート クイックソート マージソート バブルソート 特徴 : 配列の隣合う値の大小を比較し、もし前の値が大きければ値の前後を入れ替える。 この処理を繰り返し、一番大きい値を配列の一番後ろに移動さ…
問題の概要 AWSのAmazon Timestreamというデータベースにセンサーデータを蓄積している。このデータをローカルにダウンロードして利用したい。 Pythonとboto3ライブラリを利用して、Timestreamのデータベースからそこそこ大量のデータを取得しようとしたところ、レスポンスのRowsが空だった。 データがある程度小さくなるクエリでやってみると、問題なくデータが取得できるのが確認できた。 原因 TimestreamQuety.Client.query()を呼び出す際に、MaxRowsキーワード引数を指定しないと、取得結果のサイズが1MB以上になる場合に、Rowsが空の状態で…