[アルゴリズム] タグが付いた質問
アルゴリズムとは、プログラミングにおける、問題の解決手段や計算手法、実現手法またはデータ構造の扱い方、操作などを定式化したものです。数式アルゴリズムの妥当性や証明は[数学]タグがあります。データ構造(型)についての質問は[データ構造]があります。
325 件の質問
2
票
1
回答
171
閲覧数
3次元の立方体同士の衝突検知で、GJKアルゴリズムを使ったが、誤検知される
私は、現在主に、c++とvulkan、glmを使って、3Dのゲームを作成しています。
現在、直方体同士の衝突判定を行うためにGJKアルゴリズムを作製しました。
しかし、下の画像のように立方体同士が離れているのに、衝突していると検知されます。下の画像の場合は衝突していると、コマンドライン上に表示されています。
私は以下の画像のような場合は、衝突していないと検知されるようにしたいです。
なお、...
-2
票
2
回答
230
閲覧数
Xでのトレンドを表示する仕組みを知りたい
xのトレンドを表示する仕組みがわかりません。大雑把なフローチャートを日本語で教えてほしいです。それと使っている言語も教えてほしいです。
xはRubyで書かれているらしいのですが、データ分析が得意なpythonなどを使わずにトレンドを表示するのもRubyで行っているのでしょうか。
またデータ分析を行っている言語を使っている理由まで教えていただきたいです。よろしくお願いします。
2
票
0
回答
150
閲覧数
n個の集合の包含関係を求める計算量を減らすには?
n個の自然数の集合 S_1, S_2, S_3, ... S_n が与えられているとします。
この時、i!=j , S_i ⊆ S_j となる i, j が存在するか?という問題を考えます。
素朴な方法ではそれぞれの集合のペアの包含関係を調べることになると思いますが、
この時、集合の包含関係を O(n^2) 回調べる必要があります。
この回数を減らす方法はあるでしょうか?
2
票
1
回答
290
閲覧数
64bit整数の平方根の求め方について
素数の計算のために平方根を求める関数を作成しています。ただし浮動小数の平方根関数は精度の問題で使用しませんでした。関数は以下サイトを参考に作成しました。
64bit数の素数判定
作成したコードは以下の通りです。
/*
* def.h
*/
#ifndef DEF_H_40D70383_4030_8346_DF89_F0F6D9210451
#define ...
1
票
1
回答
430
閲覧数
関数のグラフをプロットする際に、特異点の周辺を取り除く方法
陽に y = f(x) の形で表されている関数のグラフを (x, y) 平面上に描くことを考えます。ただし x_min ≦ x ≦ x_max の範囲に限定してプロットするとします。
素朴には、x_min から x_max まで少しずつ x を変更しながら (x, f(x)) を計算して、それらの点を線分で繋ぐとグラフが描けそうです。
...
0
票
1
回答
58
閲覧数
51. Reverse Words in a String : Inputが"the sky is blue"のとき、"blue is is blue "と出力されてしまう。(期待結果:"blue is sky the")
現在、leetcodeの151. Reverse Words in a Stringを解いています。
下記に問題文(*1)と例(*2)、コード(*3)を載せています。
事象としては、与えられた文字列が"the sky is blue"のとき、"blue is is blue "と出力されてしまいます。
期待結果は"blue is sky the&...
0
票
1
回答
154
閲覧数
文字列結合した際に、文字Kが文字aを消してしまう
現在、leetcodeの1768. Merge Strings Alternatelyを解いています。
下記が問題文(*1)と例題(*2)です
事象は、文字列結合した際に、文字Kが文字aを消してしまうことです。
コードは'(*3)にあります。
この原因と改善方法について教えていただけると幸いです。
*1
2 つの文字列 word1 と word2 が与えられます。 word1 ...
0
票
2
回答
303
閲覧数
マンデルブロ集合の自己相似点を自動検出していい感じの画像を生成したい
マンデルブロ集合を使った画像生成システムを作るにあたって、図中の拡大箇所を自動で検出してくれるような機能を付けたいと思っています。
その際に、出力される画像を出来るだけ複雑な図柄にするために、マンデルブロ集合内の自己相似点を自動検出してそこを拡大していくようなアルゴリズムを考えているのですが、その具体的なコードが思い浮かびません…。
自分は数学がてんでダメなもので、...
1
票
1
回答
306
閲覧数
符号なし64bit変数のビット演算の挙動がおかしい
次の64bit変数 unsigned __int64 にビット演算を行うプログラムについて質問です。
XORで初期化してから6番目のビット反転 val |= (1<<5); を行うと、37 番目も一緒に反転するのはなぜなのでしょうか。
コンパイラとして MSCV や bcc32 を使っても同じ挙動でした。OS は Windows10 64bit です。
32bit変数 unsigned ...
0
票
1
回答
162
閲覧数
2種類のポインタを用いた線形リストの中央の要素の発見の仕方
長さが未知の線形リストの中央の要素はどのようにして見つければよいかという問題について、講義内で速いポインタと遅いポインタの2種類を使うことで見つけることが出来るという説明を講義内で受けたのですが、この速いポインタ、遅いポインタという概念について、解説がされている本やWebページなどがありましたら教えていただきたいです。
0
票
2
回答
1,441
閲覧数
PythonでExcelファイルを比較し更新箇所を上書きするプログラムの組み立て方を教えてください
どのようにプログラムを組み立てたらよいか、概略をご教示いただきたく質問いたしました。
実現したいこと
「ichiran.xlsx」ファイルと「kyou.xlsx」ファイルがあります。
「ichiran.xlsx」ファイルに「kyou.xlsx」ファイルの内容を反映させることを実現したいと考えています。
試したこと
以下を試しましたが、2つのファイルに同じbangouがあっても、...
2
票
1
回答
231
閲覧数
ラベル無し連結単純無向グラフの型の列挙は?
例えば頂点が3個のグラフの場合、それが単純で無向グラフでラベル無しで連結となると2通りだと直ぐに分かる。でも4個となるとイメージしても厄介だし5個だと紙と鉛筆を使っても怪しい。そこでプログラミングで列挙してみたいと思ったのだけどコレが厄介。連結の判断は兎も角、同型の判別が大変。接続行列だと頂点5個でも単純に2^10通りある。連結だからもう少しは減らせるとしても。...
-1
票
1
回答
453
閲覧数
ワードビンゴのビンゴが達成されていることを判定する
各マスが数字ではなく単語(ワード)にアレンジされたビンゴが達成されていることを判定するプログラムの書き方が分かりません。
普通の数字のビンゴゲームではなく、ワードのビンゴなので、とても複雑です。
Javescriptやpython。言語は問いません。
どの様なプログラムを書けば良いのか分からないので、御意見や助言を頂きたいです。
詳細は下記です。
S × S のサイズの、...
2
票
1
回答
255
閲覧数
相異なるn個の数を並べたときの部分単調増加/減少数列で最長なものの長さを調べて分布を確認したい
例えば, 5つの数1,2,3,4,5を並び替えた3,1,5,2,4の場合, 単調増加な部分列で最長のものが1,2,4で単調減少な部分列で最長のものは3,1や3,2、5,2や5,4。したがってこの場合の最長なものの長さは3です。
そのままの1,2,3,4,5なら5となります。
「Erdös Szekersの定理」により, n^2+1個の相違なる数を並べ替えた場合, ...
2
票
1
回答
229
閲覧数
三目並べのAIをAlphaBeta法で実装したが,MiniMax法と同じ動作をしてくれない
三目並べAIをAlphaBeta法で実装しています.
三目並べは以下のサイトを参考にしており,Minimax法で実装されていますが,それをAlphaBeta法に変更しました.
https://github.com/koki0702/tictactoe-ai-youtube
AlphaBeta法はMinimax法の上位互換であり,計算量を少なくしたアルゴリズムであることから,...
2
票
1
回答
232
閲覧数
ある範囲で広義単調増加する数列を列挙する
次の条件を満たす数列を列挙する方法はありますか.
長さがNの正整数列
1 <= A_1 <= A_2 <= ... <= A_N <= M
1 <= N, M <= 10
再帰関数を用いることにより目的は一先ず達成出来ましたが,配列のコピーのためパフォーマンスは悪いものと想像します.
N = 2
M = 3
a = [0] * N
def dfs(...
-1
票
1
回答
220
閲覧数
ある条件を満たす、matrixクラスのオブジェクトを生成したい
C++でmatrixクラスのオブジェクトで、以下の条件を満たすものを作成したいです。
オブジェクトの列数はSである
オブジェクトは0か1を成分に持つ
オブジェクトのそれぞれの行の要素の和はNである
ここで、S個の成分のうち、N個、1を選ぶ組み合わせは、M = S C N (Cはコンビネーション)通り、存在します。したがって、
オブジェクトの行数はMである
...
0
票
1
回答
585
閲覧数
Javaでテーブルでの集計方法と画面に表示する集計方法が異なる場合の処理
こんにちは。
業務でJavaのインターフェースを設計しているのですが、
どのような処理にすればよいかわからない点があり、ご質問させていただきます。
設計しているのはテーブルからレコードを取得してきて、出力編集して画面に返却するようなインターフェースになります。
java8、db2を使用しています。
○処理概要について
下記のような点数テーブルがあるとして
名前
年月
学期
国語
数学
英語
...
0
票
1
回答
242
閲覧数
クイックソートのパーティションの定義について
現在、ALDS1_6_B を行っています。
解答コードは、以下のようになります。
その中で、パーティションの中で使われているint i = p-1の意味がわかりません。
なぜ、iは、p-1を行っているのでしょうか? どういう理由で、p-1を定義しているのでしょうか?
また xを閾値として、for文の中で比較して、x未満とx以上を分けていると思うのですが、
なぜiを使うことで、...
1
票
1
回答
646
閲覧数
最長経路問題とベルマンフォード法について
非負の重み付き有効グラフに対しての最長経路問題がNP困難である事は存じ上げています。しかし、各辺の重みを-1倍したグラフに対し、ベルマンフォード法を用いて最短経路問題を解けば、必然的に最長経路問題も解けるような気がしたのですが何が問題なのでしょうか。
3
票
3
回答
407
閲覧数
セット商品の最適な内訳を選択するアルゴリズムを知りたい
顧客から商品の購入依頼があります。
その商品を最適なセット商品の購入に変更して、最安の値段で購入したいです。
よいアルゴリズムがあれば教えていただきたいです。
例)
顧客からの購入依頼
商品A 20個 単価200円 合計金額4000円
商品B 10個 単価300円 合計金額3000円
セット商品
商品ABセット 金額 450円
内訳
商品A 1個
商品B 1個
上記の場合、...
1
票
2
回答
205
閲覧数
1次元配列を木構造の形に成形したい
自身のIDと親IDを持つOriginalDataを木構造の形にしたいと考えています。
inputDatasをresultの形に変換したい
再帰的な処理をしたいのですが、いい方法が思いつきません。
言語は特に何でも大丈夫です。
struct OriginalData {
let id: String
let parentID: String?
}
struct Node {
let ...
0
票
1
回答
176
閲覧数
ダブルハッシュを使用したオープンアドレス法について
現在、AIZU ONLINE JUDEGE ALDS1_4_Cをやっています。
その中で、ダブルハッシュを使用したオープンアドレス法を学んでいます。
以下がオープンアドレス法のコードです。
#include <stdio.h>
#include <string.h>
using namespace std;
using ll =long long;
#define M ...
0
票
2
回答
509
閲覧数
Python で再帰処理を高速化するには?
以下問題についてです。
atcorder 270 問題3
https://atcoder.jp/contests/abc270/tasks/abc270_c
提出したところ10問のテストが時間切れとなってしまいます。
現在pythonでatcorderに取り組んでいるのはpython力をつけたいという目的もあり、他の言語は使いたくないと考えています。
...
4
票
1
回答
409
閲覧数
0-1整数2次計画問題に関する数理最適化のアルゴリズムについて
数理最適化に関するアルゴリズムに関して学習しています。
0-1整数2次計画に関して分岐限定法で厳密解などを解くらしいのですが、
調べても連続変数の2次計画の問題に関する内容が多く、私の検索能力が低くて見つけられません。
0-1整数2次計画問題に関して
https://www.letsopt.com/entry/2019/08/18/131125
...
1
票
2
回答
270
閲覧数
和がkとなるようなn個の非負整数の順列を全列挙する
和がkとなるようなn個の非負整数の順列を重複なく全列挙する方法が知りたいです.
ナイーブに実装しましたがO(k^n),これより計算量が改善される解法は存在しますか.
# Python 3.10.5
from itertools import product
def sol(n, k):
for perm in product(range(k+1), repeat=n):
...
0
票
1
回答
150
閲覧数
C++で挿入ソートを実装する際、一時変数の役目が分からない
挿入ソートについて学習しており、一つ疑問があるのですが、なぜ temp の変数を使わなけばならないのでしょうか?
挿入ソート | Programming Place Plus アルゴリズムとデータ構造編
正しい挙動のコード:
int arry[] = {5,2,8,3,1};
for (int i = 1; i < 5; i++)
{
int temp = ...
0
票
1
回答
632
閲覧数
キューの末尾の判定について~リングバッファ~ アルゴリズムとデータ構造
現在、こちらの記事を読んでいてリングバッファの際の末尾の判定基準が分かりません。
#include <iostream>
#include <vector>
using namespace std;
const int MAX = 100000; // キュー配列の最大サイズ
int qu[MAX]; // キューを表す配列
int tail = 0, head = 0; ...
-1
票
1
回答
396
閲覧数
Atcoder ATC001 A 深さ優先探索をC++で再帰を用いて実装したがTLEになってしまう
ATC001 A 深さ優先探索をC++で以下のように実装しましたが、88個中12個TLE、2個MLEになってしまいました。
再帰を用いています。
goalの座標も引数に渡して、v=goalとなったらreturnするというのも試しましたが、ダメでした。
どう直せば良いでしょうか。
#include <bits/stdc++.h>
using namespace std;
vector&...
3
票
2
回答
290
閲覧数
表を辞書型に直す再帰関数について
画像のような表があり、それを下記のようなjson型に変形したいと考えています。
(途中にリストはないものとしました。)
再帰関数を使って組もうとしているのですが、途中のキーが飛んでしまったりとうまく組めずにいます。
アルゴリズムに強い方、お力添えいただけないでしょうか?
使用モジュール
openpyxl
試した実装
キーで同じレベルのものをリスト化(①)し、下位のレベルのものも同様にリスト化(②)。...
1
票
2
回答
765
閲覧数
テンパズルをpythonで解くプログラム
wikipediaより
テンパズル(10パズル)は、4桁の数字を一桁の数字4つとみなし、これに四則演算などを用いて10を作る遊び。メイクテン(make10)とも呼ばれる。切符の番号や車のナンバープレートなどでの短時間の遊びに利用され、日本経済新聞で渋滞時の時間の潰し方として紹介されたことがある。
一般的なルールとしては、四則演算のみの使用を許可し、数字の並べ替えも許可されるが、...
3
票
1
回答
298
閲覧数
二分探索木を用いて英単語をキーとした連想配列を動的に作りたいが、連想配列が期待通りの動作をしてくれない。
上の表題にもある通り、二分探索木を利用して動的なハッシュマップを自分で作ろうとしたのですが、私が書いた以下のコードは実行しても入力に対して期待された出力をしません。
どのように以下のコードに改善すれば、期待された出力を得られるのでしょうか?
とても読みづらいコードになってしまっていて申し訳ないのですが、アドバイスを頂けると大変助かります。
実行したコード:
#include <stdlib....
5
票
1
回答
251
閲覧数
ランダムに複数引いた通路の幅が同じになるように整形する方法
ランダムでダンジョンのマップを作成しようとしています。
上の画像のように2つの部屋があり、その間を、2マスの幅がある通路でつなぎます。
通路の始点、終点や折れ曲がる地点はランダムで決まります。
さらに通路を追加します。
二度目以降に通路を追加する際、以前に引いた通路を気にせずに引くので、以前に引いた通路と一部が重なったり、隣り合ったりする場合があります。
こうして2、3回通路を引いた後で、...
2
票
1
回答
216
閲覧数
Ruby 要素がn個の配列を2つに分ける全ての組み合わせ
arr = [1,2,3,4,5]
このような配列を
[1,2,3],[4,5]
[1],[2,3,4,5]
[1,2],[3,4,5]
[3,4],[1,2,5]
というように2個の配列に分割したうえでの全ての組み合わせを検討したいです。
arr.permutationで行列を計算し、each_slice(2) #arr.sizeが奇数ならば+1
等を試してみましたが、...
0
票
1
回答
200
閲覧数
蟻本P.164の問題のセグメント木での累積和の計算で意図した内容と異なる内容が出力される。
セグメント木での累積和の計算を入力してみましたが意図した内容と合いません。
出力される内容をresではなく、datb[k] * (r - l) + datc[k]の内容のように正しくしたいです。
#include <iostream>
using namespace std;
typedef long long ll;
const int MAX_N = 100000;
const ...
0
票
1
回答
297
閲覧数
Pythonにおける変数の値参照について質問です
LeetCodeのアルゴリズム第83問について質問です。
https://leetcode.com/problems/remove-duplicates-from-sorted-list/
以下問題文と入力,出力例です。
Given the head of a sorted linked list, delete all duplicates such that each element ...
2
票
0
回答
85
閲覧数
レイティングを利用した推薦システムのアルゴリズム手法について
現在、レビューサイトにおける商品推薦システムのアルゴリズム改善に携わっております。
検索者が希望条件(例えば、機能、価格、使いやすさなど)とその重視度を入力すると、商品の利用者であるレビュアーが入力した各要素のレイテイングをもとに検索者の希望条件に合致すると思われる商品をランキング形式で提示し、商品詳細とレビューが見れるようなサイトです。
そこで質問なのですが、...
3
票
1
回答
188
閲覧数
gurobi からpyomoへの変換
pythonでgurobiからpyomoへ二次制約付き問題であるため、変更したいのですがやり方がわからなくて困っています。
from gurobipy import *
import pandas as pd
import numpy as np
import csv
from pyomo.environ import SolverFactory
opt = SolverFactory("...
1
票
1
回答
117
閲覧数
Zbuffer法以外の方法でポリゴンの描画順位を決定する方法
Zbuffer法 = ポリゴンの面を描画画面のピクセル単位で分割し、1px毎に描画優先順位の決定(奥行方向の並び順の決定)を行う処理する。
という認識をしておりますが、この方法以外でポリゴンの描画優先順位を決定する方法について探してます。
ネットで調べても調べ方が悪いのだと思いますがうまく見つけることができませんでした。
現状、下記条件での優先順位決定処理を考えています。
▼条件
...
0
票
1
回答
330
閲覧数
区間が重なるタイミング
それぞれある周期で循環する0と1の数列があります。
例:
010101010101...(周期2)
001100110011...(周期4)
000111000111...(周期6)
ここで、縦列が全て1になる最初の列番号やその割合を求めたいです。
上の例では最初に4列目(次に12列目)で1が揃い、無限数列全体の1/6が揃っています。
最初の列番号を求める方法は今のところ、...
1
票
2
回答
675
閲覧数
1から100までの数字をそれぞれ1つずつを100個使って、偶数もしくは奇数が4回以上続かないように並べる(配列を作る)アルゴリズム
タイトルにもあるとおり、
1から100までの数字をそれぞれ1つずつを100個使って、偶数もしくは奇数が4回以上続かないように並べる(配列を作る)アルゴリズムを教えていただきたいです。
例えば
x = [99,1,4,5,2,66,45...]
length(x)
→100
のようなものを作成したいです。
条件にもあるとおり、よくないパターンは
1, 偶数が4回以上続いている(奇数も同様)
x = [...
0
票
1
回答
335
閲覧数
最小全域木問題のプリム法のプライオリティキューを使った方法での入力と出力に関する問題
最小全域木問題のプリム法のプライオリティキューを使った方法で任意の入力をして結果を表示させたいが思うようにいきません。
addEdgeにcinを挿入して実行してみましたが出力が上手くいきません。
g.addEdge()のような形で入力の内容を代入できますか?解る方お願いします。
入力:
7 9
0 1 1
1 2 2
1 3 3
1 5 7
2 4 10
3 5 1
3 6 5
4 5 5
5 6 ...
0
票
2
回答
300
閲覧数
ワーシャルフロイド法を使った経路復元のコードをまとめてみましたが結果の出力が思うようにいきません。
ワーシャルフロイド法を使って経路復元のプログラムを書いてみましたが結果の出力が思うようにいきません。
vector get_path(int s,int t)のvector ansへのまとめ方が悪いと思うのですがどうでしょうか?
#include <iostream>
#include <vector>
using namespace std;
const int ...
0
票
2
回答
207
閲覧数
最短路問題のワーシャルフロイド法による各ノードにおけるコストを求める問題でのコードのまとめ方について。
コードを書いてみましたが出力が意図した通りになりません。
コメントのグラフを以下のコードの形式で入力して出力を各ノードにおけるコストの合計の羅列にしたいのですが、まだ理解不足です。
解る方よろしくお願します。
#include <iostream>
#include <vector>
using namespace std;
const long long MAX_V = ...
1
票
1
回答
219
閲覧数
粒子フィルタの有効サンプルサイズ (Effective Sample Size, ESS)について
粒子フィルタの有効サンプルサイズとして、以下の式があります。
※オリジナルは以下にあります。
https://qiita.com/Crafty_as_a_Fox/items/d70864ab555f91fef720#%E3%83%AA%E3%82%B5%E3%83%B3%E3%83%97%E3%83%AA%E3%83%B3%E3%82%B0%E3%81%AE%E3%82%BF%E3%82%A4%...
1
票
1
回答
416
閲覧数
コサイン類似度結果が思った通りの結果と違う理由はなぜでしょうか?
プログラミング初心者です。
コサイン類似度を勉強している際、入力したデータが明らかに違うのにも関わらず、結果値が高い値を示します。
AとBの比較では0.89という妥当な値が出ますが、AとDはデータの内容が明らかに違うにも関わらず0.9という結果が出ます。
これはなぜなのでしょうか?
言語はjavascriptです。
let A = [20,60,80];
let B = [20,80,40];
...
6
票
4
回答
1,120
閲覧数
rsa で用いる素数 p, q がもし素数ではなかったら何がおこる?
rsa の素数のペアはどのように生成される? の問いで調べていった結果、 RSA の秘密鍵(素数 p, q) は Miller-Rabin のテストによって、確率的にそれが素数であることを判定しているのだ、ということを学びました。ここでふと、これだけ世の中で RSA 鍵が使われているのであれば、そのうちのひとつぐらいは、 Miller-Rabin の素数判定を Pass ...
5
票
0
回答
69
閲覧数
Proof of Stakeのコンセンサスアルゴリズムで、validatorを選ぶノードは分散的に存在しているのでしょうか?
Proof of Stakeのコンセンサスアルゴリズムは、Stakeしているコインの量に応じてランダムにValidatorが選ばれ、ValidatorがTransactionを承認します。不正するとStakeしているコインが没収されてしまうため、不正をしないモチベーションが働きます。そのため、51%攻撃は実質不可能とされています。
色々な資料を読んでいても、...
1
票
1
回答
199
閲覧数
Sphinxで「|漢字《よみ》」という記法で文章中に振り仮名をつけたい場合、Sphinx拡張で対応は可能でしょうか?
Sphinx拡張についての質問です。
私が持っていない良いアイデアがあればと思い質問します。
よろしくお願いします。
<質問>
Sphinxで「|漢字《よみ》」という記法で文章中に振り仮名をつけたい場合、Sphinx拡張で対応は可能でしょうか?
<背景>
明示的に「単語」単位で切り出せる「.. index::」「.. glossary::」「:index:」では、「よみ|...
0
票
1
回答
416
閲覧数
三目並べ、三つの盤面で同時、✖のみ使用 先手の必勝法を考える
このゲームでは先手に必勝法がある。参照Youtube:Numberphile 3 board tic tac toe
ただし、プログラミングに落とし込むぐらいの簡単な必勝法がみつからない。
目標はその必勝法を利用して疑似AIを作ること。
ルール:
このゲームの盤面は基本的に三つの三目ならべのボードで構成されている
参加者二名が使う印は”X”で共通
ひとりずつ任意の格子に印をつける
...