Архив рубрики: ЕГЭ по информатике

Занятие 16. Указатели.


Здравствуйте друзья.
Сегодня у нас важная и сложная тема. Возможно, самая сложная тема за все время. Указатели.

Прежде вспомним основы шестнадцатеричной системы счисления.

Любое число в 16-тиричной системе счисления записывается с помощью символов 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F. Шестнадцатеричной она называется, потому что в ней для записи различных чисел используются 16 основных цифр. Например, в привычной нами десятичной системе счисления используется десять основных цифр 0,1,2,3,4,5,6,7,8 и 9. 

Первые десять цифр в 16-тиричной системе счисления такие же, как и в десятичной системе, а вот для записи следующих шести используются буквы латинского алфавита. 
A=10
B=11
C=12
D=13
E=14
F=15.

Как перевести число из шестнадцатеричной системы счисления в десятичную.

Пусть у нас есть число 2D5. И мы хотим узнать, сколько это в нашей десятичной системе счисления.
Для этого сначала разделим число на цифры:
2 D5
Теперь заменим все буквы, на их числовые обозначения:
2 13 5

Пронумеруем эти цифры справа налево начиная с нуля.

2   13   5
2         1      0

Умножим каждую из цифр, на 16 в степени, соответствующей порядковому номеру. И сложим все это между собой.
Рис.1 Перевод шестнадцатеричного числа в десятичную систему счисления
В результате получим 725. Это и есть число 2D5 в десятичной системе счисления.

Перевод числа из десятичной в шестнадцатеричную систему счисления. 

Давайте переведем число 725 обратно в шестнадцатеричную систему счисления. В результате у нас должно получится 2D5.
Рис.2 Перевод из 10-ой в 16-ричную

Для перевода, нам необходимо поделить с остатком число 725 на 16 в столбик. Получим 45 и остаток 5. 

Теперь делим 45 на 16 с остатком. Получим 2 и остаток 13. Оба числа меньше 16 значит на этом можно закончить деление.

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

Как вы уже успели заметить, мы получили то, что и ожидали 2D5.






А теперь посмотрите на следующее число 235. Оно может быть как числом в десятичной, так и в шестнадцатеричной системе счисления. А кстати, чему будет равно число 235 в шестнадцатеричной системе счисления  при переводе в десятичную систему? Переведите самостоятельно, посмотрите сколь велико отличие.
Нужно как-то уметь отличать. Для этого используются специальные обозначения. Одним из способов является запись в которой шестнадцатеричному числу предшествует пара символов «0х». Т.е. запись 0х235 говорит нам, что 235 это число, записанное в шестнадцатеричной системе счисления.

Переменные и их адреса.

Как отмечалось во втором уроке, каждая переменная хранится в памяти. Естественно у каждой переменной в памяти есть свой адрес, по которому она записана. Мы уже даже использовали адреса переменных, когда пользовались функцией scanf().
Чтобы получить адрес переменной нам необходимо перед её именем написать символ “&”.

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

Листинг16.1
#include <stdio.h>

int main (){

printf ("razmer peremennoi tipa char %dn", sizeof(char));

printf ("razmer peremennoi tipa int %dn", sizeof(int));

printf ("razmer peremennoi tipa float %dn", sizeof(float));

printf ("razmer peremennoi tipa double %dn", sizeof(double));

return(0);

}

Результат её работы:
Рис 4. Программа иллюстрирующая работу sizeof()

У вас данные цифры могут быть другими кстати. Так как стандартом языка не оговаривается какой тип сколько должен занимать в памяти. Оговариваются только из соотношения. Например, размер double не должен быть меньше чем размер float.

То есть, если я объявляю в программе переменную типа int, то под нее в памяти выделяется 4 байта (ячейки).

Так как мы уже умеем получать адрес переменной, то давайте посмотрим на него. Для того, чтобы вывести число в шестнадцатеричной системе существует специальный спецификатор “%x”. И для него есть модификатор “#” при его записи, шестнадцатеричное число выводится с символами «0х».

Листинг16.2
#include <stdio.h>

int main (){

      int a,b;

      printf ("adres peremennoi a %#xn", &a);

      printf ("adres peremennoi b %#xn", &b);

return(0);

}

Рис.5 Адреса переменных в памяти

