重複無し乱数 in C DouKaku?

整数nを渡すと1 ～ n までの整数を重複しないようランダムに出力する関数「bingo」を作ってください。

このお題はraynstardさんの投稿を元にしています。ご投稿ありがとうございました。投稿の内容には表示のしかたも含まれていたのですが、このお題では「重複しない1～nまでの乱数をどうやって作るか」という点に集中することにして、結果の整形は続編としてこの後のお題で出すことにします。サンプル入出力は下のようになります。

>>> bingo(10)
[10, 7, 8, 4, 5, 2, 3, 1, 6, 9]
>>> bingo(3)
[2, 3, 1]
>>> bingo(3)
[2, 3, 1]
>>> bingo(3)
[3, 1, 2]
>>> bingo(10)
[7, 3, 8, 6, 4, 10, 9, 2, 1, 5]

ランダムソートでいいのかな

#include <stdio.h>
#include <stdlib.h>

static int cmp(const void *p1, const void *p2)
{
    return (rand() % 2)?1:-1;
}

void bingo(int num)
{
    int i;
    int *nums;

    if(num <= 0) return;
    nums = (int*)malloc(sizeof(int) * num);
    for(i=0; i<num; i++){
        nums[i] = i + 1;
    }
    qsort(nums, num, sizeof(int), (int (*)(const void*, const void*))cmp);
    for(i=0; i<num; i++){
        printf("%d\n", nums[i]);
    }
    free(nums);
}

int main(int argc, char *argv[])
{
    if(argc < 2){
        return EXIT_FAILURE;
    }
    srand(time(NULL));
    bingo(atoi(argv[1]));
    return EXIT_SUCCESS;
}

C言語と再帰で解いて見た。
ソート関数は利用していません。多分線形時間。

**intを与えているのがちょっとかっこ悪いですが。
あと↓の部分をまともになるように書き換えればOKだけど、アルゴリズムの本質ではないので放置。
swap_point = rand() % (num+1);

アルゴリズムは以下のような感じ
[1～n-1までがシャッフルされた配列] [n]
↑のような配列があったときに、
末尾要素と、ランダムで選ばれた末尾より前の要素とスワップすることで、
全体が1～nまでがシャッフルされた配列になります。
あとはそいつを再帰している感じ。
ループで書いてもよかったかな。

#include <stdio.h>
#include <stdlib.h>

void _bingo(int num, int *result, int num_max){
	int temp;
	int swap_point;

	result[num] = num + 1;
	swap_point = rand() % (num+1);
	temp = result[swap_point];
	result[swap_point] = result[num];
	result[num] = temp;

	if (num + 1 == num_max){
		return;
	}
	_bingo(num+1, result, num_max);
	return;
}

void bingo(int num, int** result)
{
	*result = (int*)malloc(num * sizeof(int));
	_bingo(0, *result,num);
}


int main(void)
{
	int *result;
	int num;
	int i;

	num = 100;
	bingo(num, &result);
	
	for(i = 0; i < num; i++){
		printf("%d,", result[i]);
	}
}

破壊的シャッフル。#3645, #2254 に似たものが C でなかったので書いてみました。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void bingo( int n ){
   int tmp;
   int i,j;
   int *deck = (int*)malloc(sizeof(int)*n);
   for( i = 0; i < n; i++ )
      deck[i] = i+1;

   for( i = 0; i < n; i++ ){
      j = rand() % (n-i);
      tmp = deck[j];
      deck[j] = deck[ n-i-1 ];
      deck[ n-i-1 ] = tmp;
   }
   for( i = 0; i < n; i++)
      printf("%d ", deck[i] );
   free(deck);
}

int main ( void ){
   srand(time(NULL));
   bingo(10);
   printf("\n");
   bingo(15);
   printf("\n");
   return 0;
}

DouKaku?

重複無し乱数

Posted feedbacks - C

Index

Feed

Other

Link

Pathtraq