Информатика, 10 класс К. Ю. Поляков, Е. А. Еремин
 Скачать 0.95 Mb.
|
|
§ 67. Матрицы Что такое матрицы Многие программы работают сданными, организованными в виде таблиц. Например, при составлении программы для игры в крестики-нолики нужно запоминать состояние каждой клетки квадратной доски. Можно поступить так пустым клеткам присвоить код –1, клетке, где стоит нолик кода клетке с крестиком – код 1. Тогда информация о состоянии поля может быть записана в виде таблицы Такие таблицы называются матрицами или двухмерными массивами. Каждый элемент матрицы, в отличие от обычного (линейного) массива имеет два индекса – номер строки и номер столбца. На рисунке фоном выделен элемент, находящийся на пересечении строки 1 и столбца 2 в языках C и C++ строки и столбцы нумеруются с нуля. Матрица — это прямоугольная таблица, составленная из элементов одного типа (чисел, строки т.д.). Каждый элемент матрицы имеет два индекса – номера строки и столбца. При объявлении матриц в двух парах квадратных скобок указывают два размера (количество строки количество столбцов) const int N = 3 , M = 4 ; int A[N][M]; double X[ 10 ][ 12 ]; bool L[N][ 2 ]; Каждому элементу матрицы можно присвоить любое значение, допустимое для выбранного типа данных. Поскольку индексов два, для заполнения матрицы нужно использовать вложенный цикл. Далее в примерах будем считать, что объявлена матрица из N строки столбцов, аи целочисленные переменные, обозначающие индексы строки и столбца. В этом примере матрица заполняется случайными числами и выводится на экран for ( i = 0 ; i < N; i++ ) { for ( j = 0 ; j < M; j++ ) { A[i][j] = irand( 20 , 80 ); printf ( "%3d" , A[i][j] ); } printf ( "\n" ); } for ( i = 0 ; i < N; i++ ) { for ( j = 0 ; j < M; j++ ) { A[i][j] = irand ( 20 , 80 ); cout.width( 3 ); cout << A[i][j]; } cout << endl; } Такой же двойной цикл нужно использовать для перебора всех элементов матрицы. Вот как вычисляется сумма всех элементов sum = 0 ; 13 Иногда бывает удобна нумерация с единицы, в этом случае можно выделить матрицу большего размера на один столбец и одну строку больше) и не использовать элементы с нулевыми индексами. 0 1 2 0 -1 0 1 1 -1 0 1 2 0 1 -1 Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 64 22.10.2015 for ( i = 0 ; i < N; i++ ) for ( j = 0 ; j < M; j++ ) sum += A[i][j]; Обработка элементов матрицы Покажем, как можно обработать (например, сложить) некоторые элементы квадратной матрицы A, содержащей N строки столбцов. На риса выделена главная диагональ матрицы, на рис. б – вторая (побочная) диагональна рис. в – главная диагональ и все элементы под ней. Главная диагональ – это элементы A[0][0], A[1][1], …, A[N-1][N-1], то есть номер строки равен номеру столбца. Для перебора этих элементов нужен один цикл for ( i = 0 ; i < N; i++ ) { // работаем с A[i][i] } Элементы побочной диагонали – это A[0][N-1], A[1][N-2], …, A[N-1][0]. Заметим, что сумма номеров строки и столбца для каждого элемента равны N-1, поэтому получаем такой цикл перебора for ( i = 0 ; i < N; i++ ) { // работаем с A[i][N-1-i] } В случаев (обработка всех элементов на главной диагонали и под ней) нужен вложенный цикл номер строки будет меняться от 0 до N-1, а номер столбца для каждой строки i – от 0 до i: for ( i = 0 ; i < N; i++ ) for ( j = 0 ; j <= i ; j++ ) { // работаем с A[i][j] } Чтобы переставить строки или столбцы, достаточно одного цикла. Например, переcтавим строки 2 и 4, используя вспомогательную целую переменную с for ( j = 0 ; j < M; j++ ) { c = A[ 2 ][j]; A[ 2 ][j]= A[ 4 ][j]; A[ 4 ][j]= c; } 1. Что такое матрицы Зачем они нужны 2. Сравните понятия массив и матрица. 3. Как выдумаете, можно ли считать, что первый индекс элемента матрицы – это номер столбца, а второй – номер строки 4. Могут ли индексы элементов матрицы принимать отрицательные значения 5. Что такое главная и побочная диагонали матрицы 6. Почему суммирование элементов главной диагонали требует одиночного цикла, а суммирование элементов под главной диагональю – вложенного ? Контрольные вопросы а) б) в) Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 65 22.10.2015 1. Напишите программу, которая находит минимальный и максимальный элементы матрицы и их индексы. 2. Напишите программу, которая находит минимальный и максимальный из чётных положительных элементов матрицы и их индексы. Учтите, что таких элементов в матрице может и не быть. 3. Напишите программу, которая выводит на экран строку матрицы, сумма элементов которой наибольшая. 4. Напишите программу, которая выводит на экран столбец матрицы, сумма элементов которой наименьшая. 5. Напишите программу, которая заполняет матрицу случайными числами, а затем записывает нули вовсе элементы выше главной диагонали. 6. Напишите программу, которая заполняет матрицу случайными числами, а затем записывает нули вовсе элементы выше побочной диагонали. 7. Напишите программу, которая заполняет матрицу 7 ×7 случайными числами, а затем записывает в элементы, отмеченные на рисунках, число 99: 8. Заполните матрицу, содержащую N строки столбцов, натуральными числами по спирали и змейкой, как на рисунках 9. Заполните квадратную матрицу случайными числами и выполните её транспонирование так называется процедура, в результате которой строки матрицы становятся столбцами, а столбцы – строками 10. Заполните квадратную матрицу случайными числами и выполните её поворот награду- сов 11. Напишите программу, которая играет с человеком в крестики-нолики. 12. В матрице, содержащей N строки столбцов, записана карта островного государства Ли- мония (нули обозначают море, а единицы – сушу. Все острова имеют форму прямоугольника. Написать программу, которая по готовой карте определяет количество островов. а) б) в) 1 2 3 4 5 6 7 8 9 7 4 1 8 5 2 9 6 3 1 2 3 4 5 6 7 8 9 1 4 7 2 5 8 3 6 9 Задачи и задания 1 2 3 4 10 11 12 5 9 8 7 6 1 3 4 9 2 5 8 10 6 7 11 12 1 6 7 12 2 5 8 11 3 4 9 10 а) б) в) Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 66 22.10.2015 § 68. Работа с файлами Как работать с файлами Файл – это набор данных на диске, имеющий имя. Сточки зрения программиста, бывают файлы двух типов 1) текстовые, которые содержат текст, разбитый на строки таким образом, из всех специальных символов в текстовых файлах могут быть только символы перехода на новую строку 2) двоичные, в которых могут содержаться любые данные и любые коды без ограничений в двоичных файлах хранятся рисунки, звуки, видеофильмы и т.д. Мы будем рассматривать только текстовые файлы. Работа с файлом из программы включает три этапа. Сначала надо открыть файл, то есть сделать его активным для программы. Если файл не открыт, то программа не может к нему обращаться. При открытии файла указывают режим работы чтение, запись или добавление данных вконец файла. Чаще всего открытый файл блокируется так, что другие программу не могут использовать его. Когда файл открыт (активен) программа выполняет все необходимые операции с ним. После этого нужно закрыть файл, то есть освободить его, разорвать связь с программой. Именно при закрытии все последние изменения, сделанные программой в файле, записываются на диск. Такой принцип работы иногда называют принципом сэндвича», в котором три слоя хлеб, затем начинка, и потом снова хлеб В большинстве языков программирования с файлами работают через вспомогательные переменные (их называют указатели, идентификаторы и т.п.). Например, в языке С используются указатели на файлы (англ. file pointer): FILE *F; Как вызнаете, указатель – это переменная, в которую можно записать адрес какого-то объекта. В данном случаев переменной F можно хранить адрес специального блока данных для управления файлом, который называется FILE и строится в памяти при открытии (активации) файла с помощью функции fopen: F = fopen ( "input.txt" , "r" ); В этом примере файл с именем input.txt из текущего каталога (то есть из каталога, откуда запускается программа) открывается в режиме чтения (на это указывает второй параметр « r», от англ. read – читать. Если второй параметр равен « w» (от англ. write – писáть), файл открывается для записи. Можно ещё использовать режим добавления, указав вторым параметром « a» (от англ. append – добавить в этом случае новые данные дописываются вконец файла, а если файла не было, он создается. Если файл открыт неудачно (например, не обнаружен файл, открываемый для чтения, функция fopen вернет нулевой указатель (NULL). Этот факт можно использовать для обработки ошибок FILE *F; F = fopen ( "input.txt" , "r" ); if ( F ) { // здесь работаем с файлом } else Открыть файл не удалось Вспомните, что в языке C любое ненулевое значение воспринимается как истинное условие, а любое нулевое (в том числе и нулевой указатель NULL) – как ложное. Поэтому вместо if (F != NULL) часто пишут просто if (F). открыть файл работа с файлом закрыть файл хлеб хлеб начинка Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 67 Функция fclose (от англ. file close закрыть файл) закрывает файл, освобождая его. Например, если нужно читать данные из файла input.txt и записывать результаты в файл output.txt, можно использовать такую структуру FILE *Fin, *Fout; Fin = fopen ( "input.txt" , "r" ); Fout = fopen ( "output.txt" , "w" ); // здесь работаем с файлами fclose (Fin); fclose (Fout); После закрытия файла файловую переменную можно использовать повторно, для работы с этим или другим файлом. После окончания работы программы все открытые файлы закрываются автоматически. Если файл, который открывается на чтение, не найден, возникает ошибка. Если существующий файл открывается на запись, его содержимое уничтожается. Чтение из текстовых файлов выполняет функция fscanf, а запись в файлы – функция fprintf, которые используются почти также, как и уже знакомые вам функции scanf и printf, нов первом параметре им передаётся указатель на открытый файл. В остальном чтение и запись происходит также, как и для стандартных устройств – клавиатуры и текстового экрана. Если в переменных Fin и Fout записаны указатели на файлы, открытые, соответственно, на вводи на вывод, можно написать так fscanf ( Fin, "%d%d" , &a, &b ); fprintf ( Fout, "%d+%d=%d" , a, b, a+b ); У нас получилась программа, которая складывает два целых числа, прочитанные из одного файла, и записывает результат в другой файл. Как правило, текстовый файл – это устройство последовательного доступа к данным. Это значит, что для того, чтобы прочитать е по счёту значение из файла, нужно сначала прочитать предыдущие 99. В своей внутренней памяти система хранит положение указателя (файлового курсора, который определяет текущее место в файле. При открытии файла указатель устанавливается в самое начало файла, при чтении смещается на позицию, следующую за прочитанными данными, а при записи – наследующую свободную позицию. Если нужно повторить чтение сначала файла, нужно закрыть его (с помощью функции fclose), а потом снова открыть. Когда файловый курсор указывает наконец файла, логическая функция feof (от англ. end of file – конец файла) возвращает истинное значение if ( feof(Fin) ) Данные кончились В языке C++ для работы с текстовыми файлами используются файловые потоки ввода- вывода, которые подключаются с помощью заголовочного файла fstream: #include Входной поток (файл для чтения) связан с переменной типа ifstream (от англ. input file stream – входной файловый потока выходной поток – с переменной типа ofstream (от англ. output file stream – выходной файловый поток ifstream Fin; ofstream Fout; Для открытия файла (потока) используется метода для закрытия – метод close: Fin.open ( "input.txt" ); Fout.open ( "output.txt" ); // здесь работаем с файлами Fin.close(); Fout.close(); Если поток открыт неудачно, значение переменной будет равно NULL, что можно использовать для обработки ошибки ifstream F; F.open ( "input.txt" ); if ( F ) { Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 68 22.10.2015 // здесь работаем с файлом } else printf ( Открыть файл не удалось" ); Если в переменных Fin и Fout записаны указатели на потоки, открытые, соответственно, на вводи на вывод, можно написать так Fin >> a >> b; Fout << a << "+" << b << "=" << a + b; В этом фрагменте программы складываются два целых числа, прочитанные из одного файла, и результат записывается в другой файл. Когда файловый курсор указывает наконец файла, логическая функция-метод eof (от англ. end of file – конец файла) возвращает истинное значение if ( F.eof() ) printf ( Данные кончились" ); Неизвестное количество данных Предположим, что в текстовом файле записано в столбик неизвестное количество чисел и требуется найти их сумму. В этой задаче ненужно одновременно хранить все числа в памяти (и ненужно выделять массив, достаточно читать по одному числу зараз пока не конец файла прочитать число из файла добавить его к сумме Далее будем считать, что файловая переменная Fin связана с файлом, открытым на чтение. Основная часть программы (без объявления переменных, открытия и закрытия файлов) выглядит так S = 0; while ( !feof(Fin) ) { fscanf ( Fin, "%d" , &x ); S = S + x; } S = 0; while ( !Fin.eof() ) { Fin >> x; S = S + x; } К сожалению, в программе на языке C есть одна серьёзная проблема если после последнего числа в файле стоит символ перевода строки (есть одна или несколько пустых строк, последнее прочитанное число будет учтено в сумме дважды. Дело в том, что после чтения этого числа файловый курсор еще не вышел наконец файла и условие цикла истинно. В тоже время следующее чтение заканчивается неудачно, а в переменной x остается последнее прочитанное значение, которое ещё раз добавляется к сумме. Исправить ситуацию можно так int n; S = 0; while ( 1 ) { n = fscanf ( Fin, "%d" , &x ); if ( n < 1 ) break ; S = S + x; } Здесь использован бесконечный цикл вида while ( 1 ) { ... } Так как единица соответствует истинному условию, это условие никогда не будет нарушено, так что выйти из цикла можно только с помощью оператора break. Выход происходит в том случае, когда функция fscanf не смогла прочитать данные. Это можно определить по возвращаемому значению функция scanf возвращает количество прочитанных значений. В нашем случае если прочитано меньше одного значение, то чтение закончено неудачно (данные закончились. Это Информатика, 10 класс К.Ю. Поляков, Е.А. Еремин http://kpolyakov.spb.ru 69 может случиться тогда, когда достигнут конец файла или встречен недопустимый (нецифровой) символ. Обработка массивов В текстовом файле записано не более 100 целых чисел. Требуется вывести в другой текстовый файл те же числа, отсортированные в порядке возрастания. Особенность этой задачи в том, что для сортировки нам нужно удерживать в памяти все числа, то есть для их хранения нужно выделить массив. Косвенно на это указывает ограничение – чисел не более 100. Поэтому массив должен иметь не менее 100 элементов const int MAX = 100 ; |