Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > Массив из диапозона чисел

Автор: JAYBE 11.1.2013, 10:16

Добрый день!
Помогите, пожалуйста, с задачей: Задан числовой массив А[1:m, 1:n]. Составить программу поиска элемента массива, который является наибольшим из отрицательных чисел расположенных в строках.
Мой код:

Код


#include <iostream>
#include <stdlib.h>
using namespace std;

int main()
{
    int m, n, start_random, end_random, min, rnd;
    cout << "Enter length of array: ";
    cin >> m;
    cout << "Enter height of array: ";
    cin >> n;
    int array[m][n];
    srand(time(0));
    cout << "Enter start of random:";
    cin >> start_random;
    start_random+=1;
    cout << "Enter start of random:";
    cin >> end_random;
    end_random-=start_random;
    cout << "Sgenerirovanniy massiv:\n";
    for (int i=0; i<m; i++) {
        for (int y=0; y<n; y++) {
            cout << (array[i][y] = rand()%11-5) << ' ';
            //cout << rand()%10-5 << ' ';
        }
        cout << endl;
    }
    min = array[0][0];
    for (int i=0; i<m; i++) {
        for (int y=0; y<n; y++) {
            if (min>array[i][y]) {
                min = array[i][y];
            }
        }
    }
    cout << "Minimalnoe chilslo: " << min << endl;
    return 0;
}

Возникает 2 вопроса.
1) Как сделать рандомный массив из дапозона, причем

Код


array[i][y] = rand()%start_random-end_random/start_random

работает некорректно... Скажем если необходим диапозон от -10 до 15.
2) У меня циклы 2 раза "пробегают". 1 раз при создании массив и 2-ой раз при поиске минимального элемента. Как-то можно их оптимизировать с точки зрения алгоритма в один?

Автор: bsa 11.1.2013, 10:38

Цитата(JAYBE @ 11.1.2013, 11:16

)

Как сделать рандомный массив из дапозона

легко: x ∈ [-10;15] -> y ∈ [0;25], где x = (y - 10) -> y = random * 25 / RAND_MAX, где random ∈ [0;RAND_MAX]:
y = (int)(25 * (rand()/(double)RAND_MAX) + 0.5);
x = y - 10;

Автор: feodorv 11.1.2013, 11:29

Цитата(JAYBE @ 11.1.2013, 11:16

)

Как-то можно их оптимизировать с точки зрения алгоритма в один?

Можно, но смысла особого не имеет. Это две разные подзадачи:

инициализация элементов массива
поиск особого элемента в матрице

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

Тем не менее, задача стоит как

Цитата(JAYBE @ 11.1.2013, 11:16

)

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

В связи с чем возникает несколько вопросов:

"наибольшее из отрицательных чисел" - имеется в виду по модулю (-10 > -2) или по значению (-10 < -2)
почему подчёркивается "расположенных в строках"? Не следует ли для каждой строки выполнить поиск такого наибольшего значения и вывести его вместе с координатами в массиве?
что делать, если отрицательных значений в матрице (строке) нет? Не следует ли так и сообщить пользователю: "В матрице отсутствуют элементы с отрицательными значениями"...
нужно ли вывести на экран всю матрицу целиком, чтобы потом понять, правильно ли осуществлён поиск?

Автор: bsa 11.1.2013, 14:04

Цитата(JAYBE @ 11.1.2013, 11:16

)

У меня циклы 2 раза "пробегают". 1 раз при создании массив и 2-ой раз при поиске минимального элемента. Как-то можно их оптимизировать с точки зрения алгоритма в один?

конечно можно. посмотри на циклы - они имеют много общего. smile

Автор: JAYBE 11.1.2013, 22:40

А как сделать переход к следующему шагу в цикле, есть какой-либо аналог continue в js.
Тоесть так можно было бы:

Код


min = array[0][0] = array[i][y] = rand()%11-5;
    for (int i=0; i<m; i++) {
        for (int y=0; y<n; y++) {
 if ( i==0 && y==0 ) continue
            cout << (array[i][y] = rand()%11-5) << ' ';
            if (min>array[i][y]) {
                min = array[i][y];
            } ';
        }
        cout << endl;
    }
cout << min << endl;

Автор: IValdemar 11.1.2013, 23:11

JAYBE,
continue в C и C++ есть smile

Код


if ( i==0 && y==0 ) continue;

Добавлено через 6 минут и 6 секунд

Цитата(JAYBE @ 11.1.2013, 22:40

)

cout << (array[i][y] = rand()%11-5) << ' ';

вот так он выведет 1, или что-то вроде этого, если надо вывести array[i][y] тогда так:

Код


array[i][y]  = rand()%11-5;
cout<< array[i][y] <<' ';

Автор: volatile 12.1.2013, 00:24

Цитата(IValdemar @ 11.1.2013, 23:11

)

cout << (array[i][y] = rand()%11-5) << ' ';
вот так он выведет 1, или что-то вроде этого, если надо вывести array[i][y] тогда так

Нормально выведет. Код идентичен.

