| Микроконтролери и електроника http://mcu-bg.com/mcu_site/ |
|
| Алгоритъм за сравняване на числа? http://mcu-bg.com/mcu_site/viewtopic.php?f=7&t=10400 |
Страница 1 от 1 |
| Автор: | Ники [ Нед Авг 19, 2012 12:01 pm ] |
| Заглавие: | Алгоритъм за сравняване на числа? |
Искам да генерирам примерно 6 цифрени числа, в които всяка цифра се среща един път и не надвишава разредността на числото, в случая 6. Примерно 123456, 123465,654321 и т.н. Зле съм в комбинаториката и за по лесно решавам да ползвам няколко вградени for цикъла, които въртят всеки разряд на числото. Така ще трябва да отсявам нужните ми комбинации, което обаче опира до голям брой сравнения между всеки разряд с останалите. Предполагам че има по-елегантен начин да се получи това което искам, някакви идеи? |
|
| Автор: | test11 [ Нед Авг 19, 2012 12:09 pm ] |
| Заглавие: | Re: Алгоритъм за сравняване на числа? |
Заделяш 10 бита и ги нулираш. Правиш цикъл от едно от разредите на числото. Генерираш случайно числи 0..9 Проверяваш дали съответния бит е вдигнат, значи числото е било теглено вече. Повтаряш реда. Добавяш към реда с генерирани числа и вдигаш съотвения бит. 
|
|
| Автор: | Zdrav [ Нед Авг 19, 2012 12:27 pm ] |
| Заглавие: | Re: Алгоритъм за сравняване на числа? |
И накрая като остане само една възможност седиш и чакаш докато рандъм генератора ти я улучи... 
|
|
| Автор: | test11 [ Нед Авг 19, 2012 12:31 pm ] | |||||||||
| Заглавие: | Re: Алгоритъм за сравняване на числа? | |||||||||
Вероятност 1:10. Едва ли ще чакаш повече от 10мс
|
||||||||||
| Автор: | ToHu [ Нед Авг 19, 2012 6:33 pm ] |
| Заглавие: | Re: Алгоритъм за сравняване на числа? |
Ммммммм не мисля че е точно 1:10, ако рандъм генератора е наистина случаен, зависи от типа му, но може и да е 1:50 ... ако не е съвсем случаен току виж е 1:100, ти виждал ли си рандом генератор който от 10 запитвания връща 10 различни стойности .. то тогава ниакак няма да е рандъм, почвам да мечтая за покер или слот машина с такъв, 1 от 10 тегления ти е гарантирана печалба ...  По скоро малко математика трябва, ама нещо не ми хрумва как точно да стане, може да се понапъна, ама със сигурност има други които ще ме преварят, напоследък комбинаториката ми се изчрва с това как прекарам 10 тръби Ф400 със по 5 колена, така че хем да не си пречат хем да са достъпни, хем и да могат да се подменят ... ако някой си мисли че рутирането на платка е зор ... верно поне че можеш да режеш и сменяш колкото искаш, само дето всичко струва $$$, та още го разигравам в солида, да е жив и здрав който го е измислил тоя софт. |
|
| Автор: | Zdrav [ Нед Авг 19, 2012 7:22 pm ] |
| Заглавие: | Re: Алгоритъм за сравняване на числа? |
Всъщност последната цифра програмката трябва да я попълни сама без да чака. Сещам се за подобна задачка която правих преди време. Но там вместо рандом генератор всяко поредно число се въвежда от оператор. Софтуера на всяка последователна стъпка стеснява избора на оператора, като изключва от множеството на възможните числа вече въведените. Та моето предложение е за праволинеен подход. На всяка следваща стъпка стеснявай множеството на рандъм генератора. На първата стъпка връща от 0 до 9. На втората връща от 0 до 8 и т.н. на предпоследната от 0 до 1. Последната стъпка цифрата се попълва без да се ползва рандъм генератора. Съответно трябва да поддържаш нещо като map, чрез който да конвертираш полученото от рандъм генератора на всяка стъпка в конкретна цифра от множеството на възможните. Което множество на всяка стъпка се стеснява. Например в началото този map изглежда така: 0 - 0 1 - 1 2 - 2 3 - 3 4 - 4 5 - 5 6 - 6 7 - 7 8 - 8 9 - 9 Да речем че на първата стъпка е изтеглено числото 4. Съответно множеството от възможните за втора стъпка става {0,1,2,3,5,6,7,8,9}. Рандъм генератора трябва да ти върне за втората стъпка число в интервала 0 до 8. И съответно map-а за втората стъпка изглежда така: 0 - 0 1 - 1 2 - 2 3 - 3 4 - 5 5 - 6 6 - 7 7 - 8 8 - 9 Ако на втората стъпка бъде изтеглено числото 6. Според map-а това съответства на числото 7. И така докато размера на map-а стане равен на единица и съдържа последното число, което взимаме направо. ПС: Ако съм разбрал правилно задачата де
|
|
| Автор: | БатеВаньо [ Нед Авг 19, 2012 9:14 pm ] |
| Заглавие: | Re: Алгоритъм за сравняване на числа? |
Класическият начин да се направи това е с разместване. В условието на задачата не е дефинирано дали трябва да се изгенерират всички пермутации от 6 елемента или случайна пермутация, но всяка една от тях може да се получи от изходното число с (n-1) размествания. Например: - тръгва се от начална стойност 123456 (може и като стринг "123456"); - генерира се число (по случаен закон или с цикъл) от 0 до 5 и първата цифра се разменя с цифрата от тази позиция (естествено, при 0 не се прави размяна); - на следващата стъпка се генерира число от 1 до 5 и втората цифра се разменя с посочената позиция и т.н. Ако трябва да се генерират всички пермутации, на практика това става с пет вложени цикъла. |
|
| Автор: | ike [ Нед Авг 19, 2012 9:53 pm ] |
| Заглавие: | Re: Алгоритъм за сравняване на числа? |
Най добре е да си ги изгенерира. Не са толкова много числата за съвременен компютър и със сигурност няма да му се повтарят. |
|
| Автор: | Ники [ Нед Авг 19, 2012 10:21 pm ] |
| Заглавие: | Re: Алгоритъм за сравняване на числа? |
Трябват ми всички пермутации. Без значение дали са в някакъв подреден или случаен ред и начална стойност. Наистина комбинациите са малко и могат да се изгенерират всякак. Исках да разбера дали има по универсален подход, защото разредността може да е различна от посочената, като примерна. БатеВаньо, идеята с преместването е интересна, ще се опитам да вникна в нея
|
|
| Автор: | БатеВаньо [ Нед Авг 19, 2012 10:43 pm ] |
| Заглавие: | Re: Алгоритъм за сравняване на числа? |
Ако се генерират всички пермутации, тогава алгоритъмът може да се генерализира, така че броят на цифрите да не е твърдо кодиран в структурата на програмата. Ясно е, че броят на всички пермутации от n елемента е n!. Тогава може да се завърти цикъл от 0 до (n! - 1) и за всяка стойност на променливата да се изгенерира съответната пермутация. А генерирането може да стане като за всяка стойност на този (да го наречем) индекс първо се намери частното и остатъкът от делението му на 2. Остатъкът (+ n - 2) се използва като индекс за разместване на n-2-рата цифра. Частното от предишната операция се използва като се дели на 3 и пак се намира частно и остатък (напр. чрез стандартната функция div() ). Остатъкът отново се използва за разместване, а частното се използва по-нататък... Така разместването се прави в обратен ред, но пак се получават всички пермутации. |
|
| Автор: | Reader [ Пон Авг 20, 2012 12:01 pm ] |
| Заглавие: | Re: Алгоритъм за сравняване на числа? |
Има алгоритъм (мисля, че с почти линейна сложност), който осигурява съответствие между пермутациите от даден ред и естествените числа. Т.е. ти му подаваш 1, 2, 3… а той ти връща 123456, 123465,… Ако го изнамериш, достатъчно е само да извъртиш един цикъл по броя пермутации и да ги подадеш на функцията за съответствие. |
|
| Автор: | dan [ Пон Авг 20, 2012 2:04 pm ] |
| Заглавие: | Re: Алгоритъм за сравняване на числа? |
Един програмист отишъл при свой колега и го попитай: -Извинявай, имаш ли генератор на случайни числа? Колегата му отговорил: -12. |
|
| Страница 1 от 1 | Часовете са според зоната UTC + 2 часа [ DST ] |
| Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |
|
