[アルゴリズム] タグが付いた質問
アルゴリズムとは、プログラミングにおける、問題の解決手段や計算手法、実現手法またはデータ構造の扱い方、操作などを定式化したものです。数式アルゴリズムの妥当性や証明は[数学]タグがあります。データ構造(型)についての質問は[データ構造]があります。
327 件の質問
15
票
4
回答
2,618
閲覧数
ログインシステムのためのパスワードのハッシュ方式、互換性、照合方法について
ログインシステムについて質問があります。
パスワードを暗号化ではなくハッシュ関数を使い符号化する安全性と使い方はわかりました。
またそれに文字を足して何回か行う、ということもわかりました。(ソルトとストレッチングのことです)
そこで質問があります。
SHA256を使おうと思っているのですが、ハッシュ化という行為は元に戻せないということでした。いずれ新しいタイプのハッシュを使おうと思った際に、...
15
票
5
回答
2,017
閲覧数
longの飽和演算を行うアルゴリズムを教えてください
longのビット数で加減算の飽和演算を行いたいです。
検索してもSIMD関連の話題ばかり引っかかってしまいます。
int幅であればlongにキャストして演算後、intに戻すという手段を使えますが、longの場合BigIntegerを使用するというのは大げさな気がします。
効率のよいアルゴリズムがあれば教えて頂きたいです。
// SaturationLong
public struct ...
13
票
4
回答
1,870
閲覧数
クイックソートの2種類の実装法で実行速度に顕著な違いが出る
(QuickSort:GeeksforGeeksを参照)
QuickSortの大枠を、
/* low --> Starting index, high --> Ending index */
quickSort(arr[], low, high) {
if (low < high) {
pi = partition(arr, low, high)
...
11
票
4
回答
4万
閲覧数
vectorとlistどのように使い分けますか
vectorとlistどのように使い分けますか?この様な質問を受けました。
そこで私は、vectorは配列でlistはリストだろう。
具体的な使い分けとなると、リストは切ったりつなげたりが得意でvectorは配列メモリが消費が少ない。
けれど、実際に表現するときに切ったりつなげたりして使う使い方なんて心当りがない。
中間地点への一つのデータを頻繁に削除・...
11
票
5
回答
2,044
閲覧数
高橋の数の算出について
各桁を並び替えてできる最大の数と
各桁を並び替えてできる最小の数(ただし、最高位は0以外にする)の差が
自身と一致するとき、高橋の数と呼びます。
(http://masami.d2.r-cms.jp/blog_detail/blog_id=3&id=6)
以下のコードで、9桁までの高橋の数を
求めようとしたのですが、
9桁の高橋の数の算出に何時間も
かかっています。
...
10
票
1
回答
8,436
閲覧数
Git の 3-way merge とは具体的にどのようなアルゴリズムですか?
Git のドキュメントによると、git merge は内部で 3-way merge を行います。
2-way merge だと不都合があるのは分かるのですが、ではこの 3-way merge は具体的にどのようなアルゴリズムでマージをするのでしょうか? 厳密には 3-way merge と recursive 3-way merge というものがあるようですが、ここでは Git ...
9
票
1
回答
3,954
閲覧数
CRC32とMD5の使い分け
CRC32とMD5はハッシュアルゴリズム?として、どちらもよく利用されていると思います。
けれど、その使い分けはどのように行われているのですか?
9
票
2
回答
4,099
閲覧数
DOMが書き換わった後ブラウザはどのように再描画していますか?
ブラウザで HTML/CSS を読み込んでページを描画した後、もし JavaScript によって動的に DOM が書き換わったら、ブラウザはページの再描画をしなくてはなりません。
素朴に考えるとページの描画にかかるコストは無視できません。DOM がちょっと変わっただけで要素のレイアウトが変わりえますし、テキストの折り返しが変わって更にレイアウトが変わることもありそうです。
しかし多くの場合、...
9
票
1
回答
3,308
閲覧数
C言語 word2vecのベクトル化アルゴリズムについて
自然言語処理の分野を沸かせたword2vecについてです。
単語をベクトルデータに変換するプログラムにword2vecというものがあります。
word2vecのコード
このプログラムでは単語を任意の次元のベクトルに変換できます。
このプログラムで生成された単語ベクトルは驚くことに単語ベクトルをたし引きすると直感的に意味が通る単語になることが知られています。
例えば、'king' - 'man' ...
8
票
7
回答
3,885
閲覧数
数値からランダムに値を取り出す『軽い』方法
お世話になります。
かなり初歩的な質問になってしまいますが、お許し下さい。
0から19までの連続した値があるとし、そこから重複せずに
六つだけ取り出したいと思います。
やりたいことはたったこれだけなのですが、下記の条件を満たす方法で
実現したいと思っています。
1.コレクションなどの機能は使用しない
2.forやifなどといった、基本的な処理だけで実現したい
3.取得した後も、...
8
票
2
回答
1,795
閲覧数
円周率の99901桁から100000桁までを簡単に求めるには?
http://worldrecord314.com/pi
上記ページには円周率10万桁が載っているのですが、
9万9901桁から10万桁までを簡単に求めるには
どうすればよいでしょうか?
参考までにRubyのコードと実行結果を記しておきます。
require 'benchmark'
require 'bigdecimal/math'
include BigMath
puts ...
8
票
2
回答
377
閲覧数
2部グラフ(V1, V2, E)で、V2からいくつか頂点を削除し、すべてのv∈V1が、1本のみの枝をもつようにするには?
2部グラフ(V1, V2, E)があります。
V2から点をいくつか削除し、それら点に紐付いていた枝を削除することで、すべてのv∈V1が1本のみの枝を持つ部分グラフ(V1, V', E')を作りたいのですが、
そのようなV'の存在の有無を判定し、また、その条件を満たすV'を少なくとも1つ得るには、どうすればいいでしょうか。
図のように、V2からいくつか点を削除したV'を得たいです。
このようなV'...
8
票
2
回答
1,532
閲覧数
16×16や25×25の数独を計算量を抑えて作成したい
下記のように数独を作るプログラムをかきました。
升目を初期化する(例 1~9までの場合は9×9の升目を初期化する)
左上から幅優先探索で値をランダムに入れていく
ランダムで入れていき、(行・列・ブロック内でかぶって)入れられる値がなくなったら、かぶった2つの升目を初期化して再度実行
9×9では問題なく(遅いと感じることなく)作成できたのですが、
16×16では途端に重くなり、...
8
票
3
回答
2万
閲覧数
Java における Scavenge GC と Full GC の違い
Scavenge GC と Full GC の処理の違いは何か教えて下さい。以下については理解しています。
Scavenge GC が Eden 領域がいっぱいになった時に実行される
MaxTenuringThreshold の回数文、S0 から S1 に移動が発生した場合に、OLD 領域への移動が発生する
Old がいっぱいになった時に Full GC が発生する。
つまり、Old ...
7
票
6
回答
2,908
閲覧数
2 分木を ascii art で表示する方法は?
2 分木を ascii art で表示するには、どのようにプログラムを組めばよいですか?
(ruby での回答が望みですが、他の言語でも可です)
出力イメージ:(あくまでイメージ。これと異なっていても構いません。)
__9__
/ \
4 15
/\ / \
2 6 12 17
2 分木の操作プログラム例が以下にあります。...
7
票
2
回答
810
閲覧数
初速・最終速度・移動時間・移動距離が決まっている状況で、速度をスムーズに変化させる
オブジェクトを座標Aから座標Bへ、以下の条件に基づいて移動させようとしています。
・座標Aでの速度は定数Va
・座標Bでの速度は定数Vb
・AからBまで移動するのにかかる時間は定数T
・AからBまでの距離は定数D
この条件下で、速度をVaからVbへスムーズに変化させながら移動させたいのですが、どうすれば特定時刻での速度を求めることができるでしょうか?
(...
7
票
1
回答
4,764
閲覧数
長方形と円の衝突判定を行うコードを教えて下さい
2Dのゲームで長方形と円の衝突判定プログラムを書きたいのですが、計算方法を教えて下さい。
長方形の中心を P0, 横幅の半分をw/2, 縦幅の半分を h/2 とします。
円の中心は P1, 半径を r とします。
これらのパラメーターを使って円と長方形が交差しているか否かを判定するアルゴリズムとコードを教えて下さい。長方形は必ず軸に平行です。
7
票
1
回答
1万
閲覧数
教師あり学習と教師なし学習の違いは何ですか?
何冊か本を読んだのですが、抽象的ではっきりした理解を得ることができませんでした。
具体的な例を教えていだだけますか
7
票
0
回答
393
閲覧数
Git のマージ戦略 "resolve" とはどのような戦略ですか?
git merge のマージ戦略には resolve というものがあります。
resolve
This can only resolve two heads (i.e. the current branch and another branch you pulled from) using a 3-way merge algorithm. It tries to carefully ...
6
票
4
回答
1,130
閲覧数
rsa で用いる素数 p, q がもし素数ではなかったら何がおこる?
rsa の素数のペアはどのように生成される? の問いで調べていった結果、 RSA の秘密鍵(素数 p, q) は Miller-Rabin のテストによって、確率的にそれが素数であることを判定しているのだ、ということを学びました。ここでふと、これだけ世の中で RSA 鍵が使われているのであれば、そのうちのひとつぐらいは、 Miller-Rabin の素数判定を Pass ...
6
票
1
回答
1,171
閲覧数
C++での自己参照構造体におけるポインタにおいて
C++で自己参照構造体というものがあると思います。(後述の二分探索木の例を参照)
この場合、p,l,rの型はNodeではなくてNode*です。
これはNodeではいけないのでしょうか?
ネットで自己参照構造体をぐぐってみると、みんなポインタを使ってはいるものの、
ポインタである必要性を説明している記事が見当たらなかったので不思議に思ってます。
struct Node {
int key;
...
6
票
1
回答
777
閲覧数
バイナリ法を用いた多項式の累乗計算について
以前した質問 "冪乗計算を高速に行うには?" の多項式版についての質問です。
次のように「(バイナリ法を用いた)多項式の累乗計算」を行うコードを
Ruby 2.2 および Python 2.7 で作成し、それぞれ (1 + x)^n を計算させたのですが、
Python 2.7版の方が n が34以上で結果がおかしくなってしまいました。
...
6
票
2
回答
3,981
閲覧数
エイトクイーンパズルの解法について
「アルゴリズムとデータ構造」紀平拓男/春日伸弥 著 (http://www.sbcr.jp/products/4797324198.html?sku=4797324198)第10章において
エイトクイーンパズルをC言語で解いているのですが、
左上(0, 0)がクイーンの場合しか答えを出力しない
のはどうしてか教えてください。また、
他の91通りの解を出力するにはどのように修正すればよいか
...
6
票
1
回答
972
閲覧数
動画をバージョン管理するための diff アルゴリズム
Git などのバージョン管理ツールの発展の背後には「テキストデータは行単位で簡単に差分が取れ、しかもどのような差分なのか閲覧しやすい」という特徴があるように思います。
逆に音声、画像、動画といったバイナリデータでは "良い感じ" の差分が取りづらく、定期的なバックアップを使ったバージョン管理より高度なバージョン管理がやりにくそうです。個人的に動画編集をしていると、動画に対して Git ...
6
票
1
回答
847
閲覧数
量子コンピュータによってソートは速くなりますか?
ランダムアクセスできる配列に対してソートを行うとき、量子アルゴリズムは逐次の古典的アルゴリズムより漸近的に速くなりえますか?
6
票
2
回答
7,263
閲覧数
リストから取り出した3つの整数の合計が0になる組み合わせ
EDIT: 最初に投稿した時は、N個の整数の合計の一般解を求める問題だと思っていたのですが、一般解だとNP完全問題になってしまうので、出題者の意図は3つ限定だったのだろうと思います。ですので3つの合計に改題しました。回答を考えてくださった皆さんすみません!
ある任意の長さのリストに符号つきの整数が格納されています。値の重複を許します。そこから3つの整数を取り出すとき、...
6
票
2
回答
2,886
閲覧数
冪乗計算を高速に行うには?
a を整数、n を自然数とします。
一般に a^n の計算を高速に行う方法を教えてください。
なお、この質問は
「特定の n に対して最小の計算回数を求める」
という趣旨の質問ではありません。
(追記)
バイナリ法によるコード(Ruby版およびPython版)を
回答に載せました。
6
票
7
回答
933
閲覧数
12ヶ月の中の複数月の平均を求めるアルゴリズム
お世話になります。
業務で、今度の四月から開始される『働き方改革』の中に、複数月の平均が80時間を超えてはならないと
いうのがあり、それを求めるためのツールをAccessで作成しています。
四月から始まり、三月で終わる一年の期間の中で、二ヶ月以上の連続した組み合わせ(4-5,4-5-6,4-5-6-7~1-2-3,2-3まで)の平均を算出するのですが、...
5
票
2
回答
7,977
閲覧数
暗号に使える乱数と使えない乱数
暗号に使える乱数と使えない乱数があるようですが、なぜそのようになるのかわかりません
例えば、円周率からN番目の値をMだけ取り出したものは使え
漸化式で初期値MでN回実行した結果は使えないというような例だったと思います。
どちらも結果的には予測可能だと思うのですが
5
票
2
回答
1万
閲覧数
ビット演算子だけで整数の割り算(余あり)をする方法
掛け算の場合は
5 * 10 = 0b101 * 0b1010
= 0b101 * (2^3 + 2^1)
= (0b101 << 3) + (0b101 << 1) = 0b110010 = 50
で計算できるのは分かるのですが、5/3などを計算する場合どうすればいいのか思い当たらないので説明いただければと思います。
そのまま割る方法でも、...
5
票
1
回答
255
閲覧数
デザインパターンのIteratorについて
プログラミング初心者でJavaでIteratorについて学んだのですが、
・Iteratorには大まかに二つ役割があって、それはIteratorクラスとAggregateクラスの二つなのですが、実際にJavaで提供されているAPIはIteratorがjava.util.Iteratorクラス(Enumerationというのもありました)、AggregateがArrayListやMap、...
5
票
2
回答
2,658
閲覧数
負の重みを含んだ最長経路の求め方
皆様のアイデアを頂戴したいです。
仕事上の目的で、下のような有向グラフの最長経路を求めたい
と考えております。①から⑤までです。
実際のグラフはもっと複雑です。ですので総当たりは難しいです。
最初ダイクストラ法を用いようと考えましたが
①ダイクストラ法は最小経路を求めるので、そのままでは最長経路
が求められない。
②負の重みがある。
ため断念しました。
...
5
票
1
回答
254
閲覧数
ランダムに複数引いた通路の幅が同じになるように整形する方法
ランダムでダンジョンのマップを作成しようとしています。
上の画像のように2つの部屋があり、その間を、2マスの幅がある通路でつなぎます。
通路の始点、終点や折れ曲がる地点はランダムで決まります。
さらに通路を追加します。
二度目以降に通路を追加する際、以前に引いた通路を気にせずに引くので、以前に引いた通路と一部が重なったり、隣り合ったりする場合があります。
こうして2、3回通路を引いた後で、...
5
票
0
回答
70
閲覧数
Proof of Stakeのコンセンサスアルゴリズムで、validatorを選ぶノードは分散的に存在しているのでしょうか?
Proof of Stakeのコンセンサスアルゴリズムは、Stakeしているコインの量に応じてランダムにValidatorが選ばれ、ValidatorがTransactionを承認します。不正するとStakeしているコインが没収されてしまうため、不正をしないモチベーションが働きます。そのため、51%攻撃は実質不可能とされています。
色々な資料を読んでいても、...
5
票
0
回答
158
閲覧数
グラフ構造の探索に対応するデータ構造には法則があるのでしょうか?
グラフ構造、たとえばツリー構造を探索することを考えます。
ツリー構造の場合は、探索の例は幅優先探索や、深さ優先探索があります。
この時、
幅優先探索はしばしばキューを用いて
深さ優先探索はしばしばスタックを用いて
それぞれ実装されます。
これはちょうど、
各ノードを訪問した時に、そこから見えるまだ未探索のノードについて適当な順序で push() を行う
次のノードを pop() ...
4
票
2
回答
2,384
閲覧数
使用頻度を計算するには?
直接プログラミングに関係するわけではありませんが、アルゴリズムの話なのでこちらに質問させていただきます。
いま、アプリ一覧を使用頻度の高い順にソートしたいと考えています。
そこでアプリ起動頻度として、起動と起動のあいだに経過した時間の平均を取るという方法を取っています。
しかしこの方法では、過去によく使用していたが、...
4
票
2
回答
621
閲覧数
リナックスのはじめの方のコードでつまずきました。
以下のような三行のコードがありました。。。順番は不問です。
#define BUILD_BUG_ON(condition) ((void)sizeof(char[1 - 2*!!(condition)]))
struct boot_params boot_params __attribute__((aligned(16)));
BUILD_BUG_ON(sizeof ...
4
票
1
回答
515
閲覧数
完全二分木は森に分類されますか?
どういった場合が森に分類されるのですか?
4
票
2
回答
1,595
閲覧数
m×n board におけるナイト・ツアーの数えあげを高速に行うには?
以前の質問(n×n board におけるナイト・ツアーの数えあげについて)
でナイトツアーの数えあげを行いました。
さて、一般に
m×n board におけるナイト・ツアーの数えあげを高速に行うには
どうすればよろしいでしょうか?
以下のコードは、長方形の対称性を利用することで以前の計算の約1/4位になっています。
#include <stdio.h>
int ...
4
票
2
回答
1,338
閲覧数
DOT言語の有向グラフが木構造か木構造でないかの判定方法を教えて下さい。
①有向グラフが木構造か木構造でないかの判定方法を教えて下さい。
②rootは入力ですか
よろしくお願いします。
(参考)DOT言語
https://ja.wikipedia.org/wiki/DOT%E8%A8%80%E8%AA%9E
(参考)WebGraphviz is Graphviz in the Browser
http://www.webgraphviz.com/
(判定)
...
4
票
2
回答
1,606
閲覧数
pythonの辞書型の実装
pythonの辞書型を使いました。
今まで線形探索で行っていた単語の検索が異常に早くなり快適です。
ところで、ハッシュについて調べた所、
h(x)=x%5 //5はテーブルの行数
のようなハッシュ関数で振り分けていると分かりました。
しかし、私がこの前実行したpythonのコードでは単語数が100万語近くありました。
キーが衝突するかと思いましたが、高速に動作しました。
...
4
票
3
回答
1,601
閲覧数
逆ポーランド記法で被演算子が3個以上の演算はありうるのか?
中間記法「3 + 4」は逆ポーランド記法だと「3 4 +」のように書けます。
では、被演算子が3個以上、たとえば中間記法「3 + 4 + 5」は逆ポーランド記法ではどのように書けばよいのでしょうか?
「3 4 + 5 + 」と書けばよさそうですが、「3 4 5 +」のように書くことはできないのでしょうか?
(乗算でも同様にできそうですが引き算だとどうなるのかちょっとよくわからないですね)
4
票
2
回答
324
閲覧数
画像を比率を保ったまま端数なく縮小するパーセンテージの求め方
ヘタすると小学生レベルの計算なのかもしれないのですが、
例えば 128x80 の画像があったとして、
これが丁度縦横端数なく縮小できるパーセンテージを求める公式のようなモノはありますでしょうか?
Google Sheetsで下記のように一覧を出して求めてもさして時間はかからなかったのですが、よい方法があれば知りたいです。
追記:本当にやりたいこと
比率を保ったまま縮小をしたいです。
...
4
票
2
回答
1,258
閲覧数
N個の棒の中から3つをつなぎ合わせて長さがLになる組み合わせの総数を求めるプログラムについて
つなぎ合わせたときの長さLと、N個(1≦N≦5000)の棒の長さが標準入力から与えられるとき、N個の棒の中から3つをつなぎ合わせて長さがLになる組み合わせの総数を求める
という問題の解説記事(https://codeiq.jp/magazine/2015/07/26213/)があるのですが、
紹介されていた以下のRubyの解法は標準入力データを
35
10
13
12
17
10
4
18
3
...
4
票
2
回答
390
閲覧数
グラフの折れ線100本をそれぞれ異なる色にしたい場合、何か良いアルゴリズムはありますか?
やりたいこと
下図のようなグラフを、作成したいです。
生徒のテストの点数の推移を折れ線グラフで表示する
グラフに表示する生徒は、ユーザが指定できる
生徒は最大100人いるので、折れ線の数は最大100本まで表示できるようにする(100本表示して、意味のあるグラフになるかどうかは気にしない)
生徒ごとに折れ線の色は変える(折れ線の色に、意味があるかは気にしない)
質問
...
4
票
1
回答
183
閲覧数
カウンタの値が被らないことの確認方法
任意の値からループするカウンタ間の値が被らないことを確認したいのですが、その条件を出しかねています。
数学的にアプローチできると良いのですが、ネタも知識も不足しており、どのようにアプローチすれば良いのかも判断ついておりません。
どのように考えれば良いのかヒントとなる何かでも良いのでご教示いただけたら幸いです。
255までの数値を1~10個格納できる配列がある。格納した個数を格納数とする。
...
4
票
1
回答
613
閲覧数
どのような多面体かを知るコード
多面体を作る方法について
PythonでもCでもMatlabでも言語は問いません。
例えば正20面体に関する以下のようなデータがあるとします。
このデータは正20面体の各頂点0から11に関してどの3点でひとつの三角形、つまり正20面体のひとつの面を作っているかを示します。
この画像のように頂点をつなげていくことができます
データ1
6 4 0
4 9 0
9 3 0
3 11 0
...
4
票
1
回答
2,368
閲覧数
無限ループはどのようにして検出しているのですか?
windowsなどでプログラムが応答しないという記述が表示されることがありますが、
このような応答の応答がないプログラムを検出するプログラムはどのようになっているのですか?
毎回毎回プログラム以前の無知な質問ですみません
【追記】
「イベントが一定時間以上の間処理されない」
C++/cliかC#の入門で一番最初にウインドウだけを作るプログラム(いわゆるhello worldプログラム)...
4
票
4
回答
1,021
閲覧数
2からNまでを、素因数分解したときの素因数の最小値が小さい順に並べるには?
2 = 2^1
3 = 2^0 * 3^1
4 = 2^2
5 = 2^0 * 3^0 * 5^1
6 = 2^1 * 3^1
7 = 2^0 * 3^0 * 5^0 * 7^1
8 = 2^3
9 = 2^0 * 3^1
10 = 2^1 * 3^0 * 5^1
となるので、
2から10までを
素因数分解したときに含まれる素因数の最小値が小さい順に
(ただし、
m, n ...
4
票
1
回答
957
閲覧数
スーパーコンピュータはなぜ高速に計算ができるのですか?
スーパーコンピュータはなぜ高速に計算ができるのですか?
スーパーコンピュータは多くのCPUを並列にして速度を稼いでいると認識しています
しかしなぜ高速に計算できるかわかりません
理由はアムダールの法則です
複数のプロセッサを使って並列計算してプログラムの高速化を図る場合、そのプログラムの逐次的部分に制限を受ける。例えばプログラムの95%を並列化できたとしても、...