Skip to main content

[アルゴリズム] タグが付いた質問

アルゴリズムとは、プログラミングにおける、問題の解決手段や計算手法、実現手法またはデータ構造の扱い方、操作などを定式化したものです。数式アルゴリズムの妥当性や証明は[数学]タグがあります。データ構造(型)についての質問は[データ構造]があります。

絞り込み
並べ替え
タグ付けされた
15
4 回答
2,618 閲覧数

ログインシステムのためのパスワードのハッシュ方式、互換性、照合方法について

ログインシステムについて質問があります。 パスワードを暗号化ではなくハッシュ関数を使い符号化する安全性と使い方はわかりました。 またそれに文字を足して何回か行う、ということもわかりました。(ソルトとストレッチングのことです) そこで質問があります。 SHA256を使おうと思っているのですが、ハッシュ化という行為は元に戻せないということでした。いずれ新しいタイプのハッシュを使おうと思った際に、...
mic's user avatar
  • 151
15
5 回答
2,017 閲覧数

longの飽和演算を行うアルゴリズムを教えてください

longのビット数で加減算の飽和演算を行いたいです。 検索してもSIMD関連の話題ばかり引っかかってしまいます。 int幅であればlongにキャストして演算後、intに戻すという手段を使えますが、longの場合BigIntegerを使用するというのは大げさな気がします。 効率のよいアルゴリズムがあれば教えて頂きたいです。 // SaturationLong public struct ...
seo's user avatar
  • 658
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) ...
komatsuna's user avatar
  • 133
11
4 回答
4万 閲覧数

vectorとlistどのように使い分けますか

vectorとlistどのように使い分けますか?この様な質問を受けました。 そこで私は、vectorは配列でlistはリストだろう。 具体的な使い分けとなると、リストは切ったりつなげたりが得意でvectorは配列メモリが消費が少ない。 けれど、実際に表現するときに切ったりつなげたりして使う使い方なんて心当りがない。 中間地点への一つのデータを頻繁に削除・...
user avatar
11
5 回答
2,044 閲覧数

高橋の数の算出について

