Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Есть два числа. Нужно найти все числа между ними

Автор: Wowa 13.11.2005, 16:25

Есть два числа. Нужно найти все числа между ними, но случайным образом! Т.е. через Math.random. Числа не должны повторятся. И при генерировании нового случайного числа, не допускается переборка всего массива с целью проверки было ли это число уже найдено или нет. Давайте подумаем над этим алгоритмом. У меня есть такие идеи: нужно найти разницу между числами А и Б. Создать массив этой длины. И просто потом генерировать числа и записывая их в нужные ячейки массива.

Автор: cardinal 13.11.2005, 16:44

То есть числа целые как я понял (1, 2, 3 и т.д.)? Тогда надо как бы умножать то, что возвращает Math.random, то есть надо знать диапазон чисел. И так вопрос чсила идут от 1 до 10, от 10 до 100 или как?

Автор: hiHo 13.11.2005, 16:53

Попробуй так Пример у тебя числа с М1 по М2 1) Копируешь все по порядку в массив (длинна массива М2-М1+1) . 2) Берешь случайный на его место ставишь последний количество уменьшаешь на 1. 3) и тд пока массив не станит пустым.

Автор: Wowa 13.11.2005, 16:54

Цитата(cardinal @ 13.11.2005, 14:44) чсила идут от 1 до 10, от 10 до 100 или как? да, как угодно могут идти. Как задать, так и будут идти. Числа - целые. Добавлено @ 16:55 Цитата(cardinal @ 13.11.2005, 14:44) Тогда надо как бы умножать то, что возвращает Math.random На что умножать?

Автор: sergejzr 13.11.2005, 16:55

насчёт массива - правильно. В нём отмечать числа, которые уже найдены. Только вот придётся имхо сегменты вводить. то есть первое найденное число разобьёт диапазон на 2 сегмента, второе на 3 или останется 2. Если исключим 0, то ксор границ даст 0 , если диапазон заполнен полностью. Короче мудрённый алгоритм получится. Не знаю, стоит ли овчинка выделки. А вот простой алгоритм ты описал вроде. грубо говоря: Код   int cnt=0;//найденные числа   int min=5,max=15;   int interval=max-min;   while(cnt<interval)     {     int r;     for(r=random(max,min); massiv[r]; r=random(max,min));     massiv[r]=true;//нашли очередное число     cnt++;  } конечно под конец находить будет долго, но это самое простое решение. Игаче надо думать про сегменты..

Автор: Wowa 13.11.2005, 16:57

Цитата(sergej @ 13.11.2005, 14:55) Игаче надо думать про сегменты.. ну, сегменты не самое страшное. Но у меня нет мыслей, как их тут использовать.

Автор: Akina 13.11.2005, 18:42

создаем двумерный массив Код dim Array(0 to 1, MinNum to MaxNum) заполняем Код for i = MinNum to MaxNum     Array(0,i) = Random     Array(1,i) = i next i сортируем по 0-му столбцу Код Array.Sort(0,Ascending) выводим результат Код for i = MinNum to MaxNum     Print Array(1,i) next i

Автор: cardinal 13.11.2005, 20:15

Цитата(Wowa @ 13.11.2005, 14:25) Нужно найти все числа между ними, но случайным образом! Akina, а ты предлагаешь не искать их случайным образом, а расбросать случайным образом. Но вообще очень хитро! Если Wow'у устроит разбрасывание чисел, то почему бы и нет... Добавлено @ 20:16 Цитата(Wowa @ 13.11.2005, 14:54) На что умножать? Ну на 10, на 100... Просто привык, что Random возвращает числа в интевале 0..1.

Автор: Rick 13.11.2005, 20:31

идеально подходят множества, но всего от 0 до 255

Автор: Graf Zeppelin 13.11.2005, 22:23

А может через генерацию списка и выбора с удалением?

Автор: Wowa 13.11.2005, 22:32

Цитата(Graf @ 13.11.2005, 20:23) А может через генерацию списка и выбора с удалением? а подробннее? Как удаление делать будешь, если не допускается перебор всего массива.

Автор: Akina 13.11.2005, 22:35

Цитата(cardinal @ 13.11.2005, 21:15) ты предлагаешь не искать их случайным образом, а расбросать случайным образом ясен пень... просто условия Цитата(Wowa @ 13.11.2005, 17:25) Нужно найти все числа между ними, но случайным образом! и Цитата(Wowa @ 13.11.2005, 17:25) не допускается переборка всего массива с целью проверки было ли это число уже найдено или нет с учетом упора на выделенное противоречат друг другу. И вообще в контексте задачи я не понимаю термина "найти"... вывести все, но в случайном порядке? мой алгоритм это делает... что-то другое? объясните что именно, у меня фантазии не хватает.

