IT Services

Генерация псевдослучайных чисел на С и С++

B@R_LOG — Tue, 03 Dec 2013 20:43:43 GMT

Часто при начальном тестировании программы надоедает вводить разнообразные числа, чтобы проверить минимальную работоспособность программы.
Поэтому для тех, кто не любит заранее приготовлять юнит-тесты (или не знает, что это такое), я расскажу как быстро присваивать своим переменным случайные значения.

Из языка С нам известна функция int rand ( void ) из библиотеки , которая генерирует случайное число от 0 до RAD_MAX ( ~ 32767).

Пусть наше значение int value = 0;

Что нам нужно сделать, чтобы получить случайное число от 0 до 9?

value = rand( ) % 10;

А если мы хотим от 1 до 9?

value = rand( ) % 9 + 1;

Функция rand( ) генерирует последовательность значений, вычисляемую по специальному алгоритму, который зависит от "зерна" (seed), по умолчанию равного единице.

Поэтому последовательность всегда одинакова.

А что делать, если нам нужна уникальная последовательность значений при каждом присваивании?

Для этого воспользуемся void srand(unsigned int seed)

(эта функция то же из ), которая меняет "зерно".

srand( 3 ); value_1 = rand();

srand( 5 ); value_2 = rand();

Теперь value_1 не равно value_2.

Отлично! Теперь мы можем задавать огромное количество случайных последовательностей неравных друг другу, просто меняя значения зерна.

Ну а если я хочу, чтобы при повторном запуске программы все зёрна изменились?

Для этого воспользуемся функцией time_t time (time_t* timer) из , которая при вызове с нулевым указателем возвращает количество секунд прошедших с 1 января 1970 года.

srand( time(NULL) );

value_1 = rand(); /* теперь value_1 всегда разное */

srand( time(NULL) + 1);

value_2 = rand(); /* и value_1 всегда не равно value_2 */

Структуры данных: класс Stack

B@R_LOG — Mon, 02 Dec 2013 19:55:46 GMT

Стеком в программировании называется структура данных, где новый элемент всегда добавляется в конец массива и он же удаляется (извлекается) первым.

Логика стека хорошо характеризуется с помощью термина FILO (" последним пришёл, первым ушёл" ).

Таким образом самый первый элемент будет извлечён из стека самым последним.

Стек имеет свои ограничения:

1. Максимальный размер стека определяется изначально неким числом max_size. В течение существования объекта класса количество его элементов не может быть больше этого max_size.

2. Нельзя удалить элемент, если его нет. Поэтому перед удалением всегда надо проверять стек на наличие минимум одного элемента.

Ниже приведена реализация класса Stack с помощью шаблонов. Скачать исходники можно по ссылке ниже.

Скачать

Структуры данных: класс "Очередь"

B@R_LOG — Mon, 02 Dec 2013 15:49:51 GMT

Очередью в программировании называется структура данных, где новый элемент всегда добавляется в конец массива, а удаляется (извлекается) всегда первый.

FIFO ( First In, First Out - Первым прибыл, первым вышел) - сокращённое название очереди как алгоритма.

Очередь имеет свои ограничения:

1. Максимальный размер очереди определяется изначально неким числом max_size. В течение существования объекта класса количество его элементов не может быть больше этого max_size.

2. Нельзя удалить элемент, если его нет. Поэтому перед удалением всегда надо проверять, очередь на наличие минимум одного элемента.

3. Допустим есть массив из "4" элементов. Извлечём элемент. Получим что слева есть пустое место, но при этом добавить элемент справа напрямую мы не можем. То есть при max_size=4, очередь может содержать только три элемента ( а после повторного извлечения вообще только два).

Самым простым способом будет просто переместить после извлечения все элементы массива на одну ячейку влево. Причём это точно всегда будет работать. Но если у нас массив будет не из "4" элементов, а из 1 000 000, то от извлечения 50 000 элементов будет сильная потеря производительности, так как при каждый из 50 000 извлечений мы перемещаем примерно по 1 000 000 элементов массива.

Рассмотрим теперь алгоритм получше.

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