各桁を並び替えてできる最大の数と 各桁を並び替えてできる最小の数(ただし、最高位は0以外にする)の差が 自身と一致するとき、高橋の数と呼びます。 (http://masami.d2.r-cms.jp/blog_detail/blog_id=3&id=6) 以下のコードで、9桁までの高橋の数を 求めようとしたのですが、 9桁の高橋の数の算出に何時間も かかっています。 ...
TOM's user avatar
  • 1,582
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 ...
nekketsuuu's user avatar
  • 2.4万
9
1 回答
3,954 閲覧数

CRC32とMD5の使い分け

CRC32とMD5はハッシュアルゴリズム?として、どちらもよく利用されていると思います。 けれど、その使い分けはどのように行われているのですか?
溢れだすクズ's user avatar
9
2 回答
4,099 閲覧数

DOMが書き換わった後ブラウザはどのように再描画していますか?

ブラウザで HTML/CSS を読み込んでページを描画した後、もし JavaScript によって動的に DOM が書き換わったら、ブラウザはページの再描画をしなくてはなりません。 素朴に考えるとページの描画にかかるコストは無視できません。DOM がちょっと変わっただけで要素のレイアウトが変わりえますし、テキストの折り返しが変わって更にレイアウトが変わることもありそうです。 しかし多くの場合、...
nekketsuuu's user avatar
  • 2.4万
9
1 回答
3,308 閲覧数

C言語 word2vecのベクトル化アルゴリズムについて

自然言語処理の分野を沸かせたword2vecについてです。 単語をベクトルデータに変換するプログラムにword2vecというものがあります。 word2vecのコード このプログラムでは単語を任意の次元のベクトルに変換できます。 このプログラムで生成された単語ベクトルは驚くことに単語ベクトルをたし引きすると直感的に意味が通る単語になることが知られています。 例えば、'king' - 'man' ...
NLP Lover's user avatar
  • 697
8
7 回答
3,885 閲覧数

数値からランダムに値を取り出す『軽い』方法

お世話になります。 かなり初歩的な質問になってしまいますが、お許し下さい。 0から19までの連続した値があるとし、そこから重複せずに 六つだけ取り出したいと思います。 やりたいことはたったこれだけなのですが、下記の条件を満たす方法で 実現したいと思っています。 1.コレクションなどの機能は使用しない 2.forやifなどといった、基本的な処理だけで実現したい 3.取得した後も、...
たたぱた's user avatar
  • 1,205
8
2 回答
1,795 閲覧数

円周率の99901桁から100000桁までを簡単に求めるには?

http://worldrecord314.com/pi 上記ページには円周率10万桁が載っているのですが、 9万9901桁から10万桁までを簡単に求めるには どうすればよいでしょうか? 参考までにRubyのコードと実行結果を記しておきます。 require 'benchmark' require 'bigdecimal/math' include BigMath puts ...
TOM's user avatar
  • 1,582
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'...
gyu-don's user avatar
  • 299
8
2 回答
1,532 閲覧数

16×16や25×25の数独を計算量を抑えて作成したい

下記のように数独を作るプログラムをかきました。 升目を初期化する(例 1~9までの場合は9×9の升目を初期化する) 左上から幅優先探索で値をランダムに入れていく ランダムで入れていき、(行・列・ブロック内でかぶって)入れられる値がなくなったら、かぶった2つの升目を初期化して再度実行 9×9では問題なく(遅いと感じることなく)作成できたのですが、 16×16では途端に重くなり、...
hokkyokuguma's user avatar
8
3 回答
2万 閲覧数

Java における Scavenge GC と Full GC の違い

Scavenge GC と Full GC の処理の違いは何か教えて下さい。以下については理解しています。 Scavenge GC が Eden 領域がいっぱいになった時に実行される MaxTenuringThreshold の回数文、S0 から S1 に移動が発生した場合に、OLD 領域への移動が発生する Old がいっぱいになった時に Full GC が発生する。 つまり、Old ...
yoshi0309's user avatar
  • 238
7
6 回答
2,908 閲覧数

2 分木を ascii art で表示する方法は?

2 分木を ascii art で表示するには、どのようにプログラムを組めばよいですか? (ruby での回答が望みですが、他の言語でも可です) 出力イメージ:(あくまでイメージ。これと異なっていても構いません。) __9__ / \ 4 15 /\ / \ 2 6 12 17 2 分木の操作プログラム例が以下にあります。...
katoy's user avatar
  • 631
7
2 回答
810 閲覧数

初速・最終速度・移動時間・移動距離が決まっている状況で、速度をスムーズに変化させる

オブジェクトを座標Aから座標Bへ、以下の条件に基づいて移動させようとしています。 ・座標Aでの速度は定数Va ・座標Bでの速度は定数Vb ・AからBまで移動するのにかかる時間は定数T ・AからBまでの距離は定数D この条件下で、速度をVaからVbへスムーズに変化させながら移動させたいのですが、どうすれば特定時刻での速度を求めることができるでしょうか? (...
Murlock's user avatar
  • 75
7
1 回答
4,764 閲覧数

長方形と円の衝突判定を行うコードを教えて下さい

2Dのゲームで長方形と円の衝突判定プログラムを書きたいのですが、計算方法を教えて下さい。 長方形の中心を P0, 横幅の半分をw/2, 縦幅の半分を h/2 とします。 円の中心は P1, 半径を r とします。 これらのパラメーターを使って円と長方形が交差しているか否かを判定するアルゴリズムとコードを教えて下さい。長方形は必ず軸に平行です。
Udon's user avatar
  • 137
7
1 回答
1万 閲覧数

教師あり学習と教師なし学習の違いは何ですか?

何冊か本を読んだのですが、抽象的ではっきりした理解を得ることができませんでした。 具体的な例を教えていだだけますか
user avatar
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 ...
nekketsuuu's user avatar
  • 2.4万
6
4 回答
1,130 閲覧数

rsa で用いる素数 p, q がもし素数ではなかったら何がおこる?

rsa の素数のペアはどのように生成される? の問いで調べていった結果、 RSA の秘密鍵(素数 p, q) は Miller-Rabin のテストによって、確率的にそれが素数であることを判定しているのだ、ということを学びました。ここでふと、これだけ世の中で RSA 鍵が使われているのであれば、そのうちのひとつぐらいは、 Miller-Rabin の素数判定を Pass ...
Yuki Inoue's user avatar
  • 1.7万
6
1 回答
1,171 閲覧数

C++での自己参照構造体におけるポインタにおいて

C++で自己参照構造体というものがあると思います。(後述の二分探索木の例を参照) この場合、p,l,rの型はNodeではなくてNode*です。 これはNodeではいけないのでしょうか? ネットで自己参照構造体をぐぐってみると、みんなポインタを使ってはいるものの、 ポインタである必要性を説明している記事が見当たらなかったので不思議に思ってます。 struct Node { int key; ...
Haruna Ojima's user avatar
6
1 回答
777 閲覧数

バイナリ法を用いた多項式の累乗計算について

以前した質問 "冪乗計算を高速に行うには?" の多項式版についての質問です。 次のように「(バイナリ法を用いた)多項式の累乗計算」を行うコードを Ruby 2.2 および Python 2.7 で作成し、それぞれ (1 + x)^n を計算させたのですが、 Python 2.7版の方が n が34以上で結果がおかしくなってしまいました。 ...
TOM's user avatar
  • 1,582
6
2 回答
3,981 閲覧数

エイトクイーンパズルの解法について

「アルゴリズムとデータ構造」紀平拓男/春日伸弥 著 (http://www.sbcr.jp/products/4797324198.html?sku=4797324198)第10章において エイトクイーンパズルをC言語で解いているのですが、  左上(0, 0)がクイーンの場合しか答えを出力しない のはどうしてか教えてください。また、  他の91通りの解を出力するにはどのように修正すればよいか ...
TOM's user avatar
  • 1,582
6
1 回答
972 閲覧数

動画をバージョン管理するための diff アルゴリズム

Git などのバージョン管理ツールの発展の背後には「テキストデータは行単位で簡単に差分が取れ、しかもどのような差分なのか閲覧しやすい」という特徴があるように思います。 逆に音声、画像、動画といったバイナリデータでは "良い感じ" の差分が取りづらく、定期的なバックアップを使ったバージョン管理より高度なバージョン管理がやりにくそうです。個人的に動画編集をしていると、動画に対して Git ...
nekketsuuu's user avatar
  • 2.4万
6
1 回答
847 閲覧数

量子コンピュータによってソートは速くなりますか?

ランダムアクセスできる配列に対してソートを行うとき、量子アルゴリズムは逐次の古典的アルゴリズムより漸近的に速くなりえますか?
nekketsuuu's user avatar
  • 2.4万
6
2 回答
7,263 閲覧数

リストから取り出した3つの整数の合計が0になる組み合わせ

EDIT: 最初に投稿した時は、N個の整数の合計の一般解を求める問題だと思っていたのですが、一般解だとNP完全問題になってしまうので、出題者の意図は3つ限定だったのだろうと思います。ですので3つの合計に改題しました。回答を考えてくださった皆さんすみません! ある任意の長さのリストに符号つきの整数が格納されています。値の重複を許します。そこから3つの整数を取り出すとき、...
Kenji Noguchi's user avatar
6
2 回答
2,886 閲覧数

冪乗計算を高速に行うには?

a を整数、n を自然数とします。 一般に a^n の計算を高速に行う方法を教えてください。 なお、この質問は 「特定の n に対して最小の計算回数を求める」 という趣旨の質問ではありません。 (追記) バイナリ法によるコード(Ruby版およびPython版)を 回答に載せました。
TOM's user avatar
  • 1,582
6
7 回答
933 閲覧数

12ヶ月の中の複数月の平均を求めるアルゴリズム

お世話になります。 業務で、今度の四月から開始される『働き方改革』の中に、複数月の平均が80時間を超えてはならないと いうのがあり、それを求めるためのツールをAccessで作成しています。 四月から始まり、三月で終わる一年の期間の中で、二ヶ月以上の連続した組み合わせ(4-5,4-5-6,4-5-6-7~1-2-3,2-3まで)の平均を算出するのですが、...
たたぱた's user avatar
  • 1,205
5
2 回答
7,977 閲覧数

暗号に使える乱数と使えない乱数

暗号に使える乱数と使えない乱数があるようですが、なぜそのようになるのかわかりません 例えば、円周率からN番目の値をMだけ取り出したものは使え 漸化式で初期値MでN回実行した結果は使えないというような例だったと思います。 どちらも結果的には予測可能だと思うのですが
user avatar
5
2 回答
1万 閲覧数

ビット演算子だけで整数の割り算(余あり)をする方法

掛け算の場合は 5 * 10 = 0b101 * 0b1010 = 0b101 * (2^3 + 2^1) = (0b101 << 3) + (0b101 << 1) = 0b110010 = 50 で計算できるのは分かるのですが、5/3などを計算する場合どうすればいいのか思い当たらないので説明いただければと思います。 そのまま割る方法でも、...
packet0's user avatar
  • 2,439
5
1 回答
255 閲覧数

デザインパターンのIteratorについて

プログラミング初心者でJavaでIteratorについて学んだのですが、 ・Iteratorには大まかに二つ役割があって、それはIteratorクラスとAggregateクラスの二つなのですが、実際にJavaで提供されているAPIはIteratorがjava.util.Iteratorクラス(Enumerationというのもありました)、AggregateがArrayListやMap、...
hirohumi24's user avatar
5
2 回答
2,658 閲覧数

負の重みを含んだ最長経路の求め方

皆様のアイデアを頂戴したいです。 仕事上の目的で、下のような有向グラフの最長経路を求めたい と考えております。①から⑤までです。 実際のグラフはもっと複雑です。ですので総当たりは難しいです。 最初ダイクストラ法を用いようと考えましたが ①ダイクストラ法は最小経路を求めるので、そのままでは最長経路 が求められない。 ②負の重みがある。 ため断念しました。 ...
涼子津雲's user avatar
5
1 回答
254 閲覧数

ランダムに複数引いた通路の幅が同じになるように整形する方法

ランダムでダンジョンのマップを作成しようとしています。 上の画像のように2つの部屋があり、その間を、2マスの幅がある通路でつなぎます。 通路の始点、終点や折れ曲がる地点はランダムで決まります。 さらに通路を追加します。 二度目以降に通路を追加する際、以前に引いた通路を気にせずに引くので、以前に引いた通路と一部が重なったり、隣り合ったりする場合があります。 こうして2、3回通路を引いた後で、...
noprops's user avatar
  • 423
5
0 回答
70 閲覧数

Proof of Stakeのコンセンサスアルゴリズムで、validatorを選ぶノードは分散的に存在しているのでしょうか?

Proof of Stakeのコンセンサスアルゴリズムは、Stakeしているコインの量に応じてランダムにValidatorが選ばれ、ValidatorがTransactionを承認します。不正するとStakeしているコインが没収されてしまうため、不正をしないモチベーションが働きます。そのため、51%攻撃は実質不可能とされています。 色々な資料を読んでいても、...
tommy19970714's user avatar
5
0 回答
158 閲覧数

グラフ構造の探索に対応するデータ構造には法則があるのでしょうか?

グラフ構造、たとえばツリー構造を探索することを考えます。 ツリー構造の場合は、探索の例は幅優先探索や、深さ優先探索があります。 この時、 幅優先探索はしばしばキューを用いて 深さ優先探索はしばしばスタックを用いて それぞれ実装されます。 これはちょうど、 各ノードを訪問した時に、そこから見えるまだ未探索のノードについて適当な順序で push() を行う 次のノードを pop() ...
rugamaga's user avatar
  • 915
4
2 回答
2,384 閲覧数

使用頻度を計算するには?

直接プログラミングに関係するわけではありませんが、アルゴリズムの話なのでこちらに質問させていただきます。 いま、アプリ一覧を使用頻度の高い順にソートしたいと考えています。 そこでアプリ起動頻度として、起動と起動のあいだに経過した時間の平均を取るという方法を取っています。 しかしこの方法では、過去によく使用していたが、...
dryair's user avatar
  • 123
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 ...
todo's user avatar
  • 710
4
1 回答
515 閲覧数

完全二分木は森に分類されますか?

どういった場合が森に分類されるのですか?
溢れだすクズ's user avatar
4
2 回答
1,595 閲覧数

m×n board におけるナイト・ツアーの数えあげを高速に行うには?

以前の質問(n×n board におけるナイト・ツアーの数えあげについて) でナイトツアーの数えあげを行いました。 さて、一般に m×n board におけるナイト・ツアーの数えあげを高速に行うには どうすればよろしいでしょうか? 以下のコードは、長方形の対称性を利用することで以前の計算の約1/4位になっています。 #include <stdio.h> int ...
TOM's user avatar
  • 1,582
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/ (判定) ...
mrrclb48z's user avatar
  • 429
4
2 回答
1,606 閲覧数

pythonの辞書型の実装

pythonの辞書型を使いました。 今まで線形探索で行っていた単語の検索が異常に早くなり快適です。 ところで、ハッシュについて調べた所、 h(x)=x%5 //5はテーブルの行数 のようなハッシュ関数で振り分けていると分かりました。 しかし、私がこの前実行したpythonのコードでは単語数が100万語近くありました。 キーが衝突するかと思いましたが、高速に動作しました。 ...
NLP Lover's user avatar
  • 697
4
3 回答
1,601 閲覧数

逆ポーランド記法で被演算子が3個以上の演算はありうるのか?

中間記法「3 + 4」は逆ポーランド記法だと「3 4 +」のように書けます。 では、被演算子が3個以上、たとえば中間記法「3 + 4 + 5」は逆ポーランド記法ではどのように書けばよいのでしょうか? 「3 4 + 5 + 」と書けばよさそうですが、「3 4 5 +」のように書くことはできないのでしょうか? (乗算でも同様にできそうですが引き算だとどうなるのかちょっとよくわからないですね)
Akiyama Nao's user avatar
4
2 回答
324 閲覧数

画像を比率を保ったまま端数なく縮小するパーセンテージの求め方

ヘタすると小学生レベルの計算なのかもしれないのですが、 例えば 128x80 の画像があったとして、 これが丁度縦横端数なく縮小できるパーセンテージを求める公式のようなモノはありますでしょうか? Google Sheetsで下記のように一覧を出して求めてもさして時間はかからなかったのですが、よい方法があれば知りたいです。 追記:本当にやりたいこと 比率を保ったまま縮小をしたいです。 ...
shingo.nakanishi's user avatar
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 ...
TOM's user avatar
  • 1,582
4
2 回答
390 閲覧数

グラフの折れ線100本をそれぞれ異なる色にしたい場合、何か良いアルゴリズムはありますか?

やりたいこと 下図のようなグラフを、作成したいです。 生徒のテストの点数の推移を折れ線グラフで表示する グラフに表示する生徒は、ユーザが指定できる 生徒は最大100人いるので、折れ線の数は最大100本まで表示できるようにする(100本表示して、意味のあるグラフになるかどうかは気にしない) 生徒ごとに折れ線の色は変える(折れ線の色に、意味があるかは気にしない) 質問 ...
yuji38kwmt's user avatar
  • 1,854
4
1 回答
183 閲覧数

カウンタの値が被らないことの確認方法

任意の値からループするカウンタ間の値が被らないことを確認したいのですが、その条件を出しかねています。 数学的にアプローチできると良いのですが、ネタも知識も不足しており、どのようにアプローチすれば良いのかも判断ついておりません。 どのように考えれば良いのかヒントとなる何かでも良いのでご教示いただけたら幸いです。 255までの数値を1~10個格納できる配列がある。格納した個数を格納数とする。 ...
豚吐露's user avatar
  • 1,968
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 ...
potiki's user avatar
  • 49
4
1 回答
2,368 閲覧数

無限ループはどのようにして検出しているのですか?

windowsなどでプログラムが応答しないという記述が表示されることがありますが、 このような応答の応答がないプログラムを検出するプログラムはどのようになっているのですか? 毎回毎回プログラム以前の無知な質問ですみません 【追記】 「イベントが一定時間以上の間処理されない」 C++/cliかC#の入門で一番最初にウインドウだけを作るプログラム(いわゆるhello worldプログラム)...
todo's user avatar
  • 710
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 ...
TOM's user avatar
  • 1,582
4
1 回答
957 閲覧数

スーパーコンピュータはなぜ高速に計算ができるのですか?

スーパーコンピュータはなぜ高速に計算ができるのですか? スーパーコンピュータは多くのCPUを並列にして速度を稼いでいると認識しています しかしなぜ高速に計算できるかわかりません 理由はアムダールの法則です 複数のプロセッサを使って並列計算してプログラムの高速化を図る場合、そのプログラムの逐次的部分に制限を受ける。例えばプログラムの95%を並列化できたとしても、...
もっち's user avatar

1
2 3 4 5
7