Все записи автора KaDeaT

Задача о расстановке ферзей. Перебор с возвратом.




Задача о расстановке ферзей.
Небольшая подсказка к решению задачи о расстановке 8 ферзей.
Суть задачи. Необходимо было найти такие расстановки восьми ферзей на обычной шахматной доске, чтобы они не били друг друга.
Стоит сразу заметить, что перебирать все возможные варианты расстановок мы не в состоянии.  Точнее можно конечно написать такую программу, но мы поступим иначе, более оптимально.
Некоторые замечания о способе хранения расстановки.
Давайте прикинем, как мы будем хранить расположение ферзей на доске. Очевидным решением было бы завести массив 8Х8 и записывать в него единицу или нуль, в зависимости от того занята ли клетка ферзем или нет.
Но давайте подумаем, так ли нам нужна вся доска? Оказывается, что нет. Вспоминаем, как ходит ферзь.  На любое количество клеток по вертикали, горизонтали или диагонали. Очевидно, что если на какой-то вертикали имеется ферзь, то поставить на эту вертикаль еще одно ферзя никак не получится, т.к. они будут бить друг друга.  
Имеет смысл хранить лишь одномерный массив из восьми элементов, каждый из которых будет соответствовать одной из вертикалей. А значение каждого элемента будет соответствовать той строке, в которой установлен ферзь. Следующий рисунок отлично поясняет этот принцип.


О проверке, находится ли поле «под боем» или нет.
Опишем математически, какие клетки шахматной доски находятся «под боем» ферзя,  установленного в клетке [i][j].
Посмотрите на следующий рисунок.
 

Пусть [i][j] – позиция ферзя, а [k][m] – координаты проверяемой клетки. 
k=I – горизонталь,
m=j – вертикаль,
k+m =i+j – восходящая диагональ,
km = ij – нисходящая диагональ.
Эти условия легко переделать под наш способ хранения расстановки ферзей.
Допустим, что уже имеется несколько установленных ферзей, которые не бьют друг друга. Какие условия налагаются на следующего ферзя?

Понятно, что нужно последовательно обработать каждую из предыдущих элементов. Пусть мы хотим поставить ферзя на позицию k.
Начинаем проверку, с первого элемента, в нём у нас записано значение восемь. Следовательно, k не должно равняться восьми, иначе оба ферзя окажутся на одной горизонтали. Кроме того, k+4 != 8+1 (условие зеленой линии), иначе мы пытаемся поставить ферзя на занятую диагональ. И наконец, k-4 != 8-1 (условие синей линии), иначе мы снова попадаем на диагональ, которая бьётся другим ферзем. Проверку условия красной линии осуществлять не нужно, так как способ представления расстановок в памяти не позволит на одну горизонталь поставить двух ферзей.
Аналогичные проверки необходимо будем произвести для всех ферзей, которые к этому моменту уже установлены на доске. Логично будет выделить эти проверки в функцию, которая принимает два аргумента – строку и столбик клетки, в которую мы хотим установить ферзя.
Основной алгоритм решения. Перебор с возвратом.
Теперь обсудим основной алгоритм реализующий расстановку ферзей. Действовать будем так, как мы действовали бы, если у нас была бы реальная доска перед глазами. 

 

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


Он должен стоять на второй горизонтали.

Поставим его в первую клетку второй вертикали. Вызов функцию проверки, даст отрицательный результат на первом же условии, так как это строка бьется ранее установленным ферзем.
Проверим вторую клетку, второй вертикали. Результат проверки неудовлетворительный, это поле тоже бьется ранее установленным ферзем.
Теперь проверим третью клетку второй вертикали, может быть она нам подойдет? Действительно подходит. Устанавливаем туда ферзя.    Переходим к установке третьего ферзя на третью вертикаль. 
 

Проверку начинаем осуществлять с 1 клетки третей вертикали.
Думаю уже очевидно, что ни первая, ни вторая, ни третья, ни даже четвертая клетки нам не подойдут, так как они бьются ранее установленными ферзями.  А вот пятая клетка, окажется в самый раз, так как её ни первый, ни второй ферзи не бьют. Значит, устанавливаем туда нашего третьего ферзя.

Аналогичным способом заполняем четвертую, пятую, шестую и седьмую вертикали.  Пока что это всё можно реализовать стандартным перебором в два цикла. Внешний цикл двигается по вертикалям от 1 до 8, а внутренний по горизонталям.
Отдельно рассмотрим установку ферзя на последней вертикали.

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

Нет необходимости, снова проверять для седьмого ферзя клетки с 1 по 6, так как они уже были проверены ранее, и первые шесть ферзей остались на своих местах. Проверив седьмую и восьмую клетки, убеждаемся, что установить в них седьмого ферзя не получится, а поэтому снова делаем возврат, и теперь уже пробуем поставить на другое место шестого ферзя. 
 Будем проверять лишь клетки с 5 по 8. Нетрудно убедиться, что ни одна из них не подходит. А значит, выполняем еще один возврат и пытаемся установить пятого ферзя на новое место.
Проверку, как вы уже наверное догадались будем начинать с третьей клетки пятой вертикали. Она нам не подойдет, так как находится под боем, причем от двух ферзей сразу, от второго и третьего. А вот четвертая клетка свободна, и поэтому в неё и будем ставить нашего ферзя.

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


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


Задача о расстановке ферзей. Перебор с возвратом.




