[アルゴリズム] タグが付いた質問
アルゴリズムとは、プログラミングにおける、問題の解決手段や計算手法、実現手法またはデータ構造の扱い方、操作などを定式化したものです。数式アルゴリズムの妥当性や証明は[数学]タグがあります。データ構造(型)についての質問は[データ構造]があります。
321
質問
0
票
2
回答
402
閲覧数
エディタの「置換」機能と実質的に同じことをより速く処理する方法はありますでしょうか?
お世話になっております。
実質的に置換と同じことで遙かに処理の速い方法はありますでしょうか?
事例 たとえば以下のようにテキストの置換パターンが複数あったとします。
08A54G→タナ
08A→タ
54G→ナ
テキストエディタの置換のマクロでも変換していけますが、数百万字だとけっこう時間がかかります。
かかる時間とは、テキストエディタや連続置換であるかにもよりますが、速くて5分以上です。
しかし、...
2
票
1
回答
195
閲覧数
OpenGLにて、図形をマウスで引いた直線で切断したいがアルゴリズムが分からない。
OpenGLで図形をマウスで引いた直線で切断するようなプログラムを実装したいと考えています。
OpenGLのversionは4.6ですが、こちら(http://wisdom.sakura.ne.jp/system/opengl/)のver1.1に基づいたチュートリアルを勉強しています。
ユーザーが何も手を加えていない初期状況は、...
0
票
2
回答
219
閲覧数
集合当てクイズの解法
次のようなゲームを考えます。
アルファベット 'A'~'Z'を全体集合とし、その部分集合が一つ与えられているとします。これを答えと呼びます。
プレイヤーは1ターンにつき次の問い合わせを一回出来ます。
問い合わせ:アルファベット'A'~'Z'の集合を一つ入力とし、答えと入力の積集合が空集合であるか否かがYes/Noで返ってくる。
これで答えが確定するまでのターン数を競います。
...
0
票
1
回答
117
閲覧数
pythonで、intersectionの位置を調べる方法を教えて下さい。
#条件:データに重複は、ありません。
x = {"a", "b", "c"}
y = {"c", "b", "e"}
z = {"f", "b", "c"}
result = x.intersection(y, z)
...
0
票
3
回答
237
閲覧数
素因数分解を約数にする。ループ,組み合わせの方法を教えて下さい。
問題点① 素因数分解の個数が3個の場合しか対応していません。
問題点② リスト内包表記の使い方がわかりませんでした。関数部分1行で書けますか。
問題点③ ( . [ . { 。使い方、変換についての、おすすめのページを教えて下さい。
よろしくお願いします。
from sympy import *
import itertools
var('My_Yakusu')
def ...
0
票
1
回答
4,804
閲覧数
エラー: 'closure' 型のオブジェクトは部分代入可能ではありません
Bootstrap法によって機械学習アルゴリズムの精度を検証するプログラムを作っています。
以下のコードをテキストで作成し、CSVdataをread.csvで読み込んで、以下のように実行すると
> source("text.txt")
> exdata=read.csv("final_output.csv",header=TRUE)
> ...
0
票
1
回答
116
閲覧数
AtCoder Beginner Contest 180 Takahashi Unevolved D問題
D - Takahashi Unevolved 解説リンク
https://atcoder.jp/contests/abc180/editorial/219
上記リンク先に掲載されている解答コードで
ans+(y-1-x)//b
の部分がありますが、ここで-1をする理由がわかりませんでした。
こちらの意味を教えていただけないでしょうか。
よろしくお願いします
0
票
2
回答
199
閲覧数
キューに含まれた正の数値の分散をO(1)で計算するアルゴリズムはありますか
概要
キューに含まれた正の数値の分散を、キュー内の数値の個数に依存しない速度のアルゴリズムを求めています
例えば平均値の場合には、キューに含まれる数値の合計値を保持する変数を用意して、push時には加算、pop時には減算することで後は数値の個数で割るだけで計算できます
これと同じような計算方法で分散を求めることはできますでしょうか?
できる場合はどのようなアルゴリズムになりますでしょうか?
0
票
2
回答
247
閲覧数
python のitertools.permutationsの使い方を教えて下さい。全部の組み合わせの作り方を教えて下さい。
1年前の問題ですけど、確かめてみたい。
(参考)小学生のみなさんへ、場合の数「2020年度京都大学理系学部数学第5問」にチャレンジしてみて下さい。
https://qiita.com/mrrclb48z/items/a97086d25b3d0bee7125
①[1234]×[1234]×[1234]×[1234]/直積(デカルト積,Cartesian Product)の使い方を教えて下さい。
②...
0
票
1
回答
150
閲覧数
平方数の判定を、sympyの素因数分解factorintでできますか?
目的は、平方数の判定を一行でできますか?よろしくお願いします。
print(factorint(9))
{3: 2}
print(factorint(81))
{3: 4}
参考nが平方数かどうか調べる時
https://teratail.com/questions/200122
参考:Wolfram|Alpha
81は平方数ですか
https://ja.wolframalpha.com/...
0
票
1
回答
475
閲覧数
多角形同士の衝突判定のアルゴリズムについて
多角形同士の衝突判定のアルゴリズムを検討しています。
愚直に衝突判定を行う場合、多角形の各直線が別の多角形と衝突していないか、全直線同士組み合わせでチェックしていくのかと思います。
ただし、この方法だと多角形の頂点数が多い場合や、多角形が多い場合に処理が非常に多くなってしまうと思われます。(多少は処理を間引きできるとは思いますが)
高速で衝突判定ができるようなアルゴリズムはあるでしょうか?
0
票
1
回答
332
閲覧数
Pythonでの単方向リストの実装
Pythonを用いてリストを実装しようとしています。
Linked List のようにして実装しています。
以下のコードの「ここ!!」とした部分ですが、なぜreturnする必要があるのでしょうか。self.headにnew_nodeが入ってif文は終わりなのではないでしょうか。
試しにreturnを消してみると、プログラムが止まらず、同関数内のwhileから抜けられていないことがわかりました。
...
0
票
0
回答
101
閲覧数
Atcoder abc165_c 期待する答えが出力されません
以下のコードで Atcoder abc165_c (https://atcoder.jp/contests/abc165/tasks/abc165_c)の入力例を試したのですが、すべてで 0 が返ってきます。どなたか理由を教えていただけたら嬉しいです。
方向性としては、func 内でDFS的にAが求まるたびに得点を求め、その最大値を更新しています。
Atcoder abc165_c
問題概要
Q ...
2
票
1
回答
348
閲覧数
マインドマップの図形最適配置のアルゴリズム
マインドマップを作成しようとしています。
以下のルールで配置しようと思っています。
・各要素は長方形
・ルート要素は1つ
・親要素の下にぶら下がるように、直下の子要素がずらっと横一列に並ぶ
・親要素は、並んだ直下の子要素の中央に配置される
この条件を満たしつつ、なるべく全体としてコンパクトに配置するにはどうすれば良いでしょうか?
良いアルゴリズムなどはありますでしょうか?
6
票
4
回答
877
閲覧数
rsa で用いる素数 p, q がもし素数ではなかったら何がおこる?
rsa の素数のペアはどのように生成される? の問いで調べていった結果、 RSA の秘密鍵(素数 p, q) は Miller-Rabin のテストによって、確率的にそれが素数であることを判定しているのだ、ということを学びました。ここでふと、これだけ世の中で RSA 鍵が使われているのであれば、そのうちのひとつぐらいは、 Miller-Rabin の素数判定を Pass ...
2
票
2
回答
497
閲覧数
rsa の素数のペアはどのように生成される?
RSA 暗号は、今日日の(ネットワーク)セキュリティまわりの分野で、広く使われている技術だと思っています。
例えば RSA2048 では、「MSB が 2048 bit 目になるような、ただ二つの素数 p, q に素因数分解できるような合成数を、ランダムに生成する」必要があります。
これはちょっと考えて、どうやったらこれが実現できるのかが自明ではないな、と思いました。
質問
今ある RSA ...
1
票
1
回答
956
閲覧数
(openssl の) RSA 秘密鍵の中身はそれぞれ何を表す?
openssl で rsa の鍵を適当に test.pem で生成して、その中身を openssl rsa -in test.pem -text -noout で眺めていました。(長いので、この質問の末尾に付与します)
この中で、prime1, prime2 はそれぞれ 1536 == 3072/2bit 長の素数(以降、p, q と呼びます)、 modulus は p * q のかけ算の結果(...
2
票
1
回答
188
閲覧数
弧を描いて指定位置で止まりたい
弧を描いて指定位置で止まりたい
ゆるやかに減速しながら直進する物体を
境界線を超えたら一気に減速しつつ
入射角に見合った弧を描きながら境界線まで戻ってきて
ちょうど境界線で止まる(動きが止まったときの位置がちょうど境界線上になる)
ようにしたいです
1と2まではできました(まだGoogle Chromeでしか確認していませんが)
3と4はどうすればいいですか?
...
2
票
1
回答
448
閲覧数
fileの読み込みや、書き込みで出てくるstreamとは何でしょうか?
言葉の意味がよくわからないのでご質問させてください。
例えば、nim言語(おそらくPHPなどでも同じでしょうが)では、
ファイルの書き込みは以下の様に実現できます。
var fw = open("test.txt" , FileMode.fmWrite)
fw.write("hoge")
fw.close
また以下のように書いても同じ動作をしているようです。...
0
票
1
回答
168
閲覧数
Outlineビューを実現したいが、木構造を一次元のリストで表現できるような構造の名前を知りたい
概要
タイトル通り、実現したい構造があるのですが、いまいち具体的に言語化もできず、どのようにアプローチしたら良いのか分からず困っているので、以下の要件を実現できる構造をご存知であれば教えていただけると非常に助かります。
テーブルに木構造を表示するために、データを一次元配列で提供できる
その際、Orderを保持できる(画像のイメージ)
定数時間での検索が可能O(1)
AppendToParent, ...
1
票
1
回答
301
閲覧数
クイックソートと同時にランキングを作ることはできますか?
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
回答
310
閲覧数
3剤3期クロスオーバーの分散分析:誤差をエクセルで算出したい
3剤3期クロスオーバーの分散分析を、Rで実行しました(以下Rプログラム)。
この分散分析表の誤差「8.5089」をエクセルで算出したいのですが、結果が合いません。(誤差以外は検算できました)
以下に、エクセルの画像を添付しました。
どこの解釈が違うのか、どなたかアドバイスをお願いしてもよろしいでしょうか。
※データは「医薬品開発のための統計解析 第2部p.282」です。
※ 同じ質問を ...
0
票
0
回答
172
閲覧数
ASCIIで記述した回路を図面に変換するアルゴリズムを探す
現在ASCIIで記述したノードとノードとのつながりを図面に変換するアルゴリズムを探します。
特に、Synopsys VerdiのようにVerilog HDL/VHDLコードからきれいな理解しやすい回路図を生成したい。どんなアルゴリズムでこれを果たすことができますか。
ノードの形は何でも構いません。
1
票
2
回答
224
閲覧数
Excel VBA の1回の実行で、通過した通過しなかったfunction、subを分類する方法を教えて下さい
全てのfunction, subに一行ずつ debug.print”function1通過” と書く方法しかありませんか?
書くとしたら、正規表現置き換えの方法で、対応可能ですか?
全エクスポートで、エディタの正規表現置換後、全インポートを予定しています。
例) 全てのfunction, sub2行目に debug.print "なまえ通過” を挿入する方法がありますか?
他言語でも、...
0
票
1
回答
430
閲覧数
クイックソートのpivotが中央値が最も良いとされる理由
クイックソートのpivotが中央値が最もいいとされる理由の認識は下記の通りであっていますでしょうか
以下のような配列があった場合、下のようにpivotに中央値を選び均等に分割できたとします。次にグループAで同じ処理を繰り返すとき、Bの要素は無視してAの中の要素とだけ比較すればよい。Bの要素を無視するので比較回数・交換回数が大幅に減る。Bも同様
よって中央値で分割できると高速で処理できる。
[4,3,...
3
票
2
回答
4,304
閲覧数
クイックソートのpivotの決め方について
情報系学生です
クイックソートではpivotの決め方が非常に重要だと思うのですが、それぞれにどのようなメリットがあるのでしょうか?
①配列から3つ選び、その中の中央値をpivotとする
②配列の先頭2要素を比べ大きい方をpivotとする
③ランダム
④①を繰り返し、①で得られた中央値候補の中央値をpivotとする
正直優先順位的には
④>①>③>②だと思うのですがどうでしょうか
...
4
票
0
回答
141
閲覧数
R木系(特に PR 木)のアルゴリズムを理解したい
位置情報などを効率的にインデックスするための手法として、R木があります。
質問
R木(特に、 PR 木)をどうやって実装するのか、とくに、そのアルゴリズムを知りたいと思っています。当たれる書籍などはありますか?
0
票
1
回答
89
閲覧数
有向グラフの表現で、E = {⟨u, v⟩ | u|v,⟨u, v⟩ ∈ V × V and u ̸= v} の表すものが分からない
有向グラフG=(V,E)の時、V = {1, 3, 4, 5, 6, 12} and E = {⟨u, v⟩ | u|v,⟨u, v⟩ ∈ V × V and u ̸= v} といった表現がされていた場合のEの右辺の表現が理解できません。この場合はどのようなグラフが期待されるのでしょうか?ご教示いただけると幸いです。
4
票
1
回答
345
閲覧数
0-1整数2次計画問題に関する数理最適化のアルゴリズムについて
数理最適化に関するアルゴリズムに関して学習しています。
0-1整数2次計画に関して分岐限定法で厳密解などを解くらしいのですが、
調べても連続変数の2次計画の問題に関する内容が多く、私の検索能力が低くて見つけられません。
0-1整数2次計画問題に関して
https://www.letsopt.com/entry/2019/08/18/131125
...
3
票
2
回答
667
閲覧数
注文IDなどユーザーに見せるユニークなIDの作成方法
プログラムの内部でユニークなIDが欲しい場合は、UUIDが多く用いられると思いますが、
桁数が32桁と、ユーザーに見せる場合、少し桁数が多く複雑すぎるように感じます。
実際、ECサイトなどで購入したさいに得られる注文IDなどははUUIDではなさそうに見えます。
どのようなアルゴリズムで10-15桁程度の注文ID(ユニークID)を生成しているのでしょうか?
0
票
1
回答
160
閲覧数
二分探索木を分割する際の計算量
https://www.geeksforgeeks.org/split-a-bst-into-two-balanced-bsts-based-on-a-value-k/?ref=leftbar-rightbar
こちらのコードを用いてBSTを分割する際の計算量は、O(h)(hはツリーの高さ)ということは直感的には理解できるのですが、どうしても具体的に証明する方法がわかりません。...
1
票
1
回答
73
閲覧数
楽天市場で検索したときにサイドバーにある商品価格の分布はどのようなアルゴリズムで表示されてますか
楽天市場で検索したときにサイドバーにある商品価格の分布はどのようなアルゴリズムで表示されてますか
ぱっと思いつくのはSQLのGROUP BYを使うことですが、
数十万件ヒットする結果でも、非常に高速に表示されていて、
なにか集計用の高速に実行できるようなアルゴリズムがあるのではないかと思っています。
1
票
0
回答
219
閲覧数
バケツソートの最低ケースを改善するためには
バケツソート(Bucket Sort)の平均計算量はO(n)ですが、もしデータが均一に分布してない場合、最悪計算量はO(n^2)になってしまいます。しかし、その場合他のアルゴリズムと組み合わせることによって計算量は改善できるのでしょうか?
教科書からの問題なのですが、二分探索を使用できるというヒントを与えられました。しかし、二分探索を使用する意味がよくわかりません。Merge ...
0
票
1
回答
228
閲覧数
c++でのスタック構造について
逆ポーランドを実装しようとした際に、 while(scanf("%s", s) != EOF) で入力を受け取った後に if(s[0] == '+') で条件分岐が始まるのですが、なぜ s[0] と配列 s のインデックスを 0 に固定したままでも良いのでしょうか?
s[0] の次は s[1] 、さらに s[2] とインデックスを増やしていき、最終的に s[n] が EOF ...
1
票
2
回答
422
閲覧数
計数ソートを入力順にソートした際の安定性
下の疑似コードで実装された計数ソート(Counting Sort)の探索を現在と逆順にした場合、安定したソートを保持したままにするにはどの方法が効率がいいでしょうか?
事実、このアルゴリズムでは入力配列を後ろからソートしないと、同じ要素が現れた場合その要素の順番は逆になってしまい、安定したソートではなくなります。
私は。同じ要素が複数回出現した場合に限り、その要素数-...
2
票
1
回答
4,775
閲覧数
eddsa による暗号化は、 rsa の上位互換ですか?
ssh で利用される暗号化鍵には、長らく RSA が利用されてきました。RSA と比べれば最近になって、 EdDSA の暗号化方式が追加されたようです。
質問
EdDSA による暗号化は、アルゴリズム的には RSA の上位互換ですか? 具体的には、
暗号を破るための計算を行う際の計算量クラスは RSA 以上で
同等のセキュリティを提供するために必要な暗号鍵の長さは RSA 以下で
...
2
票
2
回答
1,048
閲覧数
計算量O(1)とO(n)
https://www.geeksforgeeks.org/analysis-of-algorithms-set-4-analysis-of-loops/?ref=lbp
上記のサイトには、計算量O(1)の例では
// Here c is a constant
for (int i = 1; i <= c; i++) {
// some O(1) ...
0
票
3
回答
275
閲覧数
異なる文字列の接頭語と接尾語を比較
ある文字列S1、S2があるとして、S1の接尾語はS2の接頭語を反転させたものと等しいか比較し、一致する箇所だけをS2から削除したのち、その2つの文字列を連結させるというプログラムを実装したいのですが、効率的な方法はありますでしょうか。
現在は、
S1,S2を読み込む
S1を反転
S1とS2の接頭語を一文字ずつ比較し、一致した回数を数える。一致しなくなった時点で終了。
...
3
票
1
回答
265
閲覧数
帰りがけ順から二分探索木の生成
ネットでは、行きがけ順・通りがけ順、通りがけ順・帰りがけ順からBSTを生成する方法はよく見かけますが、帰りがけ順のみ与えられた場合、そこから探索二分木を生成することは可能なのでしょうか?また、その場合どういったアルゴリズムになりますか?
0
票
1
回答
308
閲覧数
二次元配列に条件付きで数字を代入
与えられた数字を二次元で保存したいです。例えば、数列{3,12,4,1,5,8}を与えられたとして、一番目の数字3を配列1に挿入、二番目の数字12は、3より大きいので別の配列2に挿入、左から走査し、4は12より小さいので配列2に挿入、1は左から走査し3より小さいので配列1に挿入...ということを行いたいです。
構造的には、二次元リスト
int s = {3,12,4,1,5,8}
int ...
0
票
2
回答
115
閲覧数
2つのいくつかのノードを共有する連結リストをソートしたい
最後のいくつかのノードを共有している2つの昇順に整列した連結リストを、一つの連結リストに昇順で整列させる方法はありますか?
たとえば
-900->120->200->230
\
452->700
/
-10->200
...
0
票
1
回答
405
閲覧数
プログラムの実行時間をできるだけ短くしたい
プログラムの実行時間をできるだけ短くしたいです。
最終的なゴールは、入力Nを読み込み、評価して2つの連結リストにそれぞれ結果をストアし、その結果を順に出力することです
入力の条件は、
The first line contains the integer N. The second line contains N integers, a0,a1,...,aN−1. The integers ...
0
票
1
回答
590
閲覧数
一つのプログラムで複数の連結リストの作成
配列を使わず、連結リスト(単方向)のみでキューのデータ構造を実装したいです。 C言語を用いて、一つのプログラムで複数の連結リストを実装することは可能でしょうか?structの定義で行き詰まってしまったので、実例も教えてくださると嬉しいです…。
追記
struct node1
{
int data1;
struct node1 *next1;
};
struct node2
...
0
票
0
回答
155
閲覧数
分析のためにゲーム木を描写したくなったとき、利用可能なライブラリ・フレームワークは何がありますか?
ターン制の対戦ゲームは、基本的にゲーム木を構築できます。たとえば○×ゲーム(tic-tac-toe)のゲーム木はこちらです。
Game tree for Tic-Tac-Toe game using MiniMax algorithm.
今、ふとした分析のために、このようにゲーム木を描写したくなりました。
質問
ゲーム木を描写する機能を持った、つまり、ゲーム木の可視化ができる、...
2
票
1
回答
345
閲覧数
n行n列の表から各行各列1つのセルを選んでその選んだセルの合計値が最大になるようにするアルゴリズム
各セルに数字の書かれたn行n列の表があって、この各セルの数字に下記のルールで丸をつけるとします。
1行あたり必ず1つのセルに丸をつけなければならない(0個でも2個以上でも駄目)
1列あたり必ず1つのセルに丸をつけなければならない(0個でも2個以上でも駄目)
※ つまり全部でn個のセルに丸がつくことになります
この時、この丸をつけた数字の合計が最大になるようにセルを選択する、効率の良い(...
4
票
1
回答
174
閲覧数
カウンタの値が被らないことの確認方法
任意の値からループするカウンタ間の値が被らないことを確認したいのですが、その条件を出しかねています。
数学的にアプローチできると良いのですが、ネタも知識も不足しており、どのようにアプローチすれば良いのかも判断ついておりません。
どのように考えれば良いのかヒントとなる何かでも良いのでご教示いただけたら幸いです。
255までの数値を1~10個格納できる配列がある。格納した個数を格納数とする。
...
-1
票
1
回答
292
閲覧数
Can someone solve level 12 of this logic game
I run into this game and manage to solve level one to eleven but not able to solve level twelve, I think it is recursive algorithm, sorry if this is not question for this site :)
Here is the link
http:...
0
票
1
回答
145
閲覧数
画像編集ソフトなどにある、図形を再編集できる機能のロジック、考え方を教えて下さい。
知りたいこと、やりたいこと
Macのプレビューのような、図形を画像上においた後、再度サイズを変えたり場所を変えたりできるようにする機能を作りたい。
↓
これらを実装する際に、どのように図形の場所やクリックされた位置などを保持しているかを知りたい。
やってみたこと
x軸、y軸、深さ(z-index)、幅、高さを変数にもたせておく
Window上のクリックイベントを検知した際、...
0
票
0
回答
188
閲覧数
1枚の画像からワールド座標を取得する
F地点の座標(xL,yF,zo)を求めたいです.ただし,L,F,Cの座標はわかっているものとします.
何かよい導出方法ありませんか?
考えたこととして,
カメラの外部パラメータから回転並進行列を求めるP3P問題があり,求めようとしましたが,
ワールド座標と画面座標の3つの対応付けが必要で行き詰りました.
よろしくお願いします.
0
票
1
回答
240
閲覧数
値を中心として, 前後にある数だけ幅を取るために使用できるアルゴリズムがありますか
値を中心として, 前後にある数だけ幅を取るために使用できるアルゴリズムがありますか
例えばこの入力で平均値99を基準に, 幅を15とすると
98
174
58
49
78
90
75
170
下のような結果を期待しています.
36-51
52-67
68-83
84-99
100-115
116-131
132-147
148-163
164-179
これは平均値を求め, ...