[アルゴリズム] タグが付いた質問
アルゴリズムとは、プログラミングにおける、問題の解決手段や計算手法、実現手法またはデータ構造の扱い方、操作などを定式化したものです。数式アルゴリズムの妥当性や証明は[数学]タグがあります。データ構造(型)についての質問は[データ構造]があります。
31
質問
6
票
1
回答
766
閲覧数
バイナリ法を用いた多項式の累乗計算について
以前した質問 "冪乗計算を高速に行うには?" の多項式版についての質問です。
次のように「(バイナリ法を用いた)多項式の累乗計算」を行うコードを
Ruby 2.2 および Python 2.7 で作成し、それぞれ (1 + x)^n を計算させたのですが、
Python 2.7版の方が n が34以上で結果がおかしくなってしまいました。
...
4
票
4
回答
997
閲覧数
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 ...
3
票
5
回答
1,563
閲覧数
自身の要素に重複が無い昇順の配列同士で、共通している要素を求めたい
C言語についての質問です。
二つの配列A,Bがありそれぞれに整数が格納されていて、配列の中の数は昇順にソートされていて、配列Aの中には重複する数がなく、それは配列Bについても一緒である。
ただし、配列AとBのサイズは同じとは限らない。
それを踏まえて配列AとBの中には重複する数があり、その重複して含まれる数を出力するプログラムを教えてください🙏
2
票
1
回答
650
閲覧数
n×n board におけるナイト・ツアーの数えあげについて
数理パズルの一つにナイト・ツアー(https://en.wikipedia.org/wiki/Knight%27s_tour)
というものがあります。
nが6以下のときについてn×n board における directed open tour を
以下のコードで数時間かけて数えあげたのですが、
n = 6 のとき0通り(正しくは6637920通り)になるのはどうしてでしょうか?
#...
1
票
1
回答
974
閲覧数
(openssl の) RSA 秘密鍵の中身はそれぞれ何を表す?
openssl で rsa の鍵を適当に test.pem で生成して、その中身を openssl rsa -in test.pem -text -noout で眺めていました。(長いので、この質問の末尾に付与します)
この中で、prime1, prime2 はそれぞれ 1536 == 3072/2bit 長の素数(以降、p, q と呼びます)、 modulus は p * q のかけ算の結果(...
0
票
2
回答
404
閲覧数
エディタの「置換」機能と実質的に同じことをより速く処理する方法はありますでしょうか?
お世話になっております。
実質的に置換と同じことで遙かに処理の速い方法はありますでしょうか?
事例 たとえば以下のようにテキストの置換パターンが複数あったとします。
08A54G→タナ
08A→タ
54G→ナ
テキストエディタの置換のマクロでも変換していけますが、数百万字だとけっこう時間がかかります。
かかる時間とは、テキストエディタや連続置換であるかにもよりますが、速くて5分以上です。
しかし、...
-1
票
2
回答
391
閲覧数
ドット演算子とアロー演算子を用いてベクトルのノルムを求めるアルゴリズムの計算量について
ドット演算子とアロー演算子を用いて、ベクトルのノルムを求めるアルゴリズムについて
前の質問で、ドット演算子とアロー演算子の違いについて質問させていただきましたが、それぞれの演算子によってプログラムの計算量はオーダ記法では違いはあるのでしょうか。
オーダー記法で計算量を考えると、n次元のベクトルが全て0以外だった時にn回、normが計算されるのでおしなべるとO(n)という理解で合っていますか。 ...
15
票
5
回答
1,904
閲覧数
longの飽和演算を行うアルゴリズムを教えてください
longのビット数で加減算の飽和演算を行いたいです。
検索してもSIMD関連の話題ばかり引っかかってしまいます。
int幅であればlongにキャストして演算後、intに戻すという手段を使えますが、longの場合BigIntegerを使用するというのは大げさな気がします。
効率のよいアルゴリズムがあれば教えて頂きたいです。
// SaturationLong
public struct ...
8
票
1
回答
3,539
閲覧数
CRC32とMD5の使い分け
CRC32とMD5はハッシュアルゴリズム?として、どちらもよく利用されていると思います。
けれど、その使い分けはどのように行われているのですか?
6
票
2
回答
2,862
閲覧数
冪乗計算を高速に行うには?
a を整数、n を自然数とします。
一般に a^n の計算を高速に行う方法を教えてください。
なお、この質問は
「特定の n に対して最小の計算回数を求める」
という趣旨の質問ではありません。
(追記)
バイナリ法によるコード(Ruby版およびPython版)を
回答に載せました。
4
票
2
回答
1,581
閲覧数
m×n board におけるナイト・ツアーの数えあげを高速に行うには?
以前の質問(n×n board におけるナイト・ツアーの数えあげについて)
でナイトツアーの数えあげを行いました。
さて、一般に
m×n board におけるナイト・ツアーの数えあげを高速に行うには
どうすればよろしいでしょうか?
以下のコードは、長方形の対称性を利用することで以前の計算の約1/4位になっています。
#include <stdio.h>
int ...
3
票
2
回答
241
閲覧数
同じ数同士線で結んだとき、交点ができるか否かの判定について
ary1 = [1, 3, 3, 2, 2, 1]
を考えることにします。
1と1を上側で結んで、
2と2を上側で結んで、
3と3を上側で結んだとき
(無理やり結んだ曲線を交差させないかぎり)
交点は0個です。
一方
ary2 = [1, 3, 2, 3, 2, 1]
を考えることにします。
1と1を上側で結んで、
2と2を上側で結んで、
3と3を上側で結んだとき
交点は1個でできます。
...
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)...
3
票
2
回答
1,085
閲覧数
Pythonの配列の要素数が0かそれ以外かを判定する方法のパフォーマンス
次のような配列numsがあったときに、配列の要素数が0かそれ以外かを判定する方法で、
実装方法によってパフォーマンスに後述のような差がありました。どういう理由でこのような差が生まれてくるのかを教えてほしいです。
もし可能であればそれらの判定方法の計算量も教えてもらいたいです。
おそらくO(1)であって、O(N)まではいかないにしてもわずかながら差があるのだろうなと思っています。
...
3
票
2
回答
328
閲覧数
2分木へのデータの追加について
「アルゴリズムとデータ構造」紀平拓男/春日伸弥 著 (http://www.sbcr.jp/products/4797324198.html?sku=4797324198)第6章において 、2分木へのデータの追加のコードが紹介されています。
それを今Ruby版に置き換えたつもりなのですが、二つ目のデータの追加のときに上手く動かなくて困っています。
どこを修正すればよいか教えていただけないでしょうか?...
3
票
2
回答
1,905
閲覧数
8パズルで、最初にシャッフルさせる時の考え方
8パズルで、解けないような配置になることはありますか?
・最初にシャッフルさせる場合、単純にランダム配置させるだけでは駄目?
123
456
78
経緯
・ネットに掲載されていた8パズルを試しているのですが、どうしても解けないときがあります
・コード内容によっては、解けない8パズルが出来ることもある?
分からないこと
・参考にしているコードが、そもそも正しいか分からない
・...
3
票
1
回答
773
閲覧数
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
票
2
回答
518
閲覧数
rsa の素数のペアはどのように生成される?
RSA 暗号は、今日日の(ネットワーク)セキュリティまわりの分野で、広く使われている技術だと思っています。
例えば RSA2048 では、「MSB が 2048 bit 目になるような、ただ二つの素数 p, q に素因数分解できるような合成数を、ランダムに生成する」必要があります。
これはちょっと考えて、どうやったらこれが実現できるのかが自明ではないな、と思いました。
質問
今ある RSA ...
2
票
2
回答
951
閲覧数
線分群から、閉図形の数を数える方法を教えて下さい。
仕様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
票
3
回答
453
閲覧数
なぜこのコードはTLEになる?
下のコードは、競技プログラミングの問題 バトンリレーゲーム に対する回答です。サンプルはリストを使用したものを載せました。
同じテストケースでサンプルコードはメモリ時間0.03sだったのに対し自分のコードは1.99sを超えTLE (Time Limit Exceeded) となりました。
しかし、この二つのコードの根本的違いが判りません。どなたかご教授願えないでしょうか?
自分で書いたコード
#...
2
票
2
回答
749
閲覧数
オイラーの分割恒等式をプログラミングで確認するには?
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%...
2
票
4
回答
3,035
閲覧数
計算式『10/3*3』について
お世話になります。
アルゴリズムか言語特有の問題かが解らないのですが…
C#にて、スタックポインタを使用した、逆ポーランド法で式を計算するプログラムを
書いているときですが、計算する変数はdecimalを使って、小数まで計算できる
ようにしたのですが、表題のような計算式を入れると、計算結果が『10.0000000000000000』
桁数は正確に数えたわけではないので、...
1
票
2
回答
296
閲覧数
2からNまでを、素因数分解したときの次数によって並べるには?
以前(2からNまでを、素因数分解したときの素因数の最小値が小さい順に並べるには?)
と異なる規則によって、2からNまでを並びかえを行います。
①2〜Nまでを素因数分解を行い次数のみ取り出すものとします。
②次数の小さい順に並べる。
例えば、N = 10 の場合、次のようになります。
①
2 => 1,
3 => 10,
4 => 2,
5 => 100,
6 => 11,
7 => 1000,
...
1
票
1
回答
853
閲覧数
チェックサムについて
チェックサムについてご質問です。
バイナリデータのチェックサムを作成しています。
チェックサム専用の容れ物は8Byteです。
最初は1Byteずつ全てのデータを足して、それをチェックサムにしようと思いました。(16進数)
しかし、「マイナスしていった方が、2の補数になっていいよ」と言われました。
足していっても大丈夫だと思うのですが、、、
マイナスしていった方が良いという考えが分かる方、
...
1
票
5
回答
1,260
閲覧数
AIZU ONLINE JUDGEの0009で何回やってもTime Limit Exceedと表示されます。
久々にやったAIZU ONLINE JUDGEのこの問題で困ったことが起こったので、質問させていただきます。
問題を解くコードをPython3で書いたのですが、何回やってもTime Limit Exceedと表示されます。証拠となるソリューションはこのリンクにあります。
何が原因で、その解決方法はないのでしょうか?
わかる方、いましたら教えてください。
なお、コードは以下のとおりです。
...
0
票
2
回答
192
閲覧数
最短路問題のワーシャルフロイド法による各ノードにおけるコストを求める問題でのコードのまとめ方について。
コードを書いてみましたが出力が意図した通りになりません。
コメントのグラフを以下のコードの形式で入力して出力を各ノードにおけるコストの合計の羅列にしたいのですが、まだ理解不足です。
解る方よろしくお願します。
#include <iostream>
#include <vector>
using namespace std;
const long long MAX_V = ...
0
票
2
回答
248
閲覧数
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
回答
216
閲覧数
コーディングテスト問題「FrogRiverOne」について
コーディングテスト練習サイトCodilityの「FrogRiverOne」という問題について、問題の理解とコードがなぜあるケースでincorrectになるのかわからず困っています。
FrogRiverOne coding task - Learn to Code - Codility
上記のFrogRiverOneについて日本語で書かれた記事
以下問題文を原文引用しました。...
0
票
1
回答
2,051
閲覧数
ベクトルが与えられた時にノルムを求めるアルゴリズムについて
前提
ベクトル(v = (v1, v2, ...vn)^T))が与えられた時にノルム(√(v^(T)v))を求めるアルゴリズムを考えて、c言語で実装しようとしています。
実現したいこと
①擬似コードで文章になっている部分をどのように記号で表せるのか知りたい
②擬似コードのアルゴリズムを実行するためには、どのように参考記事のプログラムを変更するべきか知りたい
...
0
票
1
回答
183
閲覧数
ヒープの深さと各深さにおける要素数から和を求めるプログラムの時間計算量
今回書いたプログラムの計算量をヒープを構成する要素数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)) に抑えられると考えましたが、...