Мы получили два адреса 0x12ff60 и 0x12ff56. По этим адресам в памяти записаны наши переменные a и b. При этом они занимают в памяти по 4 клетки подряд, так как это переменные целого типа и из рисунка 3 видно, что их размер 4 байта. Это выглядит примерно следующим образом.
Рис.6. Пример расположения переменных в памяти
Как вы уже заметили, переменные в память записываются не одна за другой, а в произвольном месте, лишь бы там было пусто и хватило места. Исключение составляют массивы. Они записываются в память последовательно. Посмотрите на результат работы следующей программы.

Листинг16.3
#include <stdio.h>

int main (){

      int a[3];

      printf ("adres peremennoi a[0] %#xn", &a[0]);

      printf ("adres peremennoi a[1] %#xn", &a[1]);

return(0);

}

Рис.7 Расположение массива в памяти

Видите, каждый элемент занимает ровно 4 ячейки, потом идет следующий. По порядку и никак иначе. Это важный факт, он иногда используется в программировании. Но сейчас не об этом.

Адреса это хорошо, но что с ними делать? На кой чёрт они нам сдались?
Обо всем по порядку. 

Указатели. 

Во-первых, для хранения адресов существует специальные переменные, которые называются указателями.  Таким образом, мы вплотную подобрались к теме нашего урока - к указателям.

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

Объявление указателя.

Указатель, раз это переменная, должен как-то объявляться. Делается это почти что также как и обычно.
int * p_a;

Сначала указывается тип переменной, которая будет храниться в памяти, по адресу указателя. Далее следует специальный символ «*» (звездочка), которая и указывает на то, что мы собираемся объявить не просто переменную типа int, а указатель на переменную типа int. После звездочки пишут имя указателя. Ну и естественно заключительная точка с запятой.

В нашем примере, мы объявили  указатель с именем p_a, который будет указывать на переменную типа int. Кстати, обычно, чтобы не путать указатели с другими переменными, в их имена добавляют какой-нибудь отличительный знак. Например, я вот добавляю обычно “p_”.  Когда я вижу в своей программе переменную, имя которой начинается с этих символов, я точно знаю что это у меня указатель. Кроме того, если программа большая, я помимо этого указывают после «p» ещё и тип переменной для типа int  - i, для floatf, для char – с и так далее, получается что-то типа pi_a. Это  сразу говорит мне, что это указатель, который ссылается на переменную типа int.
  

Присвоение указателю адреса.

Давайте перепишем Листинг 16.2, используя указатели.

Листинг 16.4
#include <stdio.h>

int main (){

      int a,b,*pi_a, *pi_b;

      pi_a=&a;

      pi_b=&b;

      printf ("adres peremennoi a %#xn", pi_a);

      printf ("adres peremennoi b %pn", pi_b);

return(0);

}

Рис.8. Пример хранения адреса переменной в указателе.

Как видите, после объявления с указателем можно работать так же, как и с обычной переменной. Ему можно присвоить некоторый адрес, используя оператор «=».
И заметьте, для  вывода указателя можно использовать специальный спецификатор вывода «p».

Получение значения переменной.

Мы можем получить значение, которое хранится по адресу, записанному в указателе. Для этого используется оператор «*». Ага, снова эта пресловутая звездочка. Догадайтесь, куда она записывается? Ага, именно туда, перед именем указателя. Вот такие чудеса творятся иногда.  Надо посмотреть на примере.

Давайте немного изменим Листинг 16.4.  Добавим переменным значения и попробуем получить их, используя указатели.

Листинг16.5
#include <stdio.h>

int main (){

      int a=3, b=0, *pi_a;    //объявляем переменную a

//и указатель на переменную типа int

      pi_a=&a; // присваиваем указателю адресс переменной а

      *pi_a=b; // записываем в память, по адресу который хранится в указателе

                   // значение переменной b

      printf ("adres peremennoi a %#xn", pi_a);

      printf ("znachenie po adresu zapisannomy v pi_a %dn", *pi_a);

return(0);

}

Рис.9. Использование указателей для обращения к значениям переменных,на которые они ссылаются

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

Еще раз обсудим звездочку в указателях.
  • Если  звездочка стоит перед именем в объявлении переменной, то в этом случае она означает, что объявляется указатель.
  • Если звездочка встречается внутри программы, то в данном случае, она указывает на то, что мы обращаемся к ячейкам памяти, на которые ссылается указатель.
Еще раз внимательно перечитайте предыдущий пункт. Он очень важен, вам необходимо в этом разобраться. Задавайте вопросы в комментариях, если вам что-то непонятно. С этим обязательно нужно хорошо разобраться.

