[アルゴリズム] タグが付いた質問
アルゴリズムとは、プログラミングにおける、問題の解決手段や計算手法、実現手法またはデータ構造の扱い方、操作などを定式化したものです。数式アルゴリズムの妥当性や証明は[数学]タグがあります。データ構造(型)についての質問は[データ構造]があります。
273
質問
1
票
2回答
188 件の閲覧数
swift playgrounds while文のネストについて
swift playgroundsで何度目かの学び直しをしています。
画像のとおりにコードを打ちまして、赤い宝石までは順調に行くのですが、宝石のマスで止まってくれず、そのまま素通りしてしまいます。
while文のネストが良くないのでしょうか?
!isOngem が解除されたら(宝石のマスに来たら)外枠のwhile文から抜けてcollectGemしてほしいのですが、そのまま真っ直ぐ歩いてしまいます。
...
1
票
2回答
135 件の閲覧数
ランキングの取得と更新の計算量のうち、最悪の計算量を最小化するには?
ゲームのスコアランキングを考えます。各ユーザーに対して、スコアがただ一つ紐づいているとします。このとき、あるユーザーが与えられた時、全ユーザーの中で何番目のスコアを持っているかを知りたいとします。
このようなランキングのデータ構造は、取得と更新の計算量がトレードオフの関係にあると思います。
というのも、例えば各ユーザスコアデータについて、愚直にユーザーをキーにしたハッシュテーブルに入れておき、...
1
票
1回答
120 件の閲覧数
numpyで2つの三次元座標点列の引き当て
numpyで2つの三次元座標点列の引き当てをできるだけ高速に行いたいのですが、行き詰まっています。
<前提>
numpyのround()とbuiltinsのround()は挙動が異なります。
(これ自体は質問の主旨ではありませんが、これについても解説いただけると大変ありがたいです。)
>>> print(round(411105.886185, 5))
...
1
票
2回答
561 件の閲覧数
球内のグリッドの交点の座標をすべて求めたい
3次元空間において、r = (x, y, z)を1点決めて、
これを中心とした半径nの球を考えます。
次に、この球の内部をグリッドで細かく立方体に分割します。
この立方体の辺の長さはmとします。
このとき、グリッドの交点の座標をすべて計算したいです。
やりたいことのイメージは、3次元の球で図を書くのが難しいので、
2次元の円で図を書きました。以下がそれです。
グリッドの交点の座標(赤色の点)...
1
票
1回答
597 件の閲覧数
チェックサムについて
チェックサムについてご質問です。
バイナリデータのチェックサムを作成しています。
チェックサム専用の容れ物は8Byteです。
最初は1Byteずつ全てのデータを足して、それをチェックサムにしようと思いました。(16進数)
しかし、「マイナスしていった方が、2の補数になっていいよ」と言われました。
足していっても大丈夫だと思うのですが、、、
マイナスしていった方が良いという考えが分かる方、
...
1
票
2回答
240 件の閲覧数
Ulam number の効率の良い求め方について
Ulam number とは以下の性質を持つ数である。
(http://en.wikipedia.org/wiki/Ulam_number)
①今まで現れた相異なる2つの Ulam number の和で表そうとしたとき、1通りしか出来ない。
注)相異なる2つの Ulam number の和で表せないときは、Ulam number ではない。
N = 339 とし、
N 以下の Ulam ...
1
票
3回答
1万 件の閲覧数
ビットスワップの方法
固定ビット長さ(例16bit)のビットの順序をビット単位で反転(スワップ)する方法を教えてください。
例:0001 1010 1100 1000 を 0001 0011 0101 1000
C言語の標準ライブラリに含まれる関数だけを使用するものとしますが、ワークエリアについては特に制限をもうけません。
1
票
2回答
984 件の閲覧数
グラフ構造で節点にデータを入れたい
グラフ構造を実装しようとしています。
枝の距離をデータとして格納する方法はどの教科書を見ても詳細に記載されていましたが、節点の場合どうすればよいか分かりません。
O'Reilly Japan - アルゴリズムクイックリファレンスP.154
隣接行列のデータ構造
int A[][]=
{
{0, 0, 0, 0, 0, 0},
{6, 0,18, 0, 0, 0},
...
1
票
1回答
213 件の閲覧数
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:...
1
票
1回答
86 件の閲覧数
リストのある要素より小さい直前(直後)の要素を取得する
以下の2つの関数をより少ない行数に、または実行効率を改善する方法はあるでしょうか。
よろしくおねがいします。
findNextLessEqual()
リストの各要素に対して、同じかより小さい次の要素のインデックスを取得する
findLastLessThan()
リストの各要素に対して、より小さい直前の要素のインデックスを取得する
L = [100, 101, 102, 100, 103, ...
1
票
4回答
331 件の閲覧数
32ビット整数がでたらめな順に入っているファイルに入っていない32ビット整数を一つ見つけてください。
Q.最大で40億個の32ビット整数がでたらめな順に入っているファイルがあるとします。このファイルに入っていない32ビット整数を一つ見つけてください。
『珠玉のプログラミングー本質を見抜いたアルゴリズムとデータ構造』 column2.1.A より
と言う問題です。
本に載っている解き方としては、
40億個の整数を最初のビットが0のものと1のものにわけて、...
1
票
1回答
194 件の閲覧数
関数のグラフをプロットする際に、特異点の周辺を取り除く方法
陽に y = f(x) の形で表されている関数のグラフを (x, y) 平面上に描くことを考えます。ただし x_min ≦ x ≦ x_max の範囲に限定してプロットするとします。
素朴には、x_min から x_max まで少しずつ x を変更しながら (x, f(x)) を計算して、それらの点を線分で繋ぐとグラフが描けそうです。
...
1
票
1回答
376 件の閲覧数
ソートに必要な最低計算量は n log n ではないのか?
長さ n の配列をソートするには、最低でもオーダーで n log n の時間計算量が必要だと聞きました。しかし Wikipedia のソートの記事を見ると、バケットソートやバイトニックソートの平均時間計算量は n log n を下回っているように見えます。何故でしょうか?
1
票
1回答
676 件の閲覧数
ビットDPの思考回路について
以下のコードのアルゴリズムの思考回路がよくわかりません。
ビットDPを使っているらしいのですが、どういう風にビット演算子を使うとDPになるのか原理が分かりません(なぜDPが成立するのかがわからない)。
また、どのようにすればこのような思考でコードをかけるのでしょうか?
どなたか分かる方はいらっしゃるでしょうか?
コード元: 第16回日本情報オリンピック 予選4
#include<...
1
票
1回答
382 件の閲覧数
DeepLearningの学習データ(jpeg、raw)と組み込みシステムについて
私は画像を使ったディープラーニングについて勉強しています。
今回疑問があり皆様の意見を聞きたく投稿しました。
一般的にWebの画像認識に使用する学習データは容量を少なくする為、jpeg画像が多いと思います。
しかし、組み込みシステムで使用するカメラ画像は圧縮せずにraw形式の画像をメモリに保存し認識処理すると思います。
ここで、Web上の学習モデル(jpeg)を使用した場合、...
1
票
2回答
171 件の閲覧数
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回答
264 件の閲覧数
n進グレイコードからn進表記へ戻すには?
n進グレイコードの出力を行った
(参考:n進グレイコードの出力について)
ので、その逆をやってみました。
# n進表記から n進グレイコードへ
def to_gray(n, k, str)
str.rjust(k + 1, '0').split('').each_cons(2).map{|d| (d[1].to_i - d[0].to_i) % n}.join
end
# ...
1
票
2回答
1,784 件の閲覧数
隣り合う2数の差は3以上、1つおいた数との差も3以上の順列は何通りあるか?
次の問題を考えています。
(http://www004.upp.so-net.ne.jp/s_honma/mathbun/mathbun113.htm)
1からNまでのN個の整数で、
ア)隣り合う2数の差は3以上、1つおいた数との差も3以上
という条件を満たす順列は、何通りあるだろうか?
ただし、順番を逆にしたものもそれぞれ1つずつ数えるものとします。
(より一般的には次のような問題です。
...
1
票
1回答
381 件の閲覧数
Goで幅優先探索をしてみようとして不思議な挙動に出会う
お気楽goプログラミングというサイト
http://www.geocities.jp/m_hiroi/golang/puzgo01.html
で幅優先探索を学んでいましたが、
makePathを使うところでappendと使うと
[0 2 4 6]を2回出力します。
プリントデバッグしたところ何度か同じものをキューに入れていますが
どうしてそのような動きをしているのかわかりません
...
1
票
1回答
278 件の閲覧数
2分木を使ったマップについて
「アルゴリズムとデータ構造」紀平拓男/春日伸弥 著 (http://www.sbcr.jp/products/4797324198.html?sku=4797324198)第6章において 、2分木を使ったマップのコードが紹介されています。
前回の質問「2分木のデータ追加、サーチ、削除について」のHiroshi Yamamotoさんの回答をもとにRuby版で置き換えました。
しかし、key:6を追加、...
1
票
0回答
63 件の閲覧数
ノードの長さを自由に持てるツリーの最適配置アルゴリズム
現在、マインドマップを自作しようとしておりますが、ノードの配置のアルゴリズムについて困っています。
作ろうとしているツリーの条件は以下を考えています。
Y軸のトップにルートノードを1つ持つ
親ノードから、子ノードを複数持つことができる
ノードとそれを連結する線は重ならないが、可能な限り近くに配置される
親ノードのX軸の位置は、その子ノードの中央になる
X軸方向で、...
1
票
1回答
65 件の閲覧数
楽天市場で検索したときにサイドバーにある商品価格の分布はどのようなアルゴリズムで表示されてますか
楽天市場で検索したときにサイドバーにある商品価格の分布はどのようなアルゴリズムで表示されてますか
ぱっと思いつくのはSQLのGROUP BYを使うことですが、
数十万件ヒットする結果でも、非常に高速に表示されていて、
なにか集計用の高速に実行できるようなアルゴリズムがあるのではないかと思っています。
1
票
0回答
195 件の閲覧数
要素数nのヒープの深さと各深さにおける要素数を求める方法について
ヒープの深さと各深さにおける要素数を求める方法について調べていますが、関数などを見つけることができず、どのように求めるべきかわかりません。
import heapq
a = [6, 3, 2, 4, 5]
heapq.heapify(a)
例えば上記の場合、手で図を描いてみると、ヒープの深さ(0始まりとする)は最大で2となり、各深さにおける要素数は深さ0で1, 深さ1で2、深さ2で2となります。...
1
票
0回答
70 件の閲覧数
ベクトルで表せる能力値を持ったキャラクター(個体)たちのうち、上位互換が存在しないものたちを選びたい
たとえば、 RPG のキャラクターは、いろいろな能力値をもっています。(体力・素早さ・etc...)
つまりは、それぞれのキャラクター能力は、ベクトルで表せる、と表現できます。
# 例えば、 pandas を用いてキャラクター能力値を表現する
chara1 = pd.Series({'power': 1, 'speed': 2, 'magic': 3})
chara2 = pd.Series({...
1
票
0回答
627 件の閲覧数
BPE (Byte Pair Encoding、バイト対符号化)の効率のいい実装について
お世話になっています。さて厳密にはBPEではないと思いますが、類似のアイディアを文字列に適用したものがあります。
辞書に3つの単語があるとします(本番はもっと巨大な辞書を使います)
我
喜欢
水果
そして次の入力を取ります。
我喜欢水果
これを1文字ずつに分解します。
我 喜 欢 水 果
隣り合う2つの文字を連結して辞書引きをします。
我喜
喜欢 <- in the dic
...
1
票
0回答
1,266 件の閲覧数
Levenberg-Marquardt法の結果がEigenとGnuplotで異なるのはなぜでしょうか
C++の数値計算ライブラリEigenに含まれる、非線形最小二乗法(Levenberg-Marquardt法)で関数フィッティングを実行してみました
開発環境はVisual Studio 2015です
フィッティング対象の関数は、y = a×cos(x)^b で、ノイズを含む観測データx,yからパラメータa,bを求めます
#include <iostream>
#include <...
1
票
1回答
394 件の閲覧数
フィボナッチ数列の下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
票
4回答
1,637 件の閲覧数
連続する整数値の中に「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個とカウントする。)
よって答えは[...
0
票
1回答
861 件の閲覧数
データ構造とアルゴリズムは実務ではどんなシーンで役立つのか? [クローズ済み]
現在スタック、キュー、ツリー、ソートなどを始めとしたデータ構造とアルゴリズムの勉強をしています。これはエンジニアの基礎的なスキルだから(と世間様が言ってる)という理由が私のモチベーションです。
ですがここで質問です。
質問
これらが重要と認識されてる方は、これまでご自身の開発でどのようなシーンで使ってきたか教えてもらいたいです。もしできれば、...
0
票
3回答
741 件の閲覧数
ヒープデータ構造について
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-...
0
票
5回答
1,832 件の閲覧数
公開鍵暗号方式に疑問があります
どうして公開鍵で鍵をすることができて
公開鍵で鍵を開けられないのですか?
公開鍵で鍵を出来るのなら
誰でもなりすますことが可能ですよね
それって暗号として意味がありますか?
0
票
2回答
333 件の閲覧数
0
票
1回答
355 件の閲覧数
私の作った乱数はストリーム暗号に使えますか?
x,yを任意の置換とし秘密に保ちます。aをバイナリ配列とします。
この時次の処理をします。
z=xyx^-1
y=z
a^=a[z]
このようにして生成された出力aは次の出力の推測が難しいでしょうか?
またこの乱数はストリーム暗号に使えますか?
https://gist.github.com/anang0g0/d6be8c3a21be68f6895f10d06ae48938
0
票
1回答
509 件の閲覧数
Judy arrayとは何ですか?
連想配列のようですが
連想配列ならmapやすでにSTLで用意されているで十分に足りると思うのですが
なぜ、Judy arrayというものが生まれたのですか
mapやsetと比べてそちらで用意されているものは何が大きく違うのですか?
0
票
3回答
302 件の閲覧数
配列の中央値を求めるプログラムで毎回0しか出力されない問題について
繰り返し処理の各処理におけるパフォーマンスの中央値を求めるプログラムを書いています。
以下の記事を参考にして、配列から中央値を求める部分を書きました。
Vectorの平均値と中央値を求める
コンパイルエラーはなく、実行時の出力において、中央値の箇所が毎回「0」になってしまうという問題があります。
どのように、プログラムを修正すべきか検討がつかず、教えていただきたいです。
出力
173,
...
0
票
3回答
926 件の閲覧数
ダイクストラ法における辺の重みの正負における出力のちがいについて
単一始点最短経路問題で負の閉路がある場合、アルゴリズムとしてベルマンフォード法が適用され、負の閉路がない場合、ダイクストラ法が適用されますが、閉路でなくても辺の重みが負数の場合ダイクストラ法の出力が正しくない原因は何でしょうか。
以下のダイクストラ法の参考コードを辺の重みが非負数の場合と負数を含む場合で実行したところ、出力が変わりましたが、その理由がわかりません。
閉路でなくても、...
0
票
1回答
171 件の閲覧数
C++での深さ優先探索が無限に終わらない
https://atcoder.jp/contests/abc074/tasks/arc083_a
この問題をDFS(深さ優先探索)で解こうと思い、実装してみたのですが、下記の入力例3で無限ループになってしまい解けません。
なぜでしょうか?
書いたコード:
#include <bits/stdc++.h>
int a, b, c, d, e, f;
std::vector<...
0
票
2回答
322 件の閲覧数
入力された値の商が0.000001以下になるまで割り算
javaScript勉強中です。超初心者です。よろしくお願いいたします。
もし入力された数字が2から10の間の時、その入力された数字の商が0.000001以下になるまで2で割り続け、小数第6位以下(0.000001)に到達するまで何回割ったかというコードを書いています。例えば7/2を小数第6位まで割り切るのに23回割り算しました。という結果が欲しいです。
以下が自分のコードです。
...
0
票
1回答
257 件の閲覧数
文字がCODE128の範囲かチェックしたい
掲題の件、バーコード入力でCODE128の文字をアプリ(例えば画面)で受け付けた後、
それが本当にCODE128の範囲にあるかチェックするロジックを検討しております。
例えば、正規表現で一発で出来る等の情報がありましたら
ご教示頂きたく、よろしくお願いいたします。
開発言語はC#で、Windows Forms画面のTextBoxでバーコード入力を受け付ける場合を
想定しています。
0
票
2回答
1,721 件の閲覧数
C#でのソースファイル間でのデータ
初歩的な質問で恐縮なのですが、質問させて頂きます。
言語:C#
現在、以下の順で動くアプリを作成中です。
ファイルデータを読み込む → 読み込んだデータを変換処理 → 変換して出力
以上の処理を。勉強のため各処理を別ファイル、別クラスにしています。
ByteWorkという変数の中にファイルデータを読み込んだり、変換、出力したいと思っています。
...
0
票
2回答
1,558 件の閲覧数
チェックサムの格納byte数
チェックサムについてご質問です。
バイナリファイル(最大2048kbyte)のチェックサムを作成します。
チェックサムは1byte毎にマイナスしていき、その合計値とする予定です。
下記url参照
チェックサムについて
その際、チェックサムを格納する所は4byteです。
そこで質問なのですが、4byteに収まりきれないはどのようにすればよろしいでしょうか。
また、一般的(...
0
票
1回答
745 件の閲覧数
四則演算と論理演算で実行速度を比較した表はありませんか
私は今アルゴリズムの高速化を考えています
簡易的に演算手順から高速化できているか知るすべがほしいです。
そこで、四則演算と論理演算の実行速度について普遍的で一般的な実効速度の比較が行われていないか探しています。
例えば、レジスタ内にすでに値がある状態から答えを得るまでの時間の大小関係または、具体的なクロック数などのデータはありませんか?
0
票
1回答
444 件の閲覧数
0
票
1回答
185 件の閲覧数
再帰を用いたプログラムの計算複雑度について
ある面で、最も広い面積の正方形の辺の長さを求めるプログラムを書いています。
入力された配列の要素が0なら黒、1なら白とし、白の面積が最大となる場合の1辺の長さを出力します。
困っていること
動的計画法で書いた再帰表現を含むプログラムを実行しているのですが、計算複雑度のオーダを考える時に、最悪の場合「square(M, i+1, j+1) + 1 」が何回繰り返されるかに依存すると考えられます。
...
0
票
2回答
286 件の閲覧数
ダイクストラ法で最短経路を見つけるときに負の値を持つ辺があると経路は正しくても誤ったコストが出力される
ダイクストラ法のコード(python)を参考に以下のプログラムを実行しました。
出力として最短ルートは'A->C->B->D'と求められましたが、コストは「5+(-4)+1=2」になるところ、'A->B->D'の「3+1=4」が出力されました。原因がわからないです。
グラフ部分はコードのrouteにあたります。
出力
$ python dijkstra.py
visited to A.
...
0
票
1回答
367 件の閲覧数
JPEGとMPEGでの圧縮後データ量の比較
ボードカメラで撮像した連続画像を、1枚1枚JPEG圧縮する場合の合計と、1つのMPEG画像に圧縮する場合、どちらが小さなファイルサイズになるか見当をつけたいと考えています。
どんな画像にもよるかと思いますので、VGA 640 x 480 pixel, 8 bit color, 30 fps, 30秒間 で、カメラは固定して(背景はほとんど動かない)画面サイズの1/4くらいの大きさの物体が、...
0
票
1回答
132 件の閲覧数
画像編集ソフトなどにある、図形を再編集できる機能のロジック、考え方を教えて下さい。
知りたいこと、やりたいこと
Macのプレビューのような、図形を画像上においた後、再度サイズを変えたり場所を変えたりできるようにする機能を作りたい。
↓
これらを実装する際に、どのように図形の場所やクリックされた位置などを保持しているかを知りたい。
やってみたこと
x軸、y軸、深さ(z-index)、幅、高さを変数にもたせておく
Window上のクリックイベントを検知した際、...
0
票
3回答
252 件の閲覧数
曜日を出力するプログラム
ある日の曜日を知るプログラムの書き方を教えてほしいです。
実行例はこのようになればいいです。
$ ./a.out
年: 1999
月: 10
日: 7
1999年10月7日は木曜日です。
0
票
1回答
94 件の閲覧数
Pythonにおけるnonlocalの挙動について
質問
preorder traversalとinorder traversalをつかって。木の復元をしたいと思っています。ぐぐったら後述のページが出てきました。Solutionに書かれたソースコードを見てみるとnonlocalがないのにnonlocalであるかのような挙動を意図している部分があります。この挙動について解説してほしいです。
...
0
票
1回答
113 件の閲覧数
データ構造のヒープへの挿入方法について
データ構造のヒープへの挿入方法で質問です。
ヒープへの挿入は、今あるノードの末尾に新しいノードを追加し、
その後、ヒープの条件を満たすような修正のオペレーションをすることだと
書籍「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」で見ました。
ネットでしらべても同様でした。
また挿入の計算量はlogH (Hは完全二分木の高さ)だとも見ました。
ここで疑問です。
...