Решение задач программированияя

Методы решения задач программирования

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

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

Алгоритм - это основа программы, исполнитель программы - компьютер. На стадии отладки программы в роли исполнителя часто выступает сам программист.

Алгоритм должен соответствовать следующим свойствам

• понятность - исполнитель должен знать как выполняются все используемые в алгоритме команды;

• дискретность - представление алгоритма в виде последовательности шагов;

• определенность - каждая команда алгоритма должна быть четкой и не оставлять исполнителю места для самостоятельных решений;

• результативность - алгоритм должен приводить к решению задачи за конечное число шагов;

• массовость - применимость алгоритма к некоторому множеству исходных данных;

• однозначность - при повторном исполнении алгоритма к тем же исходным набором данных, должен быть получен тот же результат.

Алгоритм может быть записан с помощью блок-схемы, текстовым предписанием, с помощью рисунков, таблично или на специальном алгоритмическом языке. Наиболее популярны блок-схемы и предписания. Преимущество блок-схем — в наглядности.

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

Методика разработки алгоритмов

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

Алгоритм следует записывать аккуратно и разборчиво. Аккуратность записи есть аккуратность мысли программиста. Аккуратно записанный и детализированный алгоритм упрощает его программирование.

Программа — это описание алгоритма средствами языка программирования.

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

Трансляторы делятся на два типа: интерпретаторы и компиляторы.

Интерпретатор переводит в машинный код и выполняет очередной оператор (команду) программы. Если команда повторяется, то интерпретатор рассматривает ее как встреченную впервые.

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

Этапы решения задачи

Обобщим рассмотренные выше принципы разработки алгоритмов и выделим главные этапы решения задач.

1. Постановка задачи. Основное требование к постановке задачи – достаточное количество информации для решения задачи. Очень часто постановка задачи выполняется не программистом, а некоторым Заказчиком. Программист является Исполнителем заказа. Он должен уметь добиться от Заказчика полной информации о решаемой задаче.

2. Моделирование и формализация задачи. Цели этого этапа уже обсуждались выше в разделе методики разработки алгоритма. При моделировании важно иметь опыт программирования, знать возможности компьютера и языка программирования и выдвигать гипотезы с учетом этих возможностей. К разработке алгоритма следует приступать только после принятия гипотезы решения задачи. 
   
   Помимо идеи решения задачи, результатами этого этапа должны быть формализованная постановка задачи типа "дано-найти" и достаточное количество контрольных примеров для последующего тестирования программы. К категории "Дано:" обычно относятся данные, вводимые в начале работы программы и обеспечивающие массовость алгоритма. К категории "Найти:" относятся данные, получаемые в результате работы программы.

3. Разработка алгоритма. Этот этап представляет собой реализацию идеи решения задачи.

4. Тестирование алгоритма. Этап предполагает проверку алгоритма вручную с использованием подготовленных ранее контрольных примеров. Для сложных задач этот этап может оказаться весьма трудоемким, поэтому опытные программисты пропускают его и тестируют программу. 

1. Программирование алгоритма. Программирование является формальной записью алгоритма средствами языка программирования.

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

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

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

Постановка задачи. По кругу стоят m человек. Каждый из них имеет порядковый номер. Отсчет ведется по кругу в порядке следования номеров. Каждый n – й выходит из круга. Так продолжается до тех пор, пока не останется один человек. Определите его порядковый номер.

Разработка алгоритма решения задачи

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

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

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

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

1. В файл h записать m единиц, которые будут символизировать m человек;

2. Считывая элементы файла h, перепишем их в файл l, но если этот элемент оказывается n-м, то вместо него запишем нуль, который будет символизировать выход человека из круга;

3. Увеличим значение счетчика замен 1;

4. По достижении конца файла h, закроем его и вновь откроем для записи.

5. Перепишем в него файл l (разумеется, технично решив все вопросы с закрытием и открытием его, когда это необходимо);

6. Опять закроем и снова откроем файл h, но уже для чтения и продолжим процесс с пункта 2;

7. Этот процесс следует продолжать до тех пор, пока не случится (m-1) замена 1 на 0;

Разработанный алгоритм желательно проверить в “ручном режиме” хотя бы для одного частного случая. Предположим, что по кругу стоят 5 человек и из круга выходить каждый третий. Продемонстрируем процесс решения с помощью таблицы состояния файлов h и l после выполнения пунктов 2 - 7:

1

0

0

0

l:

1

1

1

1

1

h:

0

1

0

1

0

l:

1

1

1

1

1

h:

0

1

0

1

1

l:

1

1

1

1

1

h:

1

1

1

1

1

1

h:

Запомним, что при таких исходных данных последним из круга выйдет участник под № 4. Это нам пригодится при тестировании программы.

Теперь остается техническая сторона решения задачи. То есть, требуется написать программу.

Приведем текст программы с пояснениями

program krug;

var f,g,h,l:text;

d,i,j,k,p:integer;

m:char;

begin

assign(f,'in.txt');assign(g,'out.txt');

assign(h,'n1.txt');assign(l,'n2.txt');

reset(f);read(f,k,p);rewrite(h);

for j:=1 to k do write(h,1);

close(h);close(f);

reset(h);rewrite(l);

while d

begin

while not eof(h) do

begin

read(h,m);

if m='1' then j:=j+1;

if j=p

then

begin

write(l,'0');j:=0;d:=d+1;

end

else write(l,m);

end;

close(h);close(l);

reset(l);rewrite(h); for i:=1 to k do begin read(l,m);write(h,m);end;

close(h);close(l);reset(h);rewrite(l);

end;

erase(l);close(h);

reset(h);j:=0;rewrite(g);

while m='0' do

begin

read(h,m);

j:=j+1;

end;

write(g,j,' ost');

close(g);close(h);

erase(h);

end.

Перед испытанием программы ее следует сохранить (на всякий непредвиденный случай). В рабочей папке надо создать входящий файл с именем in.txt. Исходящий файл out.txt создавать не обязательно. Он будет создан в процессе исполнения программы. Чтобы убедиться в том, что программа работает правильно ее следует хорошенько “погонять”. Для ускорения процесса лучше создать компилированный файл программы.