Творческая работа по теме: Базовые алгоритмы

Творческий проект

тема: «Базовые алгоритмы»

Информатика:7-9 класс. Учебно-методические материалы

                        Сост. И.Г. Пантелеймонов, 10 класс, МОУ Лицей №1 им. Г.С. Титова, 2008 г.

Руководитель проекта:  Тимофеева Л.А., учитель информатики

1. Алгоритм  и его свойства

Понятие алгоритма так же фундаментально для информатики, как и понятие информации. Поэтому в нем очень важно как следует разобраться. Само слово «алгоритм» происходит от имени выдающегося математика средневекового Востока Мухаммеда аль-Хорезми (787-850). Им были предложены приемы выполнения арифметических вычислений с многозначными числами (вам они хорошо знакомы из школьной математики). Позже в Европе эти приемы назвали алгоритмами, от Algorithmi — латинского написания имени аль-Хорезми. В наше время понятие алгоритма понимается шире, не ограничиваясь только арифметическими вычислениями.

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

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

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

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

Играют двое. Перед ними 21 предмет, допустим, камни (также может быть 11, 16, 26 и т.д.). Игроки берут камни по очереди. За один ход можно взять 1-2-3-4 камня. Проигрывает тот, кто забирает последний камень.

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

алг Игра Баше

нач

1. Предоставить ход сопернику
2. Взять столько камней, чтобы в сумме с предыдущим
   ходом соперника получилось 5
3. Если остался один камень, то объявить о своем выигрыше, иначе вернуться к выполнению команды 1

кон

Игрок, строго следующий этому алгоритму, будет всегда выигрывать, даже если он не понимает, почему так происходит. В приведенном примере используется символика учебного Алгоритмического языка (ЛЯ).

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

Всякий алгоритм составляется в расчете на конкретного исполнителя с учетом его возможностей. Для того, чтобы алгоритм был выполним, нельзя включать в него команды, которые исполнитель не в состоянии выполнить. Нельзя повару поручать работу токаря, какая бы подробная инструкция ему не давалась. У каждого исполнителя имеется свой перечень команд, которые он может исполнить. Такой перечень называется системой команд исполнителя алгоритмов (СКИ). Каждая команда алгоритма должна определять однозначное действие исполнителя. Это требование называется точностью алгоритма. 

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

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

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

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

Дано: катеты прямоугольного

треугольника а=3см;  Ь=4см. Найти: гипотенузу с=?

Алгоритм решения этой задачи можно представить в таком виде:

алг Гипотенуза нач

1. Возвести а в квадрат.
2. Возвести b в квадрат.
3. Сложить результаты действий 1 и 2.
4. Вычислить квадратный корень из результата
   3-го действия и принять его за значение с

кон.

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

Если алгоритм обладает перечисленными выше свойствами, то работа по нему будет производиться исполнителем формально (то есть без всяких элементов творчества с его стороны). На этом основана работа программно-управляемых исполнителей-автоматов,  например,  промышленных роботов. Робот-манипулятор может выполнять работу токаря, если он умеет делать все операции токаря (включать станок, закреплять резец, перемещать резец, замерять изделие). От исполнителя не требуется понимание сущности алгоритма, он должен лишь точно выполнять команды, не нарушая их последовательности. А что такое программа? Отличается ли чем-то программа от алгоритма? Программа — это алгоритм, записанный на языке исполнителя. Иначе можно сказать так: алгоритм и программа не отличаются по содержанию, но могут отличаться по форме. Для алгоритма строго не определяется форма его представления. Алгоритм можно изобразить графически, можно — словесно, можно — какими-нибудь специальными значками, понятными только его автору. Но программа дожна быть записана на языке исполнителя.

2 Формы представления алгоритма

 1.Словесный алгоритм – оформляется с помощью словесных команд

Задание 1.  Выполните последовательность команд.

1.Построить квадрат 12 клеточек в ширину и 12 клеточек в длину.

2.Найди верхний левый угол.

