19
票
longの飽和演算を行うアルゴリズムを教えてください
C# .NETということですが、Visual C++にはSafeIntライブラリというものが用意されています。これはura14hさんの書かれているように、演算結果が飽和するかどうかをチェックしながら演算を進めてくれるテンプレートライブラリです。
このアイデアをC#で飽和加算として表現するならこのような感じでしょうか。
static long Addition(long lhs, long rhs)...
15
票
Accepted
Git の 3-way merge とは具体的にどのようなアルゴリズムですか?
「way」とは
ここでの「way」とは、マージする際に "見て" いる場所のこと。3-way merge は 3 つの場所を見ている。
2-way merge:「マージの起点コミット」「マージさせたいコミット」を見てマージする
3-way merge:「マージの起点コミット」「マージさせたいコミット」「2 つのコミットの最近共通祖先となるコミット」を見てマージする
...
14
票
CRC32とMD5の使い分け
CRC は巡回冗長検査
- ハードウエアで実装が容易
- 計算結果が小さい (CRC-32 なら 32bit)
- 逆方向演算を困難にするようには設計されていない
- 伝送誤りの検出に向く
- 改ざんの検出には向かない
- 計算方法 (計算式) がいっぱいある (標準化されてない)
(暗号論的)単方向ハッシュ (MD5 は古いので SHA 推奨)
- 計算量が多い(ハードウエア実装には向かない)
...
13
票
ログインシステムのためのパスワードのハッシュ方式、互換性、照合方法について
(suzukisさんの回答への補足です)
パスワードハッシュにSHA256などのメッセージダイジェストハッシュを使うことは推奨されません。 パスワードハッシュ用のアルゴリズムが開発されているので、それを使いましょう。
まずは結論から
現時点でベストとされているのはArgon2です。パスワードハッシュアルゴリズムの優劣を競うコンペで2015年に最良と判断されました。ただ、比較的新しいので、...
12
票
Accepted
円周率の99901桁から100000桁までを簡単に求めるには?
「99900桁目までを直接計算することなく、99901桁目からの100桁を得たい」という意図と解釈しました。現在、10進数でそのようなことをする方法は知られていないと思います。
16進数でしたら、n桁目までを飛ばしてそれ以降を直接計算する方法が知られています。Bailey–Borwein–Plouffe formulaを使います。具体的な手順は以下のページの中程に出ています。
https://...
12
票
ログインシステムのためのパスワードのハッシュ方式、互換性、照合方法について
ハッシュアルゴリズムを切り替える方法
DBのユーザー情報を保存しているテーブルにハッシュアルゴリズムを保存するカラムを追加します。すべてのユーザーに旧アルゴリズムを表す値を入れておくか、NULであれば旧アルゴリズムと見なす、とします。
ユーザー認証時は、このカラムの値を見てアルゴリズムを選択します。
パスワード変更時は新アルゴリズムを用いてハッシュ値を計算し、...
12
票
Accepted
クイックソートの2種類の実装法で実行速度に顕著な違いが出る
クイックソートでは(ほぼ)ソート済みの配列や同一要素の配列に対して平均的なO(N log N)ではなくO(N^2)のワーストケースになります。
VCやMinGWではRAND_MAXが0x7fffしかないため10000000要素の配列では305個程度同じ値があり、性能の劣化が起こります。
void randomize(vector<int> &arr) {
std::...
11
票
完全二分木は森に分類されますか?
Wikipediaによれば、木と森の定義は以下の通りです。
木: 連結で閉路を持たない無向グラフ
森: 閉路を持たない無向グラフ
森の特殊な形が木なので、すべての木は森です。完全二分木も、もちろん森です。
いくつか例を挙げます。xが節で-と|が枝だと思ってください。
x---x
|
x---x---x
|
x---x
これは木であり、森でもあります。
...
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) ...
9
票
Accepted
2部グラフ(V1, V2, E)で、V2からいくつか頂点を削除し、すべてのv∈V1が、1本のみの枝をもつようにするには?
グラフを、対応する論理式に落とし込んで変形していくことにより解けそうです。
考え方
まず、v1,i ∈ V1 と v2,j ∈ V2 がどう繋っているか、表にしてみます。
質問で例示されたグラフでは以下のようになります。o の印があるところが辺で繋がっている組み合わせです。添字 i, j は、図の一番上を1として順番に振りました。
V2
...
9
票
使用頻度を計算するには?
一般的というのは、存在しません。
hosiさんが欲しいと思っている使用頻度だけがhosiさんの正しい使用頻度であって、他の見知らぬ人々(一般)が欲しがるものに惑わされる事は不毛だと思います。
「過去に良く使用されていたものが上位に表示されるのは問題がある」という事であれば、
a) 直近1年とか、直近1か月とかを調査対象期間にする、
b) (使用回数/アプリが提供されていた期間)で頻度を求める
...
9
票
長方形と円の衝突判定を行うコードを教えて下さい
言語の指定がないので、アルゴリズムだけ示します。
下記の図で細かい説明を省いて結論だけ言うと、長方形(赤)の外側に引いた水色の実線の中に、円の中心 P1 が入った際には衝突したとみなせます。水色の線は、長方形の外縁から r の距離に相当します。そのため角を除く部分は長方形に並行に、角の部分は半径 r の円の 1/4 となっています。
あとはこの水色の実線内に入ったかどうかの判定ですが、...
9
票
Accepted
データ構造とアルゴリズムは実務ではどんなシーンで役立つのか?
巨大なシステムでは重要≒普通のシステムでは知らなくてよい、とお考えのようですがとんでもない話です。資源の少ないマイコンでは RAM も貴重 ROM も貴重、電池も貴重で、最適なアルゴリズムやデータ構造を使わないと1つ1つの処理に余計な時間がかかります。電池機器(まあ端的にはスマホっすけど)では無駄な処理は一切許されません。ほぼ同じような処理をして A 社のスマホは電池が10時間保つけど B ...
8
票
Accepted
高橋の数の算出について
ある数について、それぞれ高橋の数か? と判定していくのではなく、各桁について、ある数が何回出現したかという出現数の組から、その組は高橋の数を構成できるか、という判定をしていけば、かなり数を減らせます。
この方法なら、完全に力技で判定しても、n桁での組み合わせは、C(9 + n, 9) 通り。9桁なら 48,620 通りしかありません。
判定の手順は以下の通り。
...
8
票
ブール代数?による掛け算
掛け算(乗算)は足し算(加算)が必要になるので、まず加算の実現方法から考え、次に乗算に進みます。
加算
1ビットの加算
1ビット同士の加算は、繰り上がりを無視すれば排他的論理和です。
0 ⊕ 0 = 0
1 ⊕ 0 = 1
0 ⊕ 1 = 1
1 ⊕ 1 = 0
2ビットの加算
次に2ビット同士(3ビット目への繰り上がりは無視)です。
これには、...
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,...
7
票
既にある平均値を更新し続けるアルゴリズムを教えてください。
と置いたとき, の平均 は
と書けます. を漸化式の形で書くと
となり, これより を と を用いて
と書けます.
この方式では と だけ保持しておけばよく, を計算して を復元する処理が不要になります.
分散は
と定義されますが, これを式変形して
と書けます. 先程と同様
の漸化式
を考え, を逐次計算しやすい形で書くと
となります. 分散の場合は ...
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を求めることができます。...
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 つに ...
7
票
Accepted
プログラミングCの再帰に関しての質問です。
max() がどういう動作をするか、頭から追いかけていけば、原因が分かります。
max() が最初に呼び出されると、
変数 i が作成される
変数 result が作成され、0 に初期化される。
scanf で自然数が i に読み込まれる。 ここでユーザは 5 を入力したと仮定します。つまり i は 5 になります。
i と result, つまり 5 と 0 を比べるので、最初の if ...
7
票
Accepted
C++での自己参照構造体におけるポインタにおいて
すでにあるコメントだけで十分だと言う気もしますが。
struct MyStruct {
int a;
int b;
}
なんて宣言があると、コンパイラはMyStruct型に「int2個分」の領域を割り当てます。
struct AnotherStruct {
int key;
MyStruct subStruct;
}
だと、...
7
票
私の作った乱数はストリーム暗号に使えますか?
乱数や暗号は自前で考えるとたいてい穴があるものしかできないので、既成のものを使われるほうがよいです。
勉強したいのであれば、入門書としてまず「暗号技術入門(ISBN 4797382228)」を読んでみてはいかがでしょうか
具体的な欠陥を1つ示しておきます。
a==a[Z]になると、a^a[Z]は0となります。以後生成される数列は0となります。^a==a[Z]となっても同様です。
...
6
票
Accepted
バイナリ法を用いた多項式の累乗計算について
numpy では、整数は C などと同じフォーマットで格納されているので、桁あふれを起こしているのでしょう。20億を越えたあたりでおかしくなっているので、32bitの符号付き整数だとすると辻褄が合います。ただ、手元の Linux Mint で試したところ、64bitのためか、問題が再現しませんでした。
試しに
import numpy
def power(f, n):
p = ...
6
票
Accepted
m×n board におけるナイト・ツアーの数えあげを高速に行うには?
盤面の対称性を利用する
元質問での工夫にもある通り、縦横半分に4分割すると、それぞれ線対称・点対称の関係にありますので、各部分の解の数は同数になります。そのため、 1/4 の部分の各マスを始点とした解の数の合計を求めて4倍すると全体の解が求まります。
ただし、辺の長さが奇数の場合は工夫が必要です。中央の一列は、上記の 1/4 の部分の計算に含めず、後から改めて求めるとよいです。
縦 / 2 × ...
6
票
Accepted
ヒープデータ構造について
回答となると、この英文を訳すしかないので、解釈に必須の部分だけ書きますね。
この問題は二分ヒープを対象としていて、最深部以外は完全二分木になることが前提。上から各段のノードを数えると1,2,4,8...となりますが、最後の段は2の累乗になっているとは限りません。また"at most"はつまり取りうる最大の数という意味なので、1からn/2^(h+1)の間の数ならOKです。
ある関数f(k)...
6
票
数値からランダムに値を取り出す『軽い』方法
候補を小さい順に見ていき、選択するか否か、毎回ダイスを振れば、ランダムかつ小さい順に選択されると思います。
以下はPythonの例です。
これがいかなる意味でランダムなのか、本当にランダムなのか、などは私は分かりません。
#!/usr/bin/python3
import random
start = 0
last = 19
need = 6
selected = 0
for c in ...
6
票
Accepted
リナックスのはじめの方のコードでつまずきました。
#define BUILD_BUG_ON(condition) ((void)sizeof(char[1 - 2*!!(condition)]))
conditionが0以外だったらコンパイルエラーにする。
!は単に論理否定で、二つ続けて!!とすることで、肯定論理にしています。conditionの値がたとえ10でも論理結果(0 or 1)を返します。
char[1 - 2*!!(condition)...
6
票
リナックスのはじめの方のコードでつまずきました。
一部だけ。
否定の否定 (!!)
C言語の!演算子などを使いNOT演算(否定)を行なうと対象の真偽を逆転させます。
対象が真と見なせる値であれば真偽値の偽を、偽と見なせる値であれば真偽値の真を返します。
これを!!のように2回行うと、逆転させて、また逆転させるので、真偽は元にもどり変わりません。
対象を真偽値にする、という効果だけが得られます。
この機能は、...
6
票
Accepted
8パズルで、最初にシャッフルさせる時の考え方
どうやってランダム生成するか?
1~9 の並べ替えをランダムに生成する
以下の判定問題を解く
(もし解けないことが分かったら) 9 (空ブロック) 以外の2つの異なるブロックをランダムに選んで入れ替える
問題の定式化
問題 正解
31_ 123
275 -> 456
684 78_
上記のような盤面であったとき、これは以下のような並べ替え問題であると考える。
3 ...
6
票
Accepted
DOMが書き換わった後ブラウザはどのように再描画していますか?
基本的には、DOM, HTML, CSS の仕様に準拠する範囲で不要な処理をしない、の積み重ねです。
大まかには「DOM変更→スタイル計算→レイアウト→ペイント→コンポジション」というステップがあります。以下のような処理はどのブラウザエンジンもやっているのではないかと思います。
DOM変更が、表示されているDocumentのツリーに接続していない部分で起きたら、何もしない
...
Only top scored, non community-wiki answers of a minimum length are eligible