数値処理

[C言語] 重複しない乱数の生成方法

C言語で重複しない乱数を生成するには、まず乱数を生成するためにrand()関数を使用します。

生成された乱数を配列やリストに格納し、重複がないかを確認しながら新しい乱数を追加します。

重複を避けるために、生成された乱数をソートし、二分探索を用いて効率的に重複チェックを行う方法もあります。

また、srand()関数を用いてシード値を設定することで、乱数のパターンを変えることができます。

この方法により、指定した範囲内で重複しない乱数を効率的に生成することが可能です。

目次から探す

重複しない乱数を生成する方法
応用例
まとめ

重複しない乱数を生成する方法

乱数を生成する際に、重複しない値を得ることは多くのプログラムで重要です。

ここでは、C言語で重複しない乱数を生成するためのいくつかの方法を紹介します。

配列を用いた重複チェック

配列を使用して、生成した乱数がすでに存在するかを確認する方法です。

以下にサンプルコードを示します。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 10
int main() {
    int numbers[SIZE];
    int count = 0;
    int isUnique;
    srand(time(NULL)); // 乱数の種を設定
    while (count < SIZE) {
        int num = rand() % 100; // 0から99の乱数を生成
        isUnique = 1;
        // 重複チェック
        for (int i = 0; i < count; i++) {
            if (numbers[i] == num) {
                isUnique = 0;
                break;
            }
        }
        // 重複していなければ配列に追加
        if (isUnique) {
            numbers[count] = num;
            count++;
        }
    }
    // 結果を表示
    for (int i = 0; i < SIZE; i++) {
        printf("%d ", numbers[i]);
    }
    return 0;
}

34 67 23 89 12 45 78 56 90 11

この方法では、生成した乱数を配列に保存し、次に生成する乱数と比較して重複を避けます。

配列のサイズが大きくなると、チェックに時間がかかる可能性があります。

フィッシャー–イェーツのシャッフルアルゴリズム

フィッシャー–イェーツのシャッフルアルゴリズムは、配列をランダムに並べ替える効率的な方法です。

これを利用して、重複しない乱数を生成できます。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 10
void shuffle(int *array, int size) {
    for (int i = size - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}
int main() {
    int numbers[SIZE];
    srand(time(NULL)); // 乱数の種を設定
    // 配列を初期化
    for (int i = 0; i < SIZE; i++) {
        numbers[i] = i;
    }
    // 配列をシャッフル
    shuffle(numbers, SIZE);
    // 結果を表示
    for (int i = 0; i < SIZE; i++) {
        printf("%d ", numbers[i]);
    }
    return 0;
}

3 7 1 9 0 5 2 8 6 4

この方法では、最初に連続した数値の配列を作成し、それをシャッフルすることで重複しない乱数を得ます。

ビットマスクを用いた方法

ビットマスクを使用して、重複しない乱数を生成する方法です。

ビットマスクは、特定のビットを操作するための手法で、効率的に重複を避けることができます。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 10
#define MAX_NUM 100
int main() {
    int numbers[SIZE];
    int bitmask[MAX_NUM] = {0};
    int count = 0;
    srand(time(NULL)); // 乱数の種を設定
    while (count < SIZE) {
        int num = rand() % MAX_NUM; // 0から99の乱数を生成
        // ビットマスクで重複チェック
        if (!bitmask[num]) {
            numbers[count] = num;
            bitmask[num] = 1;
            count++;
        }
    }
    // 結果を表示
    for (int i = 0; i < SIZE; i++) {
        printf("%d ", numbers[i]);
    }
    return 0;
}

12 45 78 34 67 23 89 56 90 11

ビットマスクを用いることで、重複チェックを効率的に行うことができます。

配列の要素数が多い場合でも、比較的高速に動作します。

リストを用いた方法

リストを使用して、重複しない乱数を生成する方法です。

リストは動的にサイズを変更できるため、柔軟に対応できます。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 10
typedef struct Node {
    int value;
    struct Node *next;
} Node;
Node* createNode(int value) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->value = value;
    newNode->next = NULL;
    return newNode;
}
int isUnique(Node *head, int value) {
    Node *current = head;
    while (current != NULL) {
        if (current->value == value) {
            return 0;
        }
        current = current->next;
    }
    return 1;
}
void append(Node **head, int value) {
    Node *newNode = createNode(value);
    if (*head == NULL) {
        *head = newNode;
    } else {
        Node *current = *head;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newNode;
    }
}
void printList(Node *head) {
    Node *current = head;
    while (current != NULL) {
        printf("%d ", current->value);
        current = current->next;
    }
}
int main() {
    Node *head = NULL;
    int count = 0;
    srand(time(NULL)); // 乱数の種を設定
    while (count < SIZE) {
        int num = rand() % 100; // 0から99の乱数を生成
        // リストで重複チェック
        if (isUnique(head, num)) {
            append(&head, num);
            count++;
        }
    }
    // 結果を表示
    printList(head);
    return 0;
}