19
票
longの飽和演算を行うアルゴリズムを教えてください
C# .NETということですが、Visual C++にはSafeIntライブラリというものが用意されています。これはura14hさんの書かれているように、演算結果が飽和するかどうかをチェックしながら演算を進めてくれるテンプレートライブラリです。
このアイデアをC#で飽和加算として表現するならこのような感じでしょうか。
static long Addition(long lhs, long rhs)...
- 4.1万
18
票
Accepted
vectorとlistどのように使い分けますか
大抵のケースでは vector<T> 利用で十分かと思います。(Tは要素の型)
Scott Meyers, "Effective STL" でも、Item 1で次の言及があります
vector is the type of sequence that should be used by default.
list<T> の方が好ましいのは、...
- 9,824
17
票
Accepted
暗号に使える乱数と使えない乱数
まず重要なポイントとして、擬似乱数のシードとなる真の乱数 (質問の場合は円周率のほうではN, 漸化式の方ではM) は十分に広い空間からランダムに選ばれなくてはなりません。
どんな擬似乱数生成器を使っていたとしてもシードが高々1億程度では総当たりで(比較的)簡単にシードがみつかってしまい生成される乱数が再現できてしまいます。
円周率の先頭100万桁のどこかから選ぶなどは問題外です。
シードはRSA/...
- 756
15
票
Accepted
Git の 3-way merge とは具体的にどのようなアルゴリズムですか?
「way」とは
ここでの「way」とは、マージする際に "見て" いる場所のこと。3-way merge は 3 つの場所を見ている。
2-way merge:「マージの起点コミット」「マージさせたいコミット」を見てマージする
3-way merge:「マージの起点コミット」「マージさせたいコミット」「2 つのコミットの最近共通祖先となるコミット」を見てマージする
...
- 2.2万
14
票
CRC32とMD5の使い分け
CRC は巡回冗長検査
- ハードウエアで実装が容易
- 計算結果が小さい (CRC-32 なら 32bit)
- 逆方向演算を困難にするようには設計されていない
- 伝送誤りの検出に向く
- 改ざんの検出には向かない
- 計算方法 (計算式) がいっぱいある (標準化されてない)
(暗号論的)単方向ハッシュ (MD5 は古いので SHA 推奨)
- 計算量が多い(ハードウエア実装には向かない)
...
- 2.1万
13
票
ログインシステムのためのパスワードのハッシュ方式、互換性、照合方法について
(suzukisさんの回答への補足です)
パスワードハッシュにSHA256などのメッセージダイジェストハッシュを使うことは推奨されません。 パスワードハッシュ用のアルゴリズムが開発されているので、それを使いましょう。
まずは結論から
現時点でベストとされているのはArgon2です。パスワードハッシュアルゴリズムの優劣を競うコンペで2015年に最良と判断されました。ただ、比較的新しいので、...
- 4,298
12
票
Accepted
円周率の99901桁から100000桁までを簡単に求めるには?
「99900桁目までを直接計算することなく、99901桁目からの100桁を得たい」という意図と解釈しました。現在、10進数でそのようなことをする方法は知られていないと思います。
16進数でしたら、n桁目までを飛ばしてそれ以降を直接計算する方法が知られています。Bailey–Borwein–Plouffe formulaを使います。具体的な手順は以下のページの中程に出ています。
https://...
- 4,298
12
票
ログインシステムのためのパスワードのハッシュ方式、互換性、照合方法について
ハッシュアルゴリズムを切り替える方法
DBのユーザー情報を保存しているテーブルにハッシュアルゴリズムを保存するカラムを追加します。すべてのユーザーに旧アルゴリズムを表す値を入れておくか、NULであれば旧アルゴリズムと見なす、とします。
ユーザー認証時は、このカラムの値を見てアルゴリズムを選択します。
パスワード変更時は新アルゴリズムを用いてハッシュ値を計算し、...
- 1.2万
12
票
Accepted
クイックソートの2種類の実装法で実行速度に顕著な違いが出る
クイックソートでは(ほぼ)ソート済みの配列や同一要素の配列に対して平均的なO(N log N)ではなくO(N^2)のワーストケースになります。
VCやMinGWではRAND_MAXが0x7fffしかないため10000000要素の配列では305個程度同じ値があり、性能の劣化が起こります。
void randomize(vector<int> &arr) {
std::...
- 2,024
11
票
完全二分木は森に分類されますか?
Wikipediaによれば、木と森の定義は以下の通りです。
木: 連結で閉路を持たない無向グラフ
森: 閉路を持たない無向グラフ
森の特殊な形が木なので、すべての木は森です。完全二分木も、もちろん森です。
いくつか例を挙げます。xが節で-と|が枝だと思ってください。
x---x
|
x---x---x
|
x---x
これは木であり、森でもあります。
...
- 4,083
9
票
Accepted
初速・最終速度・移動時間・移動距離が決まっている状況で、速度をスムーズに変化させる
「スムース」の条件は何ですか? 単に「速度が連続であれば良い」なら折れ線で良いので比較的簡単です。
下図において、影の面積が距離Dになります。
Va <= Vb, T・Va <= D <= T・Vb もしくは Va > Vb, T・Va >= D >= T・Vb の場合は、
D = T・Va + T1・(Vb - Va)/2 + (T - T1)・(Vb - Va) ...
- 4,298
9
票
Accepted
2部グラフ(V1, V2, E)で、V2からいくつか頂点を削除し、すべてのv∈V1が、1本のみの枝をもつようにするには?
グラフを、対応する論理式に落とし込んで変形していくことにより解けそうです。
考え方
まず、v1,i ∈ V1 と v2,j ∈ V2 がどう繋っているか、表にしてみます。
質問で例示されたグラフでは以下のようになります。o の印があるところが辺で繋がっている組み合わせです。添字 i, j は、図の一番上を1として順番に振りました。
V2
...
- 2,338
9
票
使用頻度を計算するには?
一般的というのは、存在しません。
hosiさんが欲しいと思っている使用頻度だけがhosiさんの正しい使用頻度であって、他の見知らぬ人々(一般)が欲しがるものに惑わされる事は不毛だと思います。
「過去に良く使用されていたものが上位に表示されるのは問題がある」という事であれば、
a) 直近1年とか、直近1か月とかを調査対象期間にする、
b) (使用回数/アプリが提供されていた期間)で頻度を求める
...
- 4,235
9
票
長方形と円の衝突判定を行うコードを教えて下さい
言語の指定がないので、アルゴリズムだけ示します。
下記の図で細かい説明を省いて結論だけ言うと、長方形(赤)の外側に引いた水色の実線の中に、円の中心 P1 が入った際には衝突したとみなせます。水色の線は、長方形の外縁から r の距離に相当します。そのため角を除く部分は長方形に並行に、角の部分は半径 r の円の 1/4 となっています。
あとはこの水色の実線内に入ったかどうかの判定ですが、...
- 5,122
9
票
Accepted
データ構造とアルゴリズムは実務ではどんなシーンで役立つのか?
巨大なシステムでは重要≒普通のシステムでは知らなくてよい、とお考えのようですがとんでもない話です。資源の少ないマイコンでは RAM も貴重 ROM も貴重、電池も貴重で、最適なアルゴリズムやデータ構造を使わないと1つ1つの処理に余計な時間がかかります。電池機器(まあ端的にはスマホっすけど)では無駄な処理は一切許されません。ほぼ同じような処理をして A 社のスマホは電池が10時間保つけど B ...
- 2.1万
8
票
Accepted
教師あり学習と教師なし学習の違いは何ですか?
概念的に言うと、
教師あり学習: 人間等が付けたラベルによって、教えられた構造を学び取る
教師なし学習: データから規則性を発見して学び取る
という違いになると思います。
もう少し具体的に、0から9までの数字1文字が書かれた画像が沢山あるとしましょう。
この画像一枚一枚に、0から9までのどの数字が書かれているのかというラベルを人間が付けて、それを学習するのが教師あり学習です。
...
- 492
8
票
vectorとlistどのように使い分けますか
listで表現するのが適切なアルゴリズムやプログラムは数多く存在します。
むしろ、vectorの方が使う場面を選ぶかと。
vectorの最大の利点はメモリ消費量ではなく、アクセス速度です。
動的にサイズが変更できるのに、メモリ上は連続した領域となっている為にランダムアクセス可能というのがvectorの利点です。
欠点はサイズ変更や削除を行う際に巨大なコピーコストがかかる部分です。...
- 312
8
票
Accepted
高橋の数の算出について
ある数について、それぞれ高橋の数か? と判定していくのではなく、各桁について、ある数が何回出現したかという出現数の組から、その組は高橋の数を構成できるか、という判定をしていけば、かなり数を減らせます。
この方法なら、完全に力技で判定しても、n桁での組み合わせは、C(9 + n, 9) 通り。9桁なら 48,620 通りしかありません。
判定の手順は以下の通り。
...
- 2,338
8
票
ブール代数?による掛け算
掛け算(乗算)は足し算(加算)が必要になるので、まず加算の実現方法から考え、次に乗算に進みます。
加算
1ビットの加算
1ビット同士の加算は、繰り上がりを無視すれば排他的論理和です。
0 ⊕ 0 = 0
1 ⊕ 0 = 1
0 ⊕ 1 = 1
1 ⊕ 1 = 0
2ビットの加算
次に2ビット同士(3ビット目への繰り上がりは無視)です。
これには、...
- 632
8
票
Accepted
組み合わせ計算で 64C32 の結果がオーバーフロー
オーバーフローが起こっているのはこの計算をするときです。
(n - r + 1) * combi(n, r - 1) / r
たとえば combi(64, 32) の呼び出しでは以下の計算をすることになりますが、
33 * combi(64, 31) / 32
₆₄C₃₁ = 1,777,090,076,065,542,336 なので、これに 33 を掛けると 2⁶⁴ - 1 = 9,...
- 2.2万
7
票
16×16や25×25の数独を計算量を抑えて作成したい
あたりをつけて、簡単な検証しかしてませんので参考までに…
手順は
基本形の生成
シャッフルする
です。
は、
python ですが、以下のコードで
水平方向昇順なシンプルな数独が生成できます。
def create(num=3):
num2 = num * num
g = [[0]*num2 for i in range(num2)]
for y in ...
- 71
7
票
秘書選び問題での見送る数の決め方
応募者の数が n 人で十分大きな数の場合
見送る人数を (n / e) にすると最善の秘書を雇える確率が最大となる。
その確率は 1 / e である。
というのが、秘書選び問題(秘書問題)の解です。
ここで使われている e は、ネイピア数、オイラー数、自然対数の底などと呼ばれていて、その値は 2.718281828459045...(以下略)です。
e は、円周率と同様、無理数なので、...
- 4,235
7
票
Judy arrayとは何ですか?
簡単に言えば、「CPUのキャッシュ効率を重視した木構造」です。
質問は、機能としてのレイヤと実装としてのレイヤが混ざっているようなので、分けて説明します。
機能レイヤ
キーを与えられて、それに関連付けられた値を取り出せるデータ構造は一般的にマップと呼びます。マップには様々な実装があり得ます。単に機能としての「マップ」の話をしている場合は、操作(値の検索、挿入、削除等)...
- 4,298
7
票
既にある平均値を更新し続けるアルゴリズムを教えてください。
と置いたとき, の平均 は
と書けます. を漸化式の形で書くと
となり, これより を と を用いて
と書けます.
この方式では と だけ保持しておけばよく, を計算して を復元する処理が不要になります.
分散は
と定義されますが, これを式変形して
と書けます. 先程と同様
の漸化式
を考え, を逐次計算しやすい形で書くと
となります. 分散の場合は ...
- 374
7
票
初速・最終速度・移動時間・移動距離が決まっている状況で、速度をスムーズに変化させる
与えられた条件で速度もなめらかに変化させたい場合、位置を3次関数で表すのが簡単だと思います。
すなわち時刻tにおける位置(初期位置からの距離)をp(t)、速度をv(t)とすると
p(t) = At3 + Bt2 + Ct ・・・(1)
(1)を微分して
v(t) = 3At2 + 2Bt + C ・・・(2)
(1)(2)に条件を当てはめれば係数A、B、Cを求めることができます。...
- 1,297
7
票
Accepted
連続する整数値の中に「7」がいくつ出現するか数えるプログラムの高速化
ものごとは分けて考えましょう。
「1からnまでの連続する整数値」のうち(以下A)、1の位には 7 はいくつでてくるでしょうか? n が 10 以上ならば、少なくとも int(n / 10) 回はでてきますよね? さらに n % 10 が 7 以上であれば、それに +1 回加えて登場するはずです。つまり n = 30 までなら 7, 17, 27 の 3回ですが、n = 37 ならば前の 3 つに ...
- 5,122
7
票
Accepted
プログラミングCの再帰に関しての質問です。
max() がどういう動作をするか、頭から追いかけていけば、原因が分かります。
max() が最初に呼び出されると、
変数 i が作成される
変数 result が作成され、0 に初期化される。
scanf で自然数が i に読み込まれる。 ここでユーザは 5 を入力したと仮定します。つまり i は 5 になります。
i と result, つまり 5 と 0 を比べるので、最初の if ...
- 5,003
7
票
Accepted
C++での自己参照構造体におけるポインタにおいて
すでにあるコメントだけで十分だと言う気もしますが。
struct MyStruct {
int a;
int b;
}
なんて宣言があると、コンパイラはMyStruct型に「int2個分」の領域を割り当てます。
struct AnotherStruct {
int key;
MyStruct subStruct;
}
だと、...
- 1.9万
7
票
私の作った乱数はストリーム暗号に使えますか?
乱数や暗号は自前で考えるとたいてい穴があるものしかできないので、既成のものを使われるほうがよいです。
勉強したいのであれば、入門書としてまず「暗号技術入門(ISBN 4797382228)」を読んでみてはいかがでしょうか
具体的な欠陥を1つ示しておきます。
a==a[Z]になると、a^a[Z]は0となります。以後生成される数列は0となります。^a==a[Z]となっても同様です。
...
- 1.2万
6
票
Accepted
数式処理を行える理由
コンピュータでは数値を扱わなければ答えを得ることができません...
計算機は数値を扱うものというよりは、論理計算ができるものと捉えたほうがより本質的かと考えます。
代数演算や微分積分というのは代数式を記号列としてとらえ記号列を他の列へ一定の規則に従い変換するものです。こういったもの(記号処理)も論理計算として定式化できるので計算機で解く事ができます。
- 336
Only top scored, non community-wiki answers of a minimum length are eligible