トップページ⇒tech
41コメント18KB

君ならどう書く? in 厶板

■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん2007/01/18(木) 16:17:17
いろんなとこで行われている「君ならどう書く?」をム板でやってみませんか?既出?

良いコードを求めて出題しても良し。
自分がもっとも良いと思うコードを提示して他者に挑戦を
挑むも良し。

題材は
・パズル
・シェルスクリプトで自動化したくなった作業
・プログラム中で出くわしたちょっとした処理
など何でもOK。あまりにも規模の大きいものは遠慮してください。

使用言語等については出題者が指示すること。
ただし、あまりに条件の限定的なものはつまらなくなるので、他スレで。
0002デフォルトの名無しさん2007/01/18(木) 16:18:50
巡回セールスマン問題の解法
0003デフォルトの名無しさん2007/01/18(木) 16:49:06
じゃあ、
問題:
配列の要素をランダムにシャッフルするコード

配列じゃなくてリストなどでもOK
0004デフォルトの名無しさん2007/01/18(木) 16:51:39
ついでに

問題:
ビット列をランダムにシャッフルするコード
もちろん立っているビットの数が変わってはいけない
0005デフォルトの名無しさん2007/01/18(木) 19:35:46
extern int ビット数を数える(byte);

byte shuffle(byte target)
{
　static List<List<byte>> array;
　if (array == null){
　　array = new List<List<byte>>(sizeof(byte));
　
　　for(int i = 0; i < 255; i++)
　　{
　　　array[ビットを数える(i)].add(i);
　　}
　}

　List<int> backet = array[ビットを数える(target)];

　return backet[Math.Rand(backet.size)];
}

流れ的にこんな漢字化
0006デフォルトの名無しさん2007/01/18(木) 20:18:23
35歳キモPG男が今年中に20代のアイドルPG女と添い遂げるプログラム書いてよ
0007デフォルトの名無しさん2007/01/18(木) 21:36:25
まずはアイドルPGより仕事ができるかどうか
によるんじゃないかな？
その辺はif文で制御だな。
0008デフォルトの名無しさん2007/01/18(木) 22:25:14
>>3
@array=sort{(int rand 3)-1}@array;
0009デフォルトの名無しさん2007/01/18(木) 22:27:24
>>4って
ビット演算ですっきりやれないのかな？
0010デフォルトの名無しさん2007/01/18(木) 22:56:30
>>4を逐次的にやるようにするとこんな感じかな。効率良くは無さそうだが。
# 言語指定が無いから擬似言語で失礼
procedure bitsuffle(BitArray bits)
  on  = pop(bits) // 立っているビットの数
  len = bits.length
  for i = [0, bits.length)
    if rand(len--) < on // 0 <= rand < len, rand ∈ Z
      bits[i] = 1
      on--
    else
      bits[i] = 0
0011デフォルトの名無しさん2007/01/18(木) 23:05:30
１. ビット数の範囲内で表せる乱数を生成する
２. １の乱数とビット列をXORする
３. １で作った値を1ビットローテート
４． ２と３でXOR

でランダムにならないかな？ビット演算よくわかんないけど。
0012デフォルトの名無しさん2007/01/18(木) 23:40:15
それだと立ってるビット数かわるんじゃね？

0b10010110 ... 0
0b00100100 ... 1
0b10110010 ... 2
0b01100101 ... 3
0b11010111 ... 4
0013デフォルトの名無しさん2007/01/19(金) 00:35:11
>>4
完全にランダムにはならないけど、(32ビット整数の場合)

int n = rand() % 32;
x = (x >> n) | (x << (32-n));
x = (x & 0x0000FF00) << 8 | (x >> 8) & 0x0000FF00 | x & 0xFF0000FF;
x = (x & 0x00F000F0) << 4 | (x >> 4) & 0x00F000F0 | x & 0xF00FF00F;
x = (x & 0x0C0C0C0C) << 2 | (x >> 2) & 0x0C0C0C0C | x & 0xC3C3C3C3;
x = (x & 0x22222222) << 1 | (x >> 1) & 0x22222222 | x & 0x99999999;

これを何回か繰り返すとか。
0014デフォルトの名無しさん2007/01/19(金) 08:45:28
テーブルがいいんじゃね？
0015デフォルトの名無しさん2007/01/19(金) 08:49:14
真面目にテーブル作ったらめちゃくちゃ大きくなるような。

というか、問題がコア過ぎ(笑) >>4
0016デフォルトの名無しさん2007/01/19(金) 13:01:01
自己出力プログラム
0017デフォルトの名無しさん2007/01/19(金) 13:27:31
10 LIST
0018デフォルトの名無しさん2007/01/19(金) 14:34:07
Q
0019デフォルトの名無しさん2007/01/19(金) 15:28:47
>>4
コンパイル通してないけど、C にて。
一度ビット並びを配列に展開して、ランダムに組み立てなおすようにしてみた。