Автор: feodorv 12.1.2013, 00:41

Цитата(JAYBE @ 11.1.2013, 23:40

)

min = array[0][0] = array[i][y] = rand()%11-5;

А зачем здесь array[i][y]? i и y инициализированы корректно?

Автор: IValdemar 13.1.2013, 00:28

volatile, хм действительно правильно выводит. Не знал, что так можно.

Это потому что результатом операции

Код


(array[i][y] = rand()%11-5)

является элемент array[i][y]?

Автор: volatile 13.1.2013, 23:11

IValdemar, в данном случае мы имеем оператор присваивания.
Стандартная сигнатура этого оператора:

Код


type & operator = (const type &);

как видите он возвращает ссылку на объект, которому присваиваецца значение.

Код


cout << (array[i][y] = rand()%11-5)

здесь произодицца присваивание array[i][y] случайного значения, и затем возвращаецца ссылка на array[i][y], значение которой и выводицца в стандартный вывод.

---
Очевидно, что вы перепутали с оператором сравнения:

Код


bool operator == (const type &);

Вот он, как раз возвращает булеву переменную, как вы и описали.

Цитата(IValdemar @ 11.1.2013, 23:11

)

вот так он выведет 1, или что-то вроде этого,

В языке С/С++ оператор=, и оператор==, это два разных оператора.
Не нужно их путать.

Автор: JAYBE 14.1.2013, 10:04

Спасибо. Так и не понял bsa про объяснение рандомных чисел - сделал сам. Оставил двойной проход по массиву, по учебной задаче наврное не стоит заморачиваться так с опимизацией выполнения кода.
В итоге оставил так:

Код


#include <iostream>
#include <stdlib.h>
using namespace std;

int main()
{
    int m, n, start_random, end_random, min, rnd;
    cout << "Enter length of array: ";
    cin >> m;
    cout << "Enter height of array: ";
    cin >> n;
    int array[m][n];
    srand(time(0));
    cout << "Enter start of random:";
    cin >> start_random;
    start_random;
    cout << "Enter end of random:";
    cin >> end_random;
    end_random+=1;
    cout << "Sgenerirovanniy massiv:\n";
    for (int i=0; i<m; i++) {
        for (int y=0; y<n; y++) {
            if (start_random>=0) {
                rnd = start_random + rand()%(end_random-abs(start_random));
            } else {
                rnd = start_random+rand()%(end_random+abs(start_random));
            }
            cout << (array[i][y] = rnd) << ' ';
        }
        cout << endl;
    }
    min = array[0][0];
    for (int i=0; i<m; i++) {
        for (int y=0; y<n; y++) {
            if (min>array[i][y]) {
                min = array[i][y];
            }
        }
    }
    cout << "Minimalnoe chilslo: " << min << endl;
    return 0;
}

Автор: bsa 14.1.2013, 15:35

JAYBE, а что там непонятного? rand() возвращает значения от 0 для RAND_MAX включительно. Тебе же нужно от -10 до 15. Можно вынести -10 за скобку и получить от 0 до 25 включительно. Теперь нужно как-то RAND_MAX превратить в 25. Как это сделать? да очень просто - раздели результат rand() на double(RAND_MAX) (double необходим, чтобы деление было нецелочисленным) и получишь значения в диапазоне от 0 до 1 включительно. Теперь умножаешь на 25 и получаешь от 0 до 25. Осталось только вспомнить о -10. Правда, есть одна особенность, связанная с преобразованиями из double в int - при этом число округляется к ближайшему меньшему целому. Т.е. число 24.999999999999 округлится к 24. Чтобы этого избежать нужно добавить 0.5. Вот итоговая формула:

Код

r = int(25 * (rand() / double(RAND_MAX)) + 0.5) - 10;

Автор: volatile 14.1.2013, 16:55

Цитата(bsa @ 14.1.2013, 15:35

)

Т.е. число 24.999999999999 округлится к 24. Чтобы этого избежать нужно добавить 0.5.

bsa, в данном случае лучше не прибавлять 0,5
иначе вероятность выпадения числа 0 и 25 будет в 2 раза меньше чем остальных (1...24)

Если нужен диапазон от 0 до 25 включительно, лучше умножать на 26, и ничего не прибавлять.

Добавлено через 8 минут и 32 секунды
r = rand() % 26 - 10;

Автор: bsa 14.1.2013, 20:02

Цитата(volatile @ 14.1.2013, 17:55

)

r = rand() % 26 - 10;

в этом случае распределение неравномерно, так как RAND_MAX не делится на 26

Цитата(volatile @ 14.1.2013, 17:55

)

bsa, в данном случае лучше не прибавлять 0,5
иначе вероятность выпадения числа 0 и 25 будет в 2 раза меньше чем остальных (1...24)

Если нужен диапазон от 0 до 25 включительно, лучше умножать на 26, и ничего не прибавлять.

а что будет в случае если rand вернет RAND_MAX? Ты уверен, что будет 24.9999999999, а не 25.00000000001? Я нет.

Я вспомнил правильную формулу.

Код

