[アルゴリズム] タグが付いた質問
アルゴリズムとは、プログラミングにおける、問題の解決手段や計算手法、実現手法またはデータ構造の扱い方、操作などを定式化したものです。数式アルゴリズムの妥当性や証明は[数学]タグがあります。データ構造(型)についての質問は[データ構造]があります。
317
質問
0
票
2
回答
241
閲覧数
PythonでExcelファイルを比較し更新箇所を上書きするプログラムの組み立て方を教えてください
どのようにプログラムを組み立てたらよいか、概略をご教示いただきたく質問いたしました。
実現したいこと
「ichiran.xlsx」ファイルと「kyou.xlsx」ファイルがあります。
「ichiran.xlsx」ファイルに「kyou.xlsx」ファイルの内容を反映させることを実現したいと考えています。
試したこと
以下を試しましたが、2つのファイルに同じbangouがあっても、...
2
票
1
回答
170
閲覧数
ラベル無し連結単純無向グラフの型の列挙は?
例えば頂点が3個のグラフの場合、それが単純で無向グラフでラベル無しで連結となると2通りだと直ぐに分かる。でも4個となるとイメージしても厄介だし5個だと紙と鉛筆を使っても怪しい。そこでプログラミングで列挙してみたいと思ったのだけどコレが厄介。連結の判断は兎も角、同型の判別が大変。接続行列だと頂点5個でも単純に2^10通りある。連結だからもう少しは減らせるとしても。...
-1
票
1
回答
347
閲覧数
ワードビンゴのビンゴが達成されていることを判定する
各マスが数字ではなく単語(ワード)にアレンジされたビンゴが達成されていることを判定するプログラムの書き方が分かりません。
普通の数字のビンゴゲームではなく、ワードのビンゴなので、とても複雑です。
Javescriptやpython。言語は問いません。
どの様なプログラムを書けば良いのか分からないので、御意見や助言を頂きたいです。
詳細は下記です。
S × S のサイズの、...
2
票
1
回答
120
閲覧数
相異なる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
回答
114
閲覧数
ある範囲で広義単調増加する数列を列挙する
次の条件を満たす数列を列挙する方法はありますか.
長さがNの正整数列
1 <= A_1 <= A_2 <= ... <= A_N <= M
1 <= N, M <= 10
再帰関数を用いることにより目的は一先ず達成出来ましたが,配列のコピーのためパフォーマンスは悪いものと想像します.
N = 2
M = 3
a = [0] * N
def dfs(...
2
票
1
回答
151
閲覧数
三目並べのAIをAlphaBeta法で実装したが,MiniMax法と同じ動作をしてくれない
三目並べAIをAlphaBeta法で実装しています.
三目並べは以下のサイトを参考にしており,Minimax法で実装されていますが,それをAlphaBeta法に変更しました.
https://github.com/koki0702/tictactoe-ai-youtube
AlphaBeta法はMinimax法の上位互換であり,計算量を少なくしたアルゴリズムであることから,...
-1
票
1
回答
158
閲覧数
ある条件を満たす、matrixクラスのオブジェクトを生成したい
C++でmatrixクラスのオブジェクトで、以下の条件を満たすものを作成したいです。
オブジェクトの列数はSである
オブジェクトは0か1を成分に持つ
オブジェクトのそれぞれの行の要素の和はNである
ここで、S個の成分のうち、N個、1を選ぶ組み合わせは、M = S C N (Cはコンビネーション)通り、存在します。したがって、
オブジェクトの行数はMである
...
0
票
1
回答
230
閲覧数
Javaでテーブルでの集計方法と画面に表示する集計方法が異なる場合の処理
こんにちは。
業務でJavaのインターフェースを設計しているのですが、
どのような処理にすればよいかわからない点があり、ご質問させていただきます。
設計しているのはテーブルからレコードを取得してきて、出力編集して画面に返却するようなインターフェースになります。
java8、db2を使用しています。
○処理概要について
下記のような点数テーブルがあるとして
名前
年月
学期
国語
数学
英語
...
0
票
1
回答
174
閲覧数
クイックソートのパーティションの定義について
現在、ALDS1_6_B を行っています。
解答コードは、以下のようになります。
その中で、パーティションの中で使われているint i = p-1の意味がわかりません。
なぜ、iは、p-1を行っているのでしょうか? どういう理由で、p-1を定義しているのでしょうか?
また xを閾値として、for文の中で比較して、x未満とx以上を分けていると思うのですが、
なぜiを使うことで、...
1
票
1
回答
283
閲覧数
最長経路問題とベルマンフォード法について
非負の重み付き有効グラフに対しての最長経路問題がNP困難である事は存じ上げています。しかし、各辺の重みを-1倍したグラフに対し、ベルマンフォード法を用いて最短経路問題を解けば、必然的に最長経路問題も解けるような気がしたのですが何が問題なのでしょうか。
1
票
2
回答
94
閲覧数
1次元配列を木構造の形に成形したい
自身のIDと親IDを持つOriginalDataを木構造の形にしたいと考えています。
inputDatasをresultの形に変換したい
再帰的な処理をしたいのですが、いい方法が思いつきません。
言語は特に何でも大丈夫です。
struct OriginalData {
let id: String
let parentID: String?
}
struct Node {
let ...
3
票
3
回答
326
閲覧数
セット商品の最適な内訳を選択するアルゴリズムを知りたい
顧客から商品の購入依頼があります。
その商品を最適なセット商品の購入に変更して、最安の値段で購入したいです。
よいアルゴリズムがあれば教えていただきたいです。
例)
顧客からの購入依頼
商品A 20個 単価200円 合計金額4000円
商品B 10個 単価300円 合計金額3000円
セット商品
商品ABセット 金額 450円
内訳
商品A 1個
商品B 1個
上記の場合、...
0
票
1
回答
116
閲覧数
ダブルハッシュを使用したオープンアドレス法について
現在、AIZU ONLINE JUDEGE ALDS1_4_Cをやっています。
その中で、ダブルハッシュを使用したオープンアドレス法を学んでいます。
以下がオープンアドレス法のコードです。
#include <stdio.h>
#include <string.h>
using namespace std;
using ll =long long;
#define M ...
0
票
2
回答
320
閲覧数
Python で再帰処理を高速化するには?
以下問題についてです。
atcorder 270 問題3
https://atcoder.jp/contests/abc270/tasks/abc270_c
提出したところ10問のテストが時間切れとなってしまいます。
現在pythonでatcorderに取り組んでいるのはpython力をつけたいという目的もあり、他の言語は使いたくないと考えています。
...
1
票
2
回答
162
閲覧数
和が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
回答
130
閲覧数
C++で挿入ソートを実装する際、一時変数の役目が分からない
挿入ソートについて学習しており、一つ疑問があるのですが、なぜ temp の変数を使わなけばならないのでしょうか?
挿入ソート | Programming Place Plus アルゴリズムとデータ構造編
正しい挙動のコード:
int arry[] = {5,2,8,3,1};
for (int i = 1; i < 5; i++)
{
int temp = ...
0
票
1
回答
218
閲覧数
キューの末尾の判定について~リングバッファ~ アルゴリズムとデータ構造
現在、こちらの記事を読んでいてリングバッファの際の末尾の判定基準が分かりません。
#include <iostream>
#include <vector>
using namespace std;
const int MAX = 100000; // キュー配列の最大サイズ
int qu[MAX]; // キューを表す配列
int tail = 0, head = 0; ...
-1
票
1
回答
211
閲覧数
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&...
2
票
2
回答
208
閲覧数
表を辞書型に直す再帰関数について
画像のような表があり、それを下記のようなjson型に変形したいと考えています。
(途中にリストはないものとしました。)
再帰関数を使って組もうとしているのですが、途中のキーが飛んでしまったりとうまく組めずにいます。
アルゴリズムに強い方、お力添えいただけないでしょうか?
使用モジュール
openpyxl
試した実装
キーで同じレベルのものをリスト化(①)し、下位のレベルのものも同様にリスト化(②)。...
1
票
2
回答
349
閲覧数
テンパズルをpythonで解くプログラム
wikipediaより
テンパズル(10パズル)は、4桁の数字を一桁の数字4つとみなし、これに四則演算などを用いて10を作る遊び。メイクテン(make10)とも呼ばれる。切符の番号や車のナンバープレートなどでの短時間の遊びに利用され、日本経済新聞で渋滞時の時間の潰し方として紹介されたことがある。
一般的なルールとしては、四則演算のみの使用を許可し、数字の並べ替えも許可されるが、...
2
票
1
回答
149
閲覧数
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
回答
169
閲覧数
蟻本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
回答
264
閲覧数
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
回答
80
閲覧数
レイティングを利用した推薦システムのアルゴリズム手法について
現在、レビューサイトにおける商品推薦システムのアルゴリズム改善に携わっております。
検索者が希望条件(例えば、機能、価格、使いやすさなど)とその重視度を入力すると、商品の利用者であるレビュアーが入力した各要素のレイテイングをもとに検索者の希望条件に合致すると思われる商品をランキング形式で提示し、商品詳細とレビューが見れるようなサイトです。
そこで質問なのですが、...
1
票
1
回答
87
閲覧数
Zbuffer法以外の方法でポリゴンの描画順位を決定する方法
Zbuffer法 = ポリゴンの面を描画画面のピクセル単位で分割し、1px毎に描画優先順位の決定(奥行方向の並び順の決定)を行う処理する。
という認識をしておりますが、この方法以外でポリゴンの描画優先順位を決定する方法について探してます。
ネットで調べても調べ方が悪いのだと思いますがうまく見つけることができませんでした。
現状、下記条件での優先順位決定処理を考えています。
▼条件
...
0
票
1
回答
299
閲覧数
区間が重なるタイミング
それぞれある周期で循環する0と1の数列があります。
例:
010101010101...(周期2)
001100110011...(周期4)
000111000111...(周期6)
ここで、縦列が全て1になる最初の列番号やその割合を求めたいです。
上の例では最初に4列目(次に12列目)で1が揃い、無限数列全体の1/6が揃っています。
最初の列番号を求める方法は今のところ、...
0
票
1
回答
255
閲覧数
最小全域木問題のプリム法のプライオリティキューを使った方法での入力と出力に関する問題
最小全域木問題のプリム法のプライオリティキューを使った方法で任意の入力をして結果を表示させたいが思うようにいきません。
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 ...
1
票
2
回答
546
閲覧数
1から100までの数字をそれぞれ1つずつを100個使って、偶数もしくは奇数が4回以上続かないように並べる(配列を作る)アルゴリズム
タイトルにもあるとおり、
1から100までの数字をそれぞれ1つずつを100個使って、偶数もしくは奇数が4回以上続かないように並べる(配列を作る)アルゴリズムを教えていただきたいです。
例えば
x = [99,1,4,5,2,66,45...]
length(x)
→100
のようなものを作成したいです。
条件にもあるとおり、よくないパターンは
1, 偶数が4回以上続いている(奇数も同様)
x = [...
1
票
1
回答
117
閲覧数
粒子フィルタの有効サンプルサイズ (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
回答
273
閲覧数
コサイン類似度結果が思った通りの結果と違う理由はなぜでしょうか?
プログラミング初心者です。
コサイン類似度を勉強している際、入力したデータが明らかに違うのにも関わらず、結果値が高い値を示します。
AとBの比較では0.89という妥当な値が出ますが、AとDはデータの内容が明らかに違うにも関わらず0.9という結果が出ます。
これはなぜなのでしょうか?
言語はjavascriptです。
let A = [20,60,80];
let B = [20,80,40];
...
0
票
2
回答
261
閲覧数
ワーシャルフロイド法を使った経路復元のコードをまとめてみましたが結果の出力が思うようにいきません。
ワーシャルフロイド法を使って経路復元のプログラムを書いてみましたが結果の出力が思うようにいきません。
vector get_path(int s,int t)のvector ansへのまとめ方が悪いと思うのですがどうでしょうか?
#include <iostream>
#include <vector>
using namespace std;
const int ...
0
票
2
回答
182
閲覧数
最短路問題のワーシャルフロイド法による各ノードにおけるコストを求める問題でのコードのまとめ方について。
コードを書いてみましたが出力が意図した通りになりません。
コメントのグラフを以下のコードの形式で入力して出力を各ノードにおけるコストの合計の羅列にしたいのですが、まだ理解不足です。
解る方よろしくお願します。
#include <iostream>
#include <vector>
using namespace std;
const long long MAX_V = ...
5
票
0
回答
61
閲覧数
Proof of Stakeのコンセンサスアルゴリズムで、validatorを選ぶノードは分散的に存在しているのでしょうか?
Proof of Stakeのコンセンサスアルゴリズムは、Stakeしているコインの量に応じてランダムにValidatorが選ばれ、ValidatorがTransactionを承認します。不正するとStakeしているコインが没収されてしまうため、不正をしないモチベーションが働きます。そのため、51%攻撃は実質不可能とされています。
色々な資料を読んでいても、...
0
票
1
回答
377
閲覧数
三目並べ、三つの盤面で同時、✖のみ使用 先手の必勝法を考える
このゲームでは先手に必勝法がある。参照Youtube:Numberphile 3 board tic tac toe
ただし、プログラミングに落とし込むぐらいの簡単な必勝法がみつからない。
目標はその必勝法を利用して疑似AIを作ること。
ルール:
このゲームの盤面は基本的に三つの三目ならべのボードで構成されている
参加者二名が使う印は”X”で共通
ひとりずつ任意の格子に印をつける
...
0
票
2
回答
199
閲覧数
3つの数字を特定の規則で効率よく並び替えたい
今、[[10,20,30],[1,2,3],[5,3,8],[11,2,3]]のように、3つの数字のリストが複数あります。
これを規則に沿って並び替えたいです。
sort_method = [3,-1,2]のような規則をリストとして持たせたい場合
これは、リスト内の3番目の数字を1つ目に移動させ、1番目の数字の正負を反転した後に2つ目に移動、2番目の数字を3つ目に移動させることを意味しています。
...
1
票
1
回答
176
閲覧数
SNSのアカウント価値の計算アルゴリズムについて
アルゴリズムの相談なんですがやや抽象的な話で
純粋なプログラミング技術の話ではなくここでしていい質問かわからないんですが
(だめなら消します)
SNSのアカウントクオリティみたいなのを数値化したいと思っています
例えばツイッターを例にあげると
フォロー数 フォロワー数 開始日時
の3つがすぐ手に入り
一応時間をかければ ツイート数 やリプ数 RT数
...
1
票
1
回答
190
閲覧数
Sphinxで「|漢字《よみ》」という記法で文章中に振り仮名をつけたい場合、Sphinx拡張で対応は可能でしょうか?
Sphinx拡張についての質問です。
私が持っていない良いアイデアがあればと思い質問します。
よろしくお願いします。
<質問>
Sphinxで「|漢字《よみ》」という記法で文章中に振り仮名をつけたい場合、Sphinx拡張で対応は可能でしょうか?
<背景>
明示的に「単語」単位で切り出せる「.. index::」「.. glossary::」「:index:」では、「よみ|...
0
票
1
回答
111
閲覧数
Cipher text, Caesar Encryption のコードが理解できない
以下のコードはまずCaesar codeのアルファベットのずれ具合を調整するn_keyがある。そして、順序が変更されたaからzの文字列がつくられた。
これに基づいてplainText の 'hello' が暗号化され、printされるが、その前の ord[i]-97 の部分が全く理解できません。解説よろしくお願いいたします。
caesarEncrypt.py
plainText = 'hello'
...
0
票
2
回答
562
閲覧数
2段上がる、3段上がる、5段上がる…というように素数段だけ上がることにするとき、n段の階段を上がる方法は何通りあるでしょうか?
はじめまして、Python初心者です。
1段、2段上がる、3段上がる、5段上がる…というように一段または素数段だけ上がることにするとき、n段の階段を上がる方法は何通りあるでしょうか? ただし、nは50以下の自然数。
ルール:組み込み関数のみ使用。list/tuple/set/dictionaryを使用。
期待:フィボナッチ数列使えばいけると思った。例えば、11段の上がり方は、(11-1)段、(11-...
2
票
1
回答
118
閲覧数
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("...
0
票
1
回答
263
閲覧数
基本情報技術者試験『タブ文字を展開するプログラム』の解答を知りたい
以下の問題のaにはどの選択肢が当てはまるのでしょうか?
どなたか解答を教えてくださいませ。
タブ文字を展開するプログラム | 基本情報技術者試験 過去問
副プログラム TabSpc は、タブ文字を展開するプログラムである。
TabSpc は、引数で指定された文字型配列 Src[] を先頭から調べ、 Src[]
中のすべてのタブ文字をそれぞれ一つ以上の間隔文字(スペース)に変換して、
...
-1
票
1
回答
188
閲覧数
画像を左詰めて並べていくアルゴリズムを作るにはどうしたら良いか
5000px x 5000pxで固定されている真っ白なキャンバスの上に
(width = 300px) x (height = 500px) の画像を合計で変数x(エックス)枚並べるとします。
width,heightは縦横比固定ですが、縮小は可能で、縮小率sは初期値1.0で、widthとheightを2%ずつ縮ませる場合、縮小率はs=0.98%とします。
例えば、x=...
0
票
2
回答
484
閲覧数
python で入力を加算していくアルゴリズムについて
このように、入力値を加算していくにはどのようなプログラムを組めばよいでしょうか?言語はPythonでお願い致します。
入力値:
200
300
500
100
200
出力:
200
500
1000
1100
1300
-1
票
1
回答
646
閲覧数
2本の直線の交点計算をsolveでやってみたい。
直線が、x軸又はy軸に平行の時、場合分けの対応が必要ですか?何ケースに分ければいいですか?
よろしくお願いします。
以下のエラーが、 例7ででます。
UnboundLocalError: local variable 'a' referenced before assignment
(オリジナルポスト)2本の線分が交差しているか調べる
https://qiita.com/tydesign/...
0
票
2
回答
597
閲覧数
C言語で連結リストの作成をしましたが、要素削除の実装でメモリ解放でトラブルを連発しました。一応動くようにはなりましたが、このコードで問題はあるでしょうか?
C言語初心者です。コンパイラはgcc-11.0.1、環境はUbuntu21.0.4です。
表題のとおり、思い立って連結リスト(双方向リスト)を実装してみました。実装したのは、リストの要素を表す構造体、リストの生成、追加、削除を行う関数です。そのうち、要素の削除を行う関数でトラブルが起こりました。
トラブルが発生したコードは以下のとおりです。
struct L {
int element;
...
2
票
1
回答
1,759
閲覧数
多項式と多項式時間の関係がわかりません
https://www.kspub.co.jp/book/detail/5128442.html
この本をよんでアルゴリズムに関して学習しています
そのp.23.に
定数d>0が存在して計算量がN^dの定数倍によって上から抑えられるとき、多項式時間であるといいます。
注意点としては、NlogNやN√Nは多項式ではありませんが、O(NlogN)やO(N√N)は多項式時間です。
なぜなら、...
0
票
2
回答
388
閲覧数
エディタの「置換」機能と実質的に同じことをより速く処理する方法はありますでしょうか?
お世話になっております。
実質的に置換と同じことで遙かに処理の速い方法はありますでしょうか?
事例 たとえば以下のようにテキストの置換パターンが複数あったとします。
08A54G→タナ
08A→タ
54G→ナ
テキストエディタの置換のマクロでも変換していけますが、数百万字だとけっこう時間がかかります。
かかる時間とは、テキストエディタや連続置換であるかにもよりますが、速くて5分以上です。
しかし、...
2
票
1
回答
189
閲覧数
OpenGLにて、図形をマウスで引いた直線で切断したいがアルゴリズムが分からない。
OpenGLで図形をマウスで引いた直線で切断するようなプログラムを実装したいと考えています。
OpenGLのversionは4.6ですが、こちら(http://wisdom.sakura.ne.jp/system/opengl/)のver1.1に基づいたチュートリアルを勉強しています。
ユーザーが何も手を加えていない初期状況は、...
0
票
2
回答
218
閲覧数
集合当てクイズの解法
次のようなゲームを考えます。
アルファベット 'A'~'Z'を全体集合とし、その部分集合が一つ与えられているとします。これを答えと呼びます。
プレイヤーは1ターンにつき次の問い合わせを一回出来ます。
問い合わせ:アルファベット'A'~'Z'の集合を一つ入力とし、答えと入力の積集合が空集合であるか否かがYes/Noで返ってくる。
これで答えが確定するまでのターン数を競います。
...
0
票
1
回答
113
閲覧数
pythonで、intersectionの位置を調べる方法を教えて下さい。
#条件:データに重複は、ありません。
x = {"a", "b", "c"}
y = {"c", "b", "e"}
z = {"f", "b", "c"}
result = x.intersection(y, z)
...