[過去ﾛｸﾞ] Qiita 4 - キータぞ、来たぞ、キータだぞー (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞

---

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ

---

645(3): デフォルトの名無しさん [sage] 2024/04/05(金) 14:29:35.27 ID:2MlUL2HB(1) AAS
>>614
香ばしい人物なので他の記事も見てみた。

【終了コード9】ABC079 B - Lucas Number のTLE問題（C++, 配列と再帰関数の処理速度の違い）
https://qiita.com/yaburen/items/c8e7b0c1c581db441e34

> 色々調べた結果、再帰関数はループよりは早いものの、配列に1つずつ要素をメモしておく処理よりは数倍遅いことがわかりました。

> 再帰が深くなればなるほどスタックに多数のフレームが重なり、スタックオーバーヘッドが起こるリスクも高くなります。

「再帰関数はループよりは早い」
「スタックオーバーヘッド」

CSのごく初歩的なところすっとばして42tokyo逝って糞コーダ目指してるとしか思えんのだけど、東大出てこれってひたすら残念な気持ちになるわあ。

---

646: デフォルトの名無しさん [sage] 2024/04/05(金) 16:40:21.55 ID:HTgg0oMm(1) AAS
>>645
> 東大出てこれって

阪大→東大院 だそうなので
https://twitter.com/yaburen_AI
東大出てはなさげ
https://twitter.com/thejimwatkins

---

651: デフォルトの名無しさん [sage] 2024/04/06(土) 02:26:41.43 ID:3rTic3uQ(1) AAS
>>622
マルウェア界隈と最適化方面はアセンブラ知識あると良さそうだが

>>645
過去に見た例から再帰使う辺り、記憶力はいいが考えてねえよなあ

>>648
そもそもstrlenはsize_tでconst char*だしなあ

---

655: デフォルトの名無しさん [] 2024/04/06(土) 13:40:30.85 ID:igk81eVf(1) AAS
>>645
TLEになったという再帰版のコード、関数ft_lucasの型がintになってて引数Nの型がint64_tになってるけど

int ft_lucas(int64_t N)

問題の制約で引数Nの上限は86なのでint64_tにする必要ないし、答えは10**18より小さいということだからintじゃ足りないんだよなあ。
TLE以前にバグってるんだわ。よくこんなコード晒せるなあ。

つかこいつメモ化も知らんのな。

int64_t ft_lucas(int N)
{
　　static int64_t memo[86 + 1] = {2, 1};
　　if (memo[N] == 0) {
　　　　memo[N] = ft_lucas(N - 1) + ft_lucas(N - 2);
　　}
　　return memo[N];
}
https://wandbox.org/permlink/gVDItXL2jf2PNsNd

---

上下前次1-新書関写板覧索設栞歴

---

ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

ぬこの手 ぬこTOP 1.570s*