Skip to main content
本文に 179 文字追加
ソース リンク
soramimi
  • 1,969
  • 1
  • 15
  • 31

mjyさんのPython版と同じですが、i=0~19の範囲でループしつつ、その都度、選択される確率を求めて、採るか捨てるか決めていけばいいと思います。

i=0のとき、6/20の確率で選択します。i=0が選択されたとき、i=1が選択される確率は5/19になります。i=0が選択されなかったとき、i=1が選択される確率は6/19になります。この繰り返しです。

#include <stdio.h>
#include <stdint.h>

#ifdef _WIN32
#include <intrin.h>
#define rdtsc() __rdtsc()
#else
inline uint64_t rdtsc()
{
    uint32_t hi, lo;
    __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
    return ((uint64_t)hi << 32) | (uint64_t)lo;
}
#endif

// [0..1]の乱数
double frand()
{
    static uint64_t r = 123456789;
    r = r * 0x0123456789abcdef + rdtsc();
    return (double)r / UINT64_MAX;
}

int main()
{
    int i;
    int m = 20;
    int n = 6;
    for (i = 0; n > 0 && i < m; i++) {
        if (frand() <= (double)n / (m - i)) {
            printf("%d\n", i);
            n--;
        }
    }
    return 0;
}

乱数生成の関数は間に合わせで適当に作りましたので、精度とか信用しないでください。10万回くらい回して出現頻度を見てみましたが、概ね均一に分散していると思います。

補足
frand()(適当に実装した乱数生成関数)ですが、CPUクロックカウンタ(rdtsc命令)を利用している関係で、最初の1回目のfrand()実行時のみ、結果の値が偏ります。2回目以降はまあまあ良い感じの乱数列を生成できます。上のコードのfor文の直前でfrand();を1回実行しておくと、よりよい結果が得られます。

mjyさんのPython版と同じですが、i=0~19の範囲でループしつつ、その都度、選択される確率を求めて、採るか捨てるか決めていけばいいと思います。

i=0のとき、6/20の確率で選択します。i=0が選択されたとき、i=1が選択される確率は5/19になります。i=0が選択されなかったとき、i=1が選択される確率は6/19になります。この繰り返しです。

#include <stdio.h>
#include <stdint.h>

#ifdef _WIN32
#include <intrin.h>
#define rdtsc() __rdtsc()
#else
inline uint64_t rdtsc()
{
    uint32_t hi, lo;
    __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
    return ((uint64_t)hi << 32) | (uint64_t)lo;
}
#endif

// [0..1]の乱数
double frand()
{
    static uint64_t r = 123456789;
    r = r * 0x0123456789abcdef + rdtsc();
    return (double)r / UINT64_MAX;
}

int main()
{
    int i;
    int m = 20;
    int n = 6;
    for (i = 0; n > 0 && i < m; i++) {
        if (frand() <= (double)n / (m - i)) {
            printf("%d\n", i);
            n--;
        }
    }
    return 0;
}

乱数生成の関数は間に合わせで適当に作りましたので、精度とか信用しないでください。10万回くらい回して出現頻度を見てみましたが、概ね均一に分散していると思います。

mjyさんのPython版と同じですが、i=0~19の範囲でループしつつ、その都度、選択される確率を求めて、採るか捨てるか決めていけばいいと思います。

i=0のとき、6/20の確率で選択します。i=0が選択されたとき、i=1が選択される確率は5/19になります。i=0が選択されなかったとき、i=1が選択される確率は6/19になります。この繰り返しです。

#include <stdio.h>
#include <stdint.h>

#ifdef _WIN32
#include <intrin.h>
#define rdtsc() __rdtsc()
#else
inline uint64_t rdtsc()
{
    uint32_t hi, lo;
    __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
    return ((uint64_t)hi << 32) | (uint64_t)lo;
}
#endif

// [0..1]の乱数
double frand()
{
    static uint64_t r = 123456789;
    r = r * 0x0123456789abcdef + rdtsc();
    return (double)r / UINT64_MAX;
}

int main()
{
    int i;
    int m = 20;
    int n = 6;
    for (i = 0; n > 0 && i < m; i++) {
        if (frand() <= (double)n / (m - i)) {
            printf("%d\n", i);
            n--;
        }
    }
    return 0;
}

乱数生成の関数は間に合わせで適当に作りましたので、精度とか信用しないでください。10万回くらい回して出現頻度を見てみましたが、概ね均一に分散していると思います。

補足
frand()(適当に実装した乱数生成関数)ですが、CPUクロックカウンタ(rdtsc命令)を利用している関係で、最初の1回目のfrand()実行時のみ、結果の値が偏ります。2回目以降はまあまあ良い感じの乱数列を生成できます。上のコードのfor文の直前でfrand();を1回実行しておくと、よりよい結果が得られます。

本文に 1 文字追加
ソース リンク
soramimi
  • 1,969
  • 1
  • 15
  • 31

mjyさんのPython版と同じですが、i=0~19の範囲でループしつつ、その都度、選択される確率を求めて、採るか捨てるか決めていけばいいと思います。