Автор: Wowa 13.11.2005, 22:38

Цитата(Akina @ 13.11.2005, 20:35) с учетом упора на выделенное противоречат друг другу. почему противоречат?

Автор: Akina 13.11.2005, 22:43

Цитата(Wowa @ 13.11.2005, 23:38) почему противоречат? Почему? потому что очередное сгенерированное СЛУЧАЙНО число из заданного диапазона имеет право быть найденным ранее. А проверить так это или нет можно только сравнением с ранее найденными, т.е. сканирование найденных. Противоречие.

Автор: Wowa 13.11.2005, 22:47

Цитата(Akina @ 13.11.2005, 20:43) Почему? потому что очередное сгенерированное СЛУЧАЙНО число из заданного диапазона имеет право быть найденным ранее. А проверить так это или нет можно только сравнением с ранее найденными, т.е. сканирование найденных. Противоречие. противоречия нет. Если первое число 100, а второе 200. То создаем массив на 100 элементов. Обнуляем его. И если какое-то число найдено, то пишем его в массив по индексу этого самого числа, если же array[random]!=0 Где тут противоречие? Ключевое слово было: Цитата(Wowa @ 13.11.2005, 14:25) не допускается переборка всего массива Или же второй вариант - поиграть с знаками больше, меньше при нахождении чисел...

Автор: neutrino 14.11.2005, 00:17

Привет! Может Г.А??? Операция кросовера как раз разнообразит геном... А отбирать надо наиболее разнообразные. Но это только для сравнительно больших диапазонов чисел.

Автор: sergejzr 14.11.2005, 00:25

Akina, я немного не понял твоей идеи, поэтому возможно продублирую.. Вроде получилось оптимально и без ужасов Идея: есть "мешок" с числами достаём оттуда в случайном порядке, но не кладём числа обратно в мешок. Алгоритм: массив из n чисел (n = max - min) в случайном порядке находится не число, а индекс в этом массиве от 0 - n. Искомое число - число по этому индексу. Забрали число, на его место ставим последнее, массив таким образом сокращается на один элемент. Код #include "iostream.h" #include "math.h" #include<stdlib.h> /*начальная инициализация массива. Каждое число соответствует своему индексу */ void init(int * pool,int interval) {     for(int i=0;i<interval;i++)pool[i]=i; } /*pool - мешок с числами, ind - случайный индекс. border - конец мешка*/ int get(int*pool,int ind,int border) { int ret=pool[ind];//возвращаемое число if (ind!=border) pool[ind]=pool[border]; //кладём последнее число массива на место. где стояло искомое. return ret; } int main() {       int min=10;   int max=100;  int interval=max-min;  int * pool = new int[interval];//До сих пор понятно.     init(pool,interval);  interval--; //чтобы индекс правильный был  for(;interval>0;interval--)  {     int random=rand();      int ind=random%interval;//ставим случайное число в интервал нашего мешка     //так как случайные числа лежат от 0 до interval, добавляя min возвращаем в искомый интервал      cout<<min+get(pool,ind,interval-1)<<" "<<endl;       }   return 0; } Акина, разобрался с твоим алгом. Но если Array(0,i) = Random Несколько раз даст один и тот же результат?

Автор: Wowa 14.11.2005, 01:14

есть еще одно условие: "Числа не должны повторяться". Добавлено @ 01:14 sergej.z а чем к примеру, твой алгоритм лучше моего? Добавлено @ 01:16 Насколько я понял, твой вариант быстрее, т.к. нет вероятности того, что "выпадет" тоже самое число.

Автор: sergejzr 14.11.2005, 01:21

Мой алгоритм линеарный. Без циклов совсем. O(n). Самое сложное действие - % на 32 такта . ИМХО - оптимальное решение. Гы Ещё раз в компактной форме: Код #include "iostream.h" #include<stdlib.h> int main() {       int min=10;  int max=100;  int interval=max-min;  int * pool = new int[interval];    for(int i=0;i<interval;i++)pool[i]=i; //инициализация  interval--;  for(;interval>0;interval--)  {      int ind=rand()%interval; //случайный индекс массива      cout<<min+pool[ind]<<" "<<endl;          pool[ind]=pool[interval-1]; //последнее число на место "изъятого"  }   return 0; }

Автор: sergejzr 14.11.2005, 01:37

Гы только что прочитал всю тему. Уже до меня, пока я на танцы ходил , этот или примерно такой вариант предлагали hiHo и, как я понял, Graf Zeppelin

Автор: Akina 14.11.2005, 11:05

