Софтуерно Инженерство
Loading...
+ Нов въпрос
agogo avatar agogo 12 Точки

Програмиране 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;
}

Моля за съвет ( не искам решение, само насока :-) ) , който би оптимизирал решението в посока бързодействие! 

Благодаря, предварително.

Тагове:
RoYaL avatar RoYaL SoftUni Team Trainer 6883 Точки
Best Answer

Можеш да напълниш масива с поредните числа и после да го shuffle-неш отново ще трябва да ползваш rand() разбира се за да преместиш число на произволна позиция, но подозирам че кодът ще започне да изглежда по-елегантно.

1
Filkolev avatar Filkolev 4428 Точки

shuffle (Fisher-Yates примерно) действително изглежда най-смисленият подход.

Друг вариант е да се взима всеки път произволно число и да се проверява дали вече не е добавено в масива, но това ми се струва доста по-неефикасно - всяка проверка означава итериране на целия масив, което е линейна сложност. Като добавим, че това се случва при всяко добавяне, n пъти (а при попадане на вече добавена стойност и повече), става n^2. Fisher-Yeates е О(n).

0
agogo avatar agogo 12 Точки

Благодаря ти, отново! Ще пробвам! Хайде сега на бира!!! Лека и весела!

0