fk0, легенда (11.01.2013 10:23, просмотров: 42) ответил fk0 на Фигню спросил. Зайду издалека. Есть некий массив, который хочется перебирать каждый раз в разном порядке. Мысль какая: находим (псевдо, если srand(_real_rand_) не забыть) случайное число M (сопоставимое с N, в первом приближении) и взаимо простое
Пример (проверку типа /a.out 100000 | sort -n | uniq -d проходит):
#include <stdint.h>
#include <limits.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
uint_fast8_t ctz(unsigned n)
{
uint_fast8_t r=0;
if (n==0) return CHAR_BIT*sizeof(unsigned);
#if UINT_MAX>0xffff
#if UINT_MAX != 0xffffffff
#error "unsupported platform"
#endif
if (! (n&0xFFFF)) r+=16, n>>=16;
#endif
if (! (n&0xFF)) r+=8, n>>=8;
if (! (n&0xF)) r+=4, n>>=4;
if (! (n&3)) r+=2, n>>=2;
if (! (n&1)) r+=1;
return r;
}
unsigned gcd(unsigned m, unsigned n)
{
unsigned c;
if (m==0) return n;
if (n==0) return m;
c=ctz(m|n);
m>>=ctz(m);
while (1) {
n>>=ctz(n);
if (m==n) break;
if (m>n) {
unsigned t=m; m=n, n=t;
}
if (m==1) break;
n-=m;
}
return m<<c;
}
void iterate(unsigned n)
{
unsigned i0, i, m;
if (n==0) return;
srand(time(NULL));
do m=rand()%n; while (gcd(m,n)!=1);
i=i0=rand()%n; do {
printf("%u\n", i);
i=(i+m)%n;
} while (i!=i0);
}
int main(int argc, char *argv[])
{
unsigned n;
if (argc<2) {
iterate(10);
return 0;
}
if (sscanf(argv[1], "%u", &n)<1) {
fprintf(stderr, "%s: not a number\n", argv[1]);
return 1;
}
iterate(n);
return 0;
}
[ZX]