Цитата(sergej @ 14.11.2005, 01:25) если Array(0,i) = Random Несколько раз даст один и тот же результат? Гы... Начинающий программист: Я тут написАл программу, но она не работает, где ошибка? Опытный программист: В генах... Цитата(sergej @ 14.11.2005, 01:25) есть "мешок" с числами достаём оттуда в случайном порядке, но не кладём числа обратно в мешок. Забрали число, на его место ставим последнее при этом числа действительно будут в случайном порядке, но, увы, рандом будет неравномерным... вероятность последних чисел быть "первее" в выборке будет выше, чем первых... надо сдвигать, а не переносить последнее.

Автор: Wowa 14.11.2005, 12:30

Цитата(Akina @ 14.11.2005, 09:05) надо сдвигать, а не переносить последнее. сдвигать - это уже совсем другая работа..

Автор: sergejzr 14.11.2005, 14:03

Цитата(Akina @ 14.11.2005, 10:05) вероятность последних чисел быть "первее" в выборке будет выше, чем первых.. Вероятность остаётся той же самой. ведь случайный индекс 0 - величина_мешка. От того, где какое число стоит, ничего практически не зависит. Попробуй прогони програму 10 000 раз, никакой зависимости от сдвига не заметишь. Даже наоборот, числа дополнительно "перемешиваются"

Автор: nworm 14.11.2005, 15:05

Как вариант можно попробовать линейный конгруэнтный метод. Определения. Используются следующие неотрицательные числа: Xn, Xn >= 0 - начальное значение, a, c, a > 0, c > 0, m, m > X0, m > a, m > c - модуль. Линейная конгруэнтная последовательность случайных чисел получается из соотношения X(n+1) = (a*Xn + c) mod m, n >= 0. Теорема. Длина периода линейной конгруэнтной последовательности равна m тогда и только тогда, когда c и m взаимно просты, b = a - 1 кратно p для любого простого p, являющегося делителем m, b кратно 4, если m кратно 4. Пример. m = 7, c = 1, a = 4, X0 = 5. Последовательность 5 0=4*5+1 mod 7 1=0*5+1 mod 7 6=1*5+1 mod 7 3=6*5+1 mod 7 2=3*5+1 mod 7 4=2*5+1 mod 7 получили числа от 0 до 6 Правда, надо m раскладывать на множители...

Автор: Wowa 18.11.2005, 05:47