Задача о расстановке ферзей.
Небольшая подсказка к решению задачи о расстановке 8 ферзей.
Суть задачи. Необходимо было найти такие расстановки восьми ферзей на обычной шахматной доске, чтобы они не били друг друга.
Стоит сразу заметить, что перебирать все возможные варианты расстановок мы не в состоянии.  Точнее можно конечно написать такую программу, но мы поступим иначе, более оптимально.
Некоторые замечания о способе хранения расстановки.
Давайте прикинем, как мы будем хранить расположение ферзей на доске. Очевидным решением было бы завести массив 8Х8 и записывать в него единицу или нуль, в зависимости от того занята ли клетка ферзем или нет.
Но давайте подумаем, так ли нам нужна вся доска? Оказывается, что нет. Вспоминаем, как ходит ферзь.  На любое количество клеток по вертикали, горизонтали или диагонали. Очевидно, что если на какой-то вертикали имеется ферзь, то поставить на эту вертикаль еще одно ферзя никак не получится, т.к. они будут бить друг друга.  
Имеет смысл хранить лишь одномерный массив из восьми элементов, каждый из которых будет соответствовать одной из вертикалей. А значение каждого элемента будет соответствовать той строке, в которой установлен ферзь. Следующий рисунок отлично поясняет этот принцип.


О проверке, находится ли поле «под боем» или нет.
Опишем математически, какие клетки шахматной доски находятся «под боем» ферзя,  установленного в клетке [i][j].
Посмотрите на следующий рисунок.
 

Пусть [i][j] – позиция ферзя, а [k][m] – координаты проверяемой клетки. 
k=I – горизонталь,
m=j – вертикаль,
k+m =i+j – восходящая диагональ,
km = ij – нисходящая диагональ.
Эти условия легко переделать под наш способ хранения расстановки ферзей.
Допустим, что уже имеется несколько установленных ферзей, которые не бьют друг друга. Какие условия налагаются на следующего ферзя?

Понятно, что нужно последовательно обработать каждую из предыдущих элементов. Пусть мы хотим поставить ферзя на позицию k.
Начинаем проверку, с первого элемента, в нём у нас записано значение восемь. Следовательно, k не должно равняться восьми, иначе оба ферзя окажутся на одной горизонтали. Кроме того, k+4 != 8+1 (условие зеленой линии), иначе мы пытаемся поставить ферзя на занятую диагональ. И наконец, k-4 != 8-1 (условие синей линии), иначе мы снова попадаем на диагональ, которая бьётся другим ферзем. Проверку условия красной линии осуществлять не нужно, так как способ представления расстановок в памяти не позволит на одну горизонталь поставить двух ферзей.
Аналогичные проверки необходимо будем произвести для всех ферзей, которые к этому моменту уже установлены на доске. Логично будет выделить эти проверки в функцию, которая принимает два аргумента – строку и столбик клетки, в которую мы хотим установить ферзя.
Основной алгоритм решения. Перебор с возвратом.
Теперь обсудим основной алгоритм реализующий расстановку ферзей. Действовать будем так, как мы действовали бы, если у нас была бы реальная доска перед глазами. 

 

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


Он должен стоять на второй горизонтали.

Поставим его в первую клетку второй вертикали. Вызов функцию проверки, даст отрицательный результат на первом же условии, так как это строка бьется ранее установленным ферзем.
Проверим вторую клетку, второй вертикали. Результат проверки неудовлетворительный, это поле тоже бьется ранее установленным ферзем.
Теперь проверим третью клетку второй вертикали, может быть она нам подойдет? Действительно подходит. Устанавливаем туда ферзя.    Переходим к установке третьего ферзя на третью вертикаль. 
 

Проверку начинаем осуществлять с 1 клетки третей вертикали.
Думаю уже очевидно, что ни первая, ни вторая, ни третья, ни даже четвертая клетки нам не подойдут, так как они бьются ранее установленными ферзями.  А вот пятая клетка, окажется в самый раз, так как её ни первый, ни второй ферзи не бьют. Значит, устанавливаем туда нашего третьего ферзя.

Аналогичным способом заполняем четвертую, пятую, шестую и седьмую вертикали.  Пока что это всё можно реализовать стандартным перебором в два цикла. Внешний цикл двигается по вертикалям от 1 до 8, а внутренний по горизонталям.
Отдельно рассмотрим установку ферзя на последней вертикали.

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

Нет необходимости, снова проверять для седьмого ферзя клетки с 1 по 6, так как они уже были проверены ранее, и первые шесть ферзей остались на своих местах. Проверив седьмую и восьмую клетки, убеждаемся, что установить в них седьмого ферзя не получится, а поэтому снова делаем возврат, и теперь уже пробуем поставить на другое место шестого ферзя. 
 Будем проверять лишь клетки с 5 по 8. Нетрудно убедиться, что ни одна из них не подходит. А значит, выполняем еще один возврат и пытаемся установить пятого ферзя на новое место.
Проверку, как вы уже наверное догадались будем начинать с третьей клетки пятой вертикали. Она нам не подойдет, так как находится под боем, причем от двух ферзей сразу, от второго и третьего. А вот четвертая клетка свободна, и поэтому в неё и будем ставить нашего ферзя.

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


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


Используем сервис Pastebin для сохранения и показа своих исходников.