3.Отступи вправо 4 клетки и вниз 5 клеток.

4.Двигаясь по часовой стрелке, нарисуй квадрат со стороной 6 клеток.

5.Найди верхний левый угол квадрата.

6.Отступи вправо и вверх на 3 клеточки.

7.Поставь точку.

8.Соедини эту точку с верхними уголками квадрата.

9.Найди верхний левый угол квадрата.

10.Отступи 2 клетки вправо и 2 клетки вниз.

11.Двигаясь по часовой стрелке, нарисуй квадрат со стороной 2 клетки.

12.Раздели маленький квадрат на 4 квадрата.

Вопрос: Что в результате мы построили?  (Ответ:______________________)

2. Графический алгоритм  - оформляется с помощью геометрических фигур, которые кодируют действия исполнителя.

4. Программа – фиксированная система обозначения для описания алгоритмов и структур данных.   

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

Program Bit;

var A, B,С:real;

  begin

     writeln(‘Какое число больше?’);

     writeln(‘Введите значения A, B’);

     readln(A, B);

      if A>B then C:=A  else  C: = B;

     writeln(‘Результат:’,C)

  end.

3 Формы организации действий в алгоритме  

1) Линейный алгоритм – действия в алгоритме  выполняются последовательно

Задача. Вычисление скорости движения объекта. Язык программирования Паскаль

Program dvie;

{            вычисление скорости              }

var

    v,s,t:real;

begin

        writeln(‘введите значение:)

        readln(s);

        writeln(‘введите значение:’);

        readln(t);

{результат}

v = s/t;

write(‘Скорость объекта:’,v)

end

2) Алгоритм с ветвящейся структурой – действия в алгоритме выполняются в зависимости от условия.

Задача.  Вычисления большего числа.

Program Bit;

var A, B:integer;

  begin

     writeln(‘Вычисление А и В’);

     writeln(‘Введите значения для A, B’);

     readln(A, B);

      if A>B then A:=A + 1  else  B: = B + 1;

     writeln(‘Результат:’, A,B)

  end.

3) Циклический алгоритм – действия многократно повторяются в зависимости от условия.  

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

1 способ – цикл с «предусловием»

Program zkl1;

{  выдаем слово 5 раз }

var

N,i:integer;

begin

  i:=1;

    while i<=5 do

    begin

     writeln('->');

     readln(N);

     writeln(N);

     i:=i+1;

    end;

 end.

2 способ – цикл с «постусловием»

Program zkl2;

{  выдаем слово 5 раз }

var

N,i:integer;

begin

  i:=1;

   repeat

     writeln('->');

     readln(N);

     writeln(N);

     i:=i+1;

    until i>5;

 end.

3 способ – цикл с «переменной

Program zkl1;

{  выдаем слово 5 раз }

var

N,i:integer;

begin

    for i:=1 to 5 do

    begin

     writeln('->');

     readln(N);

     writeln(N);

     end;

 end.

4 Базовые алгоритмы. Язык программирования Borland Pascal 7.0

1) Алгоритм печати чисел Фибоначчи

Program z_b2;                                                                

{ печать чисел Фибоначчи, N<=144}                                            

var                                                                          

   i,a,b,c:integer;                                                          

   begin                                                                    

     writeln('ЧИСЛА ФИБОНАЧЧИ:');                                            

     a:=1;   b:=1;  writeln(a); writeln(b);                                

     repeat                                                                

          c:=a+b;                                                            

          a:=b;                                                              

          b:=c;                                                              

          writeln(b);                                                        

     until b>=144;                                                          

  end.                                                                      

2) Решение квадратного уравнения

Program kwa;

{решение квадратного уравнения}

var

a,b,c,x1,x2,d:real;

begin

  writeln('введите коэффициенты:');

  readln(a,b,c);

    if a=0 then writeln('уравнение вырождено');

    if a<>0 then

      begin

       d:=b*b-4*a*c;

        if d<0 then writeln('корней нет');

        if d=0 then writeln('корни кратные x1,x2:',-b/(2*a));

        if d>0 then

        begin

          x1:=(-b-sqrt(d))/(2*a);

          x2:=(-b+sqrt(d))/(2*a);

          writeln('корней уравнения х1=',x1:7:2,'x2=',x2:7:2);

        end;

     end;

