VPF::Сгенерировать число любой длины в заданном диапазо

xvr

Дата 13.4.2011, 08:28 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 48
Всего: 223

Цитата(borisbn @ 13.4.2011, 08:10

)

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

Угу. Остается только арифметика больших чисел smile

Нужно как минимум сделать операцию (a+b)/2 (над строками)

Код


String rnd(String MinV, String MaxV)
{
 String MidV;
 while(MinV!=MaxV)
  {
   MidV=AddDiv2(MinV,MaxV); // MidV=(MaxV+MinV)/2
   if (MidV==MinV) return rnd()&1?MinV:MaxV;
   (rnd()&1?MinV:MaxV)=MidV;
  }
 return MinV;
}

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

Alexey91

Дата 17.4.2011, 11:53 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 195
Регистрация: 18.9.2008

Репутация: нет
Всего: нет

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

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

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

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

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

borisbn

Дата 17.4.2011, 12:04 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 18
Всего: 135

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

Цитата(Alexey91 @ 17.4.2011, 11:53

)

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

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

Цитата(Alexey91 @ 17.4.2011, 11:53

)

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

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

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

Alexey91

Дата 17.4.2011, 12:57 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 195
Регистрация: 18.9.2008

Репутация: нет
Всего: нет

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

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

borisbn

Дата 17.4.2011, 15:54 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 18
Всего: 135

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

Код


std::string str_div_2( const std::string & a )
{
    std::string result;
    int a_length = a.length();
    int fromPrev = 0;
    for ( int i = 0; i < a_length; ++i )
    {
        int digit = a[ i ] - '0' + fromPrev;
        result = result + (char)( ( digit / 2 ) + '0' );
        fromPrev = ( digit % 2 ) * 10;
    }
    int i = 0;
    while ( result[ i ] == '0' )
    {
        i++;
    }
    return result.substr( i, result.length() );
}

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

Цитата(xvr @ 13.4.2011, 08:28

)

Нужно как минимум сделать операцию (a+b)/2 (над строками)
String rnd(String MinV, String MaxV)
{
   String MidV;
   while(MinV!=MaxV)
   {
        MidV=AddDiv2(MinV,MaxV); // MidV=(MaxV+MinV)/2
        if (MidV==MinV) return rnd()&1?MinV:MaxV;
        (rnd()&1?MinV:MaxV)=MidV;
   }
   return MinV;
}
Идея - на каждой итерации вычисляем среднее между минимумом и максимумом и выбираем (случайно) для дальнейшей генерации диапазон минимум-среднее или среднее-максимумНедостаток - будет долго работать (log2(Max-Min) итераций)

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

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

volatile

Дата 17.4.2011, 23:33 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 3
Всего: 85

Цитата(xvr @ 13.4.2011, 08:28

)

String rnd(String MinV, String MaxV)
{
String MidV;
while(MinV!=MaxV)
  {
   MidV=AddDiv2(MinV,MaxV); // MidV=(MaxV+MinV)/2
   if (MidV==MinV) return rnd()&1?MinV:MaxV;
   (rnd()&1?MinV:MaxV)=MidV;
  }
return MinV;
}

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

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

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

xvr

Дата 18.4.2011, 08:32 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 48
Всего: 223

Цитата(volatile @ 17.4.2011, 23:33

)

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

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

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C++ Builder \| Следующая тема »