Разработка алгоритмов

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

2. Для более наглядного представления алгоритма используется графическая форма. Графическая форма - изображение алгоритма в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.(см рис 2).

3. При записи алгоритма в словесной и в графической форме допускается определенный произвол при изображении команд. Вместе с тем такая запись точна на столько, что позволяет человеку понять суть дела и исполнить алгоритм. Однако на практике в качестве исполнителей алгоритмов используются специальные автоматы – компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на понятном ему языке. Такой язык принято называть языком программирования, а форму представления алгоритма - программной.

То есть программная форма записи алгоритма – это запись на языке программирования.

Рассмотрим  пример использования данных форм записи алгоритмов:

Задание: написать алгоритм “Одеться по погоде”. Если на улице температура ниже 0, то необходимо надеть шубу, иначе – куртку.

1. Словесная  форма:

Алгоритм ПОГОДА

1. Начало
2. определить температуру воздуха
3. если температура ниже 0, то надеть шубу, иначе надеть куртку
4. Конец.

2. Программная  форма (Pascal):

• program E3;
• uses crt;
• var t: real;
• begin
• clrscr;
• writeln(‘введите температуру воздуха t=’);
• readln(t);
• if t < 0 then writeln(‘одеть шубу’) else writeln(‘одеть куртку’);
• end.

3. Графическая  форма записи:

Рис. 2 Блок схема

Мы рассмотрели  на примере алгоритма разветвляющейся конструкции в виде блок-схемы.

 

Тип алгоритма	Способы записи алгоритма
	Словесная	Графическая	Программная
Линейный алгоритм – это описание действий, которые выполняются однократно в заданном порядке.	Сложить числа 100 и 15; Из полученной суммы вычесть 20; К результату прибавить 40.		program R1; var a,b,c,d,m,n: integer; begin writeln(‘Введите 4 числа’); readln(a,b,c,d); m:=a*d; n:=b*c; writeln(‘числитель=’, m); writeln(‘знаменатель=’, n); readln end.
Разветвляющийся алгоритм – это  алгоритм, в котором в зависимости  от условия выполняется либо одна, либо другая последовательность действий.	1.неполная форма: Если на улице холодно, то нужно одеть шубу.       2.полная форма: Если на улице температура ниже 0, то одеть шубу, иначе – куртку.	1. 2.	Program R2; var a: integer; begin writeln(‘Введите число’); readln(a); if a mod 2 = 0 then writeln(‘a-четное’) else writeln(‘a-нечетное’); readln end

 

Сравнительная таблица

 

Для сравнения, рассмотрим в таблице, чем отличается разветвляющийся алгоритм от линейного.

 

 

3.  Оптимизация алгоритмов

   Каждую программу можно написать по-разному, исходя из этого, задачу программы можно решить многими способами, разными алгоритмами.

Поэтому в программировании существует такой термин, как «Оптимизация». Программа написанная с оптимизированным алгоритмом будет работать быстрее  и занимать меньше места, что не мало важно для объёмных работ.

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

Рассмотрим  одни из самых популярных алгоритмов оптимизации:

1) Пузырьковая сортировка.

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

Алгоритм состоит  из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно  сравниваются попарно и, если порядок  в паре неверный, выполняется обмен  элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим наибольшим элементом, а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).

begin 

  for j:=1 to N-1 do 

    for i:=1 to N-j do 

    begin  

       if M[i] > M[i+1] then 

       begin 

             t:=M[j]; 

             M[j]:=M[j+1]; 

             M[j+1]:=t; 

       end;  

    end;

end;

 

2) Quick Sort

Быстрая сортировка  часто называемая quicksort по имени реализации в стандартной библиотеке языка Си — широко известный алгоритм сортировки, разработанный английским Информатиком Чарльзом Хоаром в 1960 году. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов), хотя и имеющий ряд недостатков.

Краткое описание алгоритма

• Выбор элемента называется опорным
• сравнить все остальные элементы с опорным, на основании сравнения разбить множество на три — «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие – равные - большие.
• повторить рекурсивно для «меньших» и «больших».

Примечание: на практике обычно разделяют сортируемое множество  не на три, а на две части: например, «меньшие опорного» и «равные  и большие». Такой подход в общем  случае оказывается эффективнее, так  как для осуществления такого разделения достаточно одного прохода по сортируемому множеству и однократного обмена лишь некоторых выбранных элементов.

procedure qSort(var ar:array of real; low,high:integer);

var i,j:integer;

    m,wsp:real;

begin

  i:=low;

  j:=high;

  m:=ar[trunc((i+j)/2)];

  repeat

    while(ar[i]<m) do i:=i+1;

    while(ar[j]>m) do j:=j-1;

    if(i<=j) then begin

      wsp:=ar[i];

      ar[i]:=ar[j];

      ar[j]:=wsp;

      i:=i+1;

      j:=j-1;

    end;

  until (i>j);

  if(low<j) then qSort(ar,low,j);

  if(i<high) then qSort(ar,i,high);

end;

3) Решето Эратосфена

