アルゴリズムに関する質問、議論総合スレ
レス数が900を超えています。1000を超えると表示できなくなるよ。
0001デフォルトの名無しさん
NGNG類似スレが多くてどこに書きこめば分からないときは
とりあえずこちらにどうぞ。
0809802
NGNGそうですねぇ，近いかもしれません．
置くきまりを，
「カ」の横に置ける文字 「キ」「ク」「ケ」「コ」
「キ」の横に置ける文字 「カ」「ク」「ケ」「コ」
「ク」の横に置ける文字 「カ」「キ」「ケ」「コ」
「ケ」の横に置ける文字 「カ」「キ」「ク」「コ」
「コ」の横に置ける文字 「カ」「キ」「ク」「ケ」
と，自身以外の文字全て指定すれば
ペントミノのピース（12種類）の形は全て作成できると思います．
ペントミノ（その他のミノでもいいですが）のピースを
生成するアルゴリズムがあれば参考になるかも知れません．．
0810デフォルトの名無しさん
NGNG個々のピースの各位置に文字を書いていけるか総当たりでチェック。
対称性のチェックは後回し。。。
ピースの構造体 (Pascal)
type
moji = (ka, ki, ku, ke, ko);
var
piece: array[1..5] of record
V: moji;
l, r, u, d: integer;{上下左右に連結してるパートの番号）
end;
■
■■■
■
例えば上のピースの定義は
piece[1].d := 2;
piece[2].u := 1; piece[2].d := 3; piece[2].r := 4;
piece[3].u := 2;
piece[4].l := 2; piece[4].r := 5;
piece[5].l := 4;
で、piece[1]からpiece[5]にルールチェックしながら文字を順に入れていく。
0811デフォルトの名無しさん
NGNGtype
moji = (ka, ki, ku, ke, ko);
var
rule: array[moji] of set of moji;
としておいて
rule[ka] := [ki, ku];
rule[ki] := [ka, ku];
rule[ku] := [ka, ki, ke];
rule[ke] := [ku, ko];
rule[ko] := [ke];
せっかくあるんだから、ついでだからと
Pascalの集合やスカラー型を目一杯使ってみたりして。
わざわざ面倒な（他言語使用者に分かりにくい）書き方をしてるとも言える。
0812デフォルトの名無しさん
NGNG0813デフォルトの名無しさん
NGNG■■■■■ ■■■■ ■■□□
□□□□□ □□□■ □■■■
■■■ ■■□ ■□□ ■■
□□■ □■■ ■■■ ■□
□□■ □□■ □□■ ■■
□■□□ ■■□ ■□□
■■■■ □■■ ■■■
□□□□ □■□ ■□□
■■■
■■□
□■□
■■■
□■□
最後の2つは、この問題の解にはならないね。
0814デフォルトの名無しさん
NGNGという問題が出んです。rand()を使ってみるといいって言われたんだが、どうもできません。助けてください！
0815そのこちゃん
NGNG0816814
NGNGぜひともアドバイスくださいまし。
0817デフォルトの名無しさん
NGNG同じ質問を答えたことがあったな。宿題スレだったかな？
そのときは
・n個の配列を作り 0〜n-1 まで順に入れてゆく
・randを使い、配列をシャッフル
・先頭からLまでを答えとする
などの解答がでた。過去ログさがしたがDATオチかな
0818デフォルトの名無しさん
NGNG0819814
NGNGそれとも同じ学校、同じ授業で誰かが毎年2chで質問？((((；ﾟДﾟ)))ｶﾞｸｶﾞｸﾌﾞﾙﾌﾞﾙ
0820デフォルトの名無しさん
NGNG0821デフォルトの名無しさん
NGNG0822814
NGNGとにかくなんとかなりそうです。ありがとうございます
0823デフォルトの名無しさん
NGNG簡単じゃないと思う。
0824814
NGNGその方法が一番早いよってことを説明する程度でよかったとおもう。
0825デフォルトの名無しさん
NGNG> その方法が一番早いよってこと
むしろそっちの方が難しいと思われ
0826814
NGNGでもうまく書けないんですよ。プログラム自体が。
100*rand()%50
こんな感じにrand使えばいいんですかね？変数にして。
0827デフォルトの名無しさん
NGNGまずは、何の言語を使うかだな。
0828814
NGNG今C++でやってます。
char s[n]
で数列ｓをつくってみて
for文でn回ループさせて・・・
ってとこまでで、それから進みません(|| ﾟДﾟ)
明日なのに、やばいです・・・・
0829デフォルトの名無しさん
NGNG0830デフォルトの名無しさん
NGNG#include <time.h>
#include <stdlib.h>
#include <stdio.h>
int shuffle_cmp(const void *x, const void *y){return 2*(random()%2)-1;}
void shuffle(void *b, size_t n, size_t s){return qsort(b,n,s,shuffle_cmp);}
int main(int argc, char **argv)
{
int n, i, *a;
long s;
n = argc>1 ? atoi(argv[1]) : 10;
s = argc>2 ? atoi(argv[2]) : time(NULL);
if (NULL == (a = (int*)malloc(n*sizeof(int)))) return 1;
for(i=0; i<n; i++) a[i] = i;
srandom(s);
shuffle(a,n,sizeof(int));
for(i=0; i<n; i++) printf("%d ", a[i]); puts("");
return 0;
}
0831デフォルトの名無しさん
NGNGこれは？いったいどうなっているのでしょうか？
変な方法なのですか？
0832デフォルトの名無しさん
NGNGerror C2065: 'shuffle' : 定義されていない識別子です。
srand(s);
っていわれます。これはどうなってるんですか？
0833デフォルトの名無しさん
NGNGC++でもっともマトモな方法ならば、
#include <algorithm>
#include <vector>
std::vector<int> make(int n, int k)
{
std::vector<int> x;
x.reserve(n);
for(int i = 0; i < n; ++i)
x.push_back(i);
std::random_shuffle(x.begin(), x.end());
return std::vector<int>(x.begin(), x.begin() + k);
}
これ以上はないでしょう
0834デフォルトの名無しさん
NGNGこのアルゴリズムである特定の順列の確率ってどうやったら求まるんだろ。
ttp://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/libstdc%2b%2b-v3/include/bits/stl_algo.h?rev=1.29&content-type=text/x-cvsweb-markup
0835デフォルトの名無しさん
NGNGより誘導されてきました。
経路探索アルゴリズムを勉強しているのですが、A*(A-Star)アルゴリズムがいまいち
つかめません。
breadth first search(bfs)にコストを導入したもの、というところまではわかったのですが…。
1.パス情報を持つデータを用意する
2.それをオープンリストとし、開始点q(親)を選ぶ
3.qの子ノードのコストを計算する
4.子ノードから一番コストの低いものを選ぶ
5.qをクローズリストに追加し、選ばれた子を親として終点にたどり着くまで繰り返す
これでいいんでしょうか？
これだと行き止まりにいってしまった場合探索が失敗すると思うのですが…。
google による検索結果から以下のURLを参考にしました。
ttp://rajiv.macnn.com/tut/search.html
0836デフォルトの名無しさん
NGNGrandom_shuffle が利用する乱数生成器が一様分布に従う場合を考える。
まず k 回目の交換が終った時点で x[k]〜x[n-1] は未交換であることに注意しよう。
n-1 回の交換の結果 x[0]〜x[n-2] の順列が等確率に生成されることを仮定すれば、
n 回目の置換によって末尾の要素 x[n-1] を x[0]〜x[n-1] のいずれかと
等確率で初めて交換されるので n 回の交換によって作られる各順列は等確率となる。
0837835
NGNG1.オープンリストに開始点を入れる
2.オープンリストが空になるまで繰り返す
3. オープンリストの中から最小コストfを持つもの選び、取り出す
4. それをqとし、周囲8セルの子ノードを作る
5. 子ノードの数繰り返し(8回)
6. コストを計算する
7. オープンリストの中に存在すればスキップ
8. クローズリストの中に存在すればスキップ
9. そうでなければオープンリストに追加する
10. 子ノード繰り返し終了
11.クローズリストにqを追加する
12.オープンリスト繰り返し終了
13.解はクローズリスト
これでOKなんでしょうか？
どうしても無駄な要素がクローズリストに出てくるのはコスト計算を失敗しているから？
0838デフォルトの名無しさん
NGNGclosed list は解じゃなくて探訪済みのすべてのノードをとっとく集合。
これがあるせいで A* は指数領域オーダー。
解かどうかの判定は5,6の間で行なって、子がゴールに到達してたらその時点で返すの。
7, 8 はコスト比較の条件が抜けてる。
0839835
NGNG申し訳ない。
closed listが探訪済みノードの集合だとすれば解は一体どこへ…？
7,8のコスト比較はリスト内にコストの低い点があればを追加すればいいという
事でOKでしょうか。
0840デフォルトの名無しさん
NGNGゴールに着いたらそこから親をたどっていけば解を作れるでしょ。
> 7,8のコスト比較はリスト内にコストの低い点があればを追加
逆。全然分かってないっぽいので注意しとくと、
比較するのは closed にある「同じ位置を指すノード」。
子が未探訪の位置を指すか探訪済みでも既知の道より近道(コストの低い道)だったら
open と closed の両方に加える。だから open 内のノードと比べる必要は本来ない。
0841835
NGNG7,8はつまりリストに一致するものがあって且つその一致するものと現在のノード
コストの比較を行えばいいんでしょうか？
つまり
function check (list, node) {
for each (list) {
if (list == node && list.cost < node.cost) skip;
}
}
抽象的な表現ですがこんな感じ？
0842デフォルトの名無しさん
NGNGコードの意図がよく分からん。正しいともいえるし間違ってるともいえる。
この辺見るよろし
ttp://www-fs.informatik.uni-tuebingen.de/~hueffner/
可能ならこの記事で参照してる以下の論文を入手して読むこと
P. E. Hart, N. J. Nilsson, and B. Raphael. A formal basis for the
heuristic determination of minimum cost paths. IEEE Transactions on
Systems Science and Cybernetics, SSC-4(2):100-107, 1968
0843835
NGNGそのページも一度みてみたんですけどね。
とりあえず論文取り寄せてみます、ありがとうございます。
＃関係ないけど「A-Star(A^*)」という出だしの(A^*)が顔文字に見えた…
0844デフォルトの名無しさん
NGNG総アタックよりも効率的な方法がありますか？
配列をソートして
・・・という感じになるような気がするんですが、そこからどうやれば良いかわかりません。
0845デフォルトの名無しさん
NGNG前も聞いてなかったか？
0846デフォルトの名無しさん
NGNG見てなかった。ごめんね
0847デフォルトの名無しさん
NGNG0848844, 846
NGNGありましたね。しかもすぐ近所に。
しかし、797の回答ではプログラムに起こすのは困難な上に
非効率的すぎるのですが・・・
もともと、仮定と推測って・・・。
そんなファジーなアルゴリズムはアルゴリズムって呼べるんでしょうか？
0849デフォルトの名無しさん
NGNG自分の無知を誇るようなレスはやめたほうがいいよ。
リアル厨房なら仕方ないが。
0850デフォルトの名無しさん
NGNGttp://www.google.co.jp/search?q=knapsack+heuristics
0851デフォルトの名無しさん
NGNGてゆーか普通にケツから詰めてけばいいんじゃねーの
それが嫌ならもっとファジーな遺伝アルゴリズムを使えば？
終
了
0852デフォルトの名無しさん
NGNG確率（ランダム）アルゴリズムは、矛盾した名称ということになるのかね？
0853デフォルトの名無しさん
NGNG配列をソートするところまでしか考えられない奴よりマシ。
0854デフォルトの名無しさん
NGNG0855デフォルトの名無しさん
NGNGお前の頭のファジーさが足りねぇ
さらに、結局総当りくらいしか思いつかず、
答えられねぇから叩くだけの香具師も能無し杉だな
と、叩くだけの能ﾅｼからのメッセージ
0856デフォルトの名無しさん
NGNG今のところ、総当りしか解が存在しないからでは？
0857デフォルトの名無しさん
NGNGここは夏休み子供相談室じゃない。
0858デフォルトの名無しさん
NGNG0859デフォルトの名無しさん
NGNG本しか読まずに考えることをしないのはどうかと。
本や資料に「出来ない・難しい」って書いてあると君はトライしようとも思わんのね
>848
工夫次第である程度までなら総当りを避けられるんだから、そっから攻めてけばいい
俺は一般的なアルゴリズム知らんからどこまで説明できるかわからんけど
大---小
0001111 ←は最小からの総和で目標値を超えない位置
0010111 この時、４つのアイテムについて確認するものとし、このリスト中のアイテム数も
0011011 ４を超えない事がわかる
0011101
0100111
0101011
0101101
で、総当りをほんの少し回避できるかなー。と思った
0860デフォルトの名無しさん
NGNGあの下もずっと同じようなルールで 1111000まで続くんよ。
0861デフォルトの名無しさん
NGNG近似解で満足しろよ
0862デフォルトの名無しさん
NGNGそこそこの解を見つけるには、いくつか手法が知られている。
代表的なものは、Genetic Algorithm（遺伝的アルゴリズム）、シミュレーティドアニーリング、など。
そんなおおざっぱな分類をあげても困るという場合は、
情報処理学会の「数理モデル化と問題解決」研究会の論文などを入手して読むよろし。
大勢の人が、弁当を詰め込むのにいかに効率よくするかを研究しているから。
ttp://www.ipsj.or.jp/sig/mps/
0863デフォルトの名無しさん
NGNG参考になります
0864862=858
NGNGLSIの設計や、暗号理論、などに組み合わせ最適化問題が使われています。
金融工学にも応用があるようですね（専門外ですが）。
その手の参考書を読むとよいかと。
0865デフォルトの名無しさん
NGNGﾊｧ？ ああ、そうですね。それはよかったですね。
ところで、二度とプログラム板には来ないでください。
アニメ板が良くお似合いです
p2pで拾ったVBでも使って時計でも作っててください。
0867デフォルトの名無しさん
NGNG???
0868デフォルトの名無しさん
NGNG厳密解に10000年かかるのが、9800年で済むのでうれしいね、くらいの役割しかない。
それがNP問題ですから。
これを現実時間でとくには、>>861 やその他で言及したように近似解で我慢するか、
P=NPであることを証明しなければならない。
...
0869デフォルトの名無しさん
NGNG正反対の感情をもって返答しているのだろうか。
0870デフォルトの名無しさん
NGNG>>859-870 が自作自演であることが判明するわけだが。
0871デフォルトの名無しさん
NGNG???
>>859
ナップザック問題といえば、一般には動的計画法を使うのがよろしいかと。
実装が容易で、実行時間も速い。
0872デフォルトの名無しさん
NGNG馬鹿だから。
0873デフォルトの名無しさん
NGNG0874デフォルトの名無しさん
NGNG内容理解できなかったから納得。理解できるものは煽る
という糞房特有の性質だから
0875デフォルトの名無しさん
NGNG863 ですが、865 ではありません。
まじめにこの問題について聞いているつもりですが
騙りが発生した責任をとって二度とここにはきません。
さようなら
0876教えて君
NGNGであるのは、何故ですか？
また、枝を一本削除するのに必要な計算時間もο(log(n))であるのは、何故ですか？
0877デフォルトの名無しさん
NGNG>>863=>>865だと思ってしまうあんたはおかしいね。
レスした時間と順番から見て別の人間だろ。
>>875
誰も騙っていないと思うが・・・
>>861を無視しないでレスしておけばよかったんだよ。
0879デフォルトの名無しさん
NGNG解決したなら、おせーて
0880デフォルトの名無しさん
NGNG0881デフォルトの名無しさん
NGNG10000桁2進数→10進数ってな感じの
0882デフォルトの名無しさん
NGNG君、本屋に行って基本情報の参考書の
一番最初の章の一番最初の項目でも
読みなさい。
0883デフォルトの名無しさん
NGNG人間が脳内変換する分には参考書の方法で良いけど、
プログラムのロジックとしてはまずいんじゃないの?
0884デフォルトの名無しさん
NGNGたいていサメンションを用いた記述変換公式が載っているかと。
0885デフォルトの名無しさん
NGNGお騒がせしました。
0886デフォルトの名無しさん
NGNG> たいていサメンションを用いた
サメが住むマンションとか？
0887デフォルトの名無しさん
NGNG10000桁2進数をそのままの精度で変換したかったらgmpかrubyでも使うかな
何にせよ多倍長数演算の除算と剰余の実装と同じことをしないと
0888デフォルトの名無しさん
NGNG0889デフォルトの名無しさん
NGNG0890デフォルトの名無しさん
NGNG>>887
足算だけ実装すれば大丈夫ですよ。
a=1
b=0;
を初期値にして
2進数で下の桁から見ながら
２進数のその桁が1ならb=a+b;
その後、 a=a+a;
0891デフォルトの名無しさん
NGNGデータ構造として10進文字列で持つってこと?
それなら10進の全加算器を書けばいいわけだから納得。
0892デフォルトの名無しさん
NGNGa1,a2,a3....anがあったとして、
それぞれ
a1<a2....<an
が保証されているとする。
この時
下限minと上限maxが与えられて
min<ai<max
となるような
すべてのiを求める最速のアルゴリズムを考えているのですが。
具体的には
1,3,5,6,7,9,10,11,13,16
という数列があった時
最小4
最大10の時
5,6,7,9を返すという処理です。
DBのbetweenのアルゴリズムなんかが参考になりそうです。
誰か興味がある人議論しましょう。
今考えているのは
線形リストで数列を保存し
それらをBTREE（ハッシュでもいい）にマッピングして
minとmaxを検出して、ぶっこ抜くのが一番速いのではと考えています。
0893デフォルトの名無しさん
NGNGhttp://members.goo.ne.jp/home/madcap0
0894名無し＠沢村
NGNG出発点 (0,0,…,0), 吸収点 (1,1,…,1) の
n次元超立方体上の対称量子ウォークの
吸収時間は Tr Xn - 1 で与えられるんだよ。
ここで Xnは方程式の解となるんだよ。わかるか？
おれはいまそういう簡単な研究に取り組んでいるんだよ！！！
0895デフォルトの名無しさん
NGNGそれで研究になるのか？
0896デフォルトの名無しさん
NGNGおまいは自分の書いていることがわかっているのかと小一時間(W
0897デフォルトの名無しさん
NGNGなぜ？
0898デフォルトの名無しさん
NGNGなんか必死だな・・・
0899デフォルトの名無しさん
NGNG普通の方法
数列を 配列に入れておいて、min max でバイナリ検索し、アドレスを求め
挟まれた区間を取り出す
0900名無し＠沢村
NGNGおまいらよ、量子重ね合わせの状態とは何かわかるか？
まあくだいていえば、一台の車が右向きに走っている状態と左向きに走っている状態が同時に成立しているということよ。
だが、おれらが実際見ると、車は右向きか左向きかに固定して走ってるだろ？それは観測することによって、重ね合わせの状態のうちのひとつが固定するからよ。
おまいらよ、重ね合わせの状態のうちのひとつがどれに固定するかは、重ね合わせの係数によって決まるのよ。おまいらよ、重ね合わせの係数は複素数よ。複素数の勉強をしてみろ？
おまいらよ、量子PCでいう演算とは、この量子重ね合わせの状態を担う物理系に対してに対して、パルス電波を与えることよ。
いままでのPCでは4bitで表現できる16の状態のうち一つについて1回づつ演算を行い、合計16回計算して16通りの結果を出力してたが、量子PCでは4bitで表現できる16の状態を同時に実現している重ねあわされた量子状態に対して1回の演算を行い、結果を出力するんだよ。
当然処理bit数が増えるほど、量子PCの威力は大きくなるわな。だから並列処理よ。
だが、おまいらよ、その演算結果を見ようとすると、重なり合った状態のうちの一つしか見れないだろ？
この問題を解決するものとしてShorのアルゴリズムというのがあるよ。
Shorのアルゴリズムは量子PCの教科書には必ず出てくる有名なアルゴリズムだから、見てみろ？
おまいらよ、このようにこれからのプログラムは量子の時代よ。
おまいらも量子に取り組んだらどうだ？量子でないプログラミングなんて意味ねーよ！
0901デフォルトの名無しさん
NGNG0902デフォルトの名無しさん
NGNG0903山崎渉
NGNGﾋﾟｭ.ｰ ( ＾＾ ） ＜これからも僕を応援して下さいね（＾＾）。
＝〔~∪￣￣〕
＝ ◎――◎ 山崎渉
0904デフォルトの名無しさん
NGNG0905デフォルトの名無しさん
NGNG量子コンピュータの登場は沢村が死んでからになります。
0906デフォルトの名無しさん
NGNGわからないことあったらここで訊いていいから
0907デフォルトの名無しさん
NGNG（ABCDは0または1の任意のビットとする）
0000ABCD
を
A0B0C0D0
に変換するスマートな方法はないものでしょうか？
今のところは、左シフトもしくは加算でAならAだけをとりあえず目的の位置に移動したのち&でゴミを除去、
というのをビットの桁数ぶんだけ行うという地道な方法しか思いつかない状態です。
0908デフォルトの名無しさん
NGNGchar c = ( b&0x08 ? 0x80 : 0x00 ) |
( b&0x04 ? 0x40 : 0x00 ) |
( b&0x02 ? 0x20 : 0x00 ) |
( b&0x01 ? 0x10 : 0x00 );
こんなんでどう？
レス数が900を超えています。1000を超えると表示できなくなるよ。