[アルゴリズム] タグが付いた質問
アルゴリズムとは、プログラミングにおける、問題の解決手段や計算手法、実現手法またはデータ構造の扱い方、操作などを定式化したものです。数式アルゴリズムの妥当性や証明は[数学]タグがあります。データ構造(型)についての質問は[データ構造]があります。
318
質問
0
票
1
回答
213
閲覧数
KMP法が分からないので調べているのですが
リンク先下表について
Q1
・「abbabbababに対するシフト幅」とはどういう意味ですか?
・「検索テキスト」と「パターン」を比較しているわけではなく、事前の「パターン」同士の比較テーブルを作成する時の話?
・「abbabbabab」はパターンのこと??
Q2
・備考欄に「一致なし」と記載されていますが、どういう意味?
・「何」と「何」が一致していないのでしょうか?
1
票
0
回答
1,585
閲覧数
Levenberg-Marquardt法の結果がEigenとGnuplotで異なるのはなぜでしょうか
C++の数値計算ライブラリEigenに含まれる、非線形最小二乗法(Levenberg-Marquardt法)で関数フィッティングを実行してみました
開発環境はVisual Studio 2015です
フィッティング対象の関数は、y = a×cos(x)^b で、ノイズを含む観測データx,yからパラメータa,bを求めます
#include <iostream>
#include <...
1
票
2
回答
754
閲覧数
球内のグリッドの交点の座標をすべて求めたい
3次元空間において、r = (x, y, z)を1点決めて、
これを中心とした半径nの球を考えます。
次に、この球の内部をグリッドで細かく立方体に分割します。
この立方体の辺の長さはmとします。
このとき、グリッドの交点の座標をすべて計算したいです。
やりたいことのイメージは、3次元の球で図を書くのが難しいので、
2次元の円で図を書きました。以下がそれです。
グリッドの交点の座標(赤色の点)...
0
票
2
回答
356
閲覧数
入力された値の商が0.000001以下になるまで割り算
javaScript勉強中です。超初心者です。よろしくお願いいたします。
もし入力された数字が2から10の間の時、その入力された数字の商が0.000001以下になるまで2で割り続け、小数第6位以下(0.000001)に到達するまで何回割ったかというコードを書いています。例えば7/2を小数第6位まで割り切るのに23回割り算しました。という結果が欲しいです。
以下が自分のコードです。
...
0
票
2
回答
8,676
閲覧数
C#でスレッドセーフなシングルトンクラスを実装したい
タイトルの件、WCFサービス上でシングルトンクラスを扱うことを想定してスレッドセーフな
実装をしたいと考えております。
検索もしてみたのですが、いくつか方法があるようで実際どれが正しいのか
よく分かりません。。
大変恐縮ですが、サンプルコード等のリンクでも構いませんので、
ご教示頂けないでしょうか?
4
票
1
回答
684
閲覧数
グラフ理論について、三次元空間における位置関係の情報をinvariantに保持する表現を計算したい
グラフ理論に関する質問です。
頂点(ノード)間の位置関係をinvariantに保持する方法・表現を考えたいです。
具体的な例として、ある化合物の分子を考えます。
ここで、その分子内の原子(グラフにおける頂点)たちと、
各原子の三次元座標(3次元ベクトル)が与えられています。
この三次元座標を用いて、頂点間の距離(グラフにおける辺の長さ)などが計算できます。
ここで、化合物内のある原子(...
0
票
1
回答
608
閲覧数
文字がCODE128の範囲かチェックしたい
掲題の件、バーコード入力でCODE128の文字をアプリ(例えば画面)で受け付けた後、
それが本当にCODE128の範囲にあるかチェックするロジックを検討しております。
例えば、正規表現で一発で出来る等の情報がありましたら
ご教示頂きたく、よろしくお願いいたします。
開発言語はC#で、Windows Forms画面のTextBoxでバーコード入力を受け付ける場合を
想定しています。
3
票
2
回答
930
閲覧数
ビッグオー、ビックシータの計算方法 (関数に再起がある場合、if文がある場合等)
引数 n が負の整数でなく、アルゴリズムの実行時間 = 代入の数 + 数を加算する数とする場合のビッグオー、ビッグシータの求め方について、
(1)
fnc(n){
a=0 // +1回
if nが奇数:
for i = 1 to n: // +n回
a += 1; // +n回
return a;
}
↑...
0
票
2
回答
434
閲覧数
データベースから取得したオブジェクト同士の親子関係をハッシュで表現したい
実現したいこと
D3.js のTreeView(以下画像のような)に利用するjsonを、Ruby on Railsアプリケーションのデータベースから動的に作成したい。
具体的には、
Item(name:string, parent: string) # ただし、parentは、ツリービューにおける親の名前を指す)
のようなItemモデルのオブジェクトが多数@itemsとしてあり、
...
-3
票
1
回答
495
閲覧数
指定した通りに配列の要素を書き換えたい
二次元配列の要素を、別の配列のデータに従って入れ替えたいです。
今、1つの配列に縦5横6の二次元配列があり、配列(array)の中身は全て "." で埋まっています。つまりarrayは
array = [
[".",".",".",".",".","."],
[".",".",".",".",".","."],
[".",".",".",".",".","."],
[".","....
3
票
2
回答
1,228
閲覧数
DOT言語の有向グラフが木構造か木構造でないかの判定方法を教えて下さい。
①有向グラフが木構造か木構造でないかの判定方法を教えて下さい。
②rootは入力ですか
よろしくお願いします。
(参考)DOT言語
https://ja.wikipedia.org/wiki/DOT%E8%A8%80%E8%AA%9E
(参考)WebGraphviz is Graphviz in the Browser
http://www.webgraphviz.com/
(判定)
...
0
票
1
回答
601
閲覧数
lzwの圧縮、解凍について
お世話になります。
今回、初めてGIFファイルの勉強をしようと、lzwの圧縮、解凍をC#で組んでみたのですが、
どうもうまくいきません。
圧縮まではうまくいっているようなのですが、解凍しようとすると、余計なところに『0』が
入ってしまい、正しく解凍されません。
ほかサイト様など、さまざまなところを拝見させていただいているのですが、どうも
原因がわかりません。
...
0
票
2
回答
2万
閲覧数
C# App.configのデータ取得について
C#のApp.configについての質問です。
アプリを立ち上げたときに、App.configからドロップダウンリスト1のデータおよび、その他のドロップダウンリスト2のデータを読み取りたいと思っています。また、keyとそのvalueは後に使用するので、まだ実装していませんが、App.configから読み込むときに、配列もしくはリストに格納しようと考えています。
App....
2
票
1
回答
1,483
閲覧数
多面体の頂点群もしくは平面群から三角ポリゴンメッシュの作成
3Dグラフィックスで凸型多面体を描画したいと考えています。
多面体はそれを囲む平面(境界無し)で定義されているため、順序を問わないのであればすべての頂点を取得することが出来ますが、三角ポリゴンメッシュをねじれ等なく作成するスマートな方法が分かりません。
0
票
2
回答
2,323
閲覧数
C#でのソースファイル間でのデータ
初歩的な質問で恐縮なのですが、質問させて頂きます。
言語:C#
現在、以下の順で動くアプリを作成中です。
ファイルデータを読み込む → 読み込んだデータを変換処理 → 変換して出力
以上の処理を。勉強のため各処理を別ファイル、別クラスにしています。
ByteWorkという変数の中にファイルデータを読み込んだり、変換、出力したいと思っています。
...
0
票
2
回答
1,951
閲覧数
チェックサムの格納byte数
チェックサムについてご質問です。
バイナリファイル(最大2048kbyte)のチェックサムを作成します。
チェックサムは1byte毎にマイナスしていき、その合計値とする予定です。
下記url参照
チェックサムについて
その際、チェックサムを格納する所は4byteです。
そこで質問なのですが、4byteに収まりきれないはどのようにすればよろしいでしょうか。
また、一般的(...
1
票
1
回答
798
閲覧数
チェックサムについて
チェックサムについてご質問です。
バイナリデータのチェックサムを作成しています。
チェックサム専用の容れ物は8Byteです。
最初は1Byteずつ全てのデータを足して、それをチェックサムにしようと思いました。(16進数)
しかし、「マイナスしていった方が、2の補数になっていいよ」と言われました。
足していっても大丈夫だと思うのですが、、、
マイナスしていった方が良いという考えが分かる方、
...
2
票
1
回答
4,703
閲覧数
Word2vecの追加学習について
Word2Vecの追加学習について質問します。
あるコーパスを一度学習し、ベクトルを生成した後、そのコーパスに未知語を追加したら、未知語のベクトル化をするためにはゼロからコーパスを再学習する必要があるのでしょうか?
(要するにコーパスを継ぎ足して繰り返し学習したいです)
西尾泰和さんの、『word2vec による自然言語処理』によると、ネガティブサンプリングは「...
1
票
1
回答
360
閲覧数
makeによってつくられたデータ構造の参照渡し
makeによってデータ構造の参照を作り、関数に参照を渡しデータの変更を行います。
以下のような出力になるのはなぜでしょうか?
https://play.golang.org/p/lOC49HmVcq
package main
import (
"fmt"
)
func main() {
a := make(map[string]int)
set(a)
fmt....
0
票
1
回答
288
閲覧数
rubyで書いた二分探索の再帰コードを評価お願いします
バイナリーサーチ/二分探索のコードを再帰を使ってRubyで自分なりに、実装してみました。
採点というか評価していただけないでしょうか? 正しく動くのですが、書き方としてどうなのかが心配でした。
※bubble_sort(list)で昇順ソートすると仮定してください。
def binary_search(list,target)
sorted_list = bubble_sort(list)
...
7
票
1
回答
3,774
閲覧数
長方形と円の衝突判定を行うコードを教えて下さい
2Dのゲームで長方形と円の衝突判定プログラムを書きたいのですが、計算方法を教えて下さい。
長方形の中心を P0, 横幅の半分をw/2, 縦幅の半分を h/2 とします。
円の中心は P1, 半径を r とします。
これらのパラメーターを使って円と長方形が交差しているか否かを判定するアルゴリズムとコードを教えて下さい。長方形は必ず軸に平行です。
0
票
4
回答
2,202
閲覧数
連続する整数値の中に「7」がいくつ出現するか数えるプログラムの高速化
大学で行っているプログラミングの問題で「連続する整数値の中に出現する「7」がいくつあるかを数えてください。」という問題が出題されました。
例えば[7, 99]なら、「1,2,3,4,5,6,7」 と 「1,2,3,...,97,98,99」の数字の中にいくつ7が出現するかというもので、7なら1、99なら20という答えになります。
(77は7が2個出現するので2個とカウントする。)
よって答えは[...
2
票
4
回答
2,869
閲覧数
計算式『10/3*3』について
お世話になります。
アルゴリズムか言語特有の問題かが解らないのですが…
C#にて、スタックポインタを使用した、逆ポーランド法で式を計算するプログラムを
書いているときですが、計算する変数はdecimalを使って、小数まで計算できる
ようにしたのですが、表題のような計算式を入れると、計算結果が『10.0000000000000000』
桁数は正確に数えたわけではないので、...
3
票
0
回答
111
閲覧数
git で subtree strategy でのマージの挙動は?
git merge -s subtree とすると、 subtree の strategy でマージを行うことができます。このときのマージを計算するアルゴリズムの挙動が、いまいちわかっていないです。
疑似コードぐらいの粒度で、このマージアルゴリズムの挙動を説明すると、どのようなものになりますか?
4
票
2
回答
314
閲覧数
画像を比率を保ったまま端数なく縮小するパーセンテージの求め方
ヘタすると小学生レベルの計算なのかもしれないのですが、
例えば 128x80 の画像があったとして、
これが丁度縦横端数なく縮小できるパーセンテージを求める公式のようなモノはありますでしょうか?
Google Sheetsで下記のように一覧を出して求めてもさして時間はかからなかったのですが、よい方法があれば知りたいです。
追記:本当にやりたいこと
比率を保ったまま縮小をしたいです。
...
4
票
2
回答
578
閲覧数
リナックスのはじめの方のコードでつまずきました。
以下のような三行のコードがありました。。。順番は不問です。
#define BUILD_BUG_ON(condition) ((void)sizeof(char[1 - 2*!!(condition)]))
struct boot_params boot_params __attribute__((aligned(16)));
BUILD_BUG_ON(sizeof ...
1
票
2
回答
930
閲覧数
このコードから三角関数表がどうして作られるのかわかりません
このコードから三角関数表がどうして作られるのかわかりません。
実行すると確かに三角関数表なのですが、奇っ怪な方法の理由はわかります。
sinを一度しか呼ばないという制限のためです。
けれど、その後どうしてこんな方法でと思ったので質問します。
static void make_sintbl(int n, float sintbl[])
{
int i, n2, n4, n8;
...
8
票
7
回答
3,702
閲覧数
数値からランダムに値を取り出す『軽い』方法
お世話になります。
かなり初歩的な質問になってしまいますが、お許し下さい。
0から19までの連続した値があるとし、そこから重複せずに
六つだけ取り出したいと思います。
やりたいことはたったこれだけなのですが、下記の条件を満たす方法で
実現したいと思っています。
1.コレクションなどの機能は使用しない
2.forやifなどといった、基本的な処理だけで実現したい
3.取得した後も、...
4
票
1
回答
2,089
閲覧数
無限ループはどのようにして検出しているのですか?
windowsなどでプログラムが応答しないという記述が表示されることがありますが、
このような応答の応答がないプログラムを検出するプログラムはどのようになっているのですか?
毎回毎回プログラム以前の無知な質問ですみません
【追記】
「イベントが一定時間以上の間処理されない」
C++/cliかC#の入門で一番最初にウインドウだけを作るプログラム(いわゆるhello worldプログラム)...
0
票
1
回答
740
閲覧数
python3で深さ優先探索の再帰関数が上手く機能しない
こんにちは。python3で作ったこちらの再帰関数が上手く機能しません。
def func(teleports_string):
strings = [{n[0],n[1]} for n in teleports_string.split(',')]
start = {'1'}
def search(strings,point,...
0
票
1
回答
418
閲覧数
JPEGとMPEGでの圧縮後データ量の比較
ボードカメラで撮像した連続画像を、1枚1枚JPEG圧縮する場合の合計と、1つのMPEG画像に圧縮する場合、どちらが小さなファイルサイズになるか見当をつけたいと考えています。
どんな画像にもよるかと思いますので、VGA 640 x 480 pixel, 8 bit color, 30 fps, 30秒間 で、カメラは固定して(背景はほとんど動かない)画面サイズの1/4くらいの大きさの物体が、...
0
票
2
回答
263
閲覧数
いい試合順にランク付けするアルゴリズム
スポーツ等の複数の試合をリアルタイムにいい試合順にランク付けするプログラムを作成しています。
いい試合の基準として、時間が大きくかつ点差が小さいものがいい試合だと考えれれます。
つまり、x軸を時間y軸を点差とした時に、試合の1時的な情報の集合を取得し、時間、点差を正規化し、グラフを描画した時に右下にある試合がいい試合(時間が経過しているのに点差が開いていない)ということになり、左上にある試合(...
3
票
2
回答
2,604
閲覧数
立っているビットを数える方法
1バイトの文字中に立っているビットの数をスマートに数える方法を
ご存じの方、ご教示いただけませんでしょうか。
ライフゲームを作成しようと構想した際に、周りのセルの状態をビットで表現すれば
次世代の行動(繁殖、維持、死滅)が判断できると思った事からこう考えるに至りました。
ビットを立てる立てないの準備段階でカウントすればいいじゃないかと、まったくの無駄手間だと
思いこの方式は使わない事にしましたが、...
0
票
2
回答
844
閲覧数
異なる文字数の、文字列類似度の算出方法は?
下記が50%だとすると、
天下
天一
下記は類似度何%になるでしょうか?
・一致数4 ÷ 全文字数22 × 100 = 22%でしょうか?
・また、この場合、「天下」から見た「天下一武道会へ出場してみたいけど」も、「天下一武道会へ出場してみたいけど」から見た「天下」の類似度も同じ?
天下
天下一武道会へ出場してみたいけど
その他、どんな「算出方法」や「考え方」...
2
票
1
回答
232
閲覧数
ランレングスのデータ構造がわかりません
WWWBBをW3B2にすると圧縮できる、というのは理解できました。しかし、11111000ならどうでしょうか?
1503と圧縮してしまうと展開時に1503と展開も出来てしまいます。
そこで1:5 0:3のように [繰り返す文字:繰り返し回数] と言うフォーマットをとれば正しく展開できます。
ただ、ここでいうコロンとスペースをバイナリでうまく表現ができません。ランレングスは一体どのようにして"...
3
票
2
回答
414
閲覧数
罫線で書かれたテーブルをhtmlに変換したいが…
お世話になります。
プレーンテキストで書かれた、下記のようなテーブルを、htmlに変換したいと思っています。
特に言語は特定しませんが、正規表現の置換などを使用して、徐々にtableタグに落とし込んでいきたいと思っているのですが、流石に途中で頭が破裂しそうになりました。
じっくりやればできるような気もしますが、できれば良いアイデアをいただければと思います。
...
14
票
4
回答
2,393
閲覧数
ログインシステムのためのパスワードのハッシュ方式、互換性、照合方法について
ログインシステムについて質問があります。
パスワードを暗号化ではなくハッシュ関数を使い符号化する安全性と使い方はわかりました。
またそれに文字を足して何回か行う、ということもわかりました。(ソルトとストレッチングのことです)
そこで質問があります。
SHA256を使おうと思っているのですが、ハッシュ化という行為は元に戻せないということでした。いずれ新しいタイプのハッシュを使おうと思った際に、...
0
票
1
回答
225
閲覧数
同じ数同士左から順に線で結んだとき、交点ができるか否かの判定について
昨日質問した
同じ数同士線で結んだとき、交点ができるか否かの判定について
の一般化を考えてみました。
ary1 = [1, 1, 2, 3, 3, 3, 2, 2, 1]
を考えることにします。
1と1を左から順番に飛ばさず上側で結びます。
同様に2と2を、3と3を飛ばさず上側で結びます。
(無理やり結んだ曲線を交差させないかぎり)
交点は0個です。
一方
ary2 = [1, 1, 3, 2,...
3
票
2
回答
240
閲覧数
同じ数同士線で結んだとき、交点ができるか否かの判定について
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個でできます。
...
0
票
2
回答
1,420
閲覧数
レーベンシュタイン距離は、「置換に割り振るコストの値」によって結果が異なる?
「kitten」「sitting」、2単語間のレーベンシュタイン距離は、設定によって「3」だったり「5」だったりするのでしょうか?
・「レーベンシュタイン距離」はあくまでも考え方であって、正式な公式は存在しない?
・あるいは、公式はあるけれども、そこへ割り振るコストは自由に設定可能ということでしょうか?
・一般的には置換コストは「1」「2」、何れなのでしょうか?
上の変形では挿入・削除・...
4
票
2
回答
2,130
閲覧数
使用頻度を計算するには?
直接プログラミングに関係するわけではありませんが、アルゴリズムの話なのでこちらに質問させていただきます。
いま、アプリ一覧を使用頻度の高い順にソートしたいと考えています。
そこでアプリ起動頻度として、起動と起動のあいだに経過した時間の平均を取るという方法を取っています。
しかしこの方法では、過去によく使用していたが、...
0
票
3
回答
970
閲覧数
ヒープデータ構造について
n 個の要素を持つヒープの、高さ h における節点が n/2^(h+1) 個である、理由がわかりません。
問題文の原文はこちらです:
Show that there are at most ⌈n/2^(h+1)⌉ nodes of height h in any n-element heap.
以下がIntroduction to Algorithms 練習問題6.3-...
1
票
2
回答
173
閲覧数
pythonのsortについて
あるlistの中の0を全部最後に移動する問題がありました。
たとえば[0,1,0,3,4,5]->[1,3,4,5,0,0]
回答を見たところ、一行で可能でした
(numsをinputのlistとすると)
nums.sort(cmp=lambda a,b:-1 if b==0 else 0)
しかしこのコードの括弧の中がよく理解できません。
どなたか解説していただけないでしょうか?...
1
票
1
回答
447
閲覧数
フィボナッチ数列の下20桁を高速に求めるには?
大きな自然数nに対しても、
フィボナッチ数列f(n)の下20桁を高速に求める
にはどうすればよろしいでしょうか?
なお、私は以下のように
f(n)を高速に求め(※)、mod をとりました。
# (a + b√x)^nの計算
def power(a, b, x, n)
return [1, 0] if n == 0
c, d = power(a, b, x, n >> 1)
...
0
票
1
回答
1,052
閲覧数
四則演算と論理演算で実行速度を比較した表はありませんか
私は今アルゴリズムの高速化を考えています
簡易的に演算手順から高速化できているか知るすべがほしいです。
そこで、四則演算と論理演算の実行速度について普遍的で一般的な実効速度の比較が行われていないか探しています。
例えば、レジスタ内にすでに値がある状態から答えを得るまでの時間の大小関係または、具体的なクロック数などのデータはありませんか?
0
票
1
回答
707
閲覧数
逆ポーランド記法に関して
お世話になります。
プログラムの初心者で、電卓を作ろうという気持ちから、この逆ポーランド記法に
たどり着きました。
各サイト様の情報を調べてみて、何とか動くところまで組めたのですが、最後の最後で
釈然としないところがあります。
通常の記述、『5 / 14 * 2 + 3』という式を処理させてみたのですが、逆ポーランドでは
『5,14,2,*,/,3,+』になってしまいます。(3.17857.....
2
票
2
回答
186
閲覧数
Java WEBAppでCollectionの内容物を全て表示用に加工するアルゴリズムについて
Java / WebApplicationでの話です。
たとえば、DBから、下記のようなDTOコレクションを取得します。
public class Model {
private Long id;
private String data;
private Date date;
private boolean enabled;
...getter ...
5
票
2
回答
6,527
閲覧数
リストから取り出した3つの整数の合計が0になる組み合わせ
EDIT: 最初に投稿した時は、N個の整数の合計の一般解を求める問題だと思っていたのですが、一般解だとNP完全問題になってしまうので、出題者の意図は3つ限定だったのだろうと思います。ですので3つの合計に改題しました。回答を考えてくださった皆さんすみません!
ある任意の長さのリストに符号つきの整数が格納されています。値の重複を許します。そこから3つの整数を取り出すとき、...
2
票
3
回答
940
閲覧数
「nをk個の相異なる数に分割する」場合の数を高速に求めるには?
「nをk個の相異なる数に分割する」場合の数をf(n, k)とします。
例えば、10 = 1 + 2 + 7 = 1 + 3 + 6 = 1 + 4 + 5 = 2 + 3 + 5
なので、f(10, 3) = 4です。
f(n, k)を高速に求めるにはどのようにすればよろしいでしょうか?
以下大変遅いコードです。
# nをk個の相異なる数(最大値がl)に分割
def g(n, l, k)
...
1
票
2
回答
3,656
閲覧数
Rubyでアルゴリズムを学ぶのに適した書籍やサイトを教えてください [クローズ済み]
はじめまして、よろしくお願い申し上げます。
以下質問となるので、お答えいただければ幸いです。
例えばなのですが、15枚の絵札から5枚のカードを引くプログラムを書いてください.
といった問題をRuby言語で学習する場合に適した書籍、サイトなどあるのでしょうか??
上記のようなテスト行い、基準点に達することができず、アルゴリズムの学習をよりしなければと強く思いググっみたのですが、...