Добрый день, друзья.
Небольшая заметка о том, как пользоваться сервисом http://pastebin.ru/
Данный сайт предлагает сохранить некоторый отрывок текста, и показать его другим.
В нашем случае он удобен тем, что позволяет не просто показывать кусок текста, а к тому же сохраняет форматирование и может подсвечивать синтаксис различных языков программирования.
А почему не продолжить писать код в комментариях?
  • При большом объеме кода, некоторые куски проглатываются. Так же проглатывается все, что записано между угловыми скобками. 
  • Мне будет гораздо легче проверять форматированный код.
  • Обилие кода, причем зачастую однотипного, увеличивает вес страницы. Чем больше текста на странице, тем дольше она загружается.
  • Я собираюсь перенести часть обсуждений в группу во Вконтакте, а там как известно тоже проблемы с форматированием кода.

Как пользоваться этим сервисом в наших нуждах.

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

Вот и всё. Всё достаточно просто.

Используем сервис Pastebin для сохранения и показа своих исходников.

Добрый день, друзья.
Небольшая заметка о том, как пользоваться сервисом http://pastebin.ru/
Данный сайт предлагает сохранить некоторый отрывок текста, и показать его другим.
В нашем случае он удобен тем, что позволяет не просто показывать кусок текста, а к тому же сохраняет форматирование и может подсвечивать синтаксис различных языков программирования.
А почему не продолжить писать код в комментариях?
  • При большом объеме кода, некоторые куски проглатываются. Так же проглатывается все, что записано между угловыми скобками. 
  • Мне будет гораздо легче проверять форматированный код.
  • Обилие кода, причем зачастую однотипного, увеличивает вес страницы. Чем больше текста на странице, тем дольше она загружается.
  • Я собираюсь перенести часть обсуждений в группу во Вконтакте, а там как известно тоже проблемы с форматированием кода.

Как пользоваться этим сервисом в наших нуждах.

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

Вот и всё. Всё достаточно просто.

Занятие №20. Некоторые особенности цикла for. Оператор последовательного вычисления.

Добрый день, друзья.
Выдалась свободная минутка, решил написать небольшой пост, по мотивам уже заданных мне ранее вопросов. Быть может кому-то эти советы, тоже будут полезны. Итак, сегодня займемся циклами.
Рассмотрим цикл for().
Как вы уже знаете, синтаксис  этой конструкции имеет следующий вид:
for(инициализация счетчика; условие; изменение счетчика)
    оператор

Кроме того, мы помним, что после цикла всегда стоит один оператор, но если нам необходимо в теле цикла выполнить несколько действий, то мы можем использовать составной оператор {}. Все что заключено в фигурные скобки, будет считаться за один единственный оператор.
Если вы еще не забыли, а это не мудрено с моей-то частотой выпуска занятий, то последнем уроке мы изучали двойные массивы. Одной из типичных задач является вывод массива размерности [N][M] на экран в виде таблицы (или матрицы) в N-строк и M столбцов. Для этой задачи очень крайне удобно использовать два вложенных цикла for. Например:
Листинг 1.
#include <stdio.h>
#include <stdlib.h>
#define N 10
#define M 8

int main(void){
    int arr[N][M];
   
    for (int i=0;i<N;i++)
        for (int j=0; j<M; j++)
            arr[i][j]=rand();
   
    for (int i=0;i<N;i++)
        for (int j=0; j<M; j++)
            printf("%d\t",arr[i][j]);
   
return (0);
}

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

#include <stdio.h>
#include <stdlib.h>
#define N 10
#define M 8

int main(void){
    int arr[N][M];
   
    for (int i=0;i<N;i++)
        for (int j=0; j<M; j++)
            arr[i][j]=rand();
   
    for (int i=0;i<N;i++){
        for (int j=0; j<M; j++)
            printf("%d\t",arr[i][j]);
        printf("\n");
    }
return (0);
}
Вот так уже лучше. Так, наша программа будет выводить все так, как нужно. Вот, посмотрите на следующую картинку.
Рис.1. Результат работы программы.

А теперь поговорим о красоте. Этот вот дополнительный перенос строки , он как шило в заднице. Из-за него одного пришлось добавить составной оператор. Некрасиво получилось. Есть ли способ этого избежать. Да, есть!
Я вам раньше не говорил, а теперь скажу. В заголовке цикла for на месте инициализации счетчика и на месте изменения счетчика, могут стоять не одна, а сразу несколько инструкций. Чтобы их туда записать нужно использовать еще один оператор, оператор последовательного выполнения – ,.  Да-да, просто запятая. 
Как это может помочь нам. Да вот как. Смотрите, мы добавляем перенос, на каждой новой итерации внешнего цикла, вот и добавим наш printf в блок изменение счетчика.
Листинг 3.
#include <stdio.h>
#include <stdlib.h>
#define N 10
#define M 8

int main(void){
    int arr[N][M];
   
    for (int i=0;i<N;i++)
        for (int j=0; j<M; j++)
            arr[i][j]=rand();
   
    for (int i=0;i<N;i++,printf("\n"))
        for (int j=0; j<M; j++)
            printf("%d\t",arr[i][j]);
       

return (0);
}

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

Рассмотрим один показательный пример. Используем для вывода двойного массива на экран  один цикл for. Это будет выглядеть например так:
Листинг 4:
#include <stdio.h>
#include <stdlib.h>
#define N 10
#define M 8