end.

3) Алгоритм определения ФАКТОРИАЛА от числа

Program z_b4;                                                              

{Определение ФАКТОРИАЛА от числа}                                          

 var                                                                      

   f,n,r:integer;                                                          

   begin                                                                  

      Write('введите число: ');                                          

      readln(n);                                                          

      f:=1;                                                                

      r:=1;   {переменная цикла}                                          

      while r<=n do                                                        

        begin                                                            

          f:=f*r;                                                          

          r:=r+1                                                          

        end;                                                            

   writeln('Факториал от введенного числа F(N)=N!:',f)                    

  end.    

4) Алгоритм поиска наибольшего и наименьшего значений в одномерном массиве

Program z_b1;                                                                

{поиск максимального и минимального значений}                                

var                                                                          

 a:array[1..10] of integer;                                                  

 max,min,i:integer;                                                          

  begin                                                                      

    Writeln('присвоить значения элементам массива');                        

      for i:=1 to 10 do readln(a[i]);                                        

    {анализ}                                                                  

   max:=a[1];    min:=a[1];                                                  

   for i:=2 to 10 do                                                          

      begin                                                                  

           if a[i]>max then max:=a[i];                                        

           if a[i]<=min then min:=a[i];                                      

      end;                                                                    

   writeln('минимальное:',min,'максимальное:',max)                            

   end.    

5) Алгоритм определения количества положительных значений в массиве Z(8)

 Program k_p;

var

i,к: integer;

z:array[l..8] of integer; begin k:=0;  

for i:=l to 8 do

 begin

   writeln('->');

   readln(z[i]);

     if z[i]>0 then k:=k+1;

end;

writeln('количества положительных значений:',k)

end.

6) Алгоритм транспонирования матрицы

Program z2_ll;

{транспонирование матрицы }

Const

N=3;

var

a:array[l..N,l..N] of word;

 b:array[l..N,l..N] of word;

i,k: integer;

begin

   randomize;

      for i:=l to N do begin

      for k:=l to N do begin

      a[i,k]:=random(100)+l;

      b[k,i]:=a[i,k];

   write(a[i,k]:4);

           end;

        writeln;

          end;

  {транспонирование}

writeln;

      for i:=l to N do begin

      fork:=l to N do begin

          a[i,k]:=b[i,k];

          write(a[i,k]:4);

       end;

   writeln;

   end;

end.

7) Алгоритм сортировки чисел  методом простого выбора по возрастанию

X – рабочая переменная

Если а(n) >= a (n+1), то  X = a(n),  a(n)=a(n+1),   a(n+1) = X

Исходный числовой ряд:                2.3    7.8    3.6    2.3     1.4

Первый проход, результат:            1.4     7.8    3.6    2.3    2.3

Второй проход, результат:             1.4     2.3    7.8    3.6    2.3

Третий проход, результат:             1.4     2.3     2.3    7.8   3.6

Четвертый проход, результат:       1.4     2.3     2.3    3.6   7.8  

Program sort;                                                            

{сортировка методом простого выбора}                                      

Const  {раздел констант}                                                

     N=5;                                                                

a:array[1..N] of real=(2.3,7.8,3.6,2.3,1.4);                              

Label  { раздел меток}                                                    

     met;                                                                

var    {раздел переменных}                                              

    i,k:integer;                                                          

    x:real;                                                              

begin                                                                    

   {сортировка}                                                          

 for i:=1 to 4 do                                                        

   begin                                                                  

     for k:=i+1 to 5 do                                                  

       begin                                                              

         if a[i]

            x:=a[i];                                                      

          a[i]:=a[k];                                                    

          a[k]:=x;                                                        

         met:                                                            

      end;                                                              

   end;                                                                  

