[アルゴリズム] タグが付いた質問
アルゴリズムとは、プログラミングにおける、問題の解決手段や計算手法、実現手法またはデータ構造の扱い方、操作などを定式化したものです。数式アルゴリズムの妥当性や証明は[数学]タグがあります。データ構造(型)についての質問は[データ構造]があります。
317
質問
8
票
2
回答
339
閲覧数
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'...
4
票
2
回答
1,567
閲覧数
m×n board におけるナイト・ツアーの数えあげを高速に行うには?
以前の質問(n×n board におけるナイト・ツアーの数えあげについて)
でナイトツアーの数えあげを行いました。
さて、一般に
m×n board におけるナイト・ツアーの数えあげを高速に行うには
どうすればよろしいでしょうか?
以下のコードは、長方形の対称性を利用することで以前の計算の約1/4位になっています。
#include <stdio.h>
int ...
3
票
3
回答
940
閲覧数
重複組み合わせ・CSVファイルへの記載方法
Ruby初心者です.
元のCSVファイル "test.CSV" A, 100, test があるとします.
2列目の値を10~0に変更し,計11個のCSVを新たに出力するために,
以下のプログラムを作成しました.
require 'csv'
# CSVを読み込んで二次元配列にする
array = CSV.read('filepath\test.csv')
puts(array.to_s)
...
-1
票
2
回答
212
閲覧数
n×n board におけるナイト・ツアーを記録するには?
以前の質問(n×n board におけるナイト・ツアーの数えあげについて)
でナイトツアーの数えあげを行いました。
このコードにさらに以下の二点を行うにはどうすればよろしいでしょうか?
①条件を満たす経路を保持する。
②これらをリスト化して名前をつけてテキストファイルとして保存する。
特に①については、
定義したsearchに対し、新たな変数(経路のログ)...
7
票
2
回答
787
閲覧数
初速・最終速度・移動時間・移動距離が決まっている状況で、速度をスムーズに変化させる
オブジェクトを座標Aから座標Bへ、以下の条件に基づいて移動させようとしています。
・座標Aでの速度は定数Va
・座標Bでの速度は定数Vb
・AからBまで移動するのにかかる時間は定数T
・AからBまでの距離は定数D
この条件下で、速度をVaからVbへスムーズに変化させながら移動させたいのですが、どうすれば特定時刻での速度を求めることができるでしょうか?
(...
2
票
1
回答
648
閲覧数
n×n board におけるナイト・ツアーの数えあげについて
数理パズルの一つにナイト・ツアー(https://en.wikipedia.org/wiki/Knight%27s_tour)
というものがあります。
nが6以下のときについてn×n board における directed open tour を
以下のコードで数時間かけて数えあげたのですが、
n = 6 のとき0通り(正しくは6637920通り)になるのはどうしてでしょうか?
#...
2
票
1
回答
350
閲覧数
ファジー制御について教えてください。
ファジー制御について完結で具体的にイメージがわくように説明してください。
3
票
2
回答
4,895
閲覧数
既にある平均値を更新し続けるアルゴリズムを教えてください。
既にある平均値を更新し続けるアルゴリズムを教えてください。
平均値や分散を逐次求めるアルゴリズムを教えてください。
0
票
1
回答
481
閲覧数
論文などに書かれているアルゴリズムをC/C++に変換するトランスレータはありませんか
論文に書かれているALGOLのような擬似コードを見るのですが、それを外形だけでもCやC++にしたいのですが、自分で打ち込むよりも手っ取り早く変換することができればより多くの論文を実行して読めると思いました。
擬似コードやALGOLをC/C++へ変換できるトランスレータはありませんか
FORTRANをCに変換するソフトウェアは有名ですがALGOLや擬似言語については見当たりませんでした。
6
票
2
回答
1,746
閲覧数
円周率の99901桁から100000桁までを簡単に求めるには?
http://worldrecord314.com/pi
上記ページには円周率10万桁が載っているのですが、
9万9901桁から10万桁までを簡単に求めるには
どうすればよいでしょうか?
参考までにRubyのコードと実行結果を記しておきます。
require 'benchmark'
require 'bigdecimal/math'
include BigMath
puts ...
2
票
1
回答
400
閲覧数
経路長を求めポイントを多く稼ぐ方法
こんにちは。いつもお世話になっています。
いまパックマンのようなゲームを作ってまして敵のキャラのAIのようなものを作っています。
その際にアイテムを取る最短経路を求めることはできるのですがそうではなくただ最短を求めないで効率の良いと自分の思いついた作りたいプログラムの書き方がわからなくて質問しました。
前提として、ルールとして
...
5
票
1
回答
762
閲覧数
バイナリ法を用いた多項式の累乗計算について
以前した質問 "冪乗計算を高速に行うには?" の多項式版についての質問です。
次のように「(バイナリ法を用いた)多項式の累乗計算」を行うコードを
Ruby 2.2 および Python 2.7 で作成し、それぞれ (1 + x)^n を計算させたのですが、
Python 2.7版の方が n が34以上で結果がおかしくなってしまいました。
...
2
票
2
回答
889
閲覧数
連続 i 個の和が N 以下の組み合わせの総数の求め方について
[条件]
1.配列 ary はソートされている。
2.N は ary の最大値以上
上記条件をみたすような一般の ary、N に対し、
連続 i (> 0) 個の和が N 以下の組み合わせの総数の求めたいと考えています。
どのように求めるのが効率的でしょうか?
例を示しますので、「下記の非効率な箇所」もしくは「より効率的な求め方」
を教えて頂けたら、幸いです。
N = 10
ary = (...
4
票
2
回答
1,251
閲覧数
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
票
1
回答
624
閲覧数
バイトニックソートとマージソートの違いを教えて [クローズ済み]
動画を見たり画像見たけど違いわからなかったよ
同じ間隔離れたものを入れ替えるって共通する点じゃないか
ほら、全く違いが見えない
4
票
1
回答
513
閲覧数
完全二分木は森に分類されますか?
どういった場合が森に分類されるのですか?
-2
票
2
回答
387
閲覧数
スロットマシンのフロー図 [クローズ済み]
スロットマシンのフロー図を作りたいのですが、
スタートボタンを押すと3つのマスがそれぞれピロピロする。
それぞれのマスには、1~9の数字が1つづつ存在。
ストップボタンは3つあり、それぞれのマスをストップする。
3つの数字が揃えば、アタリと表示する。
3つの数字が揃わないとき、ハズレと表示する。
(ストップボタンをおさないと、10秒で自動停止する。)
この仕様だとどうやって作っていきますか?
...
8
票
1
回答
3,438
閲覧数
CRC32とMD5の使い分け
CRC32とMD5はハッシュアルゴリズム?として、どちらもよく利用されていると思います。
けれど、その使い分けはどのように行われているのですか?
4
票
2
回答
2,945
閲覧数
n以下の素数の個数を高速に求めるには?
pi(n)をn以下の素数の個数と定義します。
pi(n)の正確な値を高速に求めるにはどのようなアルゴリズムを用いればよいでしょうか。
2×√n 程度のデータを用いて計算するコードを記しておきます。
(Ruby 2.2)
def pi(n)
m = Math.sqrt(n).to_i
keys = (1..m).map{|i| n / i}
keys += (1..keys[-1] ...
2
票
3
回答
1,865
閲覧数
アドレス指定方式についてです
アドレス指定方式についてです。
直接アドレス指定方式
指標アドレス指定方式
ベースアドレス指定方式
相対アドレス指定方式
間接アドレス指定方式
レジスタアドレス指定方式
即値アドレス指定方式
この7つの違いはわかりました。
しかし、それが具体的に何に使われているのか?
この思想の違いが何故生まれてきたかなどの歴史的な経緯がわかりません。
多分OSの設計思想の話だと思うのですが...
1
票
2
回答
265
閲覧数
i (1以上9以下)を含むならば、i がi 個含む数について
i (1以上9以下)を含むならば、i がi 個含む数について、
オンライン整数列大辞典のA108571(https://oeis.org/A108571)に載っています。
また、この条件をみたす数の個数は
66712890763701234740813164553708284
であることも載っています。
この個数を次のコードで求めました。
def factorial(m)
(1..m)....
2
票
1
回答
936
閲覧数
1からNまでの整数に対し、「約数の数がs個になる」のはいくつあるか調べるには?
n の約数の個数を d(n) と表すことにする。
1から10までの整数に対し、
d(n) = 1 となるのは1個、
d(n) = 2 となるのは4個、
d(n) = 3 となるのは2個、
d(n) = 4 となるのは3個ある。
一般に、
1からNまでの整数に対し、「約数の数がs個になる」のはいくつあるか調べるには
どうすれば速く求まるでしょうか?
...
4
票
1
回答
925
閲覧数
スーパーコンピュータはなぜ高速に計算ができるのですか?
スーパーコンピュータはなぜ高速に計算ができるのですか?
スーパーコンピュータは多くのCPUを並列にして速度を稼いでいると認識しています
しかしなぜ高速に計算できるかわかりません
理由はアムダールの法則です
複数のプロセッサを使って並列計算してプログラムの高速化を図る場合、そのプログラムの逐次的部分に制限を受ける。例えばプログラムの95%を並列化できたとしても、...
1
票
2
回答
247
閲覧数
Ulam number の効率の良い求め方について
Ulam number とは以下の性質を持つ数である。
(http://en.wikipedia.org/wiki/Ulam_number)
①今まで現れた相異なる2つの Ulam number の和で表そうとしたとき、1通りしか出来ない。
注)相異なる2つの Ulam number の和で表せないときは、Ulam number ではない。
N = 339 とし、
N 以下の Ulam ...
15
票
5
回答
1,868
閲覧数
longの飽和演算を行うアルゴリズムを教えてください
longのビット数で加減算の飽和演算を行いたいです。
検索してもSIMD関連の話題ばかり引っかかってしまいます。
int幅であればlongにキャストして演算後、intに戻すという手段を使えますが、longの場合BigIntegerを使用するというのは大げさな気がします。
効率のよいアルゴリズムがあれば教えて頂きたいです。
// SaturationLong
public struct ...
0
票
5
回答
2,599
閲覧数
公開鍵暗号方式に疑問があります
どうして公開鍵で鍵をすることができて
公開鍵で鍵を開けられないのですか?
公開鍵で鍵を出来るのなら
誰でもなりすますことが可能ですよね
それって暗号として意味がありますか?
1
票
3
回答
330
閲覧数
Java,Cの計算問題についての質問です
○○○○ - ○○○○ = ○○○○
他のサイトにあった問題です。
この計算の中に0~9の数字を使わなければいけないといった問題です。
同じ数字を使っても良いです。
0~9の数字を全て使ってかつ、正しい筆算になるのは何通りなのか求めたいです。
javaかCで解きたいのですが、解き方が浮かびません。
また、このような問題を解くときに便利なライブラリ等はあるのでしょうか?
...
1
票
2
回答
619
閲覧数
2からNまでを、素因数分解したときの次数の和の順に並べるには?
以前
(2からNまでを、素因数分解したときの素因数の最小値が小さい順に並べるには?
および
2からNまでを、素因数分解したときの次数によって並べるには?)
と異なる規則によって、2からNまでを並びかえを行います。
①2〜Nまでを素因数分解を行い次数のみ取り出しその和を求める。
②次数の和が小さい順に並べる。次数の和が同じなら、元の数の大きさが小さい方が先とする。
例えば、N = 10 の場合、...
1
票
2
回答
291
閲覧数
2からNまでを、素因数分解したときの次数によって並べるには?
以前(2からNまでを、素因数分解したときの素因数の最小値が小さい順に並べるには?)
と異なる規則によって、2からNまでを並びかえを行います。
①2〜Nまでを素因数分解を行い次数のみ取り出すものとします。
②次数の小さい順に並べる。
例えば、N = 10 の場合、次のようになります。
①
2 => 1,
3 => 10,
4 => 2,
5 => 100,
6 => 11,
7 => 1000,
...
4
票
4
回答
992
閲覧数
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 ...
1
票
1
回答
278
閲覧数
n進グレイコードからn進表記へ戻すには?
n進グレイコードの出力を行った
(参考:n進グレイコードの出力について)
ので、その逆をやってみました。
# n進表記から n進グレイコードへ
def to_gray(n, k, str)
str.rjust(k + 1, '0').split('').each_cons(2).map{|d| (d[1].to_i - d[0].to_i) % n}.join
end
# ...
3
票
1
回答
762
閲覧数
n進グレイコードの出力について
kビットのn進グレイコード(http://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%AC%E3%82%A4%E3%82%B3%E3%83%BC%E3%83%89)
を出力するコードを書いてみたのですが、
もっと簡単に書くにはどのようにすればよろしいでしょうか?
(n = 2 のとき、ビットシフトと排他論理和のループで書けるので、
n ...
5
票
2
回答
2,854
閲覧数
冪乗計算を高速に行うには?
a を整数、n を自然数とします。
一般に a^n の計算を高速に行う方法を教えてください。
なお、この質問は
「特定の n に対して最小の計算回数を求める」
という趣旨の質問ではありません。
(追記)
バイナリ法によるコード(Ruby版およびPython版)を
回答に載せました。
1
票
2
回答
1,820
閲覧数
隣り合う2数の差は3以上、1つおいた数との差も3以上の順列は何通りあるか?
次の問題を考えています。
(http://www004.upp.so-net.ne.jp/s_honma/mathbun/mathbun113.htm)
1からNまでのN個の整数で、
ア)隣り合う2数の差は3以上、1つおいた数との差も3以上
という条件を満たす順列は、何通りあるだろうか?
ただし、順番を逆にしたものもそれぞれ1つずつ数えるものとします。
(より一般的には次のような問題です。
...
2
票
2
回答
717
閲覧数
ブール代数?による掛け算
コンピュータ独特のシフト演算や論理積。論理和などのビット演算で掛け算はどのように表現できますか
2
票
2
回答
738
閲覧数
オイラーの分割恒等式をプログラミングで確認するには?
p(n)は、与えられた整数nの分割の総数を表すものとします。
さて、オイラーの分割恒等式とは、以下の恒等式をさします。
p(n | 和因子は奇数) = p(n | 和因子は相異なる)
(http://ja.wikipedia.org/wiki/%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%E3%81%AE%E5%88%86%E5%89%B2%E6%81%92%E7%...
11
票
5
回答
2,030
閲覧数
高橋の数の算出について
各桁を並び替えてできる最大の数と
各桁を並び替えてできる最小の数(ただし、最高位は0以外にする)の差が
自身と一致するとき、高橋の数と呼びます。
(http://masami.d2.r-cms.jp/blog_detail/blog_id=3&id=6)
以下のコードで、9桁までの高橋の数を
求めようとしたのですが、
9桁の高橋の数の算出に何時間も
かかっています。
...
2
票
2
回答
240
閲覧数
10桁までのSelf-descriptive numberの求め方について
各桁の数字がその桁の出現回数を表すような数を
Self-descriptive numberと呼びます。
(http://en.wikipedia.org/wiki/Self-descriptive_number)
以下のコードで、10桁までのSelf-descriptive numberを
求めようとしたのですが、
9桁、10桁のSelf-descriptive numberの算出に時間が
...
3
票
2
回答
1,555
閲覧数
pythonの辞書型の実装
pythonの辞書型を使いました。
今まで線形探索で行っていた単語の検索が異常に早くなり快適です。
ところで、ハッシュについて調べた所、
h(x)=x%5 //5はテーブルの行数
のようなハッシュ関数で振り分けていると分かりました。
しかし、私がこの前実行したpythonのコードでは単語数が100万語近くありました。
キーが衝突するかと思いましたが、高速に動作しました。
...
1
票
1
回答
431
閲覧数
Goで幅優先探索をしてみようとして不思議な挙動に出会う
お気楽goプログラミングというサイト
http://www.geocities.jp/m_hiroi/golang/puzgo01.html
で幅優先探索を学んでいましたが、
makePathを使うところでappendと使うと
[0 2 4 6]を2回出力します。
プリントデバッグしたところ何度か同じものをキューに入れていますが
どうしてそのような動きをしているのかわかりません
...
2
票
3
回答
2万
閲覧数
ビットスワップの方法
固定ビット長さ(例16bit)のビットの順序をビット単位で反転(スワップ)する方法を教えてください。
例:0001 1010 1100 1000 を 0001 0011 0101 1000
C言語の標準ライブラリに含まれる関数だけを使用するものとしますが、ワークエリアについては特に制限をもうけません。
3
票
0
回答
710
閲覧数
ウェーブレット変換とフーリエ変換の計算量
離散ウェーブレット変換の計算量はO(N)で、高速フーリエ変換の場合はO(N log N)になるそうですが
離散ウェーブレット変換の式も Σ(シグマ記号:summation)が2つのため二重ループになり
O(N^2)になると思うのですが、なぜ、O(N)になるのですか?
0
票
1
回答
542
閲覧数
Judy arrayとは何ですか?
連想配列のようですが
連想配列ならmapやすでにSTLで用意されているで十分に足りると思うのですが
なぜ、Judy arrayというものが生まれたのですか
mapやsetと比べてそちらで用意されているものは何が大きく違うのですか?
1
票
1
回答
2,986
閲覧数
D*アルゴリズムの概略
Dスターアルゴリズム経路詮索のうちどれに分類されますか
深さ優先探索
幅優先探索
最良優先探索
アルゴリズムに関する擬似コードのようなものは知られていますか
追記
AとくらべDは評価関数が1つまたは、2つ追加されているようですが
その1つ又は、2つの関数の目的は?
8
票
1
回答
3,275
閲覧数
C言語 word2vecのベクトル化アルゴリズムについて
自然言語処理の分野を沸かせたword2vecについてです。
単語をベクトルデータに変換するプログラムにword2vecというものがあります。
word2vecのコード
このプログラムでは単語を任意の次元のベクトルに変換できます。
このプログラムで生成された単語ベクトルは驚くことに単語ベクトルをたし引きすると直感的に意味が通る単語になることが知られています。
例えば、'king' - 'man' ...
3
票
7
回答
1万
閲覧数
四則演算はどういう順番で実行すると計算誤差が発生/伝搬しにくいですか
今ある問題は足し算と掛け算とわり算のみで構成されている演算です。
double c, m, d1, d2;
/*それぞれに値を代入*/
double x = (c* m + ( d1 + 1.0/ d2 )/ 2.0 )/ (c + 1.0 );
という式です。この式をMaximaに投げると
double x = (c* m + 0.5*( d1 + 1.0/ d2 ))/ (c + 1.0)...
11
票
4
回答
4万
閲覧数
vectorとlistどのように使い分けますか
vectorとlistどのように使い分けますか?この様な質問を受けました。
そこで私は、vectorは配列でlistはリストだろう。
具体的な使い分けとなると、リストは切ったりつなげたりが得意でvectorは配列メモリが消費が少ない。
けれど、実際に表現するときに切ったりつなげたりして使う使い方なんて心当りがない。
中間地点への一つのデータを頻繁に削除・...
3
票
2
回答
827
閲覧数
配列内のリストを効率よく走査するには
Perlで下記のような構造を持つ配列があります。
@array = ({
id => '1',
key => 'a'
},
{
id => '2',
key => 'b'
},
{
...
1
票
1
回答
282
閲覧数
2分木を使ったマップについて
「アルゴリズムとデータ構造」紀平拓男/春日伸弥 著 (http://www.sbcr.jp/products/4797324198.html?sku=4797324198)第6章において 、2分木を使ったマップのコードが紹介されています。
前回の質問「2分木のデータ追加、サーチ、削除について」のHiroshi Yamamotoさんの回答をもとにRuby版で置き換えました。
しかし、key:6を追加、...
7
票
6
回答
2,747
閲覧数
2 分木を ascii art で表示する方法は?
2 分木を ascii art で表示するには、どのようにプログラムを組めばよいですか?
(ruby での回答が望みですが、他の言語でも可です)
出力イメージ:(あくまでイメージ。これと異なっていても構いません。)
__9__
/ \
4 15
/\ / \
2 6 12 17
2 分木の操作プログラム例が以下にあります。...