Разбор лаб по программированию. Семестр 2. Часть первая

Изменено: . Разместил: FadeDemon | Меню
Количество просмотров7`131 / FD1682-6-0

Итак, начало второго семестра уже совсем близко. Конечно, все мы относимся к нему по разному, кто-то его с нетерпением ждёт, а кто-то воспринимает 11 февраля как судный день, но это, впрочем, не важно. В один прекрасный день, когда мои туманные мысли ещё не вполне отошли от сонного состояния, случайно наткнулся я на задания к лабораторным работам по программированию, которые ждали нас в этом семестре, и всего через одну минуту цель была четко осознана: сделать все 12 лаб. До начала учёбы. Во что бы то ни стало.


Надо сказать, что сложность заданий не сильно увеличилась по сравнению с первым семестром, я почему-то ожидал более заковыристых вещей, хотя в некоторых заданиях уже всё-таки нужно подключать такую вещь, как мозг. Впрочем, после включения и прогрева оного, всё пошло на автомате. Итак. Сейчас мы представим вашему вниманию разбор первых 6 лаб из 12. Выключаем свет, усаживаемся по удобнее, 3, 2, 1 и… шоу начинается…


Продолжительность 06:01    Битрейт 320 кбит/с    Шоу начинается...

Лаба первая. Функции. Использование функций в языке Си.


Самая ниочёмная лаба во всём цикле. Задания совершенно скучные и неинтересные, насчёт сложности я вообще воздержусь от комментариев. Теорию опустим, я думаю это должны знать все. Правда кое-что тут интересное есть, но больше с точки зрения математики, а не программирования на Си. Впрочем, перейдём к заданиям:


1. Написать функцию вычисления косинуса с помощью ряда Тейлора с заданной точностью.

К заданию также прилагается формула ряда Маклорена для косинуса. Так. Формула это конечно хорошо, но давайте для начала вспомним, откуда эта формула вообще взялась. Вернёмся к тому, от чего всё начиналось, к теореме Тейлора, которая прозрачно намекает, что любую аналитическую функцию f(x), у которой существует n производных, можно в точке a представить в виде вот такого многочлена:


\[ f(x) = f(a) + \sum_{k=1}^n {f^{(k)}(a) \over k! }(x - a)^k\]
Формула Тейлора

Если точка a выбрана равной нулю, то ряд возникающий в формуле обзывают ещё рядом Маклорена, и именно в такой ряд нам надо разложить сейчас косинус.


Вспомним, что производная косинуса равна синусу со знаком минус, а производная синуса — косинусу, со знаком плюс, из чего можно сделать вывод, что вторая производная косинуса, есть тот же косинус, только со знаком минус. Продолжая это рассуждение, нетрудно заметить, что четвертая производная внезапно становится равна тому-же косинусу, и история повторяется. То-есть, 4-я производная косинуса равна 8-й, 12-й, и т.д. его производным, и вдобавок, ещё и самому косинусу. Попытаемся всё это теперь подставить в формулу Тейлора:


\begin{aligned} & cos(x) = cos(a) + {-sin(a) \over 1!}(x - a)^1 + {-cos(a) \over 2!}(x - a)^2 + {sin(a) \over 3!}(x - a)^3 + \\ & + {cos(a) \over 4!}(x - a)^4 + \mathellipsis \end{aligned}


Отлично. Теперь вспомним, что a мы изначально полагаем равное нулю, а это, как можно сразу заметить, всё значительно упрощает… Значения для функции, и первых 3-х её производных в точке 0, распределяются как 1, 0, −1, 0, и на последующих производных зацикливаются, а это говорит о том, что нечётные члены в ряду, где производная превращается в ноль, сразу-же выпиливаются, и соответственно, после небольшой обработки напильником, формула, очевидным образом, приобретает желаемый вид:


\[ cos(x) = 1 - {x^2 \over 2!} + {x^4 \over 4!} - {x^6 \over 6!} + \mathellipsis = 1 - \sum_{k=1}^\infty (-1)^k \cdot {x^{2k} \over (2k)!} \]
Ряд Маклорена косинуса

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


Прежде чем переходить к кодописательству, неплохо было бы еще выяснить такую вещь, как область сходимости нашей формулы, и первое, что тут пришло мне в голову, это взять, и просто попросить Wolfram Alpha нарисовать нам график интересующего нас разложения, ну а он, в свою очередь просто не смог мне в этом отказать:


Наглядное представление ряда Тейлора для косинуса
Рис. №857. Наглядное представление ряда Тейлора для косинуса

Ведь мы же хотим получить универсальную функцию, которая будет безотказно работать в самых что ни наесть боевых условиях, правда? Из картинки выше можно сделать 2 вывода:

   1. Наш ряд сходится на всей числовой прямой, судя по converged everywhere
   2. Лучше всего ряд сходится в окрестности точки a, то-есть нуля, хотя это, вообще говоря должно быть очевидно и без всякой картинки. Чем дальше, другим словом, мы уходим от нашей точки, тем больше надо итераций, чтобы ряд сошелся более-менее точно.

Поскольку косинус — функция периодическая, то-есть верно что-то вроде этого:


\[ cos(x) = cos(x \pm 2\pi k), k \in \mathbb Z \]


нам, как не трудно понять, достаточно будет того, чтобы ряд нормально сходился на промежутке (−2π … 2π), а из входного аргумента просто вычитать лишние до тех пор, пока он не похудеет до нужных размеров.


Ну вот, теперь, когда мы знаем о косинусе уже достаточно, можно, наконец, перейти к написанию долгожданного кода. Здесь мы приведём только саму функцию, полные исходники этой, и последующих лаб можно скачать по ссылке в самом конце статьи. Итак, вот что представляет собой наш замечательный рукотворный косинус:


Код: C++
//требуемая точность для ряда Тейлора
const double EPSILON = 0.0001;

//считаем косинус через ряд Тейлора
//вычисление прерываем тогда, когда очередной
//член ряда становится меньше требуемой точности по модулю
double cos_taylor(double x){
    //для начала неплохо было бы ограничить аргумент, поскольку
    //хоть ряд Тейлора для косинуса сходится и абсолютно везде,
    //но как нетрудно догадаться, для промежутка -2пи .. 2пи
    //посчитать его можно будет за значительно меньшее количество итераций
    //а еще надо помнить, что факториал сдохнет где-то на 18-й итерации...
    
    //ежли не в промежутке между -2пи .. 2пи
    if(x > M_PI * 2){
        //попахивает легким извращением
        x -= M_PI * 2 * floor(x / (M_PI * 2));
    }else if(x < -M_PI * 2){
        //зато без цикла, все лучше же
        x += M_PI * 2 * floor(fabs(x) / (M_PI * 2));
    }
    
    double r = 1, m = 0;
    long i = 2;
    
    do{
        //вообще это не очень изящно, хоть и довольно наглядно
        //для повышения производительности от функций этих стоит отказаться
        m = pow_cycled(x, i) / fact(i);
        
        //но за производительностью тут мы пока не гонимся...
        if(0 == (i / 2) % 2){
            r += m;
        }else{
            r -= m;
        }
        
        //шагаем на 2
        i += 2;
    }while(fabs(m) > EPSILON);
    
    //возвращаем пользу
    return r;
}

Некоторые вещи надо бы прояснить: pow_cycled — это, забегая вперед, реализация второго задания, то-есть своей функции pow, а fact — ничем непримечательная функция факториала, которую все мы с вами сможем написать за две минуты. Впрочем, в полной версии кода есть всё. Требуемая точность вычислений тут вынесена в константу EPSILON, как нетрудно заметить.


Код делает две простые вещи: ограничивает входной аргумент, избавляя его от лишних , и в цикле прибавляет (или вычитает) очередной член ряда к результату, до тех пор, пока этот член по модулю не станет меньше требуемой точности. Тут ещё надо помнить, что факториал, в силу переполнения подохнет где-то на 18-19 итерации, и поэтому циклу надо бы укладываться примерно в этом промежутке, но наш цикл молодец, и как показали замеры, укладывается максимум где-то на 14-й итерации, так что, бояться в общем-то, пока нечего.


Посмотрим-же, наконец, на результаты своего умственного труда:


Как работает наш косинус
Рис. №858. Как работает наш косинус

Здесь представлены результаты работы нашей функции косинуса, и встроенной, для разных значений X, в первой колонке — значения в известных точках: 0, π, π / 2, 3 * π / 2, скриншот немного откорректирован фотошопом. Как мы можем заметить, всё работает идеально, для абсолютно любых чисел. Даже придраться не к чему, точность везде соблюдается. На этой мажорной ноте, первое задание можно считать выполненным. Вздыхаем с облегчением, и…


2. Написать функцию возведения в степень y=xⁿ, где n – целое положительное или отрицательное число; x –  вещественное число. Использовать цикл.

Ну, здесь всё значительно проще. Единственное, что надо вспомнить, это что:


\[ x^{-n} = {1 \over {x^n}} \]


но, я думаю что это помнят все. Обойдёмся, в общем, без россказней и разъяснений:


Код: C++
//возводим x в степень n
double pow_cycled(double x, signed long n){
    //если ноль, то думать не нужно
    if(0 == n){
        return 1;
    }
    
    //тут думать - тоже не нужно
    long i, n2;
    double r = x;
    
    //один икс уже есть
    n2 = abs(n) - 1;
    for(i = 0; i < n2; i++){
        r *= x;
    }
    //минус или не минус?
    return n < 0 ? 1.0 / r : r;
}

Смысл прост, и понятен: берем x, умножаем его на себя |n| − 1 раз, и если вдруг n была меньше нуля, делим единицу на то что получилось. Результат и возвращаем. Ну, если n = 0, то просто возвращаем единицу. Проще не придумаешь. Результат:


Функция возведения в степень
Рис. №859. Функция возведения в степень

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


Лаба вторая. Рекурсия. Изучение методов программирования рекурсивных алгоритмов в языке Си.


Рекурсия, это весело. Рекурсия, это когда функция вызывает сама себя, и это всё что нам надо знать о рекурсии. Если вызывать она себя будет без ограничений, то во мгновение ока мы поймаем ошибку вида stack overflow, из-за, собственно, переполнения стека, и поэтому, рекурсию надо чем-то ограничивать. Рекурсия, вообще, применяется много-где, но в основном для обхода всяких древовидных структур, например — в файловой системе. Пример с числами Фибоначчи, приведённый в методичке, хоть и верный, и довольно сносный, но тем не менее, иллюстрирует, как рекурсию применять не надо. Это-же иллюстрирует второе задание, но об этом позже. Разберёмся с первым:


1. Вычислить z = ab + cb, используя рекурсивную функцию xn

Весь лулз заключается в том, что вместе с заданием приводиться ещё и описание функции, которую собственно говоря надо реализовать:


\[ x^n = \left\lbrace \begin{aligned} & 1, & n = 0 \\ & {1 \over x^{-n}}, & n < 0 \\ & {x \cdot x^{n - 1}}, & n > 0 \\ \end{aligned} \right . \]
Рекурсивное возведение в степень

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


Код: C++
//возводим x в степень n, но уже по извращенному)
double pow_recur(double x, signed long n){

    if(0 == n){
        //если ноль, то думать не нужно
        return 1.0;
    }else if(n < 0){
        //если минус, мы от него избавляемся
        return 1.0 / pow_recur(x, -n);
    }else if(n > 0){
        //если плюс, избавляемся от едынички
        return x * pow_recur(x, n - 1);
    }
}

Как и ожидалось, функция работает абсолютно точно так же, как и такая-же функция из предыдущей лабы, поэтому обойдёмся без скриншота, просто поверьте на слово. Как она работает, вроде очевидно: если x = 0, возвращаем 1, если x < 0, то сразу делим 1 на x|n| (причем вызываем нашу-же функцию для подсчёта, и получается таки рекурсия), ну а если x > 0, то снова вызываем себя-же, но с n на единичку меньше, и результат умножаем на x. Получается, в общем, этакая извращённая версия того, что мы придумали в предыдущей лабе. Повторимся ещё раз, так программировать простые алгоритмы не нужно, поскольку, хоть и компиляторы вроде умеют оптимизировать хвостовую рекурсию, все равно очень вероятны значительно бо́льшие расходы ресурсов, по сравнению с версиями, написанными без рекурсии, и поэтому рекурсию целесообразно применять только тогда, когда без неё ну совсем плохо, например при обходе файловой системы. Но, если задание первое ещё куда ни шло, второе задание своей неподдельной извращённостью меня убило.


2. Дана последовательность ненулевых  целых чисел, признаком конца которых служит 0. Используя рекурсию, напечатать сначала все отрицательные, а потом – все положительные числа этой последовательности.

Вот и чему нас только учат? Впрочем обсуждать не будем. От нас требуется просто взять, и сделать. Здесь, очевидно, что функция должна принимать индекс элемента, делать с ним что сказано, и вызывать себя-же с индексом, увеличенным на единичку. Если элемент под этим индексом оказывается нулевым, то работа функции на этом завершается. Основываясь на этом просто суждении, тут-же получаем:


Код: C++
//тестируем эту вашу последовательность
void seqn_test(long *a, long j, bool sign){
    //если там будет ноль, все само остановится
    if(0 != a[j]){
        //обобщение на оба случая (сокращенный вариант)        
        if(sign == a[j] < 0){
            // явился следствием упрощения вот этого
            // sign && a[j] < 0 || !sign && a[j] > 0
            
            cout << a[j] << ", ";
        }
        //рекурсивность
        seqn_test(a, j + 1, sign);
    }
}

Выглядит предельно просто, но надо сказать, что когда мои сонные глаза увидели задание в первый раз, я даже не сразу понял, что они от нас хотят. Ну да ладно. Кстати, вторую лабу мы уже и сделали. Странная особенность всех лаб второго семестра заключается в том, что все они состоят почему-то из двух заданий. Кстати в этом задании приводится пример того, как можно упрощать логические выражения. Я советую проанализировать и понять, почему выражения sign && a[j] < 0 || !sign && a[j] > 0 и sign == a[j] < 0 эквивалентны, и возвращают одинаковые результаты (доказывается с помощью таблицы истинности, как и учили на информатике).


Лаба третья. Работа с одномерными динамическими массивами.


Здесь всё предельно просто, если мы имеем представление о том, что происходит в памяти процесса, когда там работает наша программа. Смотрим, какие подвиги нам предлагают совершить:


1. Используя функцию malloc(), выделить память под одномерный динамический массив b[n] (n вводить с клавиатуры). Заполнить его целыми случайными числами в диапазоне -50 … 50. Получить  динамический массив c[m], содержащий положительные числа, и динамический массив d[k], содержащий отрицательные числа. m и k должны быть равны количеству положительных и отрицательных чисел. Вывести исходный массив и полученные массивы. Освободить память.

Как же много буков-то, ужас! Суть такова: сделать массив, забить его мусором, и расчленить на 2, в одном положительные числа, в другом — нет. Массивы должны быть динамические, естественно. А это значит, что нам под них самим надо выделять память. Чтобы выделить память под массив из некоторого количества элементов, надо это количество умножить на размер одного элемента, как не трудно догадаться, то-есть, для создания массива из 4 элементов типа long, надо вызывать malloc(4 * sizeof(long)), и выделит нам эта функция как раз нужные 16 байтиков. Впрочем, рассуждения без кода часто бесполезны:


Код: C++
cout << "\nPlease, input array size:\n>";
long n, i;
cin >> n;

//запиливаем моссиво
long *b = (long *) malloc(sizeof(long) * n);
long m = 0, k = 0;

//забиваем его мусором
for(i = 0; i < n; i++){
	//от -50 до 50
	b[i] = rand() % 101 - 50;
	
	//положительные и отрицательные не содержат ноль
	//задание не предусматриваем, что делать с нулевыми
	//а действем мы изключительно по заданию..
	if(0 != b[i]){
		b[i] > 0 && ++m || ++k;
	}
}

//запиливаем есчо массивы
long *c = (long *) malloc(sizeof(long) * m);
long *d = (long *) malloc(sizeof(long) * k);

//перекладываем елементосы (второй проход)
//можно с реаллоками, но это будет в данном случае значийтельно медлнеенее
//понадобятся нам два указайтеля (не в смысле на память :)
long im = 0, ik = 0;

for(i = 0; i < n; i++){
	//ну тут все понятно. количества просто обязаны совпасть
	if(b[i] > 0){
		c[im++] = b[i];
	}else if(b[i] < 0){
		d[ik++] = b[i];
	}
}

//рисуем полезную информайцею
printf("\nSource dyn array (%d elements):\n", n);
massoprinteri(b, n);
cout << "\n\n";

printf("Positive dyn array (%d elements):\n", m);
massoprinteri(c, m);
cout << "\n\n";

printf("Negative dyn array (%d elements):\n", k);
massoprinteri(d, k);
cout << "\n\n";

//вроде все правильно
//выносим мусор
free(d);
free(c);
free(b);

Переменная n здесь хранит размер исходного массива, а функция massoprinteri() занимается распечаткой массива заданной длинны, содержащего числа типа long или int. Делается всё в два прохода: в первом считается количество положительных и отрицательных чисел, затем создаются 2 массива, и во втором проходе в эти массивы копируются уже элементы первого массива. Думаю, что такие тонкости, как например то, что переменная хранящая массив является на самом деле указателем на область памяти, в которой храниться массив, разъяснять не сто́ит — мы же все это видим, знаем, и понимаем, правда? Если это не так, то срочно, в аварийном порядке, курим матчасть лекции, до достижения полного просветления.


Расчленяем динамический массив
Рис. №860. Расчленяем динамический массив

Осталось напомнить, что память, которую мы выпросили у операционной системы вначале, надо бы, когда она нам уже не нужна, освобождать, то-есть, сообщать ОС, что нам она больше не нужна. Правда, сообщаем мы не совсем ОС, а менеджеру памяти Сишного рантайма, а он уже, в случае необходимости сообщает все подробности ОС, но нам пока это знать не слишком нужно. Нам хватит и того, что освобождением памяти заведует функция free(), принимающая, как не трудно догадаться, один указатель на выделенную область памяти. Идем, таким образом, дальше:


2. Используя оператор new, выделить память под одномерный динамический массив a[n] (n вводить с клавиатуры). Заполнить его вещественными случайными числами. Отсортировать массив по возрастанию, используя вместо индексов указатели. Вывести исходный и отсортированный массив. Освободить память.

Ну, и вот оно, первое место, где желательно включить мозг. Давайте сразу вспомним, что указатели, при применении к ним операций + и увеличиваются и уменьшаются не на плюсуемое значение, а на плюсуемое значение, умноженное на размер того типа, на который указывает указатель. Используя эту замечательную особенность, легко превратить индексы массивов в операции над указателями, но только надо не забывать разыменовывать указатели при таком обращении, то-есть ставить звёздочку в начале, говорящую о том, что мы хотим получить не значение указателя, а то значение в памяти, куда он показывает. Но ещё нужно помнить, что если указатель преобразовать к типу long, например, то с ним можно будет обращаться уже как с обыкновенным числом (в полной версии исходников есть похожий пример), то-есть, сложение и вычитание из него какого-нибудь числа не будет зависеть от размера типа, и будет добросовестно складывать и вычитать из него указанное значение по обычным правилам. Поскольку, что такое сортировка пузырьком мы тоже все знаем, просто возьмём, и напишем:


Код: C++
void inline swapd(double *a, double *b){
    //ничего умнее я не придумаль
    double temp = *a;
    *a = *b;
    *b = temp;
}

//не бузем выпендриваться и заюзаем обыкновенную пузырьковую сортировку
void bubble_sortd(double *z, long s){
    long i, j;
    
    //проще придумать сложно
    for(i = 0; i < s; i++){
        for(j = i; j < s; j++){
            //ежли испытуемый меньше
            if(*(z + i) < *(z + j)){
                //то делаем сwап-сwап
                swapd(z + i, z + j);
            }
        }
    }
}

Давайте сразу запомним, что ключевое слово inline перед функцией значит только то, что функция компилятором, по мере возможности вставляется прямо в тело вызывающей программы, а не обособляется отдельным кодом, и делается это исключительно ради повышения производительности. Но это так, лирика. Функция swapd(), как нетрудно догадаться, выполняет перестановку переменных местами, а мы вспоминаем, что когда в выражении мы хотим получить не значение переменной, а её адрес — перед переменной надо поставить амперсанд, то-есть &. Как использовать new и delete, желательно узнать из лекций и посмотреть на примерах, хотя по большому счёту это то-же самое выделение и освобождение памяти, только new сам рассчитывает необходимый размер памяти на основе типа, который мы указываем после этого слова. Больше, никакой идейной сложности тут нету, и поскольку код примера можно найти в самом конце, мы не задерживаемся и идём дальше (если код вам вдруг не ясен, читаем параграф текста перед ним, пока код не станет ясен, да).


Лаба четвёртая. Двумерные динамические массивы. Приобретение навыков работы с динамическими матрицами


Динамические матрицы, динамический Нео, динамическая ложка, которой динамически нету… Единственное, что тут надо усвоить, что структура у нас получается двухуровневая: один обыкновенный динамический массив хранит в себе не числа, а указатели на массивы из чисел, а тип такого двумерного массива описывается как указатель на другой указатель, указывающий на числа типа long. Да, знаю, с первого раза эта фраза мозг выносит капитально, но мы не сдаёмся, и вспоминаем, что в Си такие двухуровневые указатели обозначаются как type **, то-есть тип, и две звёздочки после него. Если бы указатель был трёхуровневый, звёздочек было-бы соответственно три, и так далее. По массивам, описанным с помощью таких указателей, можно ориентироваться почти как по обычным массивам с помощью двух индексов [j][i], где первый индекс j всегда показывает на элемент большей размерности чем i, то-есть, в случае матриц, всегда показывает на номер строки. А i в этом случае служит номером элемента в строке, или индексом столбика.


Далее осознаем, что выделение памяти под такой динамический массив делается в два этапа: первый этап, как в предыдущей лабе, выделяется память под массив, содержащий указатели. Второй-же этап, заключается в том, чтобы выделить память под все строки, и полученными указателями на строки заполнить первый массив. Да, всё просто, ну и не забыть надо, что освобождение памяти тоже должно производиться в два этапа: сначала освободить память, выделенную под все строки, а затем, выделенную под массив из указателей. Это значит, что для выделения и освобождения памяти, нужно будет использовать цикл по строкам.


Чтобы не погрязнуть в рассуждениях, давайте посмотрим уже на задания:


1. Задан двумерный динамический массив B размерности m x n. (n=5, m вводить с клавиатуры). Заполнить её случайными числами. Получить новую динамическую матрицу С[m-1][n-1]  путем удаления из В строки и столбца, в которых содержится максимальный элемент исходной матрицы.

Тут на самом деле всё предельно просто, и идейной сложности нету. Просто создаём две динамические матрицы, у второй из них элементов по обоим размерностям на единичку меньше, и просто копируем из первой во вторую все элементы, игнорируя те, у которых индексы совпадают с индексами элемента, содержащего максимум. Кэп здесь спешит подсказать, что индексы максимумов сначала надо-бы вычислить. Чтобы всё стало понятно, в студию мы вынесем немного кода:


Код: C++
const long MATRIX_HEIGHT = 5;

//запиливаем матричку
//p.s. не знаю как вы, а я new не люблю
long **z = matrix_create(m, MATRIX_HEIGHT);
//сразу запиливаем вторую
long **q = matrix_create(m - 1, MATRIX_HEIGHT - 1);

//первую наполняем мусором
matrix_fill_garbage(z, m, MATRIX_HEIGHT);

long maxv = z[0][0], maxi = 0, maxj = 0;

//ну типа ищем индексы максимума
for(j = 0; j < MATRIX_HEIGHT; j++){
	for(i = 0; i < m; i++){
		//если нашли чтото большее
		if(z[j][i] > maxv){
			maxv = z[j][i];
			maxi = i;
			maxj = j;
		}
	}
}

long i2 = 0, j2 = 0;

//перекладываем значения из первой во вторую, скипая индексы максимумов
for(j = 0; j < MATRIX_HEIGHT; j++){
	//скипаем
	if(j == maxj){
		continue;
	}
	i2 = 0;
	for(i = 0; i < m; i++){
		//снова скипаем
		if(i == maxi){
			continue;
		}
		//перекладываем же
		q[j2][i2++] = z[j][i];
	}
	//плюс-плюююсег
	++j2;
}

//а теперь - рисование!
printf("Original dynamic matrix (%d x %d):\n\n", m, MATRIX_HEIGHT);
matrix_display(z, m, MATRIX_HEIGHT);
cout << "\n";

printf("Maximal element %d at %d row and %d col\n", maxv, maxj, maxi);

printf("Transformed dynamic matrix (%d x %d):\n\n", m - 1, MATRIX_HEIGHT - 1);
matrix_display(q, m - 1, MATRIX_HEIGHT - 1);
cout << "\n";

//ну и по окончании банкета, надо вытереть кровь, и избавиться от трупов
matrix_free(z, MATRIX_HEIGHT);
matrix_free(q, MATRIX_HEIGHT - 1);

Мда.. Как видим, до фига всяких непонятных функций. Хотя на самом деле, они предельно понятны, и их назначения напрямую вытекают из названий. Но, чтобы всё-таки прояснить все таинства операций с памятью динамических матриц, мы всё-таки приведём код некоторых из них:


Код: C++
const long GRABAGE_SIZE = 101;
const long GRABAGE_SHIFT = 50;

//вот так мы создаем матрицы
long **matrix_create(long w, long h){
    long i;

    //создаем массив указателей
    long **r = (long **) malloc(h * sizeof(long *));

    //заполняем его валидными указателями на строки
    for(i = 0; i < h; i++){
        r[i] = (long *) malloc(w * sizeof(long));
    }    
    
    //возвращаем свежезапиленнцую матричку
    return r;
}

//а так от неё избавляемся
//тут достаточно знать только высоту матрицы
void matrix_free(long **m, long h){
    long i;
    
    //сначала освобдажаем строки
    for(i = 0; i < h; i++){
        free(m[i]);
    }
    
    //а потом и сам массив указателей на строки
    free(m);
}

//задача этой функции - много мусорить
//послее ее работы получается много мусора
//мусор можно настраивать
void matrix_fill_garbage(long **m, long w, long h){
    long i, j;
    
    //ну самый простой способ, берем и просто наполняем
    for(j = 0; j < h; j++){
        for(i = 0; i < w; i++){
            m[j][i] = rand() % GRABAGE_SIZE - GRABAGE_SHIFT;
        }
    }    
}

Мы ещё забыли сказать, что переменная m, используемая в предыдущем примере, отвечает за длину строки. Теперь, я думаю, как это работает, понятно должно стать и вам. Кстати функцию matrix_display() мы здесь рассматривать не будем, как она работает вы можете сами выяснить, раскурив полный исходный код примера. Но вот показать результат работы этой поделки, всё-таки сто́ит:


Убираем строчку
Рис. №861. Убираем строчку

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


2. Задан двумерный динамический массив А размерности m x n. (n=5, m вводить с клавиатуры). Заполнить его случайными числами. Дополнить его m+1-й строкой и n+1-м столбцом, в которые записать суммы элементов соответствующих строк и столбцов исходного массива А. В элемент A[m+1][n+1] поместить сумму всех элементов исходного массивa.

На первый взгляд всё кажется проще, но… А как мы собственно будем увеличивать длину строк?! И массива указателей, кстати, тоже?! А вот думаем. Конечно, по логике, придется выделять новую память, в которую помещается на 1 элемент больше, и содержимое имеющейся памяти копировать в новую, но на наше счастье, в Си есть замечательная функция realloc(), которая грубо выражаясь, выполняет все эти пляски с бубном за нас, то-есть изменяет размер уже выделенного блока памяти, с возможным его перемещением. Возможное перемещение, означает то, что возвращает функция указатель, который нам надо записать на место указателя, переданного в realloc(). С этой функцией алгоритм становится предельно простым, и заключается в том, что нужно просто для всех областей вызывать realloc(), с размером на один элемент большим, чем мы выделяли изначально. Не забываем везде про sizeof(), мы работаем с байтовой памятью! Вот что у нас таким образом получилось:


Код: C++
//запиливаем матричку
    //p.s. не знаю как вы, а я new не люблю
    long **z = matrix_create(m, MATRIX_HEIGHT);
    //вторую тут запиливать не надо
    //здесь надо применять напильник к первой, но чуть поздже
    //сначала заказываем наполненный мусоровоз
    matrix_fill_garbage(z, m, MATRIX_HEIGHT);
    
    //рисуем то что у нас получилось
    printf("Original dynamic matrix (%d x %d):\n\n", m, MATRIX_HEIGHT);
    matrix_display(z, m, MATRIX_HEIGHT);
    cout << "\n";
    
    //вот теперь используем напильник, имя которому realloc
    //не, я понимаю, можно там типа новую матрицу сделать, 
    //перекопировать, все дела, но НЕ ХОЧУ!!!
    z = (long **) realloc(z, (MATRIX_HEIGHT + 1) * sizeof(long *));
    //реаллокаем все строки, делая их на едыничку большими
    for(i = 0; i < MATRIX_HEIGHT; i++){
        z[i] = (long *) realloc(z[i], (m + 1) * sizeof(long));
    }
    //доделываем последнюю сторчку
    z[MATRIX_HEIGHT] = (long *) malloc((m + 1) * sizeof(long));

    long lsum = 0;
    
    //ну теперь остается посчитать нам суммы там и всю фигню
    for(j = 0; j < MATRIX_HEIGHT; j++){
        lsum = 0;
        //локальные суммы строк
        for(i = 0; i < m; i++){
            lsum += z[j][i];
        }
        z[j][m] = lsum;
    }
    
    for(i = 0; i <= m; i++){
        lsum = 0;
        //локальные суммы столбов
        for(j = 0; j < MATRIX_HEIGHT; j++){
            lsum += z[j][i];
        }
        //досчитываем глобальную сумму, ставя на место локальную
        z[MATRIX_HEIGHT][i] = lsum;
    }
    //нижний правый элемент нужэную сумму устанавливает сам, как не трудно заметить
    
    //ну и снова урок рисования
    printf("Transformed dynamic matrix (%d x %d):\n\n", m + 1, MATRIX_HEIGHT + 1);
    matrix_display(z, m + 1, MATRIX_HEIGHT + 1);
    cout << "\n";
    
    matrix_free(z, MATRIX_HEIGHT + 1);

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


Добавляем строчку
Рис. №862. Добавляем строчку

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


Лаба пятая. Многомерные динамические массивы


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


1. Сгенерировать одномерный динамический массив A из m элементов. Вводится число k (k<m). Получить из А матрицу B, по k элементов в строке.  Если m не кратно k недостающие элементы последней строки дополнить нулями.

Если проще, надо большой массив распилить бензопилой на равные огрызки, и собрать из них матрицу. Из новшеств только отметим тут функции memcpy(void *dest, void *src, int size), и memset(void *dest, int value, int size). Первая из них копирует блок памяти по адресу src в блок по адресу dest, размером size, а вторая заполняет блок памяти по адресу dest и размером size одним и тем же байтиком, значение которого указывается в value. Собственно, если вы немного подумаете, поймёте, почему мы заговорили об этих функциях — просто именно они в этом задании нам и понадобятся. И отвыкаем уже, от поэлементного копирования.


Код: C++
cout << "Please input M and K:\n>";
    long k, m, i, mz;
    scanf("%d %d", &m, &k);
    //если данные вменяемые
    if(m > k){
        //делаем ваш динамомассив
        long *au = new long[m];
        //создаём много garbage и рисуем исходный массив
        cout << "\nSource array:\n\n";
        for(i = 0; i < m; i++){
            au[i] = rand() % 101 - 50;
            cout << au[i] << ", ";
        }
        cout << "\n\n";
        
        //узнаем размер матрицы нео в длинну
        long m_size = (long) ceil((float) m / (float) k);
        //принимаем красную таблетку
        long **m_body = (long **) malloc(m_size * sizeof(long *));
        //входим в матрицу
        mz = m;
        for(i = 0; i < m_size; i++){
            m_body[i] = (long *) malloc(k * sizeof(long));
            //если строчка полная - один алгоритм
            //в противаном слуйчяе другой
            if(mz >= k){
                //тут просто копируем
                memcpy(m_body[i], au + i * k, k * sizeof(long));
            }else{
                //а тут еще юзаем мемсет, шобы было многа ноликоф
                memcpy(m_body[i], au + i * k, mz * sizeof(long));
                memset(m_body[i] + mz, 0, (k - mz) * sizeof(long));
                //указатели по известным причинам на сайзоф множить ни надо
            }
            mz -= k;
        }
        
        //используем способ рисования из предыдущей лабы
        printf("Assembled dynamic matrix (%d x %d):\n\n", k, m_size);
        matrix_display(m_body, k, m_size);
        cout << "\n";
        
        //сворачиваем лавочку
        matrix_free(m_body, m_size);
        delete au;
    }else{
        cout << "K must be less than M!\n";
    }

Теперь мы знаем, что memcpy() тут используется для копирования кусков массива на место строк матрицы, а memset() — для заполнения пустых мест нулями. Больше тут интересного нет ни-че-го. Разве что, функции некоторые используются из предыдущей лабы. Поэтому, “Just going forward, don't look behind!”


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

Выглядит таблица эта следующим образом:


Табличка умножения
Рис. №863. Табличка умножения

С нас снова снимают такую функцию как думать мозгом. Смысл создания блоков памяти разной длинны тоже малопонятен для такой таблицы, но обсуждать снова не будем. Просто возьмём, и сделаем, отметив параллельно, что длину очередной строки таблицы можно посчитать по формуле (j + 8) % 9 + 2, где j есть индекс очередной строчки. Код у меня, правда, получился сложноватым, сказывалось недосыпание, но думаю, что нам будет в самый раз:


Код: C++
//тупо лепим таблицу умножения как сказано
long **t = (long **) malloc(10 * sizeof(long *));
long i, j, xs;

for(j = 0; j < 10; j++){
	xs = (j + 8) % 9 + 2;
	t[j] = (long *) malloc(xs * sizeof(long));
	t[j][0] = t[j][1] = j;
	
	//генерим первую строчку
	if(j == 0){
		for(i = 1; i < 10; i++){
			t[j][i] = i;
		}
	}else if(j > 1){
		//генерим сами поля
		for(i = 2; i < xs; i++){
			t[j][i] = i * j;
		}
	}
	//ну как то вот так все компактно у нас, в одном цикле уместилось
}

cout << "\nMultiplication table below:\n\n";

//для рисования старая функция нам не подходит
display_hline(3, 10);
for(j = 0; j < 10; j++){
	xs = (j + 8) % 9 + 2;
	cout << "|";
	for(i = 0; i < xs; i++){
		//слегка корректрируем цвета)
		if(0 == i || 0 == j){
			console_set_color(BACKGROUND_BLUE | BACKGROUND_GREEN | BACKGROUND_RED);
		}else{
			console_set_color(FOREGROUND_BLUE | FOREGROUND_GREEN | FOREGROUND_RED);
		}
		printf("%3d", t[j][i]);
		console_set_color(FOREGROUND_BLUE | FOREGROUND_GREEN | FOREGROUND_RED);
		cout << "|";
	}
	cout << "\n";
	display_hline(3, xs + 1 < 10 ? xs + 1 : 10);
}
cout << "\n";

//а тут подходит
matrix_free(t, 10);

Идейная сложность здесь равна абсолютному нулю, но зато мне пришло в голову табличку нашу немножко перекрасить. Давайте разберём лучше функцию console_set_color(), которую здесь-же по-быстрому и сочиним:


Код: C++
bool console_set_color(short color){
    HANDLE hc = GetStdHandle(STD_OUTPUT_HANDLE);
    return SetConsoleTextAttribute(hc, color);
}

Что здесь происходит? На самом деле всё просто: используя Windows API, мы сначала получаем дескриптор потока вывода по умолчанию с помощью функции GetStdHandle(), который есть ни что иное, как та самая консоль, в которую мы постоянно с вами смотрим. Затем, используя API SetConsoleTextAttribute(), мы просто устанавливаем ей атрибуты наличия нужного цвета. Здесь вроде очевидно, что константы FOREGROUND_* отвечают за цвет шрифта, а  BACKGROUND_* — за цвет фона под шрифтом. Можете поэкспериментировать. Мне как раз и захотелось немножко перекрасить фон. Вот, кстати, что получилось в результате:


Таблица умножения
Рис. №864. Таблица умножения

Как мы видим теперь, 5-ю лабу тоже можно считать совершенно ниочёмной. Поэтому, мы собираем последние оставшиеся силы, и переходим к последней на сегодня лабе. К лабе №6.


Лаба шестая. Функции. Передача параметров по адресу.


На самом деле, после матриц, мозг здесь можно выключить, он нам не понадобиться. Важно только помнить, что в функцию можно передать указатель, и делать так, чтобы изменялось значение этой переменной именно в той ячейке памяти, куда показывает указатель, то-есть, изменения значения переменной влияли не только на функцию, но и на программу, которая функцию вызывает. Конечно, мы помним, что это делается с помощью разыменования, или подстановки звёздочки перед указателем. Кстати, того-же самого эффекта можно добиться, если ставить амперсанды в объявлении функции перед переменными, в этом случае будут в функцию тоже передаваться указатели, но неявно, то-есть, никаких звёздочек там нам не потребуется. Если честно, мне не очень нравится этот способ за его неочевидность. Сейчас, короче, всё станет понятно.


1. Написать функцию, которая вычисляет периметр и площадь треугольника. В функцию передаётся длина его сторон. Результаты возвращаются через параметры-указатели. В функции также предусмотреть ошибку в введённых данных (если такой треугольник может существовать, функция возвращает 1, иначе 0 через своё имя).

Так, треугольник… Слова-то какие интересные пошли. Здесь мы видим, что функция должна принимать три стороны, а возвращать площадь и периметр. Следовательно, две переменные должны передаваться не по значению, а адресом или по ссылке, чтобы функция могла их изменить как нужно. С этим всё понятно. Как считать периметр — тоже понятно. А вот как считать площадь надо напомнить, я уже было порвался считать её как половину модуля векторного произведения, но вдруг заметил что у нас нету векторов, а чтобы их сделать, придется повозиться. Поэтому, площадь мы сегодня считаем по формуле Герона:


\[ S = \sqrt{p(p - a)(p - b)(p - c)}, \, \,\,\, p = {a + b + c \over 2}\]
Формула Герона

Тут еще надо заметить, что от нас требуют контроль входных данных. Думаю, что подразумевается, что все длинны сторон должны быть положительными, и больше нуля, поскольку, если длинна хотя-бы одной стороны будет нулевой, это уже будет не треугольник. Ну а отрицательные длинны сторон — извините, за гранью моего понимания… Ээ, постойте-ка, ещё, если немного подумать, то каждая из сторон ещё не может быть больше, чем половина периметра! Сложив все данные в кучку воедино, получаем мы приблизительно следующее:


Код: C++
bool triangle_calculator(double a, double b, double c, double *p, double *s){
    //я думаю что отрицательные длинны сторон - это аморально
    //а при нулевых - это уже какбэ не совсем треугольник
    if(a < 0 || b < 0 || c < 0){
        return false;
    }
    
    //периметр он и в африке периметр
    *p = a + b + c;
    double p2 = *p / 2.0;

    //ещё одно условие, это одна сторона не может быть больше чем полупериметр!
    if(a > p2 || b > p2 || c > p2){
        return false;
    }
    
    //а вот площадь есть половина модуля векторного произведения, да
    //в данном случае - половина произведения длинн 2х сторон на синус угла между ними
    //но высчитывать синус мне лень, поэтому воспользуемся в данном случае формулой Герона
    *s = sqrt(p2 * (p2 - a) * (p2 - b) * (p2 - c));
    
    //в багдаде всё спокойно
    return true;
    
}

Действительно, мозг здесь и вправду не нужен. Этот пример демонстрирует передачу переменных с помощью указателей. Вызывать его, кстати, надо так:


Код: C++
double a, b, c, p, s;

//... некий код ...

triangle_calculator(a, b, c, &p, &s);

То-есть, надо просто передавать адреса переменных периметра и площади, ставив амперсанды перед ними. А сами стороны передавать как обычные переменные. И все будет отлично. Поехали дальше.


2. Написать функцию, определяющую вероятность того, что среди n детей будет m девочек или m мальчиков. Предусмотреть контроль входных данных. Вероятность рождения девочки p=0.45, мальчика q=1-p.

Ооо, вот это уже будет поинтереснее. В комплекте с заданием идёт интересная формула, в которой совсем нетрудно узнать ту самую формулу Бернулли из теории вероятности, которая выглядит следующим образом:


\[ P_{m,n} = \binom{n}{m} \cdot p^{m} \cdot(1 - p)^{n - m} \]
Формула Бернулли

С помощью формулы Бернулли как раз и рассчитывают вероятность того, что среди n событий наступит m искомых событий, вероятность которых равна p. В нашем случае, эту формулировку мы переносим на мальчиков и девочек. Обычно ещё, выражение 1 − p для компактности обозначают буквой q.


Как только мы переходим к написанию кода формулы, сразу нам бросается в глаза первый её множитель, который ВНЕЗАПНО является ни чем иным, как биномиальным коэффициентом, а что он из себя представляет, и как правильно его рассчитывать, я уже писал отдельную статью, с которой и советую вам ознакомиться. Выработанную в статье технику, мы сейчас и применим, ибо я думаю нет смысла напоминать, что произойдёт с факториалом, если попытаться посчитать достаточно большой (более 14 при типе long, большая потеря точности на double) биномиальный коэффициент в лоб…


В остальном формула Бернулли ничего интересного на своём борту не несёт. Поэтому, просто, возьмём её, и напишем.


Код: C++
double bernouili_probabiltiy(long n, long m, double p){
    return binomial(n, m) * pow(p, m) * pow(1.0 - p, n - m);
}

Далее, нам надо рассчитать, что среди n детей, m из них будут определённого типа пола. Вероятности появления мальчика и девочки связаны, и одну из них можно получить, отняв другую у единицы. Ну, пола то у нас всего два, поэтому, собственно, так и получается. Из всего этого, можно сделать определённый вывод, что нам всего-лишь надо 2 раза использовать формулу Бернулли с разными вероятностями, и сохранить её результаты в переданных переменных:


Код: C++
//g_prob - вероятность появления девочки, все что нам нужно
bool girl_and_boys_calculator(long n, long m, double g_prob, double &pg, double &pb){
    //первое что в голову приходит, вероятностим не могут вылазить за [0 .. 1]
    if(g_prob < 0.0 || g_prob > 1.0){
        return false;
    }
    //второе что приходит в голову, m не может быть больше n
    if(m > n){
        return false;
    }
    
    //просто берём, и два раза пользуемся формулой Бернулли
    pg = bernouili_probabiltiy(n, m, g_prob);
    pb = bernouili_probabiltiy(n, m, 1.0 - g_prob);
    
    //погода на марсе благоприятная
    return true;
}

Ах да! Мы же забыли про контроль входных данных, но тут что надо проверять очевидно: вероятности не могут быть меньше нуля или больше единицы, а m не может быть больше n, вернее, строго говоря, какбэ может, но в этом случае вероятность того, что среди 4 детей найдётся 7 девочек ну уж просто по любому равна нулю.


Надо заметить, что с тестированием этой лабы пришлось повозиться довольно-таки долго, причина этому была та, что формула Бернулли выдавала мягко говоря не совсем предсказуемые результаты, которые не так то просто было осознать, но, для тривиального примера вероятности того, что среди 2 детей найдется 1 девочка при вероятности появления девочки 50% алгоритм вернул верное значение: 50%, как для девочки, так и для мальчика. Нам этого, думаю будет достаточно. Вот, кстати, как это выглядело:


Девочки & Мальчики
Рис. №865. Девочки & Мальчики

Вот и всё! Первые 6 лаб готовы! Можно на этом месте кричать ура! Теперь мы все видим, что это на самом то деле, совсем не сложно, и совершенно нет причин здесь чего-то пугаться… В общем, наше шоу подошло к концу.


Заключение


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

1. Удаление или переписывание комментариев
2. Удаление или изменение отступов, лишних переводов строки
3. Изменение текстов приветствий и результатов (то что находиться в printf и cout)
4. Переименование функций и переменных
5. Лёгкое изменение логики кода (опционально)

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


Код: C++
#include <cstdlib>
#include <iostream>
#include <math.h>
#include <conio.h>
#include <windows.h>

using namespace std;

Впрочем, это заметно в подавляющем большинстве примеров. Ну, под конец, как и обещал в начале, собственно говоря, прилагаю полные версии исходников лаб, в одном zip-файле. Надеюсь они хоть кому-нибудь принесут пользу, а ещё больше надеюсь, что просветлят они не одну голову. На этом с вами мы заканчиваем, но не прощаемся: в недалёком будущем нас ждут ещё 6 лаб…


P.S. Трек слушать всем! До скорых встреч!


Продолжительность 06:37    Битрейт 320 кбит/с    Слушать всем!
Ключевые слова Программизм, математика, Повседневщина, лабораторная работа, ряд Тейлора, динамический массив, матрица, Dev-C++, Функции, Wolfram Alpha, Рекурсия, malloc, указатели, биномиальный коэффициент, формула Бернулли
QR-код
Интересное
Как обычно, был семинар по векторной алгебре. Почему-то он показался мне смертельно скучным, может потому что тема плоскостей и прямых в пространстве мне уже была относительна знакома, а может потому что я забыл дома задачник… Впрочем скука продолжалась недолго

Читать »»
Случайные фото