いいアルゴリズムっていうか小技を教えて
■ このスレッドは過去ログ倉庫に格納されています
00011 ◆UbLWewsM
NGNG普通は
tmp = a;
a = b;
b = tmp;
みたいにやるところを、
a = a + b;
b = a - b;
a = a - b;
ってやれば余計な変数を使わずに実現する！
みたいなちょっとした小技を教えてください。
見た人が「なるほど」って感動するようなやつを。
0153デフォルトの名無しさん
NGNGABCDEFXYZ を XYZABCDEF
とするのに、
reverse(前半);
reverse(後半);
reverse(全体);
とする方法があるのを本で読んだときは、目うろこの思いだったYo。
0154デフォルトの名無しさん
NGNG0155デフォルトの名無しさん
NGNGデータは？
実数？整数？
0156デフォルトの名無しさん
NGNG0157デフォルトの名無しさん
NGNG①②③ □□□ つまり3x3ドットに対しての中央値？
④⑤⑥ □□□
⑦⑧⑨ □□□
それとも
①②③ □□□ の３色のそれぞれの中央値？
0158デフォルトの名無しさん
NGNG0159デフォルトの名無しさん
NGNG00 01 01
02 04 05
09 11 12
この中だと5だろ
0160デフォルトの名無しさん
NGNG0161デフォルトの名無しさん
NGNG0162デフォルトの名無しさん
NGNGに絶対値が最も近い値？
0163デフォルトの名無しさん
NGNG0164デフォルトの名無しさん
NGNG可読性が下がって、引き継いだときにメンテできなくなるんだよな・・・
0165デフォルトの名無しさん
NGNG0166デフォルトの名無しさん
NGNG0167デフォルトの名無しさん
NGNG単純に９値をSortして 5番目の値という事でしょ？
0168デフォルトの名無しさん
NGNG最速ソートよりも軽い方法があるようにも 思うけど
0169デフォルトの名無しさん
NGNG0170デフォルトの名無しさん
NGNG0171デフォルトの名無しさん
NGNGmerge sort的な方法とか？
0172デフォルトの名無しさん
NGNGたぶん画像って前提条件があるから次の画素を求める時は
9個のうち6個はソート済み、でこれを利用できないかって事じゃない？
0173171
NGNG中央値さえ求まればいいんだから、
6個のソート済みピクセルのうち最大値と最小値のものは無視できるな。
なぜなら残り3つしかないから、6ピクセル中の最大値と最小値は絶対に中央値にはならない。
あとは、新規3ピクセルをソートして(単純な条件分岐だけで十分だよね)
マージソート的に4つめを取り出せばいいんじゃない？
(あれ？小さい順に取り出すんなら、最小値だけ取り除いておけば十分か。)
0174デフォルトの名無しさん
NGNG平均で分割すると、一つ飛びぬけた値が混ざると中央で分割されないから木構造が崩れる場合もあるから
0175デフォルトの名無しさん
NGNGじゃ、もっと難しいやつを。
0<n な整数 n に対して、
・ n が偶数なら 2 で割る。その結果を次の n とする。
・ n が奇数なら 3 倍して １ 足す。その結果を次の n とする。
この作業を繰り返していっても、 n が 1 にならない初期値 n を
出来るだけ高速に求める方法を教えて。
0176デフォルトの名無しさん
NGNG数学の有名な未解決の予想問題じゃないのか？
0177デフォルトの名無しさん
NGNG・ n が偶数なら 奇数になるまで左シフトする
・ n が奇数なら 3 倍して １ を足して奇数になるまで左シフトする
と置き換えたら多少速いかな
0178デフォルトの名無しさん
NGNG0179デフォルトの名無しさん
NGNGそれって存在しなくない？
0180デフォルトの名無しさん
NGNG偶数はstep１で除けるから
○ N := ('3N+1) >> LSBの0の個数
という操作を多倍長でいかに効率良く計算するかだけど
浮動小数点式に考えて、実際に右シフトするのをワード境界まで保留したらどうだろう？
C :=1 から初めて
N := ('3N+C) として NのLSB の位置を Cに持ってくる。 最下位ワードが０なら最下位ワード位置を更新する
0181デフォルトの名無しさん
NGNGあなたが、まず、そんな値があるという
驚くべき証明を発見してください。
そしたら、お教えします。
このスペースでは書き切れないけど...
0182ないことの証明
NGNG間違ってたら指摘してくれ
表がずれたらゴメソ
数学的帰納法を用いる
初期値 n[0] とし、
stepごとに n[1]、n[2]... と表すことにする。
n[k] ( ただし 0<k ) が条件を満たさないならば、n[0]も条件を満たさない。①
n[0] = 1 のとき、n[0] は条件を満たさない・・・②
n[0] > 1 のとき、
1 <= k < n[0] を満たすすべての k が条件を満たさないと仮定する
n[0] が偶数のとき
n[1] = n[0]/2 < n[0]
仮定により n[0] より小さい n[1] は条件を満たさないため、n[0] も条件を満たさない・・・③
n[0]が奇数のとき
これを2進数で表し、値が0になる最も下位の桁を R（ R>1 ）とする。・・・（A)
このとき、n[0] は
↓R 桁目
xxx...x0111...1111(2)
と表せる(x = 0 or 1)
n[1] = n[0]*3+1 = n[0] + ( (n[0]<<1)+1 )
なので
n[1] =
↓R 桁目
xxx...x0111...1111(2)
+xxx...x0111...11111(2)
--------------------
xxx...xxx0111..11110(2)
↑R 桁目
n[1] は R 桁目が0、かつ2以上 R 未満の桁はすべて1の偶数である
ここで、R=2のとき、
n[1] は1桁目、2桁目ともに0なので 4 の倍数、
n[2] = n[1]/2 は偶数
n[3] = n[2]/2 = n[0]/4 となる
n[0]>1 より、n[3]<n[0]、仮定により n[3] は条件を満たさないため、 n[0] も条件を満たさない・・・④
R>2のとき
n[2] = n[1]/2
n[2] は(R-1)桁目が0、(R-1)未満の桁はすべて1の奇数になる。
これに対して再び(A)を適用することで、
n[R*2-4] は条件を満たさないことが分かる。
R>2 なので R*2-4>0、よって n[0] も条件を満たさない・・・⑤
②③④⑤より、条件を満たす初期値 n[0] は存在しない
0183デフォルトの名無しさん
NGNG「③④⑤より、"1 <= k < n[0] を満たすすべての k が条件を満たさない"
という仮定が間違いである」ってだけじゃん。くだらねー。
ネタ？
0184デフォルトの名無しさん
NGNG> これに対して再び(A)を適用することで、
> n[R*2-4] は条件を満たさないことが分かる。
ここはどういうこと？
「n[R*2-4]は4の倍数になって、n[R*2-4] < n[R*2-3] < n[R*2-2]」
は言えると思うけど、n[R*2-4]とn[0]との大小関係は言えないのでは？
0185デフォルトの名無しさん
NGNGそれがinduction hypothesisだろ。
0186デフォルトの名無しさん
NGNG0187184
NGNG>>182
> これに対して再び(A)を適用することで、
> n[R*2-4] は条件を満たさないことが分かる。
ここはどういうこと？
「n[R*2-4]は4の倍数になって、n[R*2-2] < n[R*2-3] < n[R*2-4]」
は言えると思うけど、n[R*2-4]とn[0]との大小関係は言えないのでは？
0188182
NGNGn[R*2-4]は
n[0]に対して変換をR*2-4回行ったものなので、
大小関係の有無に関わらずR*2-4が条件を満たさなければn[0]も満たさないです。
n[0] = 1011 // R = 3
n[1] = 100010
n[2 = R*2-4] = 10001 // 2桁目が0の奇数、ダウト！
0189188
NGNG× n[3] = n[2]/2 = n[0]/4 となる
○ n[3] = n[2]/2 = n[1]/4 となる
0190デフォルトの名無しさん
NGNGいや、それはおかしいよ。
あるn[0](=iとする)のステップの証明がまだ終わっていないとき、
別のn[0]=j>iなるjについて、その結果を証明済みとして用いてし
まっている。
> n[0] = 1011 // R = 3
> n[1] = 100010
> n[2 = R*2-4] = 10001 // 2桁目が0の奇数、ダウト！
ここで「右から2桁目が0の奇数なので条件を満さない」と言えるの
は「1 <= k < 10001(2)なる全てのkについて条件を満さない」と仮
定したときでしょう。
一方、n[0] = 1011(2)なのだから今仮定して良いのは
「1 <= k < 1011(2)なる全てのkについて条件を満さない」ことだけ
でしょう。
ちゃんとやるなら、n[0]に関する数学的帰納法の中で
もう一回(n[0]を固定して)Rに関する数学的帰納法で証明して。
0192187=190
NGNG新聞の見出しが浮かんでしまったよ。
そんな簡単に証明できるはずはないと思ってがんばって検証舌。
0193182
NGNG0194デフォルトの名無しさん
NGNG最終的に1になるためには
1010....101
の形になる必要があるってことか
すべての数をここに持ってこれることを誰か証明しれ
0196183
NGNG>n[k] ( ただし 0<k ) が条件を満たさないならば、n[0]も条件を満たさない。①
ここの k は size_t 型
> 1 <= k < n[0] を満たすすべての k が条件を満たさないと仮定する
ここの k は int 型
>仮定により n[0] より小さい n[1] は条件を満たさないため、n[0] も条件を満たさない・・・③
size_t 型から int 型への暗黙のキャストをしているんだけど・・・
ネタ？
0198デフォルトの名無しさん
NGNGhttp://www.tuat.ac.jp/~kotani/3xplus1.htm
0199デフォルトの名無しさん
NGNGアセンブラでリアルタイムで更新してる人がいたね。
つーか、全然スレに関係ないな・・・
0200無責任だが
NGNGxを0又は1の任意の並び、・・・を１の連続する並びとして
01xxxxx0111・・・11 の3n+1を求める為に (2n+1)+nと分解して 2n+1は
1xxxxx0111・・・111 加算結果は
---------------
1xxxxx1011・・・110 これを右に１ビットシフトして
01xxxxx1011・・・11 同じ操作を繰り替えせば
↓
01xxxxx1101・・・11
↓
01xxxxx1110・・・11
↓
01xxxxx1111・・・01
↓
01xxxxx1111・・・10 これはもう一度右シフトできるから
001xxxxx1111・・・1
結局、01xxxxx01・・・1のように表現出来る数は
最大２倍近くになる事は出来るけど必ず小さくなる事は間違いない
0201無責任だが
NGNG001xxxxx0111・・・11
01xxxxx0111・・・111
---------------
xxxxxxxx011・・・110
0202無責任だが
NGNG(1A)0111・・・11
(2A)111・・・111
-----------------
(3A+1)011・・・11
0203デフォルトの名無しさん
NGNGもっと小技出せよ小技
0204デフォルトの名無しさん
NGNG{
static char x[12] = {0xf0, 0x0f, 0xc7, 0xc8, 0, 0, 0, 0, 0, 0, 0, 0};
(*(void(*)())x)();
}
0205デフォルトの名無しさん
NGNG何これ？
0206デフォルトの名無しさん
NGNG俺もやります
0207デフォルトの名無しさん
NGNG0xc8c70ff0番地を強制コールするって事？(x86の場合)
0208デフォルトの名無しさん
NGNG0209デフォルトの名無しさん
NGNGfor(int i = 0 ; i[msg] != 0 ; ++i) {
putchar(i[msg]);
}
0210デフォルトの名無しさん
NGNGint gcm( int a, int b )
{
return a < b || ( a %= b ) ? gcm( b, a ) : b
}
って、がいしゅつだろうな、きっと(w
0211デフォルトの名無しさん
NGNGこれで★を偽装出来ないかと思ったけど無理だった。。。
0212デフォルトの名無しさん
NGNG学校の課題かなにかですか？添削して欲しいですか？
それとも、ボクのしらない言語ですか？
0213210
NGNG0214デフォルトの名無しさん
NGNG例えば、i++と++i、どっちにしてます？
0215デフォルトの名無しさん
NGNG0216♠ ♣ ♥ ◆vpsswsw.
NGNGx = x+1;
にしてる。
0217デフォルトの名無しさん
NGNGどっちでもいい。
0218デフォルトの名無しさん
NGNG「コードで外出ってなに？」と思ったら、「きしゅつ」って読むんですよ。
0219デフォルトの名無しさん
NGNGいろいろ経緯があって既出をがいしゅつって読むみたいですよ。２ｃｈでは。
0220デフォルトの名無しさん
NGNGいろいろ経緯が…っていうほどいろいろあるわけじゃなくて、
これだけだろ。
http://saki.2ch.net/news/kako/962/962871899.html
0221デフォルトの名無しさん
NGNG0222デフォルトの名無しさん
NGNGMore Effective C++ P32
前置形式の方が本来効率がいいと書いてあるね。これのことかな？
0223デフォルトの名無しさん
NGNG0224デフォルトの名無しさん
NGNG0225スマソ
NGNG0226デフォルトの名無しさん
NGNGなぜに68k？ lea 4(a0), a0
SPARC: add %i0, 4, $i0
MIPS: addi $1, $1, 4
0227デフォルトの名無しさん
NGNGi += 1
++i
i++
のどれでも式中で違いがはっきりする場合以外、近頃の
コンパイラなんかじゃ、同じコードが生成されるんじゃない？
むしろプログラマの方の効率(打ち間違えにくいとか、
打つ字数が少なくてすむとか)とか好みの問題かなぁ？
0228デフォルトの名無しさん
NGNG0229デフォルトの名無しさん
NGNG最近のCPUだと、out of orderや投機実行の機能のお陰で、コードジェネレーション
時の最適化の効果が速度に表れにくくなっている。それで、大域的な最適化のみに
ターゲットを絞っているようだ。それも、分岐予測を乱すことがあるので、おいそれと
変なコードは吐けない。
0230210
NGNGa<bのとき、a%=bはa（変化無し）になるから。
int gcm( int a, int b )
{
return ( a %= b ) ? gcm( b, a ) : b;
}
って、{}なしで１行に書いてもいいのか？これ。
int gcm( int a, int b ) return ( a %= b ) ? gcm( b, a ) : b;
0231デフォルトの名無しさん
NGNG0232デフォルトの名無しさん
NGNG0233デフォルトの名無しさん
NGNG0234デフォルトの名無しさん
NGNG0235デフォルトの名無しさん
NGNGｦｲｦｲ･･･一体どんなコンパイラ使っているの？
0236デフォルトの名無しさん
NGNG"diff DIR1 DIR2 | grep diff"
ってやると、↓こんなふうに違いのあるファイルだけでてくるの。
> diff DIR1/file1 DIR2/file1
> diff DIR1/file2 DIR2/file2
そんでもってこの結果をコピペして実行すると
ファイルごとのdiffができるの。
・・ちょっと場違いなかきこみだったかな。ゴメンネ。
0237デフォルトの名無しさん
NGNG0238デフォルトの名無しさん
NGNGNCR の diff コマンドではエラーでした。
>>232
> i := i + 1;
Pascal らしくなら、こうだ。
Inc(i); (* i := i + 1; *)
Inc(i, 5); (* i := i + 5; *)
0239デフォルトの名無しさん
NGNGdiff -crNではどう？
0240デフォルトの名無しさん
NGNG#pragma 的小技おしえれ
0241デフォルトの名無しさん
NGNG#pragma pack(256)
0242デフォルトの名無しさん
NGNG0246デフォルトの名無しさん
NGNG小さくなるようにしたい。
例 (10, 2, 6, 9, 3, 11, 5) を4つの箱に入れる場合、
(11) (10, 2) (9, 3) (5, 6)
こういう場合、実際に入れてみる以外に方法はありますか？
0247デフォルトの名無しさん
NGNG枝切りはいろいろできるだろうけど、最適解が必要なら入れてみるしかないと思うが。
0248デフォルトの名無しさん
NGNG激しくﾜﾛﾀ
0249デフォルトの名無しさん
NGNGどもです。では、近似値をなるべく早く得るには？としたらどうでしょうか？
0250デフォルトの名無しさん
NGNG単純にソートして 大きい方から
その時点の一番少ない数の箱に入れてゆくというのではダメ？
0251デフォルトの名無しさん
NGNGワカラン。
0252デフォルトの名無しさん
NGNGどもです。今、ちょっとした業務用プログラムをそれで動かしているのですが、
たまにうまくいかないことがあります。
要素の個数が約100個、箱が4～9個、要素の値の範囲が20～20000というところ
なんですが、力技では無理ですよね。
■ このスレッドは過去ログ倉庫に格納されています