Архив рубрики: Дополнительные материалы

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




Задача о расстановке ферзей.
Небольшая подсказка к решению задачи о расстановке 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 шаг. Копируем ссылку и добавляем её в сообщение в комментарии.

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

Занятие №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);
}

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

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

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

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

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

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);
}

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

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

Создание пустого проекта в среде Visual Studio 2010.

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

Создание пустого проекта в Microsoft Visual Studio 2010.

Запускаем среду программирования. Перед нами открывается начальная страница.
Начальная страница Visual Studio 2010
 Теперь нам нужно создать пустой проект. Для этого переходим на вкладку Файл и выбираем пункт Создать-> Проект. Либо, можно использовать "горячие клавиши" Ctrl+Shift+N.
Создаем проект.
В появившемся окошке выбираем Visual C++, а справа выбираем значок "Пустой проект" (в английской версии это Empty project ). Ниже необходимо придумать название проекту. На следующей картинке проект называется "hello world!" Тут же можно выбрать в какую папку сохранить ваш проект.

Окно основных свойств создаваемого проекта.
Теперь необходимо добавить в наш проект файл с кодом программы.
Есть несколько способов.
1. Представлен на картинке ниже. (используем обозреватель решений)
2. Используя меню "Проект"  Проект->Добавить новый элемент -> Создать элемент
3. Горячие клавиши Ctrl+Shift+A. 
 В открывшемся окне необходимо выбрать значок "Файл .cpp" а чуть ниже написать имя нашему новому файлу. На следующем рисунке новый файл имеет имя example. 
Добавление файла в проект
Нажимаем "Добавить". 


Страница редактора.
Вуаля! Все готово. Теперь можем писать код.


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

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