{результат}                                                              

 for i:=1 to 5 do                                                        

    write(a[i]:5:1)                                                      

 end.                                                                    

8) Использование вспомогательного алгоритма. Алгоритм использования процедур и функций

program stper;

{возведение в степень и перевод кб->биты } var

st,z,S,per,i:integer; L:longint;

procedure WST(x,y:integer;var ST:integer); begin ST:=1;

for i:=l to у do

    ST:=ST*x;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    

end;

function CH(z:longint):longint; var

m:Iongint; begin

   m:=z*1024*8;

   CH:=m;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        

end;

{главный алоритм} begin

    writeln('введите число и степень:'); readln(n,st); writeln('результат:'); WST(n,st,S);

   writeln('введите число для перевода:'); readln(L); per:=CH(L);

   writeln('число в битах:',реr)

 end.

 9) Алгоритм определения площади четырехугольника

Program z_1;

var

x,y,z,t,g,Pl,P2,P:real;

procedure Geron(a,b,c:real;var S:real);

var p:real;

begin

p:=(a+b+c)/2;

S:=sqrt(p*(p-a)*(p-b)*(p-c));

end;

 begin

  writeln('введите длины сторон треугольника 1:');

   readln(x,t);

   g:=sqrt(x*x+t*t);

  Geron(x,t,g,P 1); writeln(P 1);

   writeln('введите длины сторон треугольника 2:');

   readln(y,z);

Geron(y,z,g,P2); writeln(P2);

 P:=P1+P2;

writeln('площадь ч-х угольника:',Р);

end.

5 Работа с файлами. Чтение и запись информации

Команды работы с файлами:

Rewrite(f) – открытие файла на запись

Writeln(f,n) – запись значения переменной n в файл f

Eof(f) – определяет наличие команды конца файла ( код – 26)

Not – логическое НЕ

Задача 5.1 Разработать компьютерную модель определения максимального и минимального значения в массиве D(7). Ввод информации из файла – b.in,  вывод  - b.out.

Формат входных данных, b.in:                                 Формат выходных данных, b.out:

1                                                                                     max = 300  min = 1

4

5

300

89

2

7

    Program maxmin;                                                   Алгоритм работы в среде:

   {определение max, min}                                        1.Загрузить среду программирования                                

  var                                                                             2.Создать текстовой файл b.in

     i,max,min:integer;                                                 3.Ввести программу                  

    d:array[1..7] of integer;                                            4.Отладка, тестирование

 f1,f2:text;                                                       5.Открыть файл результата  b.out                                        

 begin                                                                          6.Анализ результатов.        

   assign(f1,'b.in');                                                        

   reset(f1);                                                              

   i:=1;                                                                      

     while Not Eof(f1) do                                                    

       begin                                                                

         readln(f1,d[i]);                                                    

         i:=i+1;                                                            

       end;                                                                  

   max:=d[1];  min:=d[1];                                                    

     for i:=1 to 7 do                                                        

     begin                                                                    

       if d[i]>max then max:=d[i];                                            

       if d[i]<=min then min:=d[i];                                          

     end;                                                                    

    close(f1);  assign(f2,'b.out');  rewrite(f2);                            

    writeln('max=',max,'  min=',min);                                        

    writeln(f2,'max=',max,' min=',min);                                      

    close(f2);                                                                

   end.

Задача. Написать программу определения среднего - арифметического чисел, вводимых из файла b.in, вывод результата в файл – b.out

Program Sred;

{Среднее-арифметическое}

var

  i:integer;

  sr,s,n:real;

  f1,f2:text;

  begin

    s:=0;

    assign(f1,'b1.in'); reset(f1);

    i:=0;

    while Not Eof(f1) do

      begin

        readln(f1,n);

        s:=s+n;

        i:=i+1;

      end;

     sr:=s/i;   close(f1);

     assign(f2,'b1.out'); rewrite(f2);

     writeln(f2,'среднее:',sr);

     writeln('среднее:',sr);  close(f2)

     end.