r = int(rand() / (RAND_MAX + 1.0) * N); //r будет в диапазоне [0;N)

Я для ТС она будет выглядеть так:

Код

r = int(rand() / (RAND_MAX + 1.0) * 26) - 10;

Автор: volatile 14.1.2013, 23:27

Цитата(bsa @ 14.1.2013, 20:02

)

этом случае распределение неравномерно, так как RAND_MAX не делится на 26

Согласен, строго говоря, там будет незначительная неравномерность.
Но этой неравномерностью, в большинстве случаев можно спокойно пренебречь.

Цитата(bsa @ 14.1.2013, 20:02

)

Я вспомнил правильную формулу.
r = int(rand() / (RAND_MAX + 1.0) * N); //r будет в диапазоне [0;N)

Эта формула, лишь длиннее, но ничем не лучше.
Неравномерность там будет точно такая-же. smile

Могу показать, если пожелаете. Но думаю вы сами поймете, если задумаетесь.
кстати, именно потому, что

Цитата(bsa @ 14.1.2013, 20:02

)

RAND_MAX не делится на 26

Если уж нужна абсолютная равномерность, то надо делать так:

Код


// Получение равномерного числа в диапазоне [0..n)
int uniform_rnd (int n)
{
   int bound = RAND_MAX - RAND_MAX % n;
   int r;
   while ((r = rand ()) >= bound)
      ;
   return r % n;
}

Автор: volatile 14.1.2013, 23:51

неравномерность = есть отношение выпадений самого вероятного к самому маловероятному.

Автор: NoviceF 15.1.2013, 09:09

Цитата(volatile @ 14.1.2013, 17:55

)

r = rand() % 26 - 10;

Поясните, пожалуйста, тут же ранд может вернуть 26? Что происходит в этом случае (по условию же максимум нужно 25)?

Автор: bsa 15.1.2013, 09:35

NoviceF, что является результатом оператора % ?

Автор: NoviceF 15.1.2013, 09:46

Цитата(bsa @ 15.1.2013, 10:35)

NoviceF, что является результатом оператора % ?

Остаток от деления того, что слева, на то, что справа.

Если ранд вернёт число кратное 26, то результатом будет 0, в остальных случаях остаток будет в диапазоне от 1 до 25, так? )

Автор: bsa 15.1.2013, 10:08

Цитата(NoviceF @ 15.1.2013, 10:46

)

так?

да
Тогда в чем был смысл предыдущего вопроса?
volatile, ты был прав. Равномерность примерно одинаковая, что для варианта с остатком от деления, что с умножением (примерно, 99.6% и 99.7% соответственно на N*1000000 опытах).

Код

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>

#define N 26

int norm1(int max)
{
        return max * (rand() / (RAND_MAX + 1.0)); //можно использовать и целочисленный вариант, но так надежней
}

int norm2(int max)
{
        return rand() % max;
}

int main()
{
        int array[N];
        long long i;
        for(i = 0; i < N; ++i)
                array[i] = 0;
        //srand(time(NULL)); //закомментировано для точной воспроизводимости результатов
        for(i = N*1000000ll; i; --i) {
                int r = norm2(N);
                assert((r < N) && (r >= 0));
                ++array[r];
        }
        int min = array[0], max = array[0];
        for(i = 0; i < N; ++i) {
                printf("%d - %d\n", (int)i, array[i]);
                if (array[i] < min)
                        min = array[i];
                if (array[i] > max)
                        max = array[i];
        }
        printf("d = %.2f%%\n", (double)min/max*100);
        return 0;
}

Автор: volatile 15.1.2013, 23:23

bsa, уважаю! smile

Цитата(bsa @ 15.1.2013, 10:08

)

примерно, 99.6% и 99.7%

Фактически неравномерность у них меньше, здесь все забивает системный rand.
Там и uniform_rnd() показывает такую-же неравномерность, а должен быть идеальным.
по моим подсчетам неравномерность при N=26, для обоих методов составляет: =99.9207%
для uniform_rnd: =100.0000%
я эти числа получил просто счетчиком пройдя весь диапазон от 0 до RAND_MAX, и посмотрел что на выходе.

Но можно пойти и другим путем, испоьзуя вашу программу.
Чтобы обострить неравномерность, будем генерить числа соизмеримые с RAND_MAX,
при этом неравномерность резко возрастает, и становицца видна невооруженным глазом, даже сквозь системный rand().

Итак, на вашей программе, для:
N = int(0.55*RAND_MAX); и при количестве циклов 100*1000000ll
результаты, такие:

Код


norm1 = 44.68%
norm2 = 44.92%
norm3 = 90.18% (он же uniform_rnd)

---
при увеличении опытов norm1,norm2 стремяцца к ==> 50%; uniform_rnd ==> 100%

Резюме. при маленьком N, все замечательно и вообще по барабану какую формулу использовать.
При больших N, простые формулы дают очень плохую картину. Вероятность выпадения макс/мин в 2 раза, уже нельзя назвать ГСЧ.
и нужно использовать генератор с отбрасыванием, такой как uniform_rnd();