Есть еще один специальный указатель. Он имеет свое особое название – нулевой указатель NULL. Нулевой указатель не ссылается никуда. Он используется, чтобы обнулять указатели. Посмотрите на следующую программу.

Листинг16.6
#include <stdio.h>

int main (){

      int a=3,*pi_a;

      pi_a=&a; // присваиваем указателю адресс переменной а

      printf ("adres peremennoi a %#xn", pi_a);

      pi_a=NULL;

      printf ("adres peremennoi a %#xn", pi_a);

return(0);

}

Рис.10 Нулевой указатель

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

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

Рис.11 Простенькая головоломка. Что выведет представленная программа?
Нам известно, когда мы передаем переменные в функцию, то передаются не сами переменные, а их копии? Иногда нам это вовсе не нужно. Иногда удобно сделать так, чтобы значения все-таки изменялись. Для этого, нужно передавать в функцию не переменную, а указатель на неё.

Давайте перепишем программу с картинки, чтобы она работала так, как и предполагается.

Листинг 16.7
#include <stdio.h>

void obmen (int *pi_a, int*pi_b){

//принимаем указатели на переменные типа int

      int temp;

      temp=*pi_a;

      *pi_a=*pi_b;

      *pi_b=temp;

}

int main (){

      int x=5, y=10;

      obmen(&x,&y);

// ВНИМАНИЕ!передаем адреса, так как функция obmen принимаем указатели

      printf ("Posle x=%d y=%dn",x,y);

return(0);

}

Рис.12 Пример работы программы с указателями
Как видите, теперь работает как надо. Если вы внимательно разобрались с началом урока, то проблем с этой программой возникнуть не должно. Если вопросы есть, задавайте в комментариях. Я постараюсь все вам разъяснить.

Подробный урок о том, зачем нужны указатели.

И это еще не все возможности указателей. Следующее занятие снова будет посвящено указателям. Их связью с массивами и строками.

Отдельного домашнего задания не будет. Хорошенько разберитесь с этим занятием. Вам должна быть тут понятна каждая строчка. Если интересно, можете потренироваться переводить числа из десятичной системы счисления в шестнадцатеричную, и обратно.  И раз уж мы учимся программировать, то напишите для этого программу. =)))

Если вам понравился этот или другие уроки, расскажите пожалуйста о них, своим друзьям Вконтакте,Facebook,Google+, используя кнопки социальных сетей расположенные ниже.

Алгоритм. Формы записи. Отличие алгоритма от программы.

Добрый день!
Сегодня мы поговорим об алгоритмах и способах их записи.
Что такое алгоритм?

Алгоритм – порядок действий, выполнив который, исполнитель (некоторое устройство или даже человек), получит решение некоторой конкретной задачи.
К алгоритмам предъявляются ряд некоторых требований.

1.   Понятность.Алгоритм должен быть понятным, человеку или устройству, которое его будет выполнять. Вспомните инструкции к технике на китайском или корейском языке.
2.   Конечность. Алгоритм должен иметь конечное число шагов. Пусть их будет два миллиона, но мы точно знаем, что выполнив все два миллиона шагов по порядку, то обязательно получим результат.
3.   Определенность.Алгоритм должен быть точным и не допускать неоднозначности в его понимании. На каждом шаге, исполнитель должен точно знать, какой шаг ему делать следующим, а не додумывать или предполагать.

Естественно есть и другие. Кому интересно, можете поискать информацию в  интернете.
Способы записи алгоритмов.
Есть несколько способов записи алгоритмов. Одним из наиболее распространенных, является словесное описание алгоритма. Студентов, иногда просят записывать свой алгоритм в виде блок-схем. Это тоже один наглядных способов записи алгоритмов. Кроме того, для записи алгоритмов, часто используют «формальные языки».
Дело в том, что большинство алгоритмических языков во много схожи между собой. Так, например, в большинстве из них, есть операция присвоения значения переменной, есть сами переменные, циклы,  управляющие конструкции и т.д. А раз так, то можно придумать некоторый формальный язык, которым будут описываться эти стандартные действия. Таким образом, они будут понятны всем программистам, пишущим на других языках. Такой формальный язык называют псевдокод.
Программа это, кстати, тоже не алгоритм. Программа, это уже конкретная реализация некоторого алгоритма.
Давайте рассмотрим уже знакомый нам пример, с поиском минимума в одномерном массиве.