Решето Эратосфена — алгоритм нахождения всех простых чисел до некоторого целого числа n, который приписывают древнегреческому математику Эратосфену Киренскому.

Алгоритм:

Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:

1. Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
2. Пусть переменная p изначально равна двум — первому простому числу.
3. Считая от p шагами по p, зачеркнуть в списке все числа от 2p до n кратные p (то есть числа 2p, 3p, 4p, …)
4. Найти первое не зачеркнутое число, большее чем p, и присвоить значению переменной p это число.
5. Повторять шаги 3 и 4 до тех пор, пока p не станет больше, чем n.

 

Вход: натуральное число n

Пусть A — булевый  массив, индексируемый числами от 2 до n,

изначально  заполненный значениями true.

 для i := 2, 3, 4, ..., пока i^2 ≤ n:

  если A[i] = true:

    для j := i^2, i^2 + i, i^2 + 2i, ..., пока j ≤ n:

      если A[j] = true:

        A[j] := false

Теперь все  числа i, такие что A[i] = true, являются простыми.

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

 

 

 

 

Глава 3 Практическая задание

3.1 Описание  программы

Программа «Тренажер памяти» в Pascal.

 

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

При запуске  данной программы появляется выбор уровня сложности и инструкция. При нажатии на клавишу «ENTER» появляется строка с символами, которая спустя несколько секунд исчезает. Затем вам необходимо ввести как можно больше символов, которые вы запомнили. По окончании игры выводиться результат, и далее меню о продолжении либо о завершении тестирования.

 

3.2 Код программы

program testmemory;

uses crt,graphabc;

var

    n,ball,i,k:integer;

    h,l:byte;

    s,s1:string[15];

    ch:char;

    r1:real;

Begin

n:=3;

randomize;

    repeat

      begin

      writeln('Выберете уровень сложности от 2 до 15');

      readln(n);

      end;

    until (n>1) and (n<16);

 

repeat

begin

  ball:=0;                     {обнуление переменных}

  s1:='';

  s:='';

  for i:=1 to n do            {заполнение случаными буквами}

   begin

   k:=(random(26)+65);

   ch:=chr(k);

    s:=s+ch;

   end;

       writeln('Сейчас вам будет показана строка,ваша задача');

       writeln('запомнить как можно больше элементов и воспроизвести');

       writeln('по нажатию клавиши "ENTER" у вас будет 4 секунды');

       readln;

          begin

              for i:=1 to n do

                write(s[i],' ');

                delay(4000);

                clrscr;

          end;

       for i:=1 to n do

        begin

         read(ch);

         s1:=s1+ch;

        end;

   s1:=uppercase(s1);

for i:=1 to n do

  begin

    for k:=1 to n do

     begin

          if s1[i]=s[k] then

           begin

                 inc(ball);

                 break;

           end;

     end; {Вывод результата}

  end;

  r1:=ball/(n);

if r1>0.7 then writeln('Молодец! У вас отличная память!');

 if (r1<0.7) and (r1>=0.5) then writeln('У вас хорошая память!');

 if r1<0.5 then writeln('Вам следовало бы потренировать свою память!');

  writeln('Ваш результат ',ball,' из ',n);

  writeln;

  writeln('если хотите повысить уровень сложности то "u"');

  writeln;

  writeln('если понизить уровень сложности "l"');

  writeln;

  writeln('Если хотите поменять уровень сложности нажмите "r" ');

  writeln;

  writeln('Если вы хотите выйти из игры, то нажмите "g";');

             repeat

                 readln(ch);

             until (ch='u') or (ch='l') or (ch='g') or (ch='r');

   if ch='u' then n:=n+1;

   if (ch='l') and (n>2) then n:=n-1;

   if ch='r' then

      begin

            writeln('введите уровень сложности от 2 до 15');

            readln(n);

      end;

   clrscr;

  end;

  until ch='g';

End. 
Заключение

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

1. Изучена, история развития алгоритмов.
2. Разобраны способы написания алгоритма, его составляющих.
3. Сформировали некоторое представление об алгоритмах в целом.

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

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

 

Литература

1. Брудно А. Л., Каплан Л. И. Московские олимпиады по программированию.
2. Газета «Информатика», №35, 1997г.
3. Гейн А.Г. и др. Основы информатики и вычислительной техники.      М., Просвещение, 1994.
4. Гейн А. Г., Шолохович В.Ф. Преподавание курса “Основы информатики и вычислительной техники” в средней школе. Руководство для учителя.
5. Информатика. Еженедельное приложение к газете “Первое сентября”. 1998.
6. Извозчиков В.А. Информатика в понятиях и терминах.
7. Каныгин Ю. М., Зотов Б. И. «Что такое информатика?»
8. Касаткин В.Н. Информация, алгоритмы, ЭВМ. М., Просвещение, 1991.
9. Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. М., Энергоатомиздат, 1988.
10. Нестеренко А. В. ЭВМ и профессия программиста. М., Просвещение, 1990.
11. Радченко Н. П. Ответы на вопросы выпускных экзаменов. – Информатика и образование, 1997, №4.7. 8. М., Детская литература, 1989.
12. Шауцуков Основы информатики в вопросах и ответах.