Как именно это выглядит? Представим очередь в магазин, в которой не очередь перемещается к продавцу ( дружно шагая всем составом), а продавец к очереди: то есть позиция начала очереди постоянно изменяясь стремится к концу очереди.

В таком случае следить нужно будет не только за концом очереди, но и за её началом. Как организовать круговую работу очереди?

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

Ниже приведена сложная реализация класса Queue с помощью шаблонов. Скачать исходники можно по ссылке ниже.

http://it-solutions.ucoz.ru/load/it/code_in_cpp/class_queue/10-1-0-4

Класс обыкновенных дробей Fraction

B@R_LOG — Tue, 19 Nov 2013 06:56:46 GMT

Часто студентам дают задание реализовать класс обыкновенных дробей Fraction на языке С++ с помощью ООП.

Поэтому сегодня я покажу как должно выглядеть решение этой задачи.

Пример выполнения программы:

Мой преподаватель не нашёл данных и операций, с которыми этот класс не работает, но небольшой сюрприз я решил вам оставить:

В этой функции уже при x=24 у вас будет неправильный результат. Почему?

Потому что в результате переполнения вы получаете неправильные данные.

double_max = 9 223 372 036 854 775 807

int_max = 2 147 483 647

Везде по разному, но различие в порядках значений очевидно.

Поэтому в строчке 29, если выражение (value_1 - value_2) не умещается в int, то получим переполнение -> неправильный числитель.

Наилучшим решением будет переписать алгоритм так, чтобы он, в зависимости от "x", умножал на 10 в нужной степени, а не с запасом, как здесь.

Блок CONTROL_INPUT описан здесь.

Остальное всё просто, поэтому если возникнут вопросы - пишите их в комментарии.

Скачать

Преобразования типа в C++:

B@R_LOG — Mon, 18 Nov 2013 02:14:07 GMT

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

Поэтому сегодня я расскажу о новых операторах приведения, которые позволяют более строго оформлять свои мысли и чётче их формулировать.

/*********************************************************************************************

**********************************************************************************************

*********************************************************************************************/

Первый: const_cast < type > ( return_value )

/* Позволяет добавлять или удалять квалификаторы типов "const" и "volatile" из типов выражения.

const Person* getName() { /* тело функции */ }

Person* anName = const_cast < Person* > ( getName() );

/* "const_cast" аннулировал "const" в типе значения, возвращаемого функцией getName() */

Эквивалентно худшему варианту:

anName = ( Person* ) getName();

Плюсы "const_cast":

1) Он бросается в глаза, поэтому видно, что было преобразование типа.

2) Если будет изменение функции getName из const Person* getName() в const Name* getName(), то компилятор сообщит об этом, так как возможности "const_cast" ограничены.

/*********************************************************************************************

**********************************************************************************************

*********************************************************************************************/

Второй: static_cast < type > ( return_value )

/* Применяется для переносимых на разные платформы приведений. Чаще всего служит для приведения "вниз" по иерархии наследования от указателя (или ссылки) на базовый класс к указателю (или ссылке) на производный класс. */

Shape* sp = new Circle;

Circle* cp = static_cast < Circle* > ( sp );

/* Компилируется, потому что "sp" действительно ссылается на объект "Circle".

Но если бы "sp" указывал на какой-нибудь другой тип "Rectangle", то при использовании "cp" получил бы, скорее всего, ошибку. */

Вывод: static_cast не меняет квалификаторы типа так, как это может const_cast

const Shape* getShape() { /* тело функции */ }

Circle* cp = static_cast < Circle* > ( const_cast

/*********************************************************************************************

**********************************************************************************************

*********************************************************************************************/

Третий: reintepret_cast < type > ( type2 );

/* Обычно работает с битами объекта и позволяет осуществлять преобразования между совершенно несвязными типами. */

HP = reinterpret_cast < char* > ( 0x0f0... ) /* преобразует целое в указатель */

/* теперь будем преобразовывать char* в int* */

int* PW = reinterpret_cast < int* > ( HP );

Выводы:

1) Такие преобразования в коде низкого уровня не являются непереносимыми.

