Алгоритъм за разбъркване на масив, Много шум за 10 реда код... |
Здравейте ( Вход | Регистрация )
Алгоритъм за разбъркване на масив, Много шум за 10 реда код... |
10:25:41, 27-May-2010, Thursday
Коментар
#1
|
|
BEST ENTRY award - зад.1/2008 Група: VIP Коментари: 597 Регистриран: 19.04.07 Град: Kюстендил Потребител № 539 |
Това е един алгоритъм за разбъркване на масив, който измислих една вечер и реализирах на скоро. Идеята е следната:
1 - инициализирам масива с числата от 0 до n; 2 - избирам произволен елемент на масива; 3 - слагам го на пъво място, а този който е бил на първо взима неговото. Елементът който е с индекс 0 вече го считам за "разбъркан", затова при следващо избиране на произволен елемент него ще го прескачам. 2 - избирам произволен елемент от масива; 3 - този път той и втория елемен си разменят местата. Цикълът се повтаря докато не стигна n-1 избиране на елемент. Ето го и самият код: Код n=10 for(i=0; i<n; i+=1) array[i]=i for(i=0; i<n-1; i+=1){ rand=floor(random(n-i)+i) temp=array[i] array[i]=array[rand] array[rand]=temp } Ето и една снимка с малко разяснения: Хоризонтално са различни масиви; Вертикално са елементите на всеки масив. Какво е предимството: -При тестване на три алгоритъма за разбъркване на 1 000 и дори 10 000 елемента този се оказа най-бърз. -Този цикъл не прави излишни избирания на елементи и излишни проверки. Като пример мога да покажа един стар алгоритъм, който измислих преди доста време: Код n=1000 Представете си като стигне до момента в който с random(1000) трябва да се падне точно едно число. Да не говорим за по-голям масив. Другия алгоритъм с който го сравнявах (негов автор е krisis, измислен специално за играта "Сварка"), също имаше проверки, но беше доста по-бърз от този два реда по-нагоре. Остана да го тествам с алгоритъм на RaGiNGWhiSpeR, направен за играта "Сделка или не".for(i=0; i<n; i+=1) array[i]=0 for(i=0; i<n; i+=1){ array[i]=floor(random(n)) for(j=0; j<i; j+=1) if array[i]=array[j]{ i-=1 break } } Приложение: -Ако правите игра с карти естествено те трябва да се разбъкват, но да не се повтарят. Това е перфектно решение на проблема. Като заключение ще кажа че този алгоритъм е изцяло мой, но не изключвам възможността някой преди мен да го е измислил. Просто не съм потърсил в интернет. Качвам и програмката за тестване: array_randomize.gmk ( 9.17k ) Брой сваляния: 3 -------------------- "Последно: 18:05:07, 21.09.12" След две години мълчание пак проговори...
ИГРИ И ПРИМЕРИ НА САЙТА МИ!. |
|
|
10:47:01, 27-May-2010, Thursday
Коментар
#2
|
|
Засмян тъпоъгълник :D Група: Администратор Коментари: 1790 Регистриран: 21.07.08 Град: Това е място, населено с много хора. FPS: 60 Потребител № 1116 |
Добре измислен алгоритъм, само това не мога да разбера:
Цитат Елементът който е с индекс 0 вече го считам за "разбъркан", за това при следващо избиране на произволен елемент него ще го прескачам. Какво пречи на въпросния елемент да бъде разбъркан отново?
-------------------- Цитат Пешо: 4:53:46 Я недейти са карайти тука че да ни ва зашливйъ |
|
|
11:23:39, 27-May-2010, Thursday
Коментар
#3
|
|
BEST ENTRY award - зад.1/2008 Група: VIP Коментари: 597 Регистриран: 19.04.07 Град: Kюстендил Потребител № 539 |
Какво пречи на въпросния елемент да бъде разбъркан отново? Какъв смисъл има вече разбъркан елемент да се бърка отново. Точно това е уникалното на алгоритъма да разбърка масива за n-1 повторения. Или по друг начин казано: при rand=floor(random(n-i)+i) първия път имам: random(10) след това: random(9) random(8) ... random(2) Разбираш ли - след всяко изпълнение възможните елементи се намаляват. Само за сравнение ще покажа какво се случи при изпълнение на по-стария ми алгоритъм отново с 10 елемента: -Цикълът по i се изпълни 23 пъти; -Цикълът по j 77 пъти. Като се има предвид, че някога минава 250. Това е така защото там е възможно неколкократно падане на едно и също число. -------------------- "Последно: 18:05:07, 21.09.12" След две години мълчание пак проговори...
ИГРИ И ПРИМЕРИ НА САЙТА МИ!. |
|
|
Олекотена версия | Час: 20:54:09, 18.05.24 |