int main(void){
    int arr[N][M];
   
    for (int i=0;i<N;i++)
        for (int j=0; j<M; j++)
            arr[i][j]=rand();
   
    for (int i=0, j=0 ;i<N; j++){
        printf("%d\t",arr[i][j]);
        if (M-j==1){
           printf("\n");
           i++;
           j=-1; 
        }
    }  

return (0);
}
А на мониторе снова никаких изменений. ))
Рис.2. Результат работы программы.
Но такие штуки лучше не проворачивать, так как это может сильно запутать код. Я не буду подробно комментировать этот цикл, попробуйте разобраться самостоятельно, как он работает. Возьмите листочек и пошагово выполните его, будто бы вы компьютер.

UPD(от 2.02.14): Я говорил же вам, что этот код может запутать любого. Я и сам попался в эту ловушку. Записанный ранее код, был ошибочен. Стараниями внимательного читателя он исправлен, и теперь работает так, как ему и подобает. =))

Я не помню, рассказывал я о именованных константах, которые использую в своих примерах в этом уроке. На всякий случай расскажу еще раз.
Для объявления именованных констант служит директива #define. Её синтаксис таков
#define имя значение

Важно! Не нужно ставить в конце точку с запятой. А так же между именем и значением знак присвоения =.

Как работает эта инструкция, рассмотрим на нашем примере. Перед тем как компилятор начнет обрабатывать программу, он пройдется по всему коду и заменит все места, где встречается N или M и вместо них подставит в код их значения: 10 и 8 соответственно.  Причем компилятору вообще по барабану, что на что мы заменяем. С учетом этой особенности, некоторые используют при написании код «Боярский язык». Ну т.е. пишут код на обычном русском языке.  Например вот так.
Листинг 5.

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

#define N 10
#define M 8
#define целое int
#define присвоить =


целое main(void){
    целое arr[N][M];
   
    for (целое i присвоить 0;i<N;i++)
        for (целое j присвоить 0; j<M; j++)
            arr[i][j] присвоить rand();
   
    for (целое i присвоить 0, j присвоить 0 ;i<M,j<N;i++){
        printf("%d\t",arr[i][j]);
        if (M-i==1){
           printf("\n");
           j++;
           i присвоить 0; 
        }
    }
return (0);
}

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

На сегодня всё. Удачи вам и красивого кода. ))

Занятие №20. Некоторые особенности цикла for. Оператор последовательного вычисления.

Добрый день, друзья.
Выдалась свободная минутка, решил написать небольшой пост, по мотивам уже заданных мне ранее вопросов. Быть может кому-то эти советы, тоже будут полезны. Итак, сегодня займемся циклами.
Рассмотрим цикл for().
Как вы уже знаете, синтаксис  этой конструкции имеет следующий вид:
for(инициализация счетчика; условие; изменение счетчика)
    оператор

Кроме того, мы помним, что после цикла всегда стоит один оператор, но если нам необходимо в теле цикла выполнить несколько действий, то мы можем использовать составной оператор {}. Все что заключено в фигурные скобки, будет считаться за один единственный оператор.
Если вы еще не забыли, а это не мудрено с моей-то частотой выпуска занятий, то последнем уроке мы изучали двойные массивы. Одной из типичных задач является вывод массива размерности [N][M] на экран в виде таблицы (или матрицы) в N-строк и M столбцов. Для этой задачи очень крайне удобно использовать два вложенных цикла for. Например:
Листинг 1.
#include <stdio.h>
#include <stdlib.h>
#define N 10
#define M 8

int main(void){
    int arr[N][M];
   
    for (int i=0;i<N;i++)
        for (int j=0; j<M; j++)
            arr[i][j]=rand();
   
    for (int i=0;i<N;i++)
        for (int j=0; j<M; j++)
            printf("%dt",arr[i][j]);
   
return (0);
}

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

#include <stdio.h>
#include <stdlib.h>
#define N 10
#define M 8

int main(void){
    int arr[N][M];
   
    for (int i=0;i<N;i++)
        for (int j=0; j<M; j++)
            arr[i][j]=rand();
   
    for (int i=0;i<N;i++){
        for (int j=0; j<M; j++)
            printf("%dt",arr[i][j]);
        printf("n");
    }
return (0);
}
Вот так уже лучше. Так, наша программа будет выводить все так, как нужно. Вот, посмотрите на следующую картинку.
Рис.1. Результат работы программы.

А теперь поговорим о красоте. Этот вот дополнительный перенос строки , он как шило в заднице. Из-за него одного пришлось добавить составной оператор. Некрасиво получилось. Есть ли способ этого избежать. Да, есть!
Я вам раньше не говорил, а теперь скажу. В заголовке цикла for на месте инициализации счетчика и на месте изменения счетчика, могут стоять не одна, а сразу несколько инструкций. Чтобы их туда записать нужно использовать еще один оператор, оператор последовательного выполнения – ,.  Да-да, просто запятая. 
Как это может помочь нам. Да вот как. Смотрите, мы добавляем перенос, на каждой новой итерации внешнего цикла, вот и добавим наш printf в блок изменение счетчика.
Листинг 3.
#include <stdio.h>
#include <stdlib.h>
#define N 10
#define M 8

int main(void){
    int arr[N][M];
   
    for (int i=0;i<N;i++)
        for (int j=0; j<M; j++)
            arr[i][j]=rand();
   
    for (int i=0;i<N;i++,printf("n"))
        for (int j=0; j<M; j++)
            printf("%dt",arr[i][j]);
       

return (0);
}

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