А вот вариант на Яве. Передаем аргументами два числа (a и b) и функция возвращает в случайном порядке все числа, где: a<=x>=b x - натуральное число Код public class zahlen { static int interval;     public static void main(String[] args) {         int a=1;         int b=10;         b++;b++;         int[] zufallzahlen_array;         zufallzahlen_array=zufallzahlen(a,b);         for(int i=1;i<(b-a);i++)          {             System.out.print(zufallzahlen_array[i]+" ");          }     }          public static int[] zufallzahlen(int a, int b) {         interval=b-a;         int[] pool = new int[interval];         int[] zufallzahlen_array = new int[interval];         // Initialisierung             for (int i=0; i<interval;i++) pool[i]=i;             interval--;                                      for(;interval>0;interval--)              {                  int ind=(int)(Math.random()*interval); //случайный индекс массива                  zufallzahlen_array[interval] = a+pool[ind]; //                 System.out.println(a+pool[ind]+" ");                      pool[ind]=pool[interval-1]; //последнее число на место "изъятого"              }              return zufallzahlen_array;      } }

Автор: cardinal 26.11.2005, 18:58

Цитата(Denis @ 26.11.2005, 16:53) А дробные? Цитата(Wowa @ 13.11.2005, 14:54) Числа - целые. Denis-delphist, хватит флеймить!

Автор: eskaflone 26.11.2005, 20:17

Код int ind=(int)(Math.random()*interval); //случайный индекс массива                      zufallzahlen_array[interval] = a+pool[ind]; значения math.Random будут повторятся ,и условие Цитата Числа не должны повторятся. не выполнится.

Автор: sergejzr 26.11.2005, 21:24

eskaflone, читай внимательно весь топик. Возможно несколько раз...

Автор: Mayk 26.11.2005, 22:19

[прочитал кажется всё и не по диагонали даже] sergej.z можно записать короче Код  int * pool = new int[interval];   for(int i=0;i<interval;i++)     pool[i]=min+i; //инициализация  random_shuffle(pool, pool+interval);

Автор: sergejzr 26.11.2005, 22:28

Mayk из того, что перемешивание закрыли в функцию, не следует, что там нет переборки массива. Из того, что ктото подумал над решением задачи, не следует, что не обязательно подумать ещё раз. А в общем + за нахождение функции. Это STL, как я понимаю? Я с ним не очень много работал и в последний раз 4 года назад Добавлено @ 22:34 Кстати это помоему не намного длиннее. Если учесть, что это полная программа. Код #include "iostream.h" int main() {       int min=90;  int max=100;  int interval=max-min;  int * pool = new int[interval];    for(int i=0;i<interval;pool[i]=i,i++);  for(interval--;interval>0;interval--)  {    int ind=(rand()*time(0))%interval;    cout<<min+pool[ind]<<" "<<endl;    pool[ind]=pool[interval-1];      }   return 0; }

Автор: Mayk 26.11.2005, 22:40

Цитата(sergej @ 27.11.2005, 02:28) Mayk из того, что перемешивание закрыли в функцию, не следует, что там нет переборки массива. Она там есть. Только там делается наоборот: Там i-ый элемент(i пробегает от begin до end) swap'ается со случайным, а не случайный с j-ым (j пробегает от end до begin). Цитата(sergej @ 27.11.2005, 02:28) Это STL, как я понимаю? Угу Цитата(sergej @ 27.11.2005, 02:28) Из того, что ктото подумал над решением задачи, не следует, что не обязательно подумать ещё раз. Просто когда знаешь решение, думать уже не хочется Подобная тема, кстати, была когда-то в c++. -- добавлю в ручную чтоб тему не апать -- Цитата(sergej @ 27.11.2005, 02:28) Если учесть, что это полная программа. Ну я бы вообще так делал Код #include <algorithm> #include <iostream> #include <iterator> using namespace std; int main(){  int min=90,max=100,interval=max-min;  int * pool = new int[interval];  for(int i=0;i<interval;pool[i]=min+i++);  random_shuffle(pool, pool+interval);  copy(pool,pool+interval, ostream_iterator<int>(cout, endl));  delete[] pool; } Таким образом код сокращаем до 4 строк (от new и до delete если считать без delete'а), вместо 6. 33% строк выкинули благодаря стандартной либе

Автор: Denis-delphist 27.11.2005, 09:28

cardinal Я просто сделал задачю интереснее. Разве тебе не интерестно, как профессионалу решить задачу потруднее???

Автор: GIK 27.11.2005, 11:40

А если просто создать массив из чисел [min++] длинной в разницу. Код var mas = new Array(); var min=100; var max=200; var r=max-min;  for (var i=0; i<r; i++) { mas [i]=min++; //инкремент с минимума и присвоение итога еллементу массива  }  Или я не понял вопроса про генерацию числа??? А может тема довно закрыта Добавлено @ 11:43 Ой, я кажется не вовремя и не с тем примером

Автор: eskaflone 27.11.2005, 11:57

sergej.z в посте wowa не заметил одной строчки : Код                      pool[ind]=pool[interval-1]; //последнее число на место "изъятого" теперь все понятно.

Автор: sergejzr 27.11.2005, 16:23

Mayk, ГЫ Разница там небольшая! вот например то же в 12 строк ))) Код #include "iostream.h" int main(){   int min=90,100,interval=max-min;  int * pool = new int[interval];   for(int i=0;i<interval;pool[i]=i,i++);  for(interval--;interval>0;interval--){    int ind=(rand()*time(0))%interval;    cout<<min+pool[ind]<<" "<<endl;    pool[ind]=pool[interval-1];      }  delete [] pool; } Вообще можно извратится ещё короче, но ИМХО уже лишнее. Есть несколько нюансов на которые я ориентируюсь при ответе. любую программу можно написать в две строки Код #include "myLib.h" execMyProgramm(myArguments);  Из за этого она оптически короче, но на деле возможно тормознутее и запутаннее. То есть сравнивать длинну кода таким образом нельзя. Ещё любую программу можно записать в одну строку. Не всегда стоит подключать библиотеки. Маленькие задачи часто лучше решать вручную, заодно тренировка. Другое дело, если они уже подключены. Алгоритмы можно использовать в разных языках программирования, в то время как код - нет.. Если задают такое задание, то в основном не для того, чтобы проверить, насколько хорошо человек знает различные либы

Автор: Dov 4.12.2005, 00:15

Цитата(sergej @ 26.11.2005, 22:28) #include "iostream.h" int main() {     int min=90; int max=100; int interval=max-min; int * pool = new int[interval];   for(int i=0;i<interval;pool[i]=i,i++); for(interval--;interval>0;interval--) {   int ind=(rand()*time(0))%interval;   cout<<min+pool[ind]<<" "<<endl;   pool[ind]=pool[interval-1];    }   return 0; } Имхо, классный алгоритм. Пару лет назад мне понадобилась такая штука, но кроме перебора всего массива я ничего не придумал. sergej.z, молодец.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)