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

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

絞り込み
並べ替え
タグ付けされた
6
1 回答
766 閲覧数

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

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

自身の要素に重複が無い昇順の配列同士で、共通している要素を求めたい

C言語についての質問です。 二つの配列A,Bがありそれぞれに整数が格納されていて、配列の中の数は昇順にソートされていて、配列Aの中には重複する数がなく、それは配列Bについても一緒である。 ただし、配列AとBのサイズは同じとは限らない。 それを踏まえて配列AとBの中には重複する数があり、その重複して含まれる数を出力するプログラムを教えてください🙏
user30429's user avatar
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通り)になるのはどうしてでしょうか? #...
TOM's user avatar
  • 1,572
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 のかけ算の結果(...
Yuki Inoue's user avatar
  • 1.7万
0
2 回答
404 閲覧数

エディタの「置換」機能と実質的に同じことをより速く処理する方法はありますでしょうか?

お世話になっております。 実質的に置換と同じことで遙かに処理の速い方法はありますでしょうか? 事例 たとえば以下のようにテキストの置換パターンが複数あったとします。 08A54G→タナ 08A→タ 54G→ナ テキストエディタの置換のマクロでも変換していけますが、数百万字だとけっこう時間がかかります。 かかる時間とは、テキストエディタや連続置換であるかにもよりますが、速くて5分以上です。 しかし、...
三太郎's user avatar
-1
2 回答
391 閲覧数

ドット演算子とアロー演算子を用いてベクトルのノルムを求めるアルゴリズムの計算量について

ドット演算子とアロー演算子を用いて、ベクトルのノルムを求めるアルゴリズムについて 前の質問で、ドット演算子とアロー演算子の違いについて質問させていただきましたが、それぞれの演算子によってプログラムの計算量はオーダ記法では違いはあるのでしょうか。 オーダー記法で計算量を考えると、n次元のベクトルが全て0以外だった時にn回、normが計算されるのでおしなべるとO(n)という理解で合っていますか。 ...
user avatar
15
5 回答
1,904 閲覧数

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

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

CRC32とMD5の使い分け

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

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

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

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

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

Pythonの配列の要素数が0かそれ以外かを判定する方法のパフォーマンス

次のような配列numsがあったときに、配列の要素数が0かそれ以外かを判定する方法で、 実装方法によってパフォーマンスに後述のような差がありました。どういう理由でこのような差が生まれてくるのかを教えてほしいです。 もし可能であればそれらの判定方法の計算量も教えてもらいたいです。 おそらくO(1)であって、O(N)まではいかないにしてもわずかながら差があるのだろうなと思っています。 ...
Akiyama Nao's user avatar
3
2 回答
328 閲覧数

2分木へのデータの追加について

「アルゴリズムとデータ構造」紀平拓男/春日伸弥 著 (http://www.sbcr.jp/products/4797324198.html?sku=4797324198)第6章において 、2分木へのデータの追加のコードが紹介されています。 それを今Ruby版に置き換えたつもりなのですが、二つ目のデータの追加のときに上手く動かなくて困っています。 どこを修正すればよいか教えていただけないでしょうか?...
TOM's user avatar
  • 1,572
3
2 回答
1,905 閲覧数

8パズルで、最初にシャッフルさせる時の考え方

8パズルで、解けないような配置になることはありますか? ・最初にシャッフルさせる場合、単純にランダム配置させるだけでは駄目? 123 456 78 経緯 ・ネットに掲載されていた8パズルを試しているのですが、どうしても解けないときがあります ・コード内容によっては、解けない8パズルが出来ることもある? 分からないこと ・参考にしているコードが、そもそも正しいか分からない ・...
re9's user avatar
  • 6,396
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 ...
TOM's user avatar
  • 1,572
2
2 回答
518 閲覧数

rsa の素数のペアはどのように生成される?

RSA 暗号は、今日日の(ネットワーク)セキュリティまわりの分野で、広く使われている技術だと思っています。 例えば RSA2048 では、「MSB が 2048 bit 目になるような、ただ二つの素数 p, q に素因数分解できるような合成数を、ランダムに生成する」必要があります。 これはちょっと考えて、どうやったらこれが実現できるのかが自明ではないな、と思いました。 質問 今ある RSA ...
Yuki Inoue's user avatar
  • 1.7万
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 : ...
mrrclb48z's user avatar
  • 427
2
3 回答
453 閲覧数

なぜこのコードはTLEになる?

下のコードは、競技プログラミングの問題 バトンリレーゲーム に対する回答です。サンプルはリストを使用したものを載せました。 同じテストケースでサンプルコードはメモリ時間0.03sだったのに対し自分のコードは1.99sを超えTLE (Time Limit Exceeded) となりました。 しかし、この二つのコードの根本的違いが判りません。どなたかご教授願えないでしょうか? 自分で書いたコード #...
Ranger's user avatar
  • 71
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%...
TOM's user avatar
  • 1,572
2
4 回答
3,035 閲覧数

計算式『10/3*3』について

お世話になります。 アルゴリズムか言語特有の問題かが解らないのですが… C#にて、スタックポインタを使用した、逆ポーランド法で式を計算するプログラムを 書いているときですが、計算する変数はdecimalを使って、小数まで計算できる ようにしたのですが、表題のような計算式を入れると、計算結果が『10.0000000000000000』 桁数は正確に数えたわけではないので、...
たたぱた's user avatar
  • 1,195
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, ...
TOM's user avatar
  • 1,572
1
1 回答
853 閲覧数

チェックサムについて

チェックサムについてご質問です。 バイナリデータのチェックサムを作成しています。 チェックサム専用の容れ物は8Byteです。 最初は1Byteずつ全てのデータを足して、それをチェックサムにしようと思いました。(16進数) しかし、「マイナスしていった方が、2の補数になっていいよ」と言われました。 足していっても大丈夫だと思うのですが、、、 マイナスしていった方が良いという考えが分かる方、 ...
user19213's user avatar
1
5 回答
1,260 閲覧数

AIZU ONLINE JUDGEの0009で何回やってもTime Limit Exceedと表示されます。

久々にやったAIZU ONLINE JUDGEのこの問題で困ったことが起こったので、質問させていただきます。 問題を解くコードをPython3で書いたのですが、何回やってもTime Limit Exceedと表示されます。証拠となるソリューションはこのリンクにあります。 何が原因で、その解決方法はないのでしょうか? わかる方、いましたら教えてください。 なお、コードは以下のとおりです。 ...
Nagkei10's user avatar
  • 233
0
2 回答
192 閲覧数

最短路問題のワーシャルフロイド法による各ノードにおけるコストを求める問題でのコードのまとめ方について。

コードを書いてみましたが出力が意図した通りになりません。 コメントのグラフを以下のコードの形式で入力して出力を各ノードにおけるコストの合計の羅列にしたいのですが、まだ理解不足です。 解る方よろしくお願します。 #include <iostream> #include <vector> using namespace std; const long long MAX_V = ...
yn95ny's user avatar
  • 162
0
2 回答
248 閲覧数

python のitertools.permutationsの使い方を教えて下さい。全部の組み合わせの作り方を教えて下さい。

1年前の問題ですけど、確かめてみたい。 (参考)小学生のみなさんへ、場合の数「2020年度京都大学理系学部数学第5問」にチャレンジしてみて下さい。 https://qiita.com/mrrclb48z/items/a97086d25b3d0bee7125 ①[1234]×[1234]×[1234]×[1234]/直積(デカルト積,Cartesian Product)の使い方を教えて下さい。 ②...
mrrclb48z's user avatar
  • 427
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/...
mrrclb48z's user avatar
  • 427
0
1 回答
216 閲覧数

コーディングテスト問題「FrogRiverOne」について

コーディングテスト練習サイトCodilityの「FrogRiverOne」という問題について、問題の理解とコードがなぜあるケースでincorrectになるのかわからず困っています。 FrogRiverOne coding task - Learn to Code - Codility 上記のFrogRiverOneについて日本語で書かれた記事 以下問題文を原文引用しました。...
user avatar
0
1 回答
2,051 閲覧数

ベクトルが与えられた時にノルムを求めるアルゴリズムについて

前提 ベクトル(v = (v1, v2, ...vn)^T))が与えられた時にノルム(√(v^(T)v))を求めるアルゴリズムを考えて、c言語で実装しようとしています。 実現したいこと ①擬似コードで文章になっている部分をどのように記号で表せるのか知りたい ②擬似コードのアルゴリズムを実行するためには、どのように参考記事のプログラムを変更するべきか知りたい ...
user avatar
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)) に抑えられると考えましたが、...
user avatar