i=0のとき、6/20の確率で選択します。i=0が選択されたとき、i=1が選択される確率は5/19になります。i=0が選択されなかったとき、i=1が選択される確率は6/19になります。この繰り返しです。

#include <stdio.h>
#include <stdint.h>

#ifdef _WIN32
#include <intrin.h>
#define rdtsc() __rdtsc()
#else
inline uint64_t rdtsc()
{
    uint32_t hi, lo;
    __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
    return ((uint64_t)hi << 32) | (uint64_t)lo;
}
#endif

// [0..1]の乱数
double frand()
{
    static uint64_t r = 123456789;
    r = r * 0x0123456789abcdef + rdtsc();
    return (double)r / UINT64_MAX;
}

int main()
{
    int i;
    int m = 20;
    int n = 6;
    for (i = 0; n > 0 && i < m; i++) {
        if (frand() <= (double)n / (m - i)) {
            printf("%d\n", i);
            n--;
        }
    }
    return 0;
}

乱数生成の関数は間に合わせで適当に作りましたので、精度とか信用しないでください。10万回くらい回して出現頻度を見てみましたが、概ね均一に分散していると思います。

mjyさんのPython版と同じですが、i=0~19の範囲でループしつつ、その都度、選択される確率を求めて、採るか捨てるか決めていけばいいと思います。

i=0のとき、6/20の確率で選択します。i=0が選択されたとき、i=1が選択される確率は5/19になります。i=0が選択されなかったとき、i=1が選択される確率は6/19になります。この繰り返しです。

#include <stdio.h>
#include <stdint.h>

#ifdef _WIN32
#include <intrin.h>
#define rdtsc() __rdtsc()
#else
inline uint64_t rdtsc()
{
    uint32_t hi, lo;
    __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
    return ((uint64_t)hi << 32) | (uint64_t)lo;
}
#endif

// [0..1]の乱数
double frand()
{
    static uint64_t r = 123456789;
    r = r * 0x0123456789abcdef + rdtsc();
    return (double)r / UINT64_MAX;
}

int main()
{
    int i;
    int m = 20;
    int n = 6;
    for (i = 0; n > 0 && i < m; i++) {
    if (frand() <= (double)n / (m - i)) {
            printf("%d\n", i);
            n--;
        }
    }
    return 0;
}

乱数生成の関数は間に合わせで適当に作りましたので、精度とか信用しないでください。10万回くらい回して出現頻度を見てみましたが、概ね均一に分散していると思います。

mjyさんのPython版と同じですが、i=0~19の範囲でループしつつ、その都度、選択される確率を求めて、採るか捨てるか決めていけばいいと思います。

i=0のとき、6/20の確率で選択します。i=0が選択されたとき、i=1が選択される確率は5/19になります。i=0が選択されなかったとき、i=1が選択される確率は6/19になります。この繰り返しです。

#include <stdio.h>
#include <stdint.h>

#ifdef _WIN32
#include <intrin.h>
#define rdtsc() __rdtsc()
#else
inline uint64_t rdtsc()
{
    uint32_t hi, lo;
    __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
    return ((uint64_t)hi << 32) | (uint64_t)lo;
}
#endif

// [0..1]の乱数
double frand()
{
    static uint64_t r = 123456789;
    r = r * 0x0123456789abcdef + rdtsc();
    return (double)r / UINT64_MAX;
}

int main()
{
    int i;
    int m = 20;
    int n = 6;
    for (i = 0; n > 0 && i < m; i++) {
        if (frand() <= (double)n / (m - i)) {
            printf("%d\n", i);
            n--;
        }
    }
    return 0;
}

乱数生成の関数は間に合わせで適当に作りましたので、精度とか信用しないでください。10万回くらい回して出現頻度を見てみましたが、概ね均一に分散していると思います。

ソース リンク
soramimi
  • 1,969
  • 1
  • 15
  • 31

mjyさんのPython版と同じですが、i=0~19の範囲でループしつつ、その都度、選択される確率を求めて、採るか捨てるか決めていけばいいと思います。

i=0のとき、6/20の確率で選択します。i=0が選択されたとき、i=1が選択される確率は5/19になります。i=0が選択されなかったとき、i=1が選択される確率は6/19になります。この繰り返しです。

#include <stdio.h>
#include <stdint.h>

#ifdef _WIN32
#include <intrin.h>
#define rdtsc() __rdtsc()
#else
inline uint64_t rdtsc()
{
    uint32_t hi, lo;
    __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
    return ((uint64_t)hi << 32) | (uint64_t)lo;
}
#endif

// [0..1]の乱数
double frand()
{
    static uint64_t r = 123456789;
    r = r * 0x0123456789abcdef + rdtsc();
    return (double)r / UINT64_MAX;
}

int main()
{
    int i;
    int m = 20;
    int n = 6;
    for (i = 0; n > 0 && i < m; i++) {
    if (frand() <= (double)n / (m - i)) {
            printf("%d\n", i);
            n--;
        }
    }
    return 0;
}

乱数生成の関数は間に合わせで適当に作りましたので、精度とか信用しないでください。10万回くらい回して出現頻度を見てみましたが、概ね均一に分散していると思います。