Заполнение массива случайными числами от 1 до 10^10 в C или C++

Question

часть моего назначения основана на массиве (его размер задан пользователем), который содержит случайные числа от 1 до 10^10 , Затем мы должны найти k-е меньшее меньшее число массива. Вот что я пробовал:

#include <cstdlib> 
#include <stdlib.h> 
#include <stdio.h> 
#include <iostream> 
#include <time.h> 

using namespace std; 

void swap(int *x,int *y) 
{ 
    int temp; 
    temp = *x; 
    *x = *y; 
    *y = temp; 
} 

int choose_pivot(int i,int j) 
{ 
    return((i+j) /2); 
} 

// Print array 
void printarr(int arr[],int n) 
{ 
    int i; 
    for(i=0;i<n;i++) 
     printf("%d\t",arr[i]); 
} 

// Find algorithm 
int find1(int arr[],int left,int right,int k) 
{ 
    int i,j,pivot; 
    if (left==right) 
     return arr[left]; 
    else 
    { 
     i=left; 
     j=right+1; 
     pivot= arr[left]; 
     do 
     { 
      do { 
       i=i+1; 
      } while (arr[i]>=pivot); 
      do { 
       j =j-1; 
      } while (arr[j]<=pivot); 
      if (i<j) 
       swap(arr[i],arr[j]); 
     } while (j<=i); 
    } 
    swap(arr[left],arr[j]); 
    if (k==j) 
     return arr[j]; 
    else if (k<j) 
     find1(arr,left,j-1,k); 
    else 
     find1(arr,j+1,right,k-j); 
} 

int main(int argc, char *argv[]) 
{ 
    srand(time(NULL)); 
    int n,i,fi,k; 
    printf("Give array's size:\n"); 
    scanf("%d",&n); 
    int pin[n]; 
    for (i=0;i<n;i++) 
     pin[i]=((rand()*rand()) % 1000000000) +1; 
    printf("Give k: \n"); 
    scanf("%d",&k); 
    printf("The array contains the following numbers:\n\n"); 
    printarr(pin,n); 
    fi=find1(pin,0,n-1,k);//find the k-th smallest number in the array 
    printf("The k-th smallest number is: %d",fi); 

    system("PAUSE"); 
} 

Как вы можете видеть, 10^10 это очень большая ценность, и я сделал что-то еще, чтобы заполнить массив со случайными числами. Правильно ли это? Есть ли что-то еще, что я мог бы сделать? И моя вторая проблема заключается в алгоритме поиска. Это не работает. Может ли кто-нибудь помочь мне с этим? Большое спасибо

Answer 1

rand()*rand() сильно отличается, чем один rand(), он уменьшает хаотичность и изменяет его распределение. См. this question для более глубокого объяснения.

Кроме того, целое число обычно составляет 4 байта. Он может содержать значение 2^31 (2 миллиарда и что-то еще) или 2^32 (4 миллиарда и более), если оно не указано. Вы можете увидеть максимальное число, которое может содержать проверку макроса INT_MAX, определенного в limits.h. 10^10 - это 10 миллиардов, он не будет вписываться в целое число, вам придется использовать больший тип (long long обычно составляет 64 байта, таким образом, больше, чем вам нужно).

rand, также, возвращает число до RAND_MAX, и так как она возвращает int, он не будет больше, чем INT_MAX. Вы должны использовать какой-либо другой способ генерировать число, равное 10^10.

Если вам не нужны случайные и случайные числа, вы можете суммировать n случайных чисел (полученных rand), так что n=10^10/RAND_MAX.

Answer 2

Если вы более подробно рассмотрите 10 , вы заметите, что это довольно круглый предел. Я беру на себя это, чтобы генерировать каждое число, по одной цифре за раз и игнорируя незначительные нули. На этом этапе у вас будет число от 0 до 10 -1 включительно. Все, что вы остались делаете добавления 1.

Как для random()*random(), то есть точная тема this other question.

Алинь

Answer 3

Проблема № 1, ИНТ будет содержать только число размером 2^31 размера. Вам понадобится немного большая альтернатива для вашего массива булавки.

Кроме того, умножение ваших двух случайных чисел на самом деле не очень много - за исключением, возможно, сделать число менее случайным.

Затем вы не можете динамически создавать массив в стеке с помощью ввода пользователем. Для этого потребуется новое решение для выделения массива для вас.

Answer 4

Вы забыли свои заявления о возврате. в конце find1 вы должны делать:

if (k==j) 
    return arr[j]; 
else if (k<j) 
    return find1(arr,left,j-1,k); 
else 
    return find1(arr,j+1,right,k-j); 
} 

Answer 5

long long get_big_rand() 
{ 

    long long result; 
    do { 
     result = (rand() & 0x3ff); 
     result <<= 12; 
     result |= (rand() & 0xfff); 
     result <<= 12; 
     result |= (rand() & 0xfff); 
    } while (++result > 10000000000ULL); 
    return result; 
} 

Answer 6

рандов() * рандов() не собирается ничего делать для вас.Он не масштабируется так, как вы думаете, и это изменяет дистрибутив. Фактически

double norm_rand(){ 
    double r=0; 
    for(unsigned i=0;i!=12;++i) 
     r+=rand()/static_cast<double>(RAND_MAX); 
    return (r/12)-6; 
} 

- общий способ моделирования нормального распределения со средним 0 и дисперсией 1;

Лучший способ получить большие случайные числа - это использовать случайное числовое устройство, например/dev/urandom или RtlGenRandom. т.е.

typedef unsigned long long big_type; 
std::vector<double> rnums; 
std::vector<big_type> buf(numtoread); 
     std::ifstream rnds("/dev/urandom"); 
rnds.read(reinterpret_cast<char*>(&buf[0],buf.size()*sizeof(big_type)); 
std::transform(buf.begin(),buf.end(),std::back_inserter(rnums), 
    [](big_type const& i){ 
     return (i*100000000000.)/(std::numeric_limits<big_type>::max()); 
    }); 

Рискуя делать свою домашнюю работу для вас, совершенно другой подход заключается в использовании библиотеки, которые приходят с C++.

#include <cassert> 
#include <sstream> 
#ifndef _MSC_VER //then assume Linux 
#include <tr1/random> 
#else 
#include <random> 
#endif 
#include <boost/lexical_cast.hpp> 
#include <algorithm> 
#include <iterator> 
#include <iostream> 
int main(int argc, char** argv) 
{ 
    assert(argc==3); 
    unsigned const numentries=boost::lexical_cast<unsigned>(argv[1]); 
    unsigned const k=boost::lexical_cast<unsigned>(argv[2]); 
    std::cout<<" finding "<<k<<"th of "<< numentries<<" entries\n"; 
    assert(k<=numentries); 
    std::vector<double> nums(numentries); 
    std::tr1::uniform_real<> rng(0.,10000000000.); 
    std::tr1::minstd_rand generator(42u); 
    std::tr1::variate_generator<std::tr1::minstd_rand, std::tr1::uniform_real<> > 
      uni(generator, rng); 
    std::generate_n(nums.begin(),nums.size(),uni); 
    std::cout<<" Generated:\t "; 
    std::copy(nums.begin(),nums.end(),std::ostream_iterator<double>(std::cout,"\t")); 
    std::sort(nums.begin(),nums.end()); 
    std::cout<<"\n The "<<k<<"th smallest entry is "<<nums[k]<<"\n"; 
    return 0; 
} 

(Если вы находитесь в классе на уровне просто прошу сделать массив чисел ранда и сдаете, что они, вероятно, подведут) Что делать на практике, чтобы объединить два подходы. Это используется вместо линейного conguentual ГСЧ, используемого выше (в minstd_rand):

template<typename bigtype=unsigned> 
struct randeng { 
    typedef bigtype result_type; 
    randeng(unsigned x) : 
     m_samplesrequired(x), m_samples(x), m_lastused() { 
     std::ifstream rand; 
     rand.open("/dev/urandom"); 
     assert(rand); 
     rand.read(reinterpret_cast<char*> (&*(m_samples.begin())), 
       m_samplesrequired * sizeof(unsigned)); 
    } 
    result_type operator()() const { 
     assert(m_lastused<m_samplesrequired); 
     return m_samples[m_lastused++]; 
    } 
    result_type max() const { 
     return std::numeric_limits<result_type>::max(); 
    } 
    result_type min() const { 
     return 0; 
    } 
    unsigned m_samplesrequired; 
    std::vector<result_type> m_samples; 
    mutable unsigned m_lastused; 
}; 

Это всегда кажется, дает гораздо лучшие результаты.