Рассмотрим один показательный пример. Используем для вывода двойного массива на экран  один цикл for. Это будет выглядеть например так:
Листинг 4:
#include <stdio.h>
#include <stdlib.h>
#define N 10
#define M 8

int main(void){
    int arr[N][M];
   
    for (int i=0;i<N;i++)
        for (int j=0; j<M; j++)
            arr[i][j]=rand();
   
    for (int i=0, j=0 ;i<N; j++){
        printf("%dt",arr[i][j]);
        if (M-j==1){
           printf("n");
           i++;
           j=-1; 
        }
    }  

return (0);
}
А на мониторе снова никаких изменений. ))
Рис.2. Результат работы программы.
Но такие штуки лучше не проворачивать, так как это может сильно запутать код. Я не буду подробно комментировать этот цикл, попробуйте разобраться самостоятельно, как он работает. Возьмите листочек и пошагово выполните его, будто бы вы компьютер.

UPD(от 2.02.14): Я говорил же вам, что этот код может запутать любого. Я и сам попался в эту ловушку. Записанный ранее код, был ошибочен. Стараниями внимательного читателя он исправлен, и теперь работает так, как ему и подобает. =))

Я не помню, рассказывал я о именованных константах, которые использую в своих примерах в этом уроке. На всякий случай расскажу еще раз.
Для объявления именованных констант служит директива #define. Её синтаксис таков
#define имя значение

Важно! Не нужно ставить в конце точку с запятой. А так же между именем и значением знак присвоения =.

Как работает эта инструкция, рассмотрим на нашем примере. Перед тем как компилятор начнет обрабатывать программу, он пройдется по всему коду и заменит все места, где встречается N или M и вместо них подставит в код их значения: 10 и 8 соответственно.  Причем компилятору вообще по барабану, что на что мы заменяем. С учетом этой особенности, некоторые используют при написании код «Боярский язык». Ну т.е. пишут код на обычном русском языке.  Например вот так.
Листинг 5.

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

#define N 10
#define M 8
#define целое int
#define присвоить =


целое main(void){
    целое arr[N][M];
   
    for (целое i присвоить 0;i<N;i++)
        for (целое j присвоить 0; j<M; j++)
            arr[i][j] присвоить rand();
   
    for (целое i присвоить 0, j присвоить 0 ;i<M,j<N;i++){
        printf("%dt",arr[i][j]);
        if (M-i==1){
           printf("n");
           j++;
           i присвоить 0; 
        }
    }
return (0);
}

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

На сегодня всё. Удачи вам и красивого кода. ))

Занятие 19. Двумерные массивы.


Добрый день друзья.
Сегодня затронем новую тему. Двумерные массивы. Или их еще называют матрицы.   

Прочитайте улучшенную версию этого урока "Двумерные массивы".

В новой версии:

  • Ещё более доступное объяснение
  • Дополнительные материалы
  • 10 задач на программирование с автоматической проверкой решения

Что такое двумерный массив?

Двумерный массив это прямоугольная таблица с определенным количеством строк и столбиков.  Каждая строка и каждый столбик имеют свой порядковый номер. На рисунке изображен двумерный массив, который имеет 6 строк и 7 столбцов.
Рис.1. Двумерный массив. Общий вид.

Обратите внимание, что столбцы и строки нумеруются, начиная с нуля, как и в одномерных массивах.
Сразу же покажу, как объявить двумерный массив. В сущности, ничего нового. Синтаксис прост и очень похож на объявление обычного массива и любой другой переменной.  Сначала указываем тип данных, затем имя массива, а после в квадратных скобках его размерность, то есть количество строк и количество столбиков.  На рисунке ниже мы объявили двумерный массив размерностью 6 на 7.
Рис.2 Двумерный массив, объявление.

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

Следующий естественный вопрос:

Как работать с двумерным массивом?

Как и другие переменные, двумерные массивы мы можем инициализировать  при их объявлении. Для этого нам нужно указать все элементы массива. Делается это следующим образом.

Листинг 19.1
int arr [2][4] = {{1,2,4,29},{3,4,6,1}};

Записанный выше код создает массив с двумя строчками и четырьмя столбцами, и присваивает каждому элементу определенные значения. Получится вот такой массив.
Рис.3. Двумерный массив инициализированный при объявлении


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

Листинг 19.2
int arr [2][4] = {{1,2,4},{3,4}};

При таком объявлении мы получим массив, который изображен на следующем рисунке.
Рис.4. Двумерный массив, инициализированный не полностью.


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

Как работать с отдельным элементом массива.

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

Рис.5. Обращение к элементу двумерного массива.

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

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

Листинг19.3
#include <stdio.h> 
int main (){ 
      int arr [2][4] = {{1,2,4},{3,4}}; 
      for (int i=0; i<2; i++){ // 1 цикл 
            for (int j=0; j<4; j++) // 2 цикл 
                  printf("%d\t",arr[i][j]); 
            printf("\n"); 
      } 
return 0; 
}  
Данная программа, выводит последовательно все элементы массива. Результат её работы, представлен на следующем рисунке.
Рис.6. Двумерный массив. Поэлементный вывод на экран.

Как  работает вложенный цикл, вам уже должно быть понятно.
Сначала переменной i присваивается значение нуль, проверяется условие 0<2, и так как оно выполняется, программа начинает выполнять тело первого цикла. В теле первого цикла программа опять попадает в цикл, теперь уже второй. Переменной j присваивается значение 0 и проверяется условие 0<4. Оно истинно, поэтому выполняется тело второго цикла. Оно состоит из одной инструкции вывода на экран элемента arr[i][j]. Так как на данном шаге у нас i=0 j=0, то выводится значение элемент из нулевой строки и нулевого столбика. В нашем примере это элемент число 1. Тело второго цикла закончилось, происходит увеличение j на единицу j=1.
Проверка условия 1<4. Выполнение тела второго цикла: вывод на экран элемента arr[0][1] в нашем случае это 2. И так далее …
Используя вложенные циклы, мы можем и заполнять двумерные массивы.  

Зачем нужны двумерные массивы?

Двумерные массивы используются для хранения данных одинакового типа и одинаковой структуры. Приведу пример. В одном из практических заданий к прошлым урокам,  необходимо было составить программу, которая хранила оценки ученика по разным предметам. Для их хранения в памяти компьютера мы использовали несколько одномерных массивов. Это было не очень удобно. Для этих же целей, мы могли использовать двумерный массив. Например, нам нужно хранить оценки ученика по русскому, математике, физике и информатике, за целый месяц. Для этого мы создадим массив с 4 строками и 30 столбиками (или наоборот, 30 строк и 4 столбика, кому как больше нравится), и в каждую отдельную строчку будем записывать оценки по какому либо предмету. Это гораздо удобнее и практичнее.
Например, рассмотрим такую задачку. Пусть нам нужно было бы найти среднее арифметическое всех оценок по всем предметам.  Если бы у нас было четыре одномерных массива, то нам пришлось бы писать четыре цикла, в каждом из них считать среднее арифметическое оценок по одному предмету, потом  находить среднее арифметическое этих четырех чисел. Если оценки у нас хранятся в двумерном массиве, нам достаточно будет просто пройтись по всем элементам массива, используя два вложенных цикла for, и найти среднее арифметическое.
Но это еще не всё. Представьте, что вы хотите добавить один предмет и снова посчитать среднюю арифметическую оценку для всех предметов.   Сколько мороки будет, если вы храните оценки в одномерных массивах. Вам придется кучу изменений вносить, дописывать еще один цикл (а вдруг добавилось 7 предметов?). Потом еще среднее искать между этими цифрами.
Другое дело если вы храните оценки в двумерном массиве. Всего лишь изменить условие в одном из циклов. Поменять одно число, представляете как удобно?


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

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

Практическое задание.

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

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

Занятие 19. Двумерные массивы.


Добрый день друзья.
Сегодня затронем новую тему. Двумерные массивы. Или их еще называют матрицы.   

Прочитайте улучшенную версию этого урока "Двумерные массивы".

В новой версии:

  • Ещё более доступное объяснение
  • Дополнительные материалы
  • 10 задач на программирование с автоматической проверкой решения

Что такое двумерный массив?

Двумерный массив это прямоугольная таблица с определенным количеством строк и столбиков.  Каждая строка и каждый столбик имеют свой порядковый номер. На рисунке изображен двумерный массив, который имеет 6 строк и 7 столбцов.
Рис.1. Двумерный массив. Общий вид.

Обратите внимание, что столбцы и строки нумеруются, начиная с нуля, как и в одномерных массивах.
Сразу же покажу, как объявить двумерный массив. В сущности, ничего нового. Синтаксис прост и очень похож на объявление обычного массива и любой другой переменной.  Сначала указываем тип данных, затем имя массива, а после в квадратных скобках его размерность, то есть количество строк и количество столбиков.  На рисунке ниже мы объявили двумерный массив размерностью 6 на 7.
Рис.2 Двумерный массив, объявление.

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

Следующий естественный вопрос:

Как работать с двумерным массивом?

Как и другие переменные, двумерные массивы мы можем инициализировать  при их объявлении. Для этого нам нужно указать все элементы массива. Делается это следующим образом.

Листинг 19.1
int arr [2][4] = {{1,2,4,29},{3,4,6,1}};

Записанный выше код создает массив с двумя строчками и четырьмя столбцами, и присваивает каждому элементу определенные значения. Получится вот такой массив.
Рис.3. Двумерный массив инициализированный при объявлении


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

Листинг 19.2
int arr [2][4] = {{1,2,4},{3,4}};

При таком объявлении мы получим массив, который изображен на следующем рисунке.
Рис.4. Двумерный массив, инициализированный не полностью.


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

Как работать с отдельным элементом массива.

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

Рис.5. Обращение к элементу двумерного массива.

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

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

Листинг19.3
#include <stdio.h> 
int main (){ 
      int arr [2][4] = {{1,2,4},{3,4}}; 
      for (int i=0; i<2; i++){ // 1 цикл 
            for (int j=0; j<4; j++) // 2 цикл 
                  printf("%d\t",arr[i][j]); 
            printf("\n"); 
      } 
return 0; 
}  
Данная программа, выводит последовательно все элементы массива. Результат её работы, представлен на следующем рисунке.
Рис.6. Двумерный массив. Поэлементный вывод на экран.

Как  работает вложенный цикл, вам уже должно быть понятно.
Сначала переменной i присваивается значение нуль, проверяется условие 0<2, и так как оно выполняется, программа начинает выполнять тело первого цикла. В теле первого цикла программа опять попадает в цикл, теперь уже второй. Переменной j присваивается значение 0 и проверяется условие 0<4. Оно истинно, поэтому выполняется тело второго цикла. Оно состоит из одной инструкции вывода на экран элемента arr[i][j]. Так как на данном шаге у нас i=0 j=0, то выводится значение элемент из нулевой строки и нулевого столбика. В нашем примере это элемент число 1. Тело второго цикла закончилось, происходит увеличение j на единицу j=1.
Проверка условия 1<4. Выполнение тела второго цикла: вывод на экран элемента arr[0][1] в нашем случае это 2. И так далее …
Используя вложенные циклы, мы можем и заполнять двумерные массивы.  

Зачем нужны двумерные массивы?

Двумерные массивы используются для хранения данных одинакового типа и одинаковой структуры. Приведу пример. В одном из практических заданий к прошлым урокам,  необходимо было составить программу, которая хранила оценки ученика по разным предметам. Для их хранения в памяти компьютера мы использовали несколько одномерных массивов. Это было не очень удобно. Для этих же целей, мы могли использовать двумерный массив. Например, нам нужно хранить оценки ученика по русскому, математике, физике и информатике, за целый месяц. Для этого мы создадим массив с 4 строками и 30 столбиками (или наоборот, 30 строк и 4 столбика, кому как больше нравится), и в каждую отдельную строчку будем записывать оценки по какому либо предмету. Это гораздо удобнее и практичнее.
Например, рассмотрим такую задачку. Пусть нам нужно было бы найти среднее арифметическое всех оценок по всем предметам.  Если бы у нас было четыре одномерных массива, то нам пришлось бы писать четыре цикла, в каждом из них считать среднее арифметическое оценок по одному предмету, потом  находить среднее арифметическое этих четырех чисел. Если оценки у нас хранятся в двумерном массиве, нам достаточно будет просто пройтись по всем элементам массива, используя два вложенных цикла for, и найти среднее арифметическое.
Но это еще не всё. Представьте, что вы хотите добавить один предмет и снова посчитать среднюю арифметическую оценку для всех предметов.   Сколько мороки будет, если вы храните оценки в одномерных массивах. Вам придется кучу изменений вносить, дописывать еще один цикл (а вдруг добавилось 7 предметов?). Потом еще среднее искать между этими цифрами.
Другое дело если вы храните оценки в двумерном массиве. Всего лишь изменить условие в одном из циклов. Поменять одно число, представляете как удобно?


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

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

Практическое задание.

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

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

Занятие 18. Передача одномерных массивов в функцию. Возвращение массива из функции.

Добрый вечер друзья. Продолжаем изучать работу с массивами и указателями.

Сегодня научимся передавать массив в функцию и возвращать массив из функции.

Прочитайте улучшенную версию этого урока "Передача аргументов в функцию".

В новой версии:

  • Ещё более доступное объяснение
  • Дополнительные материалы
  • 12 задач на программирование с автоматической проверкой решения


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

В зависимости от этого и нужно плясать.

Первый случай. Передача в функцию статического массива. 

Для определенности будем передавать массив символов. Напишем функцию, которая принимает строку и выводит её на экран.

Листинг 18.1


void print_arr(char a[], int n){
      for (int i=0; i<n; i++)
            printf("%c",a[i]);
      printf("\n");
}


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

В скобках, не нужно указывать размерность массива. С размерностью массива вообще все не так просто. Функции в Си не умеют самостоятельно определять размерность переданного им массива. Поэтому отдельным параметром нам необходимо передавать его размер. В нашей функции мы передаем размер массива с помощью переменной n.

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

Листинг 18.2


#include <stdio.h>
#include <string.h>
void print_arr(char a[], int n){
      for (int i=0; i<n; i++)
            printf("%c",a[i]);
      printf("\n");

}
int main(){
      char arr[]="kirill";
      int t=strlen(arr);
      print_arr(arr,t);
      return 0;
}


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

Второй случай. Передача в функцию динамического массива.

Давайте решим такую задачу. имеется текстовый файл input.txt. Пусть в нем в первой строчке записано натуральное число N не превосходящее 100. А в следующих N строках записаны некоторые вещественные числа. Пусть мы хотим посчитать среднее арифметическое всех этих чисел и вывести.

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

И так напишем требуемую программу.

Листинг 18.3
#include <stdio.h>
void sa_arr(float *a, int n){
      double summ=0;
      for (int i=0; i<n; i++)
            summ+=a[i];
      printf("srednee arifmeticheskoe: %.2f\n", summ/n);
}

int main(){
      freopen("input.txt","r",stdin);
      int N;
      scanf("%d",&N);
      float *arr = new (float [N]);
      for (int i=0; i<N; i++)
            scanf("%f", &arr[i]);
      sa_arr(arr,N);
      delete []arr;
      return 0;
}


Обратите внимание на аргументы функции. Как видите, если мы передаем динамический массив, то нам нужно явно указывать на то, что функция принимает указатель на первый элемент массива. В случае одномерного массива это не критично, и вы можете объявить аргументы как и в прошлый раз, т.е.
void sa_arr(float a[], int n)
но так делать не стоит. Приучайтесь сразу передавать динамические массивы таким образом.

Теперь вернемся к нашим отличиям а так же второму вопросу.

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

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

Листинг 18.4


#include <stdio.h>
void sa_arr(float *a, int n){
      double summ=0;
      for (int i=0; i<n; i++)
            summ+=a[i];
      printf("srednee arifmeticheskoe: %.2f\n", summ/n);
      //изменим какой-нибудь элемент массива внтури функции
      a[2]=43.2;
} 


int main(){
      freopen("D:\\input1.txt","r",stdin);
      int N;
      scanf("%d",&N);
      float *arr = new (float [N]);
      for (int i=0; i<N; i++)
            scanf("%f", &arr[i]);
      //выводим массив
      for (int i=0; i<N; i++)
            printf("%f\t",arr[i]);
      printf("\n");
      sa_arr(arr,N);    
      // снова выводим массив на экран, после вызова функции
      // внутри которой, мы изменили один его элемент
      for (int i=0; i<N; i++)
            printf("%f\t",arr[i]);
      printf("\n");
      delete []arr;
      return 0; 
}

Результат работы программы на следующем рисунке.


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

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


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

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

2. Напишите функцию, которая ищет максимальный элемент в массиве.

3. Напишите функцию, которая принимает два массива одинаковой длинны и поэлементно перемножает их. Результат работы она записывает в элементы первого массива. Т.е. буквально она должна вернуть результат свой работы в первом массиве.
В программе, НЕ В ФУНКЦИИ, выведите результат на экран.

Если мы передаем массивы
[2,5,6]
[1,4,2]

то в результате своей работы, программа должна вывести
2 20 12

Занятие 18. Передача одномерных массивов в функцию. Возвращение массива из функции.

Добрый вечер друзья. Продолжаем изучать работу с массивами и указателями.

Сегодня научимся передавать массив в функцию и возвращать массив из функции.

Прочитайте улучшенную версию этого урока "Передача аргументов в функцию".

В новой версии:

  • Ещё более доступное объяснение
  • Дополнительные материалы
  • 12 задач на программирование с автоматической проверкой решения


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

В зависимости от этого и нужно плясать.

Первый случай. Передача в функцию статического массива. 

Для определенности будем передавать массив символов. Напишем функцию, которая принимает строку и выводит её на экран.

Листинг 18.1


void print_arr(char a[], int n){
      for (int i=0; i<n; i++)
            printf("%c",a[i]);
      printf("\n");
}


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

В скобках, не нужно указывать размерность массива. С размерностью массива вообще все не так просто. Функции в Си не умеют самостоятельно определять размерность переданного им массива. Поэтому отдельным параметром нам необходимо передавать его размер. В нашей функции мы передаем размер массива с помощью переменной n.

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

Листинг 18.2


#include <stdio.h>
#include <string.h>
void print_arr(char a[], int n){
      for (int i=0; i<n; i++)
            printf("%c",a[i]);
      printf("\n");

}
int main(){
      char arr[]="kirill";
      int t=strlen(arr);
      print_arr(arr,t);
      return 0;
}


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

Второй случай. Передача в функцию динамического массива.

Давайте решим такую задачу. имеется текстовый файл input.txt. Пусть в нем в первой строчке записано натуральное число N не превосходящее 100. А в следующих N строках записаны некоторые вещественные числа. Пусть мы хотим посчитать среднее арифметическое всех этих чисел и вывести.

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

И так напишем требуемую программу.

Листинг 18.3
#include <stdio.h>
void sa_arr(float *a, int n){
      double summ=0;
      for (int i=0; i<n; i++)
            summ+=a[i];
      printf("srednee arifmeticheskoe: %.2f\n", summ/n);
}

int main(){
      freopen("input.txt","r",stdin);
      int N;
      scanf("%d",&N);
      float *arr = new (float [N]);
      for (int i=0; i<N; i++)
            scanf("%f", &arr[i]);
      sa_arr(arr,N);
      delete []arr;
      return 0;
}


Обратите внимание на аргументы функции. Как видите, если мы передаем динамический массив, то нам нужно явно указывать на то, что функция принимает указатель на первый элемент массива. В случае одномерного массива это не критично, и вы можете объявить аргументы как и в прошлый раз, т.е.
void sa_arr(float a[], int n)
но так делать не стоит. Приучайтесь сразу передавать динамические массивы таким образом.

Теперь вернемся к нашим отличиям а так же второму вопросу.

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

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

Листинг 18.4


#include <stdio.h>
void sa_arr(float *a, int n){
      double summ=0;
      for (int i=0; i<n; i++)
            summ+=a[i];
      printf("srednee arifmeticheskoe: %.2f\n", summ/n);
      //изменим какой-нибудь элемент массива внтури функции
      a[2]=43.2;
} 


int main(){
      freopen("D:\\input1.txt","r",stdin);
      int N;
      scanf("%d",&N);
      float *arr = new (float [N]);
      for (int i=0; i<N; i++)
            scanf("%f", &arr[i]);
      //выводим массив
      for (int i=0; i<N; i++)
            printf("%f\t",arr[i]);
      printf("\n");
      sa_arr(arr,N);    
      // снова выводим массив на экран, после вызова функции
      // внутри которой, мы изменили один его элемент
      for (int i=0; i<N; i++)
            printf("%f\t",arr[i]);
      printf("\n");
      delete []arr;
      return 0; 
}

Результат работы программы на следующем рисунке.


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

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


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

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

2. Напишите функцию, которая ищет максимальный элемент в массиве.

3. Напишите функцию, которая принимает два массива одинаковой длинны и поэлементно перемножает их. Результат работы она записывает в элементы первого массива. Т.е. буквально она должна вернуть результат свой работы в первом массиве.
В программе, НЕ В ФУНКЦИИ, выведите результат на экран.

Если мы передаем массивы
[2,5,6]
[1,4,2]

то в результате своей работы, программа должна вывести
2 20 12