6 Обработка символьных величин

1) Сборка нового слова из набора слов

program z1;

{сборка слова}

var

st1,st2:string;

i,k:integer;

begin

  writeln('введите количество слов');

  readln(k);

  st1:='';

   for i:=1 to k do

     begin

     writeln('->');

     readln(st2);

     st1:=st1+st2[1];

    end;

 writeln('новое слово:',st1)

 end.

2) Диалоговая программа: вводимое слово палиндром или нет

program z2;

{диалоговая программа}

var

  otv,s1,s2:string;

 l,i:integer;

  begin

  writeln('введите символьную строку');

  readln(s1);

 l:=Length(s1); s2:='';

    for i:=l downto 1 do

        s2:=s2+s1[i];

 writeln('анализ:');

 writeln(s2);

   readln;

 writeln('слово палиндром?');

   readln(otv);

   readln;

 end.

3) Алгоритм определения количества символов в строке

Program ks;

{ количество символов в строке }

var

  i,k:integer;

  st:string;

  begin

    writeln('->'); readln(st);

    for i:=1 to Length(st) do

       if copy(st,i,1)='а' then k:=k+1;

    writeln('k=',k); writeln('строка:',st)

    end.

4) Алгоритм удаления символов из строки

Program ks;

{ удаление символов }

var

  i,k:integer;

  st:string;

  begin

    writeln('->'); readln(st);

      for i:=1 to Length(st) do

        if copy(st,i,1)='а' then delete(st,i,1);

    writeln('k=',k); writeln('строка:',st)

    end.

Самостоятельная работа

1.Составьте программу вычисления степени числа а с натуральным показателем п.
(Записать варианты программы с разными видами циклов while, repeat, for).

2.Составьте программу вычисления суммы всех двузначных чисел.

3.Составьте программу вычисления факториала натурального числа n. Факториалом (n!) натурального числа n называется произведение всех чисел от 1 до n включая n.

4.Для     заданного     числа     n     составьте     программу     вычисления     суммы
S=1 + l/2+l/3+l/4+...+l/n, где n  — натуральное число

5.Дана последовательность: 1; 1+1/2; 1+1/2+1/3; 1+1/2+1/3+1/4; ...;  1+1/2+...+1/n. Составьте программу, вычисляющую первый член последовательности, превосходящий заданное число  а.

6.Каждая бактерия делится на две в течение одной минуты. В начальный момент имеется одна бактерия. Составьте программу, которая рассчитывает количество бактерий на заданное вами целое значение момента времени (15 мин , 7 мин и т.п.).

7.Составьте программу вывода на экран всех простых чисел, не превосходящих за
данного N. (Простым называется натуральное число больше единицы, имеющее только два делителя: единицу и само это число.)

8.В 1202 г. итальянский математик Леонард Пизанский (Фибоначчи) предложил та кую задачу: пара кроликов каждый месяц дает приплод — двух кроликов (самца и самку), от
которых через два месяца уже получается новый приплод. Сколько кроликов будет через
год, если в начале года имелась одна пара? Согласно условию задачи числа, соответствую-
щие количеству кроликов, которые появляются через каждый месяц, составляют последовательность 1, 1, 2, 3, 5, 8, 13,21, 34,...

9.Составьте программу, позволяющую найти все числа Фибоначчи, меньшие заданного числа N.

10.Даны координаты вершин многоугольника. Определить его периметр (вычисление расстояния между вершинами оформить подпрограммой.

11.Старинная  задача. Сколько можно купить быков, коров и телят, если плата за быка -10 рублей, за корову – 5 рублей, за телят – полтинник (0.5 рубля) и на 100 рублей надо купить 100 голов скота?

12.Курица высиживает N цыплят в год. Известно, что каждый шестой цыпленок – петушок. Цыплята-курочки год спустя становятся наседками, высиживающими цыплят, аналогично вышеупомянутой курице. Определите количество кур через Х лет (не учитывая цыплят ), если на данный момент имеется одна курица