データ構造,アルゴリズム,デザインパターン総合ｽﾚ 2

1 名前：デフォルトの名無しさん mailto:sage [2013/03/03(日) 18:10:11.63 .net] 【関連スレ】 3Dアルゴリズム全般 toro.2ch.net/test/read.cgi/tech/1164171086/ ＜集大成＞アルゴリズム大辞典 toro.2ch.net/test/read.cgi/tech/1086272325/ アルゴリズム総合スレ in ム板 toro.2ch.net/test/read.cgi/tech/1217773415/ アルゴリズムとデータ構造 - Kaneko Lab. ttp://www.kkaneko.com/adp/algo/index.html アルゴリズムとデータ構造 - ソースコード探険隊 ttp://www.codereading.com/algo_and_ds/ 各種アルゴリズムの C++ による実装 - Spaghetti Source ttp://www.prefield.com/algorithm/ アルゴリズムとデータ構造 - プログラミングスレまとめ in VIP ttp://vipprog.net/wiki/algo_and_data_const.html 116 名前：デフォルトの名無しさん mailto:sage [2013/11/18(月) 22:58:36.70 .net] >>115 くじ引きと同じ論法でO(N)で作れるだろ 117 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 07:10:30.69 .net] >>116 それって、1000000個の重複のない数列から7000個を取り出すんだろ？ 重複のないくじを作るのに結局シャッフルがいるんじゃないのか？ だったら、やってることは>>111と同じだと思うが というか、>>111だってシャッフルはO(N)なんだから、 そもそも質問の意図もよう分からんが 118 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 07:44:36.62 .net] >>117 シャッフルは要らない。n本のくじの中にm本の当たりがある場合と同じ。 それを配列番号1からn番まで引く。くじ引きは何番目に引こうが当たりが出る確率は等確率。 >>111も確かにO(N)だな。ソートと勘違いしてた。 だけどくじ方式の場合は逐一頭から取り出す場合は配列を用意する必要はないし、 必要な分だけ計算すればいい。 int array[n]; for (size_t i=0; i<n; ++i) { bool hit = m/(n-i)の確率のrand; if (hit) { --m; array[i] = 1; } else { array[i] = 0; } } 119 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 13:06:53.22 .net] 偏りをなくしたいということは低周波成分をなくしたいということかな？ すなわち、1が連続したり、なかなか出なかったりするのを無くすということ。 だったら乱数を使うのは誤り。 120 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 20:29:44.62 .net] >>118 すごいですね、その発想は出てこなかったです。 簡単な例で図を描いて確かめてみましたが、みんな当たる確率は同じになりました。 Fisher-Yates shuffle でやるより断然スジがいいです。 採用させてもらいます。 >>119 たしかに、1 や 0 があまりに連続しているの好ましくないです。 その場合、乱数を使わずにどうやるのでしょうか。 1 か o かを選ぶのに乱数を使うのではなく、もっと別のところで使うという意味でしょうか。 それとも、全くどこにも使わないのでしょうか。 121 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 21:16:46.95 .net] >>120 乱数から低周波成分を除去した数列を使います。別名ブルーノイズ。 配列を参照するだけなので超高速で偏りの無いパターンを作ることができる。 100万個から7000個を選んでも１が連続する確率は0。規則性もなし。 ブルーノイズ数列の一部をとってもブルーノイズ数列。使い回しができる。 欠点として１回はブルーノイズ数列を作る必要があるが時間がかかる。100万個 の数列だと1時間くらいかかる。一回作ってファイルに保存しておけばOK。 122 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 21:23:07.46 .net] >>120 不思議に思ったんだがひょっとして 配列の全要素の初期値って不定扱いなのか？ なら>>118を採用する理由もわかるが 123 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 22:01:24.83 .net] 言語にもよるけど、int 型なら多くの場合0じゃない？ で気づいたけど、1 か 0 しか入らないなら bool 型でいいんじゃないか？メモリもグッと節約できる。 124 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 22:12:20.58 .net] >>122 いえ、今回は、必ず何らかの値で初期化される、という種類のデータ構造（配列）を使っています。 （言語的は初期値として未定を表す値を指定できる配列も簡単に作れますが、 今回は意味ないので、そのような配列は使っていません） >>118を採用しようと思ったのは、配列の頭から順に要素をトラバースしながら、 その要素のみを参照して値を設定していけるという点がシャッフルに比べて優れていると思ったからです。 要するに、データ構造そのものをどんどん大きくしながら作っていけます。 シャッフルも Fisher-Yates shuffle でしたら順にトラバースしますが、 その要素と、別のランダムに選んだ要素を参照しなければならず、 シャッフル処理をする前にデータ構造が完全に出来上がっていなければなりません。 その上で要素をスワップしていきます。 じつはプログラミング言語はCではなくHaskellを使っており、Haskellでは後者より前者のように、 値を入れた要素を次々と繋げながらデータ構造を（目的の規模まで）大きくしていく方が プログラムしやすいんです。 >>123 すいません、0 と 1 を使ったのは単に質問をシンプルにするためでした。 本当は、質問で 1 を入れるところでは min < x < max のランダムな浮動小数点を入れます。 そもそもの目的をぶっちゃけますと、ランダムな重み付き有向グラフの隣接行列を作ることです。 125 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 22:14:23.54 .net] >>124 > >>118を採用しようと思ったのは、配列の頭から順に要素をトラバースしながら、 > その要素のみを参照して値を設定していけるという点がシャッフルに比べて優れていると思ったからです。 すいません、ちょっと言い方がおかしいですね。 配列の頭から順に要素をトラバースしながら、ではなくて、順に配列を大きくしながら、 とか、配列を組み上げながらと言うべきでした。 126 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 22:23:35.67 .net] >>121 申し訳ないです、そこまで強力なものは今回は求めていないです。 あまりに偏りすぎていると使えないな、という程度のことでした。 しかし、これはこれで大変興味深いです。 ホワイトノイズやピンクノイズなどは聞いたことがありますが、ブルーは初耳です。 調べてみます。 127 名前：122 mailto:sage [2013/11/19(火) 22:35:24.77 .net] なるほど納得 非零要素を一次元上（あるいは二次元とか）に並べて それを仮想電子のようにみなし仮想クーロン斥力みたいなの計算して 要素番号補正したらとか考えてたんだが それだと逆に傾向出ちゃうか 値を入れた同じ行、同じ列に対して再度選択を阻害するパラメーターを入れて 云々かんぬん…いかん、わけがわからくなってきた 逃走っ（しゅたたた…） 128 名前：デフォルトの名無しさん mailto:sage [2013/11/19(火) 22:54:30.96 .net] やってみましたら、たとえ Haskell であっても、 >113 程度の規模ではシャッフルでもくじ引きでも、あっという間でした。 >>114 の指摘通りで、かなり恥ずかしいです。 憶測で遅いと決めつけず、質問する前に試すべきでした。 プログラムの見やすさが抜群に良いという点で、くじ引きの方法でやることにします。 みなさん、ありがとうございました。 129 名前：デフォルトの名無しさん mailto:sage [2013/11/27(水) 04:14:03.66 .net] Edmonds's Blossom Algorithmを詳しく説明していただけないでしょうか 130 名前：デフォルトの名無しさん mailto:sage [2013/12/14(土) 23:50:45.85 .net] 二次元座標に、ラベル(高さ固定、横書き)を 重ならないように配置したいです。 現在は、y軸をラベル高さで分割して、 各領域で、ラベルが指定座標を含むように左側から詰めて配置しています。 この方法だと、3点以上集中すると、大きくずれてしまいます。 どのようなアルゴリズムがありますでしょうか？ また、動的生成なので、優先順位は コスト > 見栄え です。 131 名前：デフォルトの名無しさん mailto:sage [2013/12/15(日) 02:57:49.26 .net] >>130 ある点を矢印で示すようなラベルなら多少点から離れてもいいよね それなら幾らでもやり方はあると思うよ 例えば、点や四角（ラベル）の当たり判定で配置 132 名前：デフォルトの名無しさん mailto:sage [2013/12/15(日) 12:12:29.22 .net] >>131 おっしゃる通り、多少離れるのはかまわないです。 >点や四角（ラベル）の当たり判定で配置 ラベルの矩形の判定はやってみたのですが、 どの方向にずらすべきかのところで詰ってしまいました。 結果、上記のx軸+方向のみ補正な方法になってしまいました。 何かヒントがいただけたらと思います。 133 名前：デフォルトの名無しさん mailto:sage [2013/12/15(日) 15:32:28.35 .net] >>132 そういったアルゴリズムを組んだことはないけど ラベルの矩形が重なった時 指し示す点とラベルの四隅の点との距離が一番短いラベルの点を選出し 最初に、2点間の傾きを保ちならがら、そのラベルが指し示す点との距離を縮めて 縮めた際に2点間の距離が0になっても矩形が重なっているなら2点間の傾きを変える 目安となる距離と傾きの初期値を設定しておけばいいかな 傾きの初期値はラベルの4隅それぞれ、回転して考える 判定する矩形の4隅の点を左下にのみ、指示す点の45度右上の傾きにラベルを固定してしまってもいいかもね 机上の空論だから上手くいくかどうか分からないのは許してね 難しく考えすぎているのかもしれないわ 134 名前：デフォルトの名無しさん mailto:sage [2013/12/16(月) 00:06:30.24 .net] こういう事ができればいいんでしょ ja.wikipedia.org/wiki/%E5%8A%9B%E5%AD%A6%E3%83%A2%E3%83%87%E3%83%AB_(%E3%82%B0%E3%83%A9%E3%83%95%E6%8F%8F%E7%94%BB%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0) キーとなるのはここ ＞グラフの頂点と辺に仮想的な力を割り当て、力学的エネルギーの低い安定状態を探す ＞それぞれの辺をフックの法則にしたがうばねとみなし、それぞれの頂点をクーロンの法則にしたがう電荷をもつ粒子とみなす。 自分が以前勉強した時はgrineditっていうオープンソースソフトが解りやすかった 135 名前：デフォルトの名無しさん mailto:sage [2013/12/16(月) 21:53:44.96 .net] 力学エネルギーに基づくグラフ描画が求めていたもののようです。 まとまった時間を作って、出ているアルゴリズムを読んでみます。 お付き合いしてくださった皆様ありがとうございました。 136 名前：デフォルトの名無しさん [2013/12/28(土) 23:22:37.13 .net] グーグルの検索エンジンのアルゴリズム webblogsakusei.main.jp/seo_taisaku_syukyaku.html 137 名前：デフォルトの名無しさん [2014/01/17(金) 16:44:24.77 .net] ふぇぇ」 138 名前：デフォルトの名無しさん mailto:sage [2014/01/19(日) 15:03:35.30 .net] 計算量のオーダーの考え方で質問です。 (a # b) を a の b 個の下降階乗冪を表す式とし、 (#) は除算 (/) よりも優先順位が高いとします。 x や y は m よりも十分大きい数とすると、 f(m) = x#m / y#m この場合、計算量のオーダーは O(m) と考えていいでしょうか。 139 名前：デフォルトの名無しさん mailto:sage [2014/01/19(日) 22:30:57.31 .net] ダーク構造、エルゴリズム、ディザインパクトに見えたマジで。 140 名前：デフォルトの名無しさん mailto:sage [2014/01/20(月) 22:08:25.07 .net] 下記の問題について、私が考えた方法では計算量が n 乗のオーダーになってしまい、 たいして大きくない数で試しても計算にかなり時間がかかるのですが、 みなさんならどのような解き方をするでしょうか。 [問題] m 枚のカードの束からランダムに x 枚引き（x <= m）、引いたカードに印をつける。 引いたカードを元のカードの束に戻し、再度ランダムに先ほどと同数 x 枚引き、 印がついていなかったら印をつけ、また元の束に戻す。 このように x 枚カードを引いて印を付けて戻す行為を n 回繰り返した後、 m 枚のカードの束に印のついていないカードが p 枚ある確率を求める関数 F(m, x, n, p) を作れ。 141 名前：140 mailto:sage [2014/01/20(月) 22:09:20.78 .net] [私の考え] 全体の事象は、{C(m,x)}^n です。（関数 C(a,b) は組み合わせ aCb） m 枚のカードから x 枚引く行為を n 回繰り返した後に結局 p 枚無印で残る引き方のパターン数を求める関数 R(m, x ,n, p) は漸化式で、 R(m, x ,n, p) = Σ[i=0..x]{ R(m, x, n-1, p+i) * A(m, x, p+i, p) } ただし、 n = 1 かつ p = m-x ---> C(m, x) (n = 1 かつ p ≠ m-x) または (n >= 2 かつ p > m-x) ---> 0 ここで関数 A(m, x, p, q) は、p 枚無印で残ってた状態を q 枚無印で残るようにするような、 m 枚のカードからの x 枚のカードの引き方のパターン数で（q <= p）、 A(m, x, p, q) = C(m-p, x+q-p) * C(p, p-q) よって、F(m, x, n, p) = R(m, x ,n, p) / {C(m,x)}^n です。 これをこのまま素直にプログラムコードにしています。 [欠点] 関数 R の計算量がざっと O(x^n) です（本当は他の変数もオーダーに関わってますが）。 分割統治でやってるのだからマルチコア使って並列処理できるのですが、 もっと根本的にアルゴリズムを改善したいです。 142 名前：デフォルトの名無しさん mailto:sage [2014/01/20(月) 22:18:46.73 .net] ちょいと質問だけど、有理数で計算してるの？ 143 名前：140 mailto:sage [2014/01/20(月) 23:12:18.37 .net] >>142 私は、関数 R と D と {C(m,x)}^n の計算は任意精度整数で、 関数 F 内の割り算は有理数型で、 そして最後にそれを倍精度浮動小数点型にしています。 144 名前：デフォルトの名無しさん mailto:sage [2014/01/20(月) 23:44:20.55 .net] これってアルゴリズムの問題じゃなくて数学の問題じゃね？ オイラーのガンマとか関係してそうだけど。数学できるやつならパパっと式が出てくるんだろうな。 残念ながら僕は数学ができたという過去形なので無理です。 145 名前：デフォルトの名無しさん mailto:sage [2014/01/21(火) 00:23:40.46 .net] F(m,x,n,p)=C(m,p)*{C(m-p,x)/C(m,x)}^n ？ 146 名前：140 mailto:sage [2014/01/21(火) 00:24:59.04 .net] >>144 わたしも、これを代数的に解く方法は知らないのでプログラムで解こうと思いました。 プログラムで解く場合に n 乗よりも低いオーダーのアルゴリズムが存在しないのなら諦めます。 今のところ私が挑戦した限りでは、n 乗のオーダーが限界でした。 147 名前：140 mailto:sage [2014/01/21(火) 00:42:19.10 .net] >>145 それは違います。 例えば F(4, 2, 2, 1) で計算してみてください。 つまり、4枚のカードから2枚ランダムに引くことを2回繰り返して、 一回も引かれなかったカードが1枚存在する確率です。 本当は 2/3 ≒ 66% です。 しかし >>145 で計算すると 1/1 = 100% になってしまいます。 148 名前：デフォルトの名無しさん mailto:sage [2014/01/21(火) 01:34:30.52 .net] >>145 C(m,p) で選んだp枚に対し、m-p枚からx枚選ぶ過程が一意でなく重複が入ってるから×だな 149 名前：デフォルトの名無しさん mailto:sage [2014/01/31(金) 19:15:00.72 .net] a[0]からa[n-1]までの配列があって、 その中身をコンマで区切って表示したい print a[i] + ',' みたいなことをすると、最後の要素にもコンマが付くので、 これをうまく避けるアルゴリズムは無いものか 150 名前：デフォルトの名無しさん mailto:sage [2014/01/31(金) 19:50:00.15 .net] if (a=next()) { push(a); while (a=next()) push(cat(",",a)); } 151 名前：デフォルトの名無しさん mailto:sage [2014/01/31(金) 21:02:09.78 .net] for (int ic = 0; ic < n; ++ic) {std::cout << a[ic]; if (ic < n - 1) std::cout << ',';} 152 名前：デフォルトの名無しさん mailto:sage [2014/01/31(金) 21:15:03.01 .net] 出力してしまわずに一旦文字列に出して、 出来上がってから最後のコンマを1個削る 153 名前：デフォルトの名無しさん mailto:sage [2014/01/31(金) 21:30:32.04 .net] n が小さければ >>151 の方法でOK。シンプルでわかりやすい。 ただし、if 文で n 回の比較が発生するから、n があまりに大きい場合は >>152 のやり方がいいと思う。 最後の文字を削れない場合は for 文で a[n-2] まで ',' と一緒に出力して、追加で a[n-1] を出力するか。 >>150 は何の言語？ 154 名前：デフォルトの名無しさん mailto:sage [2014/01/31(金) 21:35:58.74 .net] 最初の要素と残りの配列に分ければいいだろと、Haskell なら考える 155 名前：デフォルトの名無しさん mailto:sage [2014/01/31(金) 22:35:19.83 .net] 分ければ簡単なんだけど、同じような処理を2回書く羽目になるんだよな 156 名前：デフォルトの名無しさん mailto:sage [2014/01/31(金) 22:38:32.60 .net] >>149 puts a[0..n-1].join('.') 157 名前：デフォルトの名無しさん mailto:sage [2014/01/31(金) 22:49:27.58 .net] 結局、うまい方法が無いので言語側で join 機能を提供している join があるならそれを使うのが最もスマート 158 名前：SD mailto:sage [2014/02/01(土) 15:47:33.85 .net] String d="" String r=""; for(String b:a){r+=d+b;d=",";} 159 名前：デフォルトの名無しさん mailto:sage [2014/02/01(土) 16:20:22.09 .net] コンマが先にあると考えて、先頭のコンマを削除する方式だな 毎回同じ値で更新するのが美しくない 160 名前：デフォルトの名無しさん mailto:sage [2014/02/01(土) 16:50:11.43 .net] if(0<a.length)print(a[0]); for(int i=1;i<a.length;i++)print(','+a[i]); 161 名前：デフォルトの名無しさん mailto:sage [2014/02/01(土) 17:23:17.66 .net] それが正解だろうな lengthが2回出てくる以外は殆ど無駄がない 162 名前：デフォルトの名無しさん mailto:sage [2014/02/01(土) 17:47:07.99 .net] printの部分が長いコードなど２つに分けたくない事情があるときは>>158の方がいい。 定数へのポインタを代入するだけなので効率も悪くない。 163 名前：デフォルトの名無しさん mailto:sage [2014/02/01(土) 18:04:45.52 .net] 長くなくても、似た出力が2箇所あるのは嫌だな コンマ部分だけ出力が別にあるのは構わないけど str = a[i]; if (i < n - 1) {str += ','} こうすれば一箇所 >>151とほぼ同じ 164 名前：デフォルトの名無しさん mailto:sage [2014/02/01(土) 18:09:57.02 .net] 俺もかつては悩んだがあるとき以降はずっとこう書いてる。 for (int i = 0; i < a.size; i++) { if (i != 0) print(,) print(a[i]) } 165 名前：デフォルトの名無しさん mailto:sage [2014/02/01(土) 18:53:19.10 .net] 俺ならdo-whileの条件文にカンマ出力ねじ込んで軍事法廷に召喚される 166 名前：デフォルトの名無しさん mailto:sage [2014/02/01(土) 19:42:53.65 .net] >>164 for (int i = 0; i < a.size; i++) { print(a[i]) if (i < a.size - 1) print(,) } 最初だけコンマを付けない、よりは最後だけコンマを付けない、の方が 人間が理解しやすいような ただ、条件文が読みにくい 167 名前：デフォルトの名無しさん mailto:sage [2014/02/01(土) 19:46:34.49 .net] は？ 168 名前：デフォルトの名無しさん mailto:sage [2014/02/01(土) 19:48:28.34 .net] 二個目以降はカンマがつくよ、であり読みやすい。 しかも、ループごとの状態がたとえば[a, b, c]のとき、 0: a 1: a, b 2: a, b, cとなっておりどの状態も気持ちいい。 後カンマ方式だと、 0: a, 1: a, b, 2: a, b, cとなり、0と1の状態が気持ち悪い。 169 名前：デフォルトの名無しさん mailto:sage [2014/02/01(土) 21:03:39.16 .net] それはただのバグだな 170 名前：デフォルトの名無しさん mailto:sage [2014/02/01(土) 23:11:17.91 .net] 関数型の発想で命令型のコードを導く手順 (1) 最初は組み込みメソッド join を使って簡潔に書く(>>156,157) 　puts xs[0..n-1].join(', ') (2) joinの代わりに畳み込み(fold)であるメソッド inject で書き直す 　puts xs[0..n-1].inject('') { |ys, x| 　　　if ys.empty? then x.to_s else ys << ', ' + x.to_s end 　} 　# docs.ruby-lang.org/ja/2.1.0/class/Enumerable.html#I_INJECT (3) これを命令型へ書き換えることを考える 　　まず(2)では先頭要素であるか否かを累積変数 ys が空か否かで判断している 　　この累積変数の代わりに、先頭か否かを表すフラグ is_first を使う 　is_first = true 　for x in xs[0..n] 　　　if is_first 　　　　　printf x.to_s 　　　　　is_first = false 　　　else 　　　　printf ", %s", x.to_s 　　　end 　end 　printf "&yen;n" ここまで展開すれば、これをたとえばC言語へ移植することも容易いだろう 171 名前：デフォルトの名無しさん mailto:sage [2014/02/01(土) 23:18:11.99 .net] >>168 この考え方、感じ方は大事だね 例えば、これを範囲を指定してコンマ区切りの文字列を返す関数にしたら 前者ならすんなり行く 172 名前：デフォルトの名無しさん mailto:sage [2014/02/02(日) 00:01:46.64 .net] テキストエディタでコンマ区切りのデータを編集する時に、 どうしてもコンマが余ったり足りなかったりする 173 名前：デフォルトの名無しさん mailto:sage [2014/02/02(日) 00:49:30.38 .net] print (xs[0]) for x in (xs[1..n]) 　print (", " + x) では間違い？ 174 名前：デフォルトの名無しさん mailto:sage [2014/02/02(日) 01:00:24.64 .net] 例えばファイルへの出力に変更した時に、 複数箇所のprintを直して回らないといけない 175 名前：デフォルトの名無しさん mailto:sage [2014/02/02(日) 01:07:52.48 .net] バカ？ 176 名前：デフォルトの名無しさん mailto:sage [2014/02/02(日) 01:15:24.41 .net] >>173 もし言語がRubyであるならば、以下の問題がある (1) 最後のendが抜けている（これは、おそらくtypoだと思う） (2) メソッド print は実行のたびに改行するから、期待する結果とは一致しない (3) (2)の対策として print の代わりに printf を使ったとしても、 　もし xs が空であると xs[0] の値は nil になるから、 　メソッド printf の実行が引数エラーになる 　（メソッド仕様上、printf の第一引数は文字列であるべき） 177 名前：デフォルトの名無しさん mailto:sage [2014/02/02(日) 01:21:27.65 .net] ぷーん 178 名前：デフォルトの名無しさん mailto:sage [2014/02/02(日) 01:34:06.21 .net] >>176 ネタにしてはつまらんし、素なら悲しい。 179 名前：デフォルトの名無しさん [2014/02/02(日) 08:15:43.49 .net] for(i=0;i<n;i++) printf((i==0)?"%d":",%d",a[i]); または， for(i=0;i<n;i++) printf("%s%d",(i==0)?"":",",a[i]); int a[]; としてるけど． 180 名前：デフォルトの名無しさん mailto:sage [2014/02/02(日) 08:40:42.33 .net] 出力するぎりぎりまで判断を遅延するのが賢いので、 文字列に修飾子としてコンマの追加の条件文を書けるような言語なら綺麗に書ける筈 三項演算子はそれに一番近い 181 名前：151 mailto:sage [2014/02/02(日) 21:14:08.47 .net] for (int ic = 0; ic < n; ++ic) {if (ic > 0) std::cout << ','; std::cout << a[ic];} // 宗旨替え 182 名前：デフォルトの名無しさん mailto:sage [2014/02/03(月) 00:06:18.13 .net] 前にコンマが付いてると見るか後にコンマが付いてると見るかは、 完全に相対的なので、どっちでも等価 セパレータだと思えば前だし、エンドマークだと思えば後 文末のセミコロンが本当は行の区切りだと判ってる人には、 後にコンマが付くのが基本で、例外的に外しているという考えに近い筈 183 名前：デフォルトの名無しさん mailto:sage [2014/02/03(月) 00:40:01.64 .net] エンドマークだぁ？？ 例外的に外すという考えだぁ？？ カンマは区切りっしょ。 CSV形式という文化はずーっと前からあるように。 Comma Separated Valuesだぞ？ 184 名前：デフォルトの名無しさん mailto:sage [2014/02/03(月) 00:55:38.64 .net] イタリヤコンマ 185 名前：デフォルトの名無しさん mailto:sage [2014/02/03(月) 19:57:58.39 .net] pascalで最後の行だけはセミコロン付けてはならんというルールに律儀に従っていればいい 186 名前：デフォルトの名無しさん mailto:sage [2014/02/03(月) 20:21:35.73 .net] ターミネータとセパレータの違いだ 187 名前：デフォルトの名無しさん mailto:sage [2014/02/03(月) 21:22:48.71 .net] コンマタレブー 188 名前：デフォルトの名無しさん mailto:sage [2014/02/07(金) 11:44:16.71 .net] Cは最後のやつにもセパレータ付ける文化。 189 名前：デフォルトの名無しさん mailto:sage [2014/02/07(金) 12:49:17.86 .net] じゃなくて、最後に(も)付くのがターミネータで、 C言語のコンマのように、最後には付かないのがセパレータ。 ついでに言うと、C言語においてセミコロンは、式文やdo-while文みたいな、 「一部の文の」ターミネータ。あと for の頭部でセパレータとしても使われてる。 190 名前：デフォルトの名無しさん mailto:sage [2014/02/07(金) 23:08:20.67 .net] 単に空文の存在を許容してるだけ 191 名前：デフォルトの名無しさん mailto:sage [2014/02/08(土) 10:34:10.24 .net] 違う。 C言語において「空文」は、「空文字列にセミコロンが付いたもの」だよ。 192 名前：デフォルトの名無しさん mailto:sage [2014/02/10(月) 00:14:12.54 .net] 違う。 C言語において「空文」は、「セミコロンだけの文」だよ。 193 名前：デフォルトの名無しさん [2014/02/10(月) 17:16:31.68 .net] 死ねゴミ共がw ばーかw 194 名前：デフォルトの名無しさん mailto:sage [2014/02/10(月) 17:30:49.07 .net] 違う。 どうでもいい。 195 名前：デフォルトの名無しさん mailto:sage [2014/02/11(火) 08:40:29.35 .net] >>149 最後の","を'\0'で潰すのがはやい 196 名前：デフォルトの名無しさん mailto:sage [2014/02/11(火) 09:17:01.18 .net] そんなことできる言語もめっきり無くなったな 197 名前：デフォルトの名無しさん mailto:sage [2014/02/11(火) 16:18:25.25 .net] C言語だって文字列定数とかを指してたらやっちゃダメだし 198 名前：デフォルトの名無しさん mailto:sage [2014/02/11(火) 16:31:18.09 .net] どう考えてもバグの宝庫な仕様だよな 199 名前：デフォルトの名無しさん mailto:sage [2014/02/11(火) 19:16:39.02 .net] 文字列がイミュータブルなこととミュータブルなことのどっちが？ それとも \0 ターミネーション？ 200 名前：デフォルトの名無しさん mailto:sage [2014/02/13(木) 11:20:17.62 .net] 文字列は文字数と文字データの構造体だったんだけどな 201 名前：デフォルトの名無しさん mailto:sage [2014/02/13(木) 23:24:36.15 .net] lenで1バイト持っても末尾の00に1バイト持っても同じだしな 202 名前：デフォルトの名無しさん mailto:sage [2014/02/13(木) 23:33:36.34 .net] 最初にサイズが分かるか、辿っていかないとサイズが分からないかの違いは有る。 前者はBSTR型とかね。 203 名前：デフォルトの名無しさん mailto:sage [2014/02/13(木) 23:49:03.85 .net] データチャンクだと、サイズ+データの繰り返しだな 204 名前：デフォルトの名無しさん mailto:sage [2014/02/14(金) 00:32:59.75 .net] >>201 256以上の長さの文字列どうするんだよ？ 205 名前：デフォルトの名無しさん mailto:sage [2014/02/14(金) 08:03:36.41 .net] そんなもん、長さに4バイト取っても必ず有限だろ 206 名前：デフォルトの名無しさん mailto:sage [2014/02/14(金) 11:03:48.78 .net] そう言えば、255バイト長のパケットを送れない通信プロトコルがあったな。尤もあれは長くても508バイト長までだけど。 可変長文字列を管理するデータ構造を考えるだけでも楽しそうだね。 207 名前：デフォルトの名無しさん mailto:sage [2014/02/14(金) 19:07:04.66 .net] >>204 0-127 のときは そのままの値 128-255 のときは (その値 - 127) x 128 + その次のバイトの値 ただしその次のバイトの値が 0-127 のときはその次のバイトの値をそのまま使うが その次のバイトの値が 128-255 のときはさらに (上の値 - 127) x 128 + その次の次の値とする とか 208 名前：デフォルトの名無しさん mailto:sage [2014/02/14(金) 23:05:25.36 .net] 7bitのリトルエンディアンで格納して、最終バイトの8bit目を立てる 209 名前：デフォルトの名無しさん mailto:sage [2014/02/17(月) 01:31:20.81 .net] BigInt 210 名前：デフォルトの名無しさん mailto:sage [2014/03/05(水) 11:39:12.46 .net] 文字列の中のパターンの置き換えをおしえてください。 たとえばxを任意の文字としてabxをbxに置き換えbxをxにおきかえるとしたら abcをcに置き換えたいです。 この時、この置き換え操作は無限に続かないことを前提としています。 この例では一つのパターンでしたが、プログラムの入力としてパターンと 置き換える文字列、出力として置き換え後の文字列であるものの 作成方法が分かりたいです。 211 名前：デフォルトの名無しさん [2014/03/05(水) 12:09:18.80 .net] 正規表現ライブラリのソースでも読んでみたら 212 名前：デフォルトの名無しさん mailto:sage [2014/03/09(日) 19:39:16.05 .net] 再帰処理を使った順列のプログラム（JavaScript）について質問があるのですが、 ここで教えてくださる人はいますか？ 213 名前：デフォルトの名無しさん mailto:sage [2014/03/09(日) 20:01:44.88 .net] >>212 とりあえず質問内容を書いてみたら？ 答えるかどうかは気分次第だけど。 214 名前：デフォルトの名無しさん [2014/03/09(日) 20:20:18.06 .net] アルゴリズムとデータ構造の勉強に使える本で木構造やリストの実装、 バックトラックとか動的計画法まで載ってる本で読みやすくてコードが書いてるやつ 何がいい？ はじめてのアルゴリズム　上原 とかエイホさんのとかっていいの？ 215 名前：デフォルトの名無しさん mailto:sage [2014/03/09(日) 20:44:41.37 .net] アルゴリズムイントロダクションの総合版買っとけばいいよ 216 名前：デフォルトの名無しさん mailto:sage [2014/03/09(日) 23:15:50.81 .net] あの巨大な枕か

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef