Есть два числа. Нужно найти все числа между ними, но случайным образом! Т.е. через Math.random.
Числа не должны повторятся.

И при генерировании нового случайного числа, не допускается переборка всего массива с целью проверки было ли это число уже найдено или нет.


Давайте подумаем над этим алгоритмом.

У меня есть такие идеи: нужно найти разницу между числами А и Б. Создать массив этой длины.
И просто потом генерировать числа и записывая их в нужные ячейки массива.

То есть числа целые как я понял (1, 2, 3 и т.д.)?

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

Попробуй так

Пример у тебя числа с М1 по М2

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

Цитата(cardinal @ 13.11.2005, 14:44)

чсила идут от 1 до 10, от 10 до 100 или как?

да, как угодно могут идти. Как задать, так и будут идти.

Числа - целые.
Добавлено @ 16:55

Цитата(cardinal @ 13.11.2005, 14:44)

Тогда надо как бы умножать то, что возвращает Math.random

На что умножать?

насчёт массива - правильно. В нём отмечать числа, которые уже найдены. Только вот придётся имхо сегменты вводить. то есть первое найденное число разобьёт диапазон на 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++;  }

конечно под конец находить будет долго, но это самое простое решение. Игаче надо думать про сегменты..

Цитата(sergej @ 13.11.2005, 14:55)

Игаче надо думать про сегменты..

ну, сегменты не самое страшное. Но у меня нет мыслей, как их тут использовать.

создаем двумерный массив

Код

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

Цитата(Wowa @ 13.11.2005, 14:25)

Нужно найти все числа между ними, но случайным образом!

Akina, а ты предлагаешь не искать их случайным образом, а расбросать случайным образом.

Но вообще очень хитро!

Если Wow'у устроит разбрасывание чисел, то почему бы и нет...
Добавлено @ 20:16

Цитата(Wowa @ 13.11.2005, 14:54)

На что умножать?

Ну на 10, на 100... Просто привык, что Random возвращает числа в интевале 0..1.

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

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

Цитата(Graf @ 13.11.2005, 20:23)

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

а подробннее? Как удаление делать будешь, если не допускается перебор всего массива.

Цитата(cardinal @ 13.11.2005, 21:15)

ты предлагаешь не искать их случайным образом, а расбросать случайным образом

ясен пень... просто условия

Цитата(Wowa @ 13.11.2005, 17:25)

Нужно найти все числа между ними, но случайным образом!

и

Цитата(Wowa @ 13.11.2005, 17:25)

не допускается переборка всего массива с целью проверки было ли это число уже найдено или нет

с учетом упора на выделенное противоречат друг другу.

И вообще в контексте задачи я не понимаю термина "найти"... вывести все, но в случайном порядке? мой алгоритм это делает... что-то другое? объясните что именно, у меня фантазии не хватает.

Цитата(Akina @ 13.11.2005, 20:35)

с учетом упора на выделенное противоречат друг другу.

почему противоречат?

Цитата(Wowa @ 13.11.2005, 23:38)

почему противоречат?

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

Цитата(Akina @ 13.11.2005, 20:43)

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

противоречия нет. Если первое число 100, а второе 200. То создаем массив на 100 элементов. Обнуляем его.
И если какое-то число найдено, то пишем его в массив по индексу этого самого числа, если же array[random]!=0

Где тут противоречие? Ключевое слово было:

Цитата(Wowa @ 13.11.2005, 14: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
Несколько раз даст один и тот же результат?

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

Мой алгоритм линеарный. Без циклов совсем. 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; }

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

Цитата(sergej @ 14.11.2005, 01:25)

если Array(0,i) = Random Несколько раз даст один и тот же результат?

Гы...
Начинающий программист: Я тут написАл программу, но она не работает, где ошибка?
Опытный программист: В генах...

Цитата(sergej @ 14.11.2005, 01:25)

есть "мешок" с числами достаём оттуда в случайном порядке, но не кладём числа обратно в мешок. Забрали число, на его место ставим последнее

при этом числа действительно будут в случайном порядке, но, увы, рандом будет неравномерным... вероятность последних чисел быть "первее" в выборке будет выше, чем первых... надо сдвигать, а не переносить последнее.

Цитата(Akina @ 14.11.2005, 09:05)

надо сдвигать, а не переносить последнее.

сдвигать - это уже совсем другая работа..

Цитата(Akina @ 14.11.2005, 10:05)

вероятность последних чисел быть "первее" в выборке будет выше, чем первых..

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

Как вариант можно попробовать линейный конгруэнтный метод.

Определения.

Используются следующие неотрицательные числа:

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 раскладывать на множители...

Это сообщение отредактировал(а) nworm - 14.11.2005, 15:06

А вот вариант на Яве. Передаем аргументами два числа (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;      } }

Цитата(Denis @ 26.11.2005, 16:53)

А дробные?

Цитата(Wowa @ 13.11.2005, 14:54)

Числа - целые.

Denis-delphist, хватит флеймить!

Код

int ind=(int)(Math.random()*interval); //случайный индекс массива                      zufallzahlen_array[interval] = a+pool[ind];

значения math.Random будут повторятся ,и условие

Цитата

Числа не должны повторятся.

не выполнится.

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

[прочитал кажется всё и не по диагонали даже]
sergej.z
можно записать короче

Код

int * pool = new int[interval];   for(int i=0;i<interval;i++)     pool[i]=min+i; //инициализация  random_shuffle(pool, pool+interval);

Это сообщение отредактировал(а) Mayk - 26.11.2005, 22:19

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

Цитата(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% строк выкинули благодаря стандартной либе

Это сообщение отредактировал(а) Mayk - 26.11.2005, 23:04

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

А если просто создать массив из чисел [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
Ой, я кажется не вовремя и не с тем примером

sergej.z

в посте wowa не заметил одной строчки :

Код

pool[ind]=pool[interval-1]; //последнее число на место "изъятого"

теперь все понятно.

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

Вообще можно извратится ещё короче, но ИМХО уже лишнее.

Есть несколько нюансов на которые я ориентируюсь при ответе.

1. любую программу можно написать в две строки
   

   Код

   #include "myLib.h" execMyProgramm(myArguments);

   
   Из за этого она оптически короче, но на деле возможно тормознутее и запутаннее. То есть сравнивать длинну кода таким образом нельзя. Ещё любую программу можно записать в одну строку.
2. Не всегда стоит подключать библиотеки. Маленькие задачи часто лучше решать вручную, заодно тренировка. Другое дело, если они уже подключены.
3. Алгоритмы можно использовать в разных языках программирования, в то время как код - нет..
4. Если задают такое задание, то в основном не для того, чтобы проверить, насколько хорошо человек знает различные либы

Цитата(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, молодец.