int x = rand()%m;
for(int i=0;i<m;i++)
{
a = x;
x = (a*x+c)%m;
}
Забивка рендом
Нужна максимально рациональная ф-ция, забивающая рендом (по модулю, например на 10) массив без повторений.
Спасибо.
Спасибо.
Цитата:
Originally posted by Stalcer
Нужна максимально рациональная ф-ция, забивающая рендом (по модулю, например на 10) массив без повторений.
Спасибо.
Нужна максимально рациональная ф-ция, забивающая рендом (по модулю, например на 10) массив без повторений.
Спасибо.
Нужна. И что?
Пожалуйста.
Цитата:
Originally posted by Stalcer
Нужна максимально рациональная ф-ция, забивающая рендом (по модулю, например на 10) массив без повторений.Спасибо.
Нужна максимально рациональная ф-ция, забивающая рендом (по модулю, например на 10) массив без повторений.Спасибо.
Используется т.н. линейный конгруэнтный метод. (Дядя Кнут. Иск.прог. Т.2)
X[n+1] = (a*X[n]+c) mod m
Для массива из 100 элементов,
напр. m = 100, c = 17, a = 21
================================
1) НОД(c,m) = 1 (т.е. c и m взаимно просты);
2) a - 1 кратно p для всех простых p - делителей m;
3) a - 1 кратно 4, если m кратно 4.
Цитата:
Originally posted by rostyslav
Используется т.н. линейный конгруэнтный метод. (Дядя Кнут. Иск.прог. Т.2)
X[n+1] = (a*X[n]+c) mod m
Для массива из 100 элементов,
напр. m = 100, c = 17, a = 21
================================
1) НОД(c,m) = 1 (т.е. c и m взаимно просты);
2) a - 1 кратно p для всех простых p - делителей m;
3) a - 1 кратно 4, если m кратно 4.
Используется т.н. линейный конгруэнтный метод. (Дядя Кнут. Иск.прог. Т.2)
X[n+1] = (a*X[n]+c) mod m
Для массива из 100 элементов,
напр. m = 100, c = 17, a = 21
================================
1) НОД(c,m) = 1 (т.е. c и m взаимно просты);
2) a - 1 кратно p для всех простых p - делителей m;
3) a - 1 кратно 4, если m кратно 4.
Спасибо, но как это применить в конкретной ф-ции?
Можно использовать такой алгоритм:
Код:
1 забиваем рендом первую ячейку массива
2 начиная со второй проверяем предыдущие ячейки на повторение,
пока есть повторение - обновляем ренд и сравниваем,
если повторений нет - продолжаем забивать массив
2 начиная со второй проверяем предыдущие ячейки на повторение,
пока есть повторение - обновляем ренд и сравниваем,
если повторений нет - продолжаем забивать массив
Как это реализовать в коде? Как обновлять ренд (случайное число) методом вызова?
Если неизвестно наперед размерность массива, тогда наверно придется написать ф-ю, которая по заданному m вычислит a и c.
Допустим m = 100, нужно заполнить массив int a[100];
Допустим m = 100, нужно заполнить массив int a[100];
Код:
Цитата:
Originally posted by rostyslav
Если неизвестно наперед размерность массива, тогда наверно придется написать ф-ю, которая по заданному m вычислит a и c.
Допустим m = 100, нужно заполнить массив int a[100];
Если неизвестно наперед размерность массива, тогда наверно придется написать ф-ю, которая по заданному m вычислит a и c.
Допустим m = 100, нужно заполнить массив int a[100];
Код:
int x = rand()%m;
for(int i=0;i<m;i++)
{
a = x;
x = (a*x+c)%m;
}
for(int i=0;i<m;i++)
{
a = x;
x = (a*x+c)%m;
}
Регардсы, попробую.
Цитата:
Originally posted by rostyslav
Если неизвестно наперед размерность массива, тогда наверно придется написать ф-ю, которая по заданному m вычислит a и c.
Допустим m = 100, нужно заполнить массив int a[100];
Если неизвестно наперед размерность массива, тогда наверно придется написать ф-ю, которая по заданному m вычислит a и c.
Допустим m = 100, нужно заполнить массив int a[100];
Код:
int x = rand()%m;
for(int i=0;i<m;i++)
{
a = x;
x = (a*x+c)%m;
}
for(int i=0;i<m;i++)
{
a = x;
x = (a*x+c)%m;
}
Не получается... Компилятор не понимает a*, с не определено.
Все -таки мой алгоритм ,наверное ,адаптированей...
Как обновлять значение rand() в разных участках программы?
Цитата:
Originally posted by Stalcer
Спасибо, но как это применить в конкретной ф-ции?
Можно использовать такой алгоритм:
Как это реализовать в коде? Как обновлять ренд (случайное число) методом вызова?
Спасибо, но как это применить в конкретной ф-ции?
Можно использовать такой алгоритм:
Код:
1 забиваем рендом первую ячейку массива
2 начиная со второй проверяем предыдущие ячейки на повторение,
пока есть повторение - обновляем ренд и сравниваем,
если повторений нет - продолжаем забивать массив
2 начиная со второй проверяем предыдущие ячейки на повторение,
пока есть повторение - обновляем ренд и сравниваем,
если повторений нет - продолжаем забивать массив
Как это реализовать в коде? Как обновлять ренд (случайное число) методом вызова?
Попробуй реализовать мой алгоритм плз.
Цитата:
Originally posted by Stalcer
Не получается... Компилятор не понимает a*, с не определено.
Все -таки мой алгоритм ,наверное ,адаптированей...
Не получается... Компилятор не понимает a*, с не определено.
Все -таки мой алгоритм ,наверное ,адаптированей...
Конечно твой алгоритм адаптированней. В ней хоть все переменные определены :D. А что мешает написать
Код:
void fillArray(int array, int a, int c, int m)
{
int x = rand()%m;
for(int i=0;i<m;i++)
{
array = x;
x = (a*x+c)%m;
}
}
Вызов где-то в программе
void main()
{
int a[100];
fillArray(a, 21, 17, 100);
...
}
{
int x = rand()%m;
for(int i=0;i<m;i++)
{
array = x;
x = (a*x+c)%m;
}
}
Вызов где-то в программе
void main()
{
int a[100];
fillArray(a, 21, 17, 100);
...
}
Цитата:
Как обновлять значение rand() в разных участках программы?
Или Randomize(), или RandSeed = число. В зависимости от того, что нужно. Всегда другая последовательность или одна и та же последовательность при разных вызовах программы. Если я правильно понял вопрос.
Цитата:
Originally posted by Stalcer
Попробуй реализовать мой алгоритм плз.
Попробуй реализовать мой алгоритм плз.
Архи неэффективный алгоритм, но пусть будет, в "моей" нужно бы определять коэф. a, c
Код:
void fillArray(int *ar/*массив*/, int m/*размерность массива*/)
{
Randomize(); //при каждом вызове другая последовательность
for(int i=0; i<m; i++)
{
while(true)
{
int x = rand()%m;
for(int j=0; j<i; j++)
{
if(ar[j]==x)
{
x = -1;
break;
}
}
if(x!=-1)
{
ar = x;
break;
}
}
}
}
{
Randomize(); //при каждом вызове другая последовательность
for(int i=0; i<m; i++)
{
while(true)
{
int x = rand()%m;
for(int j=0; j<i; j++)
{
if(ar[j]==x)
{
x = -1;
break;
}
}
if(x!=-1)
{
ar = x;
break;
}
}
}
}
Цитата:
Originally posted by rostyslav
Архи неэффективный алгоритм, но пусть будет, в "моей" нужно бы определять коэф. a, c
С тебя 20 копеек на счет sq_deep
Архи неэффективный алгоритм, но пусть будет, в "моей" нужно бы определять коэф. a, c
Код:
void fillArray(int *ar/*массив*/, int m/*размерность массива*/)
{
Randomize(); //при каждом вызове другая последовательность
for(int i=0; i<m; i++)
{
while(true)
{
int x = rand()%m;
for(int j=0; j<i; j++)
{
if(ar[j]==x)
{
x = -1;
break;
}
}
if(x!=-1)
{
ar = x;
break;
}
}
}
}
{
Randomize(); //при каждом вызове другая последовательность
for(int i=0; i<m; i++)
{
while(true)
{
int x = rand()%m;
for(int j=0; j<i; j++)
{
if(ar[j]==x)
{
x = -1;
break;
}
}
if(x!=-1)
{
ar = x;
break;
}
}
}
}
Какие заголовки грузить(Randomize(); не понимает)?
Фенкс! На счет 20-ти копеек или 7 алтынов - без Б. Считайте каждую консультацию (их будет достаточно :)), а потом все вместе и оплачу вебманями ;)
Цитата:
Originally posted by Stalcer
Какие заголовки грузить(Randomize(); не понимает)?
Фенкс! На счет 20-ти копеек или 7 алтынов - без Б. Считайте каждую консультацию (их будет достаточно :)), а потом все вместе и оплачу вебманями ;)
Какие заголовки грузить(Randomize(); не понимает)?
Фенкс! На счет 20-ти копеек или 7 алтынов - без Б. Считайте каждую консультацию (их будет достаточно :)), а потом все вместе и оплачу вебманями ;)
У меня Visual C++, MSDN нет :(
Цитата:
Originally posted by Stalcer
Какие заголовки грузить(Randomize(); не понимает)?
Какие заголовки грузить(Randomize(); не понимает)?
Оппа. Я думал, что это ветка Buildera.
Для Visual C, вместо Randomize() нужно вызвать
srand((unsigned)time(NULL));
и подключить #include <time.h>
Цитата:
Originally posted by Stalcer
У меня Visual C++, MSDN нет :(
У меня Visual C++, MSDN нет :(
Все OK, я испльзовал srand(time(NULL)); Спасибо за оперативную помощь, на вашем счету 20 центов .:D
Цитата:
Originally posted by rostyslav
...
С тебя 20 копеек на счет sq_deep
...
С тебя 20 копеек на счет sq_deep
От этих 20 коп. отказываюсь: я здесь ни при чём.
А как насчёт заполнения массива с помощью STL? Вот пример из MSDN:
Код:
// alg_random_shuffle.cpp
// compile with: /EHsc
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
int main( ) {
using namespace std;
vector <int> v1;
vector <int>::iterator Iter1, Iter2;
int i;
for ( i = 1 ; i <= 9 ; i++ )
{
v1.push_back( i );
}
random_shuffle( v1.begin( ), v1.end( ) );
cout << "The original version of vector v1 is: ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
// Shuffled once
random_shuffle( v1.begin( ), v1.end( ));
push_heap( v1.begin( ), v1.end( ) );
cout << "Vector v1 after one shuffle is: ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
// Shuffled again
random_shuffle( v1.begin( ), v1.end( ));
push_heap( v1.begin( ), v1.end( ) );
cout << "Vector v1 after another shuffle is: ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
}
// compile with: /EHsc
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
int main( ) {
using namespace std;
vector <int> v1;
vector <int>::iterator Iter1, Iter2;
int i;
for ( i = 1 ; i <= 9 ; i++ )
{
v1.push_back( i );
}
random_shuffle( v1.begin( ), v1.end( ) );
cout << "The original version of vector v1 is: ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
// Shuffled once
random_shuffle( v1.begin( ), v1.end( ));
push_heap( v1.begin( ), v1.end( ) );
cout << "Vector v1 after one shuffle is: ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
// Shuffled again
random_shuffle( v1.begin( ), v1.end( ));
push_heap( v1.begin( ), v1.end( ) );
cout << "Vector v1 after another shuffle is: ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
}
Код:
The original version of vector v1 is: ( 9 2 7 3 1 6 8 4 5 ).
Vector v1 after one shuffle is: ( 1 4 7 9 2 5 8 6 3 ).
Vector v1 after another shuffle is: ( 3 2 8 5 4 9 6 7 1 ).
Vector v1 after one shuffle is: ( 1 4 7 9 2 5 8 6 3 ).
Vector v1 after another shuffle is: ( 3 2 8 5 4 9 6 7 1 ).
Цитата:
Originally posted by sq_deep
От этих 20 коп. отказываюсь: я здесь ни при чём.
От этих 20 коп. отказываюсь: я здесь ни при чём.
Ok. Просто Вы любите решать студ.задачи, наверно для отдыха.
Цитата:
А как насчёт заполнения массива с помощью STL? Вот пример из MSDN:
Код:
// alg_random_shuffle.cpp
// compile with: /EHsc
...
// compile with: /EHsc
...
Нормально. Даже можно бы написать не stl версию алгоритма.
От этих 20 копеек я отказался, потому что они всецело Ваши, rostyslav.
Цитата:
Originally posted by rostyslav
Даже можно бы написать не stl версию алгоритма.
Даже можно бы написать не stl версию алгоритма.
Кстати, я думаю — почти уверен, — что std::random_shuffle() использует именно алгоритм из Кнута, который Вы предложили. Тогда там должна быть и предоженная Вами "функция, которая по заданному m вычислит a и c". Если бы версия STL от Microsoft была написана хоть чуть-чуть более "reader-friendly", я бы посмотрел в их тексты, чтобы это проверить. Интересно было бы узнать, как они это делают, но копаться в их коде, в котором все идентификаторы называются "_a", "_l" и т.п. у меня нет ни малейшего желания.
Кстати, когда-то давно я использовал бейсик от Hewlett-Packard, в котором допускались только двухсимвольные идентификаторы типа A1, C8 и т.п. А идом массива там могло быть только однобуквенное слово, и таким образом в программе не могло быть больше 26 массивов. Вот это была хорошая шутка! даже лучше, чем в MS STL. До сих пор забыть не могу :roll:
Цитата:
Originally posted by sq_deep
От этих 20 коп. отказываюсь: я здесь ни при чём.
А как насчёт заполнения массива с помощью STL? Вот пример из MSDN:
Результат
От этих 20 коп. отказываюсь: я здесь ни при чём.
А как насчёт заполнения массива с помощью STL? Вот пример из MSDN:
Код:
// alg_random_shuffle.cpp
// compile with: /EHsc
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
int main( ) {
using namespace std;
vector <int> v1;
vector <int>::iterator Iter1, Iter2;
int i;
for ( i = 1 ; i <= 9 ; i++ )
{
v1.push_back( i );
}
random_shuffle( v1.begin( ), v1.end( ) );
cout << "The original version of vector v1 is: ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
// Shuffled once
random_shuffle( v1.begin( ), v1.end( ));
push_heap( v1.begin( ), v1.end( ) );
cout << "Vector v1 after one shuffle is: ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
// Shuffled again
random_shuffle( v1.begin( ), v1.end( ));
push_heap( v1.begin( ), v1.end( ) );
cout << "Vector v1 after another shuffle is: ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
}
// compile with: /EHsc
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
int main( ) {
using namespace std;
vector <int> v1;
vector <int>::iterator Iter1, Iter2;
int i;
for ( i = 1 ; i <= 9 ; i++ )
{
v1.push_back( i );
}
random_shuffle( v1.begin( ), v1.end( ) );
cout << "The original version of vector v1 is: ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
// Shuffled once
random_shuffle( v1.begin( ), v1.end( ));
push_heap( v1.begin( ), v1.end( ) );
cout << "Vector v1 after one shuffle is: ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
// Shuffled again
random_shuffle( v1.begin( ), v1.end( ));
push_heap( v1.begin( ), v1.end( ) );
cout << "Vector v1 after another shuffle is: ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")." << endl;
}
Код:
The original version of vector v1 is: ( 9 2 7 3 1 6 8 4 5 ).
Vector v1 after one shuffle is: ( 1 4 7 9 2 5 8 6 3 ).
Vector v1 after another shuffle is: ( 3 2 8 5 4 9 6 7 1 ).
Vector v1 after one shuffle is: ( 1 4 7 9 2 5 8 6 3 ).
Vector v1 after another shuffle is: ( 3 2 8 5 4 9 6 7 1 ).
Тоже вариант.
Цитата:
Originally posted by Stalcer
Тоже вариант.
Тоже вариант.
Тогда гони 20-у sq_deep :D
Цитата:
Originally posted by rostyslav
Тогда гони 20-у sq_deep :D
Тогда гони 20-у sq_deep :D
Обоим по twenty cents.
Цитата:
Originally posted by Stalcer
Обоим по twenty cents.
Обоим по twenty cents.
sq_deep: А Биллу Гейтсу?!!
Stalcer: Послушайте, sq_deep, ну при чём здесь Билл Гейтс?