時は 2020 年 5 月 3 日。 ここ最近、AtCoder では、「再帰関数を用いた DFS な全探索」というタイプの問題が激増しています！！！ AtCoder ABC 165 C - Many Requirements (昨日のやつ) AtCoder ABC 114 C - 755 AtCoder ABC 119 C - Synthetic Kadomatsu AtCoder ABC 161 D - Lunlun Number パナソニックプログラミングコンテスト D - String Equivalence これらの多くは緑後半から水色前半の difficulty を叩き出す、とても恐れられている問題たちです。しかし実のところ、「ちょっと複雑だけど、単純に全探索するだけ」という側面もあります。 これらの出題が最近急増しているのは、おそらくは AtCoder 社側に 最近の AtCo
StartupStockPhotosによるPixabayからの画像 こんにちは。倉内です。 プログラミング問題には、計算問題だけでなく配列や文字列を操作したり、図形から法則を見つけたりといろいろなものがあります。その中でも「関数を定義して処理を書くのは苦手だな…」と感じている方は多いのではないでしょうか。 私もまさにそのひとりで、基本は学んだものの使いこなせていません…。そこで今回は、さまざまな問題を集めた「レベルアップ問題集」の中から再帰関数を使って解く問題に挑戦しようと思います！ 今回はスマートな解き方や綺麗なコードを書くというよりは、プログラミング初心者でもこういう方針を立てて、こう考えてみたら解けるかもということを重視して解いていきます。 プログラミング学習を始めたばかりの初心者の方もぜひ参考にしてみてください。 レベルアップ問題集「山折り谷折り」をPythonで解く paizaで
0. はじめに bit 全探索は、世の中で「AtCoder 温室育ちだと弱い」と言われるタイプの問題の代表かもしれません。何も考えずに思考停止して全探索すればよいのですが、ちょっと実装が重たい傾向にあって、書き切るのが大変という感じです。difficulty を見ても ABC-C の中でも高めの傾向です。 ABC 147 C - HonestOrUnkind2 (972) ABC 128 C - Switches (728) ABC 119 C - Synthetic Kadomatsu (1306) ABC 104 C - All Green (1396) bit 全探索の考え方や実装は、以下の記事にまとめてみました。 drken1215.hatenablog.com しかし、全探索アルゴリズムにおいて、より汎用的な方法として再帰関数を用いるというのがあります。むしろ、再帰関数を自在に書
エンジニアに転職して早2年半。いまだに再帰関数が苦手です。 再帰関数を含むコードレビューがあると「よく分からんけど、動作も良いしテストも書かれてるしヨシ！！approved!!」としてしまったことも...（絶対あかん😇）。 さすがにそれはヤバイと、再帰関数を学び直したのでその結果をまとめてみました。 再帰関数とは？ 再帰関数とは、関数内で、自分自身を呼び出す関数です。 この時点で謎ですよね。最初にみたときは「無限ループでは？」って思いました。 以下再帰関数の例として度々あげられる階乗の計算です。 const factorial = (n: number): number => { if (n < 2) { return 1; } return n * factorial(n - 1); }; test('factorial' => { expect(factorial(0)).toBe(
諸般の理由で『Pythonのlambda式を用いたラムダ計算の基礎表現』を書いた後にHaskellに触れたところ，無名再帰関数を実行する不動点コンビネータfixがとんでもなく簡単に書けたため，同じ方法で他のプログラミング言語でもできないか試したところ，これまたあっさりできたので，まとめメモ的に新しく記事にした． このような内容がQiitaや書籍，ネット上に星の数の更に星の数乗ほどあることは承知しているが，この手の話はYコンビネータが大きな割合を占めており（実際，元記事でも取り上げている），関心のある人々の数多ある参考資料のひとつ程度に捉えてもらえると幸いである．ツッコミ，編集リクエスト歓迎． 不動点コンビネータの定義 不動点コンビネータとは，$f(g(f))=g(f)$が成り立つ関数$g$を指す．この記事では，Haskellの呼称であるfixを不動点コンビネータの関数名とする． Haske
先日面白い記事を読んだ。The Y combinator in Go with generics である。 一番最初目に入ってきたのは難解なジェネリクスのコードである。 type Func[T, U any] func(T) U type TagFunc[T, U any] func(Func[T, U]) Func[T, U] type CombinatorFunc[T, U any] func(CombinatorFunc[T, U]) Func[T, U] func Y[T, U any](f TagFunc[T, U]) Func[T, U] { return func(self CombinatorFunc[T, U]) Func[T, U] { return f(func(n T) U { return self(self)(n) }) }(func(self Combinat
必要な知識 JavaScript の基本的な構文、関数、プロパティ、配列 イントロ 例えば「JavaScript で Web ページ上に <a> 要素が何個あるか数えろ」と言われたら、どのようなコードを書くだろうか？もちろん getElementsByTagName() などを使えば簡単だが、それらを使わずに自分で DOM ツリー上を探索して数えるアルゴリズムを実装するとしたら、どうするだろうか？ DOM ツリーというのがどういうものかわからない人も、構造自体はシンプルなので調べてみてほしい。<div> や <a> といったものは要素といい、要素の中にさらに別の要素(子供要素 / child element)がいくつか含まれたり含まれなかったりする。 このような問題は、再帰関数を使えば簡潔かつ直感的なコードで表現することができる。この記事では JavaScript を用いて説明するが、同じ
はじめに Python 組合せ列挙などと検索すると、標準ライブラリitertoolsのpermutationsやcombinationsを使って実装している記事が多くでてきます。 しかしそんなものは甘えに過ぎません、$Pythonista$たるもの標準ライブラリくらい一度は自力で実装しておきたいものです。 ※ライブラリの利用を否定しているわけではありません。 ※むしろ、自力で実装するよりはライブラリの方が高速でしょうから、実際に運用するときは大人しくitertools使いましょう。 対象読者 「じゃあpermutations / combinationsの中身はどうなってるの？」と思ってるそこのあなた いざ実装 再帰関数って？？ すごくわかりやすい記事があるのでそちらを参照してください。 再帰関数を学ぶと、どんな世界が広がるか 順列(Permutations) itertools.perm
エンジニアに転職して早2年半。いまだに再帰関数が苦手です。 再帰関数を含むコードレビューがあると「よく分からんけど、動作も良いしテストも書かれてるしヨシ！！approved!!」としてしまったことも...（絶対あかん😇）。 さすがにそれはヤバイと、再帰関数を学び直したのでその結果をまとめてみました。 再帰関数とは？ 再帰関数とは、関数内で、自分自身を呼び出す関数です。 この時点で謎ですよね。最初にみたときは「無限ループでは？」って思いました。 以下再帰関数の例として度々あげられる階乗の計算です。 const factorial = (n: number): number => { if (n < 2) { return 1; } return n * factorial(n - 1); }; test('factorial' => { expect(factorial(0)).toBe(
たまに、関数内部で自身を呼び出すような関数に出会う機会があるかと思います。 それは再帰関数と呼ばれ、自分自身を内部で呼び出すことによってループのように振る舞います。 そんな再帰関数を書くときの個人的なポイントを整理してみました。 再帰関数について 再帰関数は、自分自身を呼び出す関数のことを指します。 自分自身を呼び出す事によってある種のループのように振る舞います。 いくつかのアルゴリズムでは再帰を使うことによってシンプルにかける場合があると個人的には思っています。 具体例（フィボナッチ数列） 以下は再帰を用いてN番目のフィボナッチ数列を生成する関数です。 フィボナッチ数列は1, 1, 2, 3, 5, 8...のような２個づつ数字を足していくような数列です。 フィボナッチ数列（再帰） def fibonacci_recursive(n): # ここが終了条件になる if n == 1 or
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
よくやる再帰関数の書き方 〜 n 重 for 文を機械的に 〜 - けんちょんの競プロ精進記録
【Python】再帰関数を使ったプログラミング問題の解き方を解説する - paiza times
bit 全探索を「再帰関数」で書く 2 つの流儀 - けんちょんの競プロ精進記録
再帰関数が苦手なエンジニアのための再帰関数入門 - Qiita
不動点コンビネータを用いた無名再帰関数の実行まとめ - Qiita
Go Generics で実装する Y コンビネータ、再帰関数を汎用的にメモ化する - アルパカの徒然文
自分自身を呼び出す関数=再帰関数をできるだけ分かりやすく解説する【初心者向け】 - Qiita
Pythonで順列・組合せを列挙する(再帰関数) - Qiita
再帰関数が苦手なエンジニアのための再帰関数入門 - Qiita
個人的な再帰関数を書くときのポイント | DevelopersIO