typedef unsigned int WORD;
#define BITLEN (sizeof(WORD) * 8)

WORD bit_shuffle(WORD x)
{
　WORD bittbl[BITLEN];
　int p;

　for(p = 0; p < BITLEN; p++) {
　　bittbl[p] = x & 1;
　　x >>= 1;
　}

　p = BITLEN;
　while(p > 1) {
　　int r = rand() % p;
　　x = (x | bittbl[r]) << 1;
　　bittbl[r] = bittbl[--p];
　}

　return x | bittbl[0];
}
0020デフォルトの名無しさん2007/01/19(金) 16:09:09
>>16
Q
0021192007/01/19(金) 16:11:03
>>4
もう一個作ってみた。
0ビット目とランダムビット目を入れ替えていくのをループさせるタイプ。

typedef unsigned int WORD;
#define BITLEN (sizeof(WORD) * 8)
#define LOOPCNT 100

WORD bit_shuffle(WORD x)
{
　int c = LOOPCNT;
　do {
　　int r = rand()%(BITLEN-1)+1;
　　WORD b = (WORD)1 << r;
　　if(x & b) {
　　　if(!(x & 1)) x ^= b | 1;
　　}
　　else {
　　　if(x & 1) x ^= b | 1;
　　}
　} while(--c);

　return x;
}
0022デフォルトの名無しさん2007/01/19(金) 22:11:47
>>3
そういやVCのSTLのは高速化ねらって厳密にランダムには並べ替えてないんだよね。
2つ以上要素があるとき、シャッフル前と同じ並びになることがない。
だから要素が少ないとき統計的に問題がある。
0023デフォルトの名無しさん2007/01/19(金) 22:47:19
for(i = 1; i < length; i++) swap(p+i, p+random(i));
//randomは引数未満の正の整数をランダムに返す

みたいなのでいいんだっけか？自信ない
0024デフォルトの名無しさん2007/01/23(火) 04:36:24
【ネガティブ派遣根性チェック】

3つ以上、思い当たる点があればアナタの性格はひん曲がっており、ネガティブ負け組人生を歩んでいます。

□派遣先の人事権のある社員の意見はたとえ間違っていてもマンセーする
□派遣先から「いつまでもここで仕事してくださいね(安い金でｗ)」と言われている
□自社に仕事を持ち帰れるように言われるとムカつく
□自社で仕事なんてできるわけがない
□派遣労働の問題点の話題が出ると感情剥き出しにする
□派遣労働の問題を指摘する人は嫌いだ
□派遣先には仕事だけでなく自分のプライベートについても指示して欲しい
□自分の月額金額を知らない
□派遣先社員より自分の生涯収入が低いのは当然だ
□派遣先に尻尾を振り、いつまでも派遣を続けることが大切だ
0025デフォルトの名無しさん2007/01/23(火) 10:19:10
>>16
HQ
0026デフォルトの名無しさん2007/01/23(火) 19:17:07
uint = 32bitかつrandが0から2^32までの値を生成すると仮定する。
理屈としては2,4,8,16,32とシャッフルする範囲を拡大していく方法でO(logN)
uint bit_shuffle(uint x){
    uint r1,r2;
    r1 = rand() & 0x55555555;
    r2 =   r1 ^ 0x55555555;
    x = (x & (r1|r1<<1) ) | (x>>1 & r2) | (x<<1 & r2<<1);
    r1 = rand() & 0x33333333;
    r2 =   r1 ^ 0x33333333;
    x = (x & (r1|r1<<2) ) | (x>>2 & r2) | (x<<2 & r2<<2);
    r1 = rand() & 0x0F0F0F0F;
    r2 =   r1 ^ 0x0F0F0F0F;
    x = (x & (r1|r1<<4) ) | (x>>4 & r2) | (x<<4 & r2<<4);
    r1 = rand() & 0x00FF00FF;
    r2 =   r1 ^ 0x00FF00FF;
    x = (x & (r1|r1<<8) ) | (x>>8 & r2) | (x<<8 & r2<<8);
    r1 = rand() & 0x0000FFFF;
    r2 =   r1 ^ 0x0000FFFF;
    x = (x & (r1|r1<<16)) | (x>>16& r2) | (x<<16 & r2<<16);
    return x;
}
0027262007/01/23(火) 21:15:59
俺は馬鹿か。
(a & m) | (b & ~m)  　　== 　　( (a ^ b) & m) ^ a
ということを、うっかり忘れてた。
これで十分だな。
uint bit_shuffle(uint x){
    uint y;
    y = (x ^ x>>1 ) & rand() & 0x55555555;
    x ^= y | y<<1;
    y = (x ^ x>>2 ) & rand() & 0x33333333;
    x ^= y | y<<2;
    y = (x ^ x>>4 ) & rand() & 0x0F0F0F0F;
    x ^= y | y<<4;
    y = (x ^ x>>8 ) & rand() & 0x00FF00FF;
    x ^= y | y<<8;
    y = (x ^ x>>16) & rand() & 0x0000FFFF;
    x ^= y | y<<16;
    return x;
}