Задача:  Дан массив целых чисел. Найти минимальный элемент в массиве.
Идея решения: Сравнить между собой все элементы и найти минимальный.

Алгоритм: (словесное описание)
1.   Принимаем в качестве минимального первый элемент предложенного массива.
2.   Начиная со второго, последовательно сравниваем каждый элемент с минимальным значением, пока не достигнем конца массива.
2.1. Если текущий элемент меньше минимального, принимаем его значение в качестве минимума.
2.2. В противном случае, переходим к следующей итерации.

Теперь представим блок-схему данного алгоритма. Имеем массив чисел arr[N], N – длина массива.

Рис 1. Блок-схема алгоритма поиска  

 

Все эти квадратики, кружочки и ромбики это не моя прихоть, а специальные обозначения. Существует даже специальный государственный документ, который определяет наклон линий, размеры этих фигур, подписи и т.д. (кому интересно поищите стандарт ЕСПД).  Я уже давно не занимался этим, и стандарты давно не читал, поэтому в тонкостях могу и ошибаться, но общий вид блок схемы правильный. К тому же соблюдать эти стандарты требуется только в официальной документации, студентов обычно не просят делать этого. Быть может, я еще подробнее остановлюсь на составлении блок-схем к алгоритмам, но пока рассмотрим основные элементы. 
Скругленные квадраты в начале и в конце обозначают начало и конец программы.
Овал – ввод или вывод данных.
В прямоугольнике записывают вычисления и присвоения.
Ромб – это условие, буквально оператор if-else. Из него две ветви одна выполняется, когда условие истинно, другая - когда ложно.
Шестигранник используется для обозначения цикл со счетчиком, хотя это и так понятно. После окончания цикла выполняется правая веточка этого значка (хотя я встречал и другие способы записи циклов).

Запись алгоритма на псевдокоде.
Вы можете встретить различные виды псевдокода, синтаксис некоторых может быть похож на синтаксис языка программирования Pascal. Я привожу здесь тот, что используется в задания типа ЕГЭ. 

Листинг 1.
АЛГ
НАЧ
ЦЕЛ N, min;
МАССИВ arr[N];
ЦЕЛ i;
min = arr[0];
НЦ  (i=0;i < N;i++)  
                 ЕСЛИ (arr[i]<min)  
                 ТО min=arr[i];
КЦ
ВЫВОД min;
КОН

Листинг 2.
#include <stdio.h>
int main(){
      int min, arr[11]={5,14,7,4,11,2,6,12,8,7,3};
      min = arr[0];
      for (int i=1; i<11; i++){
            if (arr[i]<min)
                  min = arr[i];
      }
      printf("%dn", min);
return(0);
}

Не правда ли очень похоже? 

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

Занятие 11. Одномерные массивы. Программирование для начинающих.

Добрый день. Сегодня поговорим о массивах. Не будем тянуть быка за хвост, а сразу же возьмем его за рога. Вот представьте, вы хотите написать программу, которая будет вычислять среднее арифметическое ваших (или вашего чада) оценок за четверть/семестр.  И при этом вы хотите не только посчитать среднее, а еще и по какому предмету, у вас максимальный средний балл, сколько пятерок получено за все предметы вместе взятые, и сколько неудов поставлено за весь период и много еще чего. Ясное дело все эти оценки надо где-то хранить. Можно конечно завести пару сотен переменных, придумать им всем разные названия, да еще и так, чтобы отличать в каких именно хранятся оценки по математике, а в которых по русскому. А как средний балл потом как считать? Складывать между собой 200 разных переменных и  результат сложения делить на 200? Ну общая идея конечно такова, но в такой реализации её может исполнить только истинный мазохист. Но есть и хорошая новость для нас с вами. Для хранения больших объемов однотипной информации можно использовать массивы.

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

Кстати, запомните, в массиве могут храниться данные только одного типа. Т.е. нельзя в одном массиве хранить данные типа int и типа float. В примере выше, все данные в массиве целые числа. Это и понятно, так как оценок 3.7, 4.2, 2.73 не предусмотрено.

Теперь разберемся с тем, как объявить массив, как с ним работать и чем он может нам помочь.

Для начала научимся объявлять массив. Ничего нового тут нет, Америку сейчас я не открою.
Итак, внимание на экран.

Рис 2. Объявление массива

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

Пришло время рассказать еще об одной особенности массива. Каждый элемент массива имеет свой номер. И причем нумерация элементов начинается с нуля. Поэтому многие программисты, вероятно чувствуя свою элитарность начинают счет с нуля. Ну вы понимаете... =)))
Рис 3. Массив оценок

Кстати, это является не только поводом для шуток, но и для трудностей. Одной из самых распространенных ошибок, при работе с массивами является выход за пределы массива. Это когда у нас есть массив из 8 элементов, а мы пытаемся обратиться к элементу с номером 53. Как видите, размерность у нас 8, а последний номер элемента 7. Вроде бы ничего сложно, помни, что у тебя на один номер меньше, чем объявлял и всё. Но нет ошибались, ошибаются и будут ошибаться.

Теперь посмотрим как занести данные в массив, и как их оттуда извлечь.
Например, мы хотим сохранить данные в первый элемент массива ( помним, что это первый элемент это, элемент с цифрой 0).

Листинг 11.1
ochenka [0] = 4; // занести в нулевой элемент  значение 4
printf("%d ", ochenka[0]); // вывести значение хранящееся в                                  // нулевом элементе

В общем и целом работа с отдельным элементом массива ничем не отличается от работы с обычной переменной. Элемент массива можно использовать везде, где вы использовали переменные. Единственно что нужно следить за типом данных, но это нужно делать и при работе с обычными переменными.

А теперь рассмотрим одну из задач, которые встречаются в ЕГЭ. Как будет выглядеть массив после выполнения следующей программы. Только не надо её переписывать в среду разработки, прокрутите программу ручками. Это называется компиляция в уме. Нарисуйте массив, и последовательно выполняйте операции, шаг за шагом.

Листинг 11.2

#include <stdio.h>

int main(){
      int A[10], k=0;
       for (int i=0; i<=9; i++)
             A[i]=9-i;
       for (int i=0; i<=4; i++){
             k = A[i];
             A[i] = A[9-i];
             A[9-i] = k;
       } 
      for (int i=0; i<=9; i++)
            printf("%d ", A[i]);
return(0); 
}

Правильный ответ написан ниже, белым цветом.Выделите строку и сразу его увидите. Настоятельно вас прошу, проделать это упражнение самостоятельно, без помощи компьютера.
0 1 2 3 4 5 6 7 8 9

Вернемся на секундочку к нашему примеру, который мы описали в начале урока. Давайте таки найдем среднее арифметическое из оценок и посчитаем количество двоек например.

Листинг 11.3


#include <stdio.h>

int main(){
      int ochenka[8];
      for (int i=0; i<=7; i++){
            printf ("Vvedite %d ochenku:", i+1);
            scanf("%d", &ochenka[i]);
      }
int k=0; //переменная счетчик для двоек 
float s_a=0; //переменная для хранения среднего арифметического 
      for (int i=0; i<=7; i++){
            if (ochenka[i] == 2)
                  k++;
            s_a+=ochenka[i];
      }
printf("Kolichestvo dvoek = %d srednii ball = %3.2fn", k, s_a/8);
return(0);
}


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



Хотел еще написать про основные алгоритмы, используемые при работе с массивами написать, но решил оставить это на следующий урок.

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

 Задание для практической работы:

  • Выполнить задание, которое описано в уроке. Разобраться в нем, особенно если у вас не сразу получился правильный ответ.
  • Задан целочисленный массив из N элементов. N<=30. Пользователь задает некоторое целое число. Необходимо посчитать, количество элементов массива  меньших по модулю этого числа
  • Написать программу, которой на вход подается три массива оценок: сначала по русскому языку, потом по математике и наконец по физике. Причем, количество их заранее не известно, но не превышает 20 штук, по любому из предметов.  По разным предметам может быть введено различное количество оценок. Ввод оценок производится пользователем с клавиатуры, причем сначала он вводит одну из цифр 1, 2, 3 которая определяет,  по какому предмету эта оценка. (1 -русский язык, 2 - математика и 3 - физика)
Ввод данных заканчивает, когда пользователь введет цифру 0.
Например:
1 5
1 4
2 3
1 5
3 4
0
Такой набор исходных данных означает, что ученик получил
по русскому языку 5,4,5
по математике 3
по физике 4
Программа, должна вывести на экран все оценки ученика по каждому из предметов в формате:
rus: 5 4 5
math: 3
fiz: 4
Посчитать средний балл по каждому из предметов. Посчитать количество двоек по каждому из предметов, если их нет, то вывести 0. Посчитать средний балл по всем оценкам. Посчитать количество пятерок, которые получены по всем предметам.


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