[アルゴリズム] タグが付いた質問
アルゴリズムとは、プログラミングにおける、問題の解決手段や計算手法、実現手法またはデータ構造の扱い方、操作などを定式化したものです。数式アルゴリズムの妥当性や証明は[数学]タグがあります。データ構造(型)についての質問は[データ構造]があります。
273
質問
2
票
1回答
185 件の閲覧数
二分探索木を用いて英単語をkeyとした連想配列を動的に作りたいが、連想配列が期待通りの動作をしてくれない。
上の表題にもある通り、二分探索木を利用して動的なハッシュマップを自分で作ろうとしたのですが、私が書いた以下のコードは実行しても入力に対して期待された出力をしません。
どのように以下のコードに改善すれば、期待された出力を得られるのでしょうか?
とても読みづらいコードになってしまっていて申し訳ないのですが、アドバイスを頂けると大変助かります。
実行したコード:
#include <...
2
票
3回答
326 件の閲覧数
なぜこのコードはTLEになる?
下のコードは、競技プログラミングの問題 バトンリレーゲーム に対する回答です。サンプルはリストを使用したものを載せました。
同じテストケースでサンプルコードはメモリ時間0.03sだったのに対し自分のコードは1.99sを超えTLE (Time Limit Exceeded) となりました。
しかし、この二つのコードの根本的違いが判りません。どなたかご教授願えないでしょうか?
自分で書いたコード
#...
2
票
1回答
219 件の閲覧数
ランレングスのデータ構造がわかりません
WWWBBをW3B2にすると圧縮できる、というのは理解できました。しかし、11111000ならどうでしょうか?
1503と圧縮してしまうと展開時に1503と展開も出来てしまいます。
そこで1:5 0:3のように [繰り返す文字:繰り返し回数] と言うフォーマットをとれば正しく展開できます。
ただ、ここでいうコロンとスペースをバイナリでうまく表現ができません。ランレングスは一体どのようにして"...
2
票
1回答
329 件の閲覧数
2
票
2回答
238 件の閲覧数
10桁までのSelf-descriptive numberの求め方について
各桁の数字がその桁の出現回数を表すような数を
Self-descriptive numberと呼びます。
(http://en.wikipedia.org/wiki/Self-descriptive_number)
以下のコードで、10桁までのSelf-descriptive numberを
求めようとしたのですが、
9桁、10桁のSelf-descriptive numberの算出に時間が
...
2
票
2回答
342 件の閲覧数
2分木のデータ追加、サーチ、削除について
「アルゴリズムとデータ構造」紀平拓男/春日伸弥 著 (http://www.sbcr.jp/products/4797324198.html?sku=4797324198)第6章において 、2分木のデータ追加、サーチ、削除のコードが紹介されています。
それを今Ruby版に置き換えたつもりなのですが、
53を追加、25を追加、85を追加、83を追加、52を追加したあと、53を削除すると「...
2
票
2回答
161 件の閲覧数
rsa の素数のペアはどのように生成される?
RSA 暗号は、今日日の(ネットワーク)セキュリティまわりの分野で、広く使われている技術だと思っています。
例えば RSA2048 では、「MSB が 2048 bit 目になるような、ただ二つの素数 p, q に素因数分解できるような合成数を、ランダムに生成する」必要があります。
これはちょっと考えて、どうやったらこれが実現できるのかが自明ではないな、と思いました。
質問
今ある RSA ...
2
票
1回答
307 件の閲覧数
動的計画法の分割数について
下記、動的計画法を用いて分割数を求める問題についてです。
下記dp配列を定義し、漸化式を立て本問題を解くそうなのですが理解できていない点が三つあります。疑問点を上手く言語化できておりませんが解説いただけると幸いです。
わからない箇所
漸化式のdp[i][j-i]は予めi個を1個ずつi個の集合に割り当てて残ったj-...
2
票
1回答
253 件の閲覧数
再帰的な処理のトレースができずコードの理解ができない
以下のようにリストを使った再帰的定義のフィボナッチ数列のコードを理解しようとしています。
def fib(n):
if n < 1:
return [0]
if n == 1:
return [0,1]
A = fib(n-1)
print(A)
return A + [A[-1] + A[-2]] #...
2
票
2回答
403 件の閲覧数
線分群から、閉図形の数を数える方法を教えて下さい。
仕様1:2次元
仕様2:線分と線分の交差は、気にしません。
目的:輪(環)がいくつあるか知りたい。
例1
input : 線分1 [ 0, 0], [10, 0]
線分2 [10, 0], [ 0,10]
線分3 [ 0,10], [ 0, 0]
線分4 [-5, 0], [-5,10]
output : 閉図形の数=1
: ...
2
票
1回答
3,829 件の閲覧数
Word2vecの追加学習について
Word2Vecの追加学習について質問します。
あるコーパスを一度学習し、ベクトルを生成した後、そのコーパスに未知語を追加したら、未知語のベクトル化をするためにはゼロからコーパスを再学習する必要があるのでしょうか?
(要するにコーパスを継ぎ足して繰り返し学習したいです)
西尾泰和さんの、『word2vec による自然言語処理』によると、ネガティブサンプリングは「...
2
票
1回答
622 件の閲覧数
n×n board におけるナイト・ツアーの数えあげについて
数理パズルの一つにナイト・ツアー(https://en.wikipedia.org/wiki/Knight%27s_tour)
というものがあります。
nが6以下のときについてn×n board における directed open tour を
以下のコードで数時間かけて数えあげたのですが、
n = 6 のとき0通り(正しくは6637920通り)になるのはどうしてでしょうか?
#...
2
票
2回答
497 件の閲覧数
2つの確率変数X,Yをとる確率関数 を表現するのに適したデータ構造を教えて下さい
C++言語において、確率P(x,y)を実装しています。
P(x)については実装してみました。といってもmapを利用してkeyが何回出現したかをsecondのカウンターを利用して全体で割ったものですが、
std::map<int,int> P;
for(int i=0;i<10;i++)
P.insert(std::make_pair(i,0));
P.find(rand())...
2
票
2回答
116 件の閲覧数
キューに含まれた正の数値の分散をO(1)で計算するアルゴリズムはありますか
概要
キューに含まれた正の数値の分散を、キュー内の数値の個数に依存しない速度のアルゴリズムを求めています
例えば平均値の場合には、キューに含まれる数値の合計値を保持する変数を用意して、push時には加算、pop時には減算することで後は数値の個数で割るだけで計算できます
これと同じような計算方法で分散を求めることはできますでしょうか?
できる場合はどのようなアルゴリズムになりますでしょうか?
2
票
2回答
166 件の閲覧数
計数ソートを入力順にソートした際の安定性
下の疑似コードで実装された計数ソート(Counting Sort)の探索を現在と逆順にした場合、安定したソートを保持したままにするにはどの方法が効率がいいでしょうか?
事実、このアルゴリズムでは入力配列を後ろからソートしないと、同じ要素が現れた場合その要素の順番は逆になってしまい、安定したソートではなくなります。
私は。同じ要素が複数回出現した場合に限り、その要素数-...
2
票
1回答
1,338 件の閲覧数
多面体の頂点群もしくは平面群から三角ポリゴンメッシュの作成
3Dグラフィックスで凸型多面体を描画したいと考えています。
多面体はそれを囲む平面(境界無し)で定義されているため、順序を問わないのであればすべての頂点を取得することが出来ますが、三角ポリゴンメッシュをねじれ等なく作成するスマートな方法が分かりません。
2
票
1回答
223 件の閲覧数
makeによってつくられたデータ構造の参照渡し
makeによってデータ構造の参照を作り、関数に参照を渡しデータの変更を行います。
以下のような出力になるのはなぜでしょうか?
https://play.golang.org/p/lOC49HmVcq
package main
import (
"fmt"
)
func main() {
a := make(map[string]int)
set(a)
fmt....
2
票
1回答
900 件の閲覧数
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個になる」のはいくつあるか調べるには
どうすれば速く求まるでしょうか?
...
2
票
1回答
680 件の閲覧数
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 ...
2
票
0回答
44 件の閲覧数
matlabでnsga2を実装.目的関数の範囲指定,設計変数と目的変数の最大化を行いたい.
NSGA2をmatlabで動かせるよう以下のURLからダウンロードし実装.
https://jp.mathworks.com/matlabcentral/fileexchange/10429-nsga-ii-a-multi-objective-optimization-algorithm
実際に動かしてみて,成功はしたのですが
目的変数はすべて最小化
設計変数の範囲のみが指定可能
...
2
票
1回答
178 件の閲覧数
3剤3期クロスオーバーの分散分析:誤差をエクセルで算出したい
3剤3期クロスオーバーの分散分析を、Rで実行しました(以下Rプログラム)。
この分散分析表の誤差「8.5089」をエクセルで算出したいのですが、結果が合いません。(誤差以外は検算できました)
以下に、エクセルの画像を添付しました。
どこの解釈が違うのか、どなたかアドバイスをお願いしてもよろしいでしょうか。
※データは「医薬品開発のための統計解析 第2部p.282」です。
※ 同じ質問を ...
2
票
0回答
74 件の閲覧数
0-1整数2次計画問題に関する数理最適化のアルゴリズムについて
数理最適化に関するアルゴリズムに関して学習しています。
0-1整数2次計画に関して分岐限定法で厳密解などを解くらしいのですが、
調べても連続変数の2次計画の問題に関する内容が多く、私の検索能力が低くて見つけられません。
0-1整数2次計画問題に関して
https://www.letsopt.com/entry/2019/08/18/131125
...
2
票
0回答
109 件の閲覧数
バケツソートの最低ケースを改善するためには
バケツソート(Bucket Sort)の平均計算量はO(n)ですが、もしデータが均一に分布してない場合、最悪計算量はO(n^2)になってしまいます。しかし、その場合他のアルゴリズムと組み合わせることによって計算量は改善できるのでしょうか?
教科書からの問題なのですが、二分探索を使用できるというヒントを与えられました。しかし、二分探索を使用する意味がよくわかりません。Merge ...
2
票
0回答
225 件の閲覧数
クイックソートにおけるデータ列のソートの仕方について
はじめまして。
アルゴリズム初心者でクイックソートでつまづいております。
{5,3,2,6,4,1,3,7}というデータ列で、真ん中の4を基準値(ピボット)とした場合(6と4の間にパーテーションを設けた場合、)どのように(昇順)ソートされていくか順を追ってご説明頂けますと幸いです。
※自分で試した場合、なぜか昇順でソートすることができませんでした。(1が最左端に来ず、並び順が{3,3,2,1,:...
1
票
5回答
685 件の閲覧数
AIZU ONLINE JUDGEの0009で何回やってもTime Limit Exceedと表示されます。
久々にやったAIZU ONLINE JUDGEのこの問題で困ったことが起こったので、質問させていただきます。
問題を解くコードをPython3で書いたのですが、何回やってもTime Limit Exceedと表示されます。証拠となるソリューションはこのリンクにあります。
何が原因で、その解決方法はないのでしょうか?
わかる方、いましたら教えてください。
なお、コードは以下のとおりです。
...
1
票
3回答
335 件の閲覧数
プログラミングCの再帰に関しての質問です。
Cの初心者です。
再帰を使用して、ユーザーが入力した自然数(入力される自然数の数は分からない)をscanfで読み取り、その中から最大値を返す関数int max()を書くという課題です。ユーザーが入力する最後の自然数は0でなくてはならず、0が入力されたら関数は必ず終了し、その時点での最大値を返す。
配列やリスト、ループを使わずに再帰だけで書かなければならず、...
1
票
3回答
602 件の閲覧数
C言語 直線状の線分の重複回数を求めるアルゴリズム
x軸上にいくつかの線分があり、その線分の重なる数の最も大きい値を求める方法がわかりません。どのようなアルゴリズムで求めればいいのでしょうか?
例
・線分1の範囲(2<=x<=5)
・線分2の範囲(3<=x<=9)
・線分3の範囲(4<=x<=11)
の場合、
2<=x<=3, 9<=x<=11 の範囲で1回重複
3<=x<...
1
票
2回答
161 件の閲覧数
シャッフルパズルゲームのシャッフルについて
pythonを使い、数字を順番通りにならべかえるゲームを作っています。terminalで表示して遊べるところまではできたのですが、ソースコードにも書いているrandom.shuffle(list1)を使ってしまうと、本当に数字がランダムにシャッフルされてしまい、元どおりにならべかえることが難しくなってしまうゲームになっています。
現在、
123
456
78
と右下に1マス空け、...
1
票
2回答
3,064 件の閲覧数
Rubyでアルゴリズムを学ぶのに適した書籍やサイトを教えてください [クローズ済み]
はじめまして、よろしくお願い申し上げます。
以下質問となるので、お答えいただければ幸いです。
例えばなのですが、15枚の絵札から5枚のカードを引くプログラムを書いてください.
といった問題をRuby言語で学習する場合に適した書籍、サイトなどあるのでしょうか??
上記のようなテスト行い、基準点に達することができず、アルゴリズムの学習をよりしなければと強く思いググっみたのですが、...
1
票
3回答
597 件の閲覧数
再帰関数について
再帰関数を用いて回答するこの問題についての実装が理解できておりません。
再帰関数自体の理解は概要と簡単なフィボナッチ数列を求めるなどの実装は理解できている程度の状態です。
コードを注意深く読むと理解できるような当たり前のことなのかもしれませんが下記再帰関数がイメージできておりません。
※コード途中でデバックのような値の出力を試してみたりはしてみました。
...
1
票
1回答
238 件の閲覧数
テストケースに通らない理由がわかりません。
テストケースが通りません。
入力結果を何個か確認したところあってそうなのですがどこがテストケースにひかかっているか不明です。
解説いただければ幸いです。
▼問題文
正整数
A,Bが与えられます。
Aも Bも割り切る正整数のうち、N番目に大きいものを求めてください。
なお、与えられる入力では、
Aも Bも割り切る正整数のうち N番目に大きいものが存在することが保証されます。
制約
...
1
票
1回答
175 件の閲覧数
クイックソートと同時にランキングを作ることはできますか?
A,10,50,32
B,30,60,21
C,15,45,61
というcsvファイルを読み込んで、A~Cの順番を崩さずに次の条件を満たしたdat、csvファイルを出力したいです。順番を崩したくない理由は、A, B, Cの並び順によって一意な値(配列の添え字)を割り振るためです。
降順にソートした結果の4列目のデータだけのdatファイル
期待する出力:
61
32
21
...
1
票
1回答
176 件の閲覧数
耐久試験を想定したアルゴリズムにおいて計算量を減らす方法
入力で正の整数Nを与え、1からNまで各要素の差が1の配列Aを作成する
1からNまでの間の整数で探索する値をランダムに生成し、探索する値を超えないが最も値が近い配列Aの要素を見つけるプログラムを書いています。
具体的なアルゴリズムの用途には、衝撃吸収材の精度を測るため、高い所から生卵を落として割れない限界の高さを調べる試験を想定しています。
高さは最大でNmで、...
1
票
2回答
867 件の閲覧数
二分探索木の平均の計算量を示す方法について
二分探索木の平均の計算量を示す方法について
下記画像の結果よりすべてのnについてT(n)<4logn+1が示せたことになり、木の平均深さがO(logn)であることがわかるそうです。
下記画像の二分探索木の平均の計算量を示す方法について5点不明な箇所がございます。
⑴ T(n)<= alogn+bを仮定する理由について
...
1
票
1回答
247 件の閲覧数
ユークリッドの互除法でZeroDivisionErrorが発生する原因について
ZeroDivisionError: integer division or modulo by zero
以下がコードです.
def Euclidean_algo(m, n):
while m%n != 0:
m = n
n = m%n
else:
return n
m = int(input('the bigger int ...
1
票
2回答
833 件の閲覧数
このコードから三角関数表がどうして作られるのかわかりません
このコードから三角関数表がどうして作られるのかわかりません。
実行すると確かに三角関数表なのですが、奇っ怪な方法の理由はわかります。
sinを一度しか呼ばないという制限のためです。
けれど、その後どうしてこんな方法でと思ったので質問します。
static void make_sintbl(int n, float sintbl[])
{
int i, n2, n4, n8;
...
1
票
2回答
599 件の閲覧数
2からNまでを、素因数分解したときの次数の和の順に並べるには?
以前
(2からNまでを、素因数分解したときの素因数の最小値が小さい順に並べるには?
および
2からNまでを、素因数分解したときの次数によって並べるには?)
と異なる規則によって、2からNまでを並びかえを行います。
①2〜Nまでを素因数分解を行い次数のみ取り出しその和を求める。
②次数の和が小さい順に並べる。次数の和が同じなら、元の数の大きさが小さい方が先とする。
例えば、N = 10 の場合、...
1
票
1回答
260 件の閲覧数
レーベンシュタイン距離(編集距離/エディットグラフ)の出力とグラフにおける最短経路に関して
レーベンシュタイン距離(編集距離)を計算して、2単語間の最小編集コストを求めようとしています。
以下のように、python-Levenshteinというライブラリを使って簡単に実行できますが、グラフを書いて同数の最短ルートが求められずに困っています。
「kitten」を「sitting」に変形する場合には、3回の処理が必要で手で文字を入れ替え・削除処理をする場合や、レーベンシュタイン距離(...
1
票
1回答
132 件の閲覧数
ヒープの深さと各深さにおける要素数から和を求めるプログラムの時間計算量
今回書いたプログラムの計算量をヒープを構成する要素数len(a) =n としてオーダで考えると O(log2(n)) という理解でしょうか。
2**x for x in range(num)もfor j in range (len(depth_list))も繰り返し回数は log2(n)+1 なので、オーダ記法だと全体として O(log2(n)) に抑えられると考えましたが、...
1
票
1回答
196 件の閲覧数
数式の変形の過程について
下記数式についてです。
上の式から下の式に変形する過程や数学的な性質が理解できません。
数学に弱くお恥ずかしいですのですが、ご解説いただければ幸いです。
▼分からない箇所
下記の1/n^2Σnが1/nΣ1になる式(下記画像の1行目、2行目)になる箇所がわかりませんでした。
また、最終式についてなのですがシグマ通しの足し算はシグマの左側(今回でいうところの1/n^...
1
票
2回答
121 件の閲覧数
ZIPコンテナを効率よく読み込むには?
通信用語の基礎知識さんのZIPコンテナの記事を見て、自分でZIPコンテナファイルの実装を作ろうと考えているのですが、ZIPファイルを解凍せずにZIPファイルの中身を読み込んだり書き込んだりするにはどうすればいいのでしょうか?
(ZIPコンテナというのはePubで使われている規格です。)
...
1
票
1回答
797 件の閲覧数
pythonによるFFTの実装
pythonでFFT(高速フーリエ変換)を実装しようと思っています
コードはご覧の通りです
(FFT_sort.py)
import numpy as np
def sort(N):
flag = ~(N & (N - 1))
if flag != -1:
return None
result = np.zeros(N, dtype=np....
1
票
2回答
258 件の閲覧数
i (1以上9以下)を含むならば、i がi 個含む数について
i (1以上9以下)を含むならば、i がi 個含む数について、
オンライン整数列大辞典のA108571(https://oeis.org/A108571)に載っています。
また、この条件をみたす数の個数は
66712890763701234740813164553708284
であることも載っています。
この個数を次のコードで求めました。
def factorial(m)
(1..m)....
1
票
3回答
323 件の閲覧数
Java,Cの計算問題についての質問です
○○○○ - ○○○○ = ○○○○
他のサイトにあった問題です。
この計算の中に0~9の数字を使わなければいけないといった問題です。
同じ数字を使っても良いです。
0~9の数字を全て使ってかつ、正しい筆算になるのは何通りなのか求めたいです。
javaかCで解きたいのですが、解き方が浮かびません。
また、このような問題を解くときに便利なライブラリ等はあるのでしょうか?
...
1
票
2回答
289 件の閲覧数
2からNまでを、素因数分解したときの次数によって並べるには?
以前(2からNまでを、素因数分解したときの素因数の最小値が小さい順に並べるには?)
と異なる規則によって、2からNまでを並びかえを行います。
①2〜Nまでを素因数分解を行い次数のみ取り出すものとします。
②次数の小さい順に並べる。
例えば、N = 10 の場合、次のようになります。
①
2 => 1,
3 => 10,
4 => 2,
5 => 100,
6 => 11,
7 => 1000,
...
1
票
1回答
2,302 件の閲覧数
D*アルゴリズムの概略
Dスターアルゴリズム経路詮索のうちどれに分類されますか
深さ優先探索
幅優先探索
最良優先探索
アルゴリズムに関する擬似コードのようなものは知られていますか
追記
AとくらべDは評価関数が1つまたは、2つ追加されているようですが
その1つ又は、2つの関数の目的は?
1
票
2回答
175 件の閲覧数
python のitertools.permutationsの使い方を教えて下さい。全部の組み合わせの作り方を教えて下さい。
1年前の問題ですけど、確かめてみたい。
(参考)小学生のみなさんへ、場合の数「2020年度京都大学理系学部数学第5問」にチャレンジしてみて下さい。
https://qiita.com/mrrclb48z/items/a97086d25b3d0bee7125
①[1234]×[1234]×[1234]×[1234]/直積(デカルト積,Cartesian Product)の使い方を教えて下さい。
②...
1
票
1回答
166 件の閲覧数
(openssl の) RSA 秘密鍵の中身はそれぞれ何を表す?
openssl で rsa の鍵を適当に test.pem で生成して、その中身を openssl rsa -in test.pem -text -noout で眺めていました。(長いので、この質問の末尾に付与します)
この中で、prime1, prime2 はそれぞれ 1536 == 3072/2bit 長の素数(以降、p, q と呼びます)、 modulus は p * q のかけ算の結果(...
1
票
2回答
149 件の閲覧数
Excel VBA の1回の実行で、通過した通過しなかったfunction、subを分類する方法を教えて下さい
全てのfunction, subに一行ずつ debug.print”function1通過” と書く方法しかありませんか?
書くとしたら、正規表現置き換えの方法で、対応可能ですか?
全エクスポートで、エディタの正規表現置換後、全インポートを予定しています。
例) 全てのfunction, sub2行目に debug.print "なまえ通過” を挿入する方法がありますか?
他言語でも、...
1
票
2回答
170 件の閲覧数
重み付き無向グラフを解くためのダイクストラ法に関するコードのエラー
重み付き無向グラフを解くためにダイクストラ法を実装したプログラムを書いています。
以下の入力で実行するとエラーが起きてしまうのですが、どのように修正するべきかわからず、質問させていただきました。
ダイクストラ法を実装したコード
def shortest_length(G, start):
S = {start:0}; D={}
while len(S)>0:
...