Програмиране C : Домашно 6 : Генериране и подреждане .
Здравейте!
Ако може да хвърлите един поглед на следната задача. Тя от домашните, които решавам с огромно закъснение. Та въпросната задача ме мъчи 2 дена и от домашното за цикли - трябва да се реши със знанията до цикли. Според мен достигнах до адекватно решение, но дали е най-удачното(бързодействие)? Бъдете снизходителни - начинаещ съм!
Условие: Да се въведе число N и да се генерират случайни числа от 1 до N без да се повтарят.
Моето решение: Масив от N числа чрез библиотечна функция rand(). Нулиране на всички повтарящи се числа и запълване с наново генерирани стойности, който не се срещат в масива. Ето и кода:
#include <stdio.h>
#include <stdlib.h>
int main() {
int n, a[10], random, i, j, exist ;
puts("n = "); scanf("%d",&n);
for(i=0;i<n;i++) a[i] = rand() % n + 1;
for(i=0;i<n;i++){
for(j=1;j<n;j++)
while( a[i] == a[j] && i != j && a[i] !=0 ) a[j] = 0;
}
for(i=0;i<n;i++) {
if(a[i] == 0) {
do {
exist = 0;
random = rand() % n + 1;
for(j=0;j<n;j++) if(random == a[j]) exist++;
}while( exist != 0);
a[i] = random;
}
}
for(i=0;i<n;i++) printf("%d ",a[i]);
return 0;
}
Моля за съвет ( не искам решение, само насока :-) ) , който би оптимизирал решението в посока бързодействие!
Благодаря, предварително.
shuffle (Fisher-Yates примерно) действително изглежда най-смисленият подход.
Друг вариант е да се взима всеки път произволно число и да се проверява дали вече не е добавено в масива, но това ми се струва доста по-неефикасно - всяка проверка означава итериране на целия масив, което е линейна сложност. Като добавим, че това се случва при всяко добавяне, n пъти (а при попадане на вече добавена стойност и повече), става n^2. Fisher-Yeates е О(n).
Благодаря ти, отново! Ще пробвам! Хайде сега на бира!!! Лека и весела!