2) reinterpret_cast обычно считает, что указатель на базовый класс является указателем на производный класс и не меняет его значение. А static_cast осуществляет правильную работу с адресами.

/*********************************************************************************************

**********************************************************************************************

*********************************************************************************************/

Четвёртый: dynamic_cast

/* Обычно применяется для безопасного нисходящего приведения от указателя на базовый класс к указателю на производный класс.

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

Правильность приведения проверяется во время выполнения. И если у statc_cast издержки времени минимальны, то dynamic_cast предполагает более существенные издержки времени выполнения.

const Circle* cp = dynamic_cast < const Circle* > ( getShape() );

/* Если getShape возвращает указатель на Circle (или какой-то наследуемый от Circle класс), то приведение будет успешным и cp будет указывать на Circle. Иначе cp будет нулевым.

Удобно в if ( ) { /* */} поместить объявление "const Circle* ... ". Тогда cp, когда в нём исчезнет необходимость, сам уйдёт из области видимости.

const Circle& rc = dynamic_cast < const Circle& > ( *getShape( ) );

/*Приведение аналогично,но вместо возврата нулевого указателя формирует исключение std::bad_cast */

Применение dynamic_cast к указателю это вопрос:

"Этот указатель на Shape фактически указывает на Circle? Если нет, я могу заняться этим!"

Применение dynamic_cast к ссылке это утверждение:

"Предполагается, что этот Shape есть не что иное, как Circle. Если это не так, значит что-то не в порядке!"

Контроль ввода в C и С++:

B@R_LOG — Mon, 18 Nov 2013 00:50:34 GMT

Я думаю многие начинающие программисты С/C++ хотели, чтобы при запросе о вводе целого числа пользователь мог ввести только его, а никак не double или char, который преобразовывается в int.

Сегодня я опишу как это сделать.

#include using namespace std;

/* Функция, восстанавливающая поток ввода в случае ошибки.*/

void skip_to_int()

{

if (cin.fail() )

{

cin.clear();

char ch;

while ( cin >> ch && !( isdigit(ch) ) );

if (!cin) cerr << ("Is not input");

cin.unget();

}

/* Собственно это и есть вызываемая функция, не позволяющая ввести значение другого типа.

Например, если хотим ввести значение типа bool, то пишем:
bool value = -1;

value = the_contol_input

И ввод будет продолжаться до тех пор, пока не введём 0 или 1.*/

template /* напомню, что для шаблонных функций нет разделения на ".cpp" и ".h". */

Type the_control_input()

{

Type n=0;

while (true)

{

if (cin >> n) return n; /* если введённое значение не принадлежит типу Type - идём дальше.*/

cout << "It is not number. Repeat input!\n";

skip_to_int();

}

А теперь поговорим о работе с функциями из файла

Поток - это последовательность символов, к которым возможен только последовательный доступ. Извлечённый символ удаляется из потока.

Если из потока прочитаны не все символы до конца строки ( символ "\n") включительно, то после операции чтения поток не будет пустым.

int istream :: get() - извлекает из входного потока один символ и возвращает его int-код

Пример её неправильной работы:

cout << cin.get(); /* набираем abcd и жмём enter */

cout << cin.get(); /* программа, вместо того, чтобы ждать 2ого пользовательского ввода прочитает символ 'b' */

istream& istream :: ignore (streamsize n=1, int delim=EOF)

Извлекает из потока символы и отбрасывает их. Причём поступает так либо с "n" символами, либо со всеми символами, предшествующими символу заданному параметром "delim".

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

Обращение к нему через streambuf* istream::rdbuf() const;

Количество символов в нём равно streamsize streambuf::in_avail();

Пример их использования:

cin.ignore ( cin.rdbuf()->in_avail() );

void ios::clear (iostate state = goodbit);

Восстанавливает поток (если он оказался в ошибочном состоянии), делая его работоспособным.

Например, при попытке прочитать число, когда в потоке были буквы, поток переводится в состояние отказа и с ним нельзя работать (с помощью того же cin.get(); )