0028デフォルトの名無しさん2007/01/24(水) 00:34:27
>>27
すげー

でも仕事でこんなソース回ってきたら、なんの処理なのか理解できないかも・・・
0029・∀・）っ-○◎●創聖のダンゴリオン ◆DanGorION6 2007/01/24(水) 01:37:06
VC++のrand()は線形合同で0〜32767だからうまく混ざらない。

0030デフォルトの名無しさん2007/01/24(水) 11:44:41
>>27
品質が微妙な気がするがそれは速度重視？
4bits で、途中の rand の全パターンを計算してみる検算プログラム。
こっちが間違ってる？
#include <stdlib.h>
#include <stdio.h>
int main( void )
{
for ( int src = 0; src < 16; src++ ) {
for ( int i = 0; i < 4; i++ ) {
int x = src;
int y = (x ^ (x>>1) ) & ((i&2)*2+(i&1))/*0,1,4,5*/;
x ^= y | (y<<1);
for ( int j = 0; j < 4; j++ ) {
int y = (x ^ (x>>2) ) & j;
x ^= y | (y<<2);
printf( "%x -> %x (%x %x)\n", src, x, (i&2)*2+(i&1), j );
}
}
}
return 0;
}
0031デフォルトの名無しさん2007/01/24(水) 13:43:15
アルゴリズム的には>>27はrandがちゃんと乱数なら
どのビットへも均等に1/32の確率で移動するよね。

>>30
randって2bit目は常に0なのか。2とか出ない、と。勉強になるなぁ。
0032デフォルトの名無しさん2007/01/24(水) 15:04:04
>>27のコード、こう書いたほうが一時変数が1個少なくなるのに今気づいた。
x ^= y = (x ^ x >> 1 ) & rand & 0x55555555;
x ^= y << 1;
まぁ乱数の速度がほぼアルゴリズムの速度になるから殆ど意味ないけど

>>30
うん、自分は基本的に最適化厨だから速度重視。
アルゴリズム自身には偏りはないけど、
乱数の質の影響を思いっきり受けるコードだから、悪い乱数だと、品質がおもいっきり悪くなる。
0033デフォルトの名無しさん2007/01/24(水) 17:34:32
まあ二人とも >30 を実行してシャッフル結果を見てご覧よ。
そんで、>30 のコードにミスがあったら指摘してくれよ。

>>31
>randって2bit目は常に0なのか。2とか出ない、と。勉強になるなぁ。
rand() & 5 だからね。
0034デフォルトの名無しさん2007/01/24(水) 18:30:42
なるほど。
＞y = (x ^ x>>2 ) & rand() & 0x33333333;
は正しくは
tmp = rand() & 0x11111111; tmp |= tmp<<1;
y = = (x ^ x>>2 ) & tmp;
って感じか。2bitセットでon/offになるように。以下同様。
0035デフォルトの名無しさん2007/01/24(水) 19:55:49
>>27
分割統治法だっけ？
0036デフォルトの名無しさん2007/01/24(水) 20:21:52
>>30
3重ループの中のxがループ毎の変更にしているけどループの終了時に元の値に戻していない。
xに直接代入せずにint x2 = x ^ (y | y<<2)とかして表示しないと駄目。
0037342007/01/24(水) 20:25:09
逝ってくる
0038デフォルトの名無しさん2007/01/24(水) 20:26:45
>>36
確かに。俺が悪かった。
ちゃんと均等になった。
0039デフォルトの名無しさん2007/01/27(土) 01:31:19
randがちゃんと乱数ならば
もう一回randとったらビットもシャッフルされてないの?
0040・∀・）っ-○◎●創聖のダンゴリオン ◆DanGorION6 2007/01/27(土) 01:58:16
ちゃんとした乱数なんてない

ビット単位のランダムシャッフルって、1の立ってるビットをカウントしたうえ
シャッフル結果を全通り列挙したテーブルを疑似乱数を使ってランダムにピックアップ
ってのはどう？
0041デフォルトの名無しさん2007/01/27(土) 04:06:30
>>40
シャッフル結果の組み合わせは、整数のビット数をn,たっているビット数をmとしたとき
nCmだからテーブルが馬鹿でかくなりすぎると思う。
■ このスレッドは過去ログ倉庫に格納されています