Сложно это..

Применяю для представления целых чисел любой длины тип AnsiString, т.е. с самой генерацией чисел проблем не возникает:
Берем нужную длину числа, и в цикле пока всю длину не прошли, присваиваем строке random(10);

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

Вообщем, не знаю что делать.

Выкладываю, кусок НЕрабочего кода, может кого наведут какие мысли:



По коду. Как я решил делать: сначала делаю проверку если у нас число разрядов у чисел не одинаковые, то дописываю нули у числа, у которого
меньше разрядов. Потом сравнениваю. Если первый разряд первого числа меньше первого разряда второго числа, то по значит
в первом числе могут быть сгенерированы любые числа после первого разряда.

Это не работает, скажем на примере:

351 452



Это сообщение отредактировал(а) Alexey91 - 12.4.2011, 09:48

- это ? или я ничего не понимаю

A5uKa, у человека, походу, арифметика длинных чисел

Alexey91, генери число от 0 до (max - min), а затем добавляй min, как ты это делаешь на бумажке в столбик



Это сообщение отредактировал(а) borisbn - 12.4.2011, 13:21

опять не понимаю   

1) Добиваешь короткую строку нулями слева (как у тебя и было)
2) Берешь самую левую цифру, точнее 2 цифры - минимум и максимум. Генерируешь цифру в диапазоне min-max
3) Если цифра не совпала с min (или max), то все дальнейшие цифры в min (max) числе принимаешь равными 0 (9)
4) Повторять, пока вся строка не будет сгенерена
 

вау ! ( это я  xvr-у )
хм... надо быть проще и к тебе люди потянутся ( это я себе  )

borisbn К сожалению не понял(

xvr

На примере 903 и 1107

1) Дописываю нули 0903, 1107
2) Беру 0 и 1
Случайные числа нахожу по такой формуле: random(max[i]-min[i]+1)+min[i]
Получаю например 0
0 совпал с min[i]

что дальше? Исходя из твоего алгоритма   




Это сообщение отредактировал(а) Alexey91 - 12.4.2011, 17:34

мда, поспешил я хвалить...
при min=999999, max=1999999 и при первом рандоме, равном 0, рез-т будет всегда 999999, т.е. в 50% будет нормальный ранд, в 50% - всегда равен min...


тебе нужно создать ф-ции вычитания и сложения чисел, представленных в виде строки.
такие ф-ции проще всего реализовать методом, который все в школе учили - в столбик.
Берёшь одно число, снизу под ним пишешь другое, выровняв нулями вначале меньшее из них.
Затем начиная справа (последний символ в строке) складывашь две цифры. Остаток от деления на 10 записываешь в рез-т, а рез-т целочисленного деления на 10 добавляешь к следующей сумме...
Школа 1-й или 2-й класс.

а дальше вызывая эти ф-ции делаешь то же самое, что и с обычными числами

ну, а сама ф-ция str_random будет уже попроще, т.к. мин. число у неё 0.
вот её, кстати, можно реализовывать как предложил xvr

Это сообщение отредактировал(а) borisbn - 12.4.2011, 17:56

так и быть, лови сумму

http://liveworkspace.org/code/c3c088470490...6919d945eea835a
разность - сам. по аналогии и по школьному курсу за 1-й класс .

Это сообщение отредактировал(а) borisbn - 12.4.2011, 21:00

borisbn, спасибо   

А я вывел следующий алгоритм (рабочий):

На примере двух чисел: 603, 2954

Если длина разная, то дописываем (длина_второй_строки-длина_первой_строки) нулей к первому числу
Получаем: 0603, 2954

Берем первые разряды двух предельных значений (>=, <=), т.е. 0 и 2
И генерируем число в диапазоне этих двух первых разрядов (т.е. в данном случае 0 и 2)

Если сгенерированное значение равно 1, то последующие разряды генерируемого числа можем забивать числами от 0 до 9
(в самом деле, если первый разряд 1, то остальные разряды могут быть из любых цифр... 1504, 1999, 1704, 1613 - все они в любом
случае войдут в заданный диапазон)

Если сгенерированное значение равно 0, то работаем с первым числом (0603), а именно таким образом:

1.Берем второй разряд (6) и генерируем числа в диапазоне от 6 до 9
2.Если сгенерированное число равно 6, то смотрим следующие разряды (возвращаемся к пункту 1 и берем третий разряд и.т.д.)
3.Если нет (получились 7, 8, 9), то последующие разряды забиваем любыми числами от 0 до 9
(734,799,954 все они в любом случае будут больше 609)

Если сгенерированное значение равно 2, то работаем со вторым число (2954), а именно таким образом:

1.Берем второй разряд (9) и генерируем числа в диапазоне от 0 до 9
2.Если сгенерированное число равно 9, то смотрим следующие разряды (возвращаемся к пункту 1 и берем третий разряд и.т.д.)
3.Если нет (получились 0,1,2,4,5,6,7,8),то последующие разряды забиваем лбыми числами от 0 до 9
(2854,2299,2899,2403 все они в любом случае будут меньше 2954)

Добавлено @ 18:41
Рано я обрадовался, нужно еще генерировать вещественные числа, и учитывать то, что они могут быть отрицательными   

Это сообщение отредактировал(а) Alexey91 - 12.4.2011, 18:46

1. Это ничем не отличается от алгоритма xvr. Почти
2. Проверь при при min=999999, max=1999999 и первом рандоме, равном 0
3. У меня в ф-ции ошибка. В строке, где выбирается shortest нужно поменять < на <=

Да, есть такая бяка. И она будет у любого алгоритма, генерирующего цифры поштучно   Что бы получить хорошее распределение у результирующего числа его надо создавать именно как число. Твой вариант с str_random не является исключением. Как генерировать эту самую рандомную строку/число?  Если по 1 цифре, то получим то же самое, что и в моем варианте   


Псевдокод. MinStr, MaxStr - строки (уже дополненные нулями)

если генерить [ 0; max ], то твой алгоритм должен работать.

--------------
отредактировал сообщение с ф-цией str_add и пример на liveworkspace

      
давно хотел попросить boostcoder'а, чтобы он сделал на сайте liveworkspace пометочку какой щаз используется компилятор, версия boost и т.п. 

boostcoder, если читаешь, сделай, плиз.

Если интересует быстродействие, то нужно писать нормальную арифметику длинных чисел, а не представлять числа в символьном десятичном виде. Только так можно сделать по-настоящему юниформ-рандом генератор случайных чисел в заданном диапазоне.
Кстати по настоящему юниформ-рандом гсч, тоже отрбасывает неподходящие числа, до тех пор пока не сгенерирует подходящее. иначе никак. Просто в двоичном виде в самом худшем варианте будет 50% вероятности получить правильное число, что приемлемо. В десятичном виде (в общем случае) вероятность гораздо меньше.
Ну а с символьным представлением вообще о быстродействии можно забыть.

неа. не будет. (0...1000000). надо что-то другое думать.

Угу. Остается только арифметика больших чисел   Нужно как минимум сделать операцию (a+b)/2 (над строками)

Идея - на каждой итерации вычисляем среднее между минимумом и максимумом и выбираем (случайно) для дальнейшей генерации диапазон минимум-среднее или среднее-максимум
Недостаток - будет долго работать (log2(Max-Min) итераций)

Извиняюсь за свое отсутствие, почитал ваши ответы, так и не понял в конечном счете что мне делать

Если символьное представление не годиться, то что тогда можно сделать?

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

Но тогда как быть с вещественными числами

Это сообщение отредактировал(а) Alexey91 - 17.4.2011, 11:59

здесь kemiisto дал три ссылки на библиотеки с арифметикой больших чисел. посмотри их. может, хоть и не заюзаешь, но будет понятно, как и что сделано...


почему же не годится ? вполне. оч. удобно выводить для отладки... просто нельзя генерить посимвольно. 



не вижу проблемы ни с вещественными числами, ни с тем, что для удобства и простоты алгоритмов можно начинать число с '0'

Хорошо, посмотрю GMP
Только как ее поставить на Windows????




Это сообщение отредактировал(а) Alexey91 - 17.4.2011, 13:50

вот ф-ция деления на 2

объёдени мою str_add с этой и вставь их в алгоритм, предложенный xvr. 

Я так сделал, проверил - работает.

возьмем простой пример. будем генерить числа в диапазоне 1..3

вероятность выпадения:
1 - 25%
2 - 50%
3 - 25%

По настоящему равномерно распределенный ГСЧ (uniform random) не получится, ребята.

Ну если надо и для таких чисел тоже, то можно слегка модифицировать выбор половин (в моем алгоритме). Можно выбирать их не равновероятно, а пропорционально их размеру (что имеет смысл когда диапазон сойдется до нескольких цифр. Кстати, в этом случае вообще можно отконвертить разность в банальный int и сделать выбор сразу по нему всему, обычным rnd)