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;
}

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

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

Тагове:
0
Programming Basics
RoYaL avatar RoYaL Trainer 6849 Точки
Best Answer

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

1
Filkolev avatar Filkolev 4482 Точки

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

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

0
agogo avatar agogo 12 Точки

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

0
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.