15/03/26 17:08:05.75 BDjvcE7V.net
n桁のm進数の桁を入れ替えるプログラムを作りたいのですが、どうしたら効率的でしょうか。
桁数分(n個)ループを回すような愚直な方法しか思い付きません。
任意の並び替えを実現したいのですが、「○桁目を右に△個ずらす」ようなアルゴリズムでも構いません。
それを何回かやれば任意のケースに対応できると思うので。
nは16まで、mは64までに限っても良いです。
333:デフォルトの名無しさん
15/03/26 17:40:04.67 4eocBIkU.net
char C[16];
swap(C[x], C[y]);
334:デフォルトの名無しさん
15/03/26 18:10:22.30 DVfty8jF.net
二進数を考える。
左シフトはN*2^M 右シフトはN/2^Mだよな。
これを一般化して、N*Radix^Mで左シフト N/Radix^Mで右シフト
出来そうじゃね？
335:デフォルトの名無しさん
15/03/26 18:15:03.52 DVfty8jF.net
結局POW使うんであればループは避けられん。か？
336:デフォルトの名無しさん
15/03/26 18:19:03.95 nSqXA52d.net
設計に制限がなければ
n桁m進数表現クラスを作ってその桁を入れ替える、って素直にやるけど
337:デフォルトの名無しさん
15/03/26 18:25:41.64 BDjvcE7V.net
自分で言うのもなんですが>>332に書いた愚直な方法だとコストはO(m^n)で最悪ですね。
338:デフォルトの名無しさん
15/03/26 18:26:10.15 4eocBIkU.net
なるべく一変数(多倍長一変数も)でやりたいなら
m < 2 ^ k となる最小のkを見つけて2進k桁の移動をする。
339:デフォルトの名無しさん
15/03/26 18:29:36.94 4eocBIkU.net
>>338だと全体の数値がいい加減だった。
各桁を一変数にいれたほうがいいな。
結局、数値を取り出そうとすると同程度のコストだ。
340:デフォルトの名無しさん
15/03/26 18:32:38.24 nSqXA52d.net
n桁m進数をx (>0)とする
i桁の数字x_i = (x - (x / m^(i+1) ) * m^(i+1)) / m^i
^は指数演算 /は整数同士の割り算であまり切り捨て
i桁とj桁の入れ替えは
x = x + (x_i-x_j) * (m^j - m^i)
これで行けるかな？
341:デフォルトの名無しさん
15/03/26 18:46:41.53 DVfty8jF.net
URLﾘﾝｸ(ideone.com)
手抜きで書くんだったらこんな感じだけど、数学的にやったらもっと別の解があるのかなー？？
俺、数学ダメだから識者に任せる。
342:デフォルトの名無しさん
15/03/26 20:10:26.73 BDjvcE7V.net
もし、任意の入れ替えを諦めてサイクリックな置換にだけ対応しようとしたらコスト減らせたりするでしょうか。
例えば8桁の
abcdefgh
を
ghabcdef
に入れ替えるようなケースです。
343:デフォルトの名無しさん
15/03/26 20:19:07.25 BDjvcE7V.net
配列要素全部を入れ替えようとしなければ>>340で一発ですかね？
ちょっと考えてみます。
344:デフォルトの名無しさん
15/03/28 18:45:50.47 EQ3zAKR0.net
ポインターって識別子として使ってもいいのか？
時間によって値が変わるとかないよな？
345:デフォルトの名無しさん
15/03/28 20:37:48.75 /OKG1/Xj.net
問題ないよ、ポインタが有効な間は。
346:デフォルトの名無しさん
15/03/28 20:38:30.01 EQ3zAKR0.net
非有効でもハッシュテーブルのキーとして使ってもいいですよね。
347:デフォルトの名無しさん
15/03/28 21:42:14.53 HPuG9XXV.net
いいよ、ポインタなんてただの数字だよ。
348:デフォルトの名無しさん
15/03/28 21:50:37.06 LYzvh/ES.net
数字 w
349:デフォルトの名無しさん
15/03/28 22:02:14.95 wVsC1fdL.net
そりゃあ、数字だよな。10進数が16進数や2進数になってるだけだし。
でも、「数字」じゃなくて「数値」と言って欲しかった
350:デフォルトの名無しさん
15/03/29 02:18:34.60 abbduuww.net
>>342
そりゃ、簡単にできる。
Rubyでは例えば、配列の先頭要素を削除する、shiftでも、
一々、別の配列にコピーしないで、同じ配列を使う
配列の要素のstart位置を、0から1へ変えて、
配列の要素数、lengthを1減らし、
要素[0]には、nilを代入する
同様に、start, end位置を管理すれば、
コピーすることなしに、その配列をそのまま使える
351:デフォルトの名無しさん
15/03/29 03:38:15.93 gsIKbDqn.net
>>346
寿命が尽きたオブジェクトへのポインタを使った場合の動作は保証されないよ。
352:デフォルトの名無しさん
15/03/29 04:28:35.51 xroka6Go.net
>>350
CやC++でも？