вы должны делать:

асть назначения основана на массиве (его размер задается пользователем), который содержит случайные числа от 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 - это очень большое значение, и я сделал что-то еще, чтобы заполнить массив случайными числами. Это правильно? Есть ли что-то еще, что я мог сделать? И моя вторая проблема - алгоритм поиска. Не работает Может ли кто-нибудь помочь мне с этим? большое спасибо

 Keith Irwin15 янв. 2011 г., 18:09
Вы действительно должны использовать rand () * rand (). Это не имеет равномерного распределения.
 Benjamin Lindley15 янв. 2011 г., 18:11
@ Киет, ты имеешь в виду, не так ли?
 Tim15 янв. 2011 г., 18:26
Мы действительно не должны делать домашнее задание для какого-то ребенка, особенно когда он слишком ленив, чтобы попытаться скомпилировать его.
 Alin Purcaru15 янв. 2011 г., 18:51
@Tim Большинство моих бывших школьных коллег компилировали свой код только после того, как закончили с его написанием (большинство из них только тогда сохраняли ...). Я думаю, что это общая черта людей, которые только начали изучать программирование. Однако это не делает его ленивым. Как вы можете видеть, он дал ему шанс и пришел сюда с некоторым вопросом относительноего код. Другое дело, что обычно, если человек идентифицирует свой код как домашнее задание, люди, отвечающие на него, только дают ему подсказки, чтобы никто не делал его домашнюю работу.
 Tim15 янв. 2011 г., 19:15
@ Алин. Я в порядке, помогая тем, кто застрял на домашнем задании - я просто хочу подчеркнуть, что мы не должны давать ответ. Я думаю, что публикация «Вот моя ошибка компиляции, но я ее не понимаю» совершенно верна. Однако pr_prog84 просто опубликовал свой код и сказал, что «это не работает». Это красный флаг для меня.

Ответы на вопрос(6)

Вы забыли свои ответные заявления. в конце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);
}

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

Кроме того, целое число обычно составляет 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.

 Oliver Charlesworth15 янв. 2011 г., 18:44
Я не уверен, что это уменьшает случайность ...
 pr_prog8415 янв. 2011 г., 18:30
Спасибо Тим за твой ответ. Я пытался весь день найти то, что пошло не так, как найти ..
 Ben Voigt15 янв. 2011 г., 18:22
Сдвиг битов и объединение частей в OR будет намного эффективнее, чем сложение случайных чисел, а также даст гораздо более линейное распределение. Добавление их вместе дает нормальное распределение.
 Ben Voigt15 янв. 2011 г., 19:11
@ Алин: опасно предполагать, что мое понимание неверно. Два момента: (1) комментарий слишком мал, чтобы объяснить более слабые и сильные центральные предельные теоремы, и (2) это целые числа, так что да, это только приближение нормального распределения, но не потому, что у нас есть конечные аддитивные члены, а скорее потому, что это дискретное распределение, а нормальное непрерывное. С участиемN = 10**10 / RAND_MAXЭто несколько миллионов, и я чувствую себя вполне уверенно, утверждая, что полученное распределение настолько близко к нормальному, насколько это возможно для целых чисел в этом диапазоне.
 pr_prog8415 янв. 2011 г., 18:16
Спасибо большое peoro!

как вы думаете, и меняет распределение. по факту

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

(Если вы находитесь в классе на уровне простого запроса на создание массива случайных чисел, и вы сдадите их, они, вероятно, вас подведут) На практике я объединяю два подхода. Это используется вместо линейного последовательного rng, использованного выше (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;
};

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

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

Что касаетсяrandom()*random(), этоточный темаэтот другой вопрос.

Алинь

 Ben Voigt15 янв. 2011 г., 18:27
Это будет сделано за 10 шагов, используя двоичные цифры (7 бит за раз), это можно сделать за 5.
 Alin Purcaru15 янв. 2011 г., 18:41
@Ben Voigt Я не знаком с C или C ++, поэтому не могу высказать свое мнение о вашем решении. Все, что я могу сказать, это то, что я опубликовал общий алгоритмический подход, который можно использовать аналогичным образом в большинстве языков программирования, и он легко поддерживает более широкие диапазоны (скажем, от 1 до 10 ^ 100).

int будет содержать только число размером 2 ^ 31. Вам понадобится немного большая альтернатива для вашего набора выводов.

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

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

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;
}
 pr_prog8415 янв. 2011 г., 18:33
благодарю вас!!!! так много
 Oliver Charlesworth15 янв. 2011 г., 18:52
+1: это лучший ответ на данный момент. Предположительно, вы могли бы генерировать больше битов за раз, если были уверены в значенииRAND_MAX.
 Ben Voigt15 янв. 2011 г., 19:16
@ Оли: точно. Требуется 34 бита, которые могут быть 5 шагов по 7 каждый, 4 шага по 9 каждый или 3 шага по 12 каждый, так как наиболее распространенное значение реального мираRAND_MAX вероятно 215-1. Похоже на стандартные гарантии минимум 215-1, я обновлю свой ответ.

Ваш ответ на вопрос