Как составить псевдокод по блок схеме

Понятие об алгоритмах. Псевдокод. Блок-схемы.

Вначале пару слов: у нас сегодня радостный день (ну, не знаю, как у вас, а у меня – точно), т.к. у меня появился помошник в написании уроков VB. Прошу любить и жаловать – с сегодняшнего дня с вами – Dusk!!! Он согласился взять на себя тяжкий труд по подбору и сочинению заданий для уроков. Dusk, большое спасибо, ты  значительно мне помогаешь. В том числе-морально.

Предыдущий урок С,—-Следующий урок С ///предыдущий урок VB—-следующий урок VB

Эпиграф.

Ученые проводят опыт. Под потолком подвешен вне досягаемости банан и бутылка водки. Испытуемые – шимпанзе и алкоголик. В углу лежит ящик. Обезьяна пару раз подпрыгивает, останавливается, потом идет к ящику, ставит его под банан, достает и ест. Пьяница прыгает дальше. Ученые сжалились и стали подсказывать: “Да ты погоди, постой, подумай!..” На что получили ответ: “Что тут думать! Прыгать надо!!!”

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

Для программиста алгоритм всегда был важнее языка, т.к. он показывает как сделать, а язык – как это написать. Непонятно в чем разница? Разберемся.

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

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

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

Очень часто начинающие программисты ахают и открывают рты, когда маститые мэтры бросают через плечо: “Да какая разница на чем писать!” Понятно, эту фразу очень трудно понять, когда ты еще путаешься в элементарных синтаксических правилах одного языка, а остальные ощущаются как какие-то неподъемные громады в тумане: нечто неясное и аморфное… И очень неясно зачем писать какие-то алгоритмы непонятные… Код надо писать, код! А если неправильно написали, мы чего-нибудь исправим, и опять запустим, и так пока не заработает.

О! В таком виде работа очень напоминает приведенный эпиграф. Прямо один в один!

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

Итак, алгоритм – это последовательность операций (в обычной жизни – действий). Что за чем мы должны сделать, чтобы получить какой-то результат. На самом деле мы уже знакомились с составлением алгоритмов, во всяком случае те, кто читал Вводную лекцию по курсу программирования для начинающих. Напомню – посмотрите задание 1. То, что в нем предлагалось вам сделать, и было написанием алгоритма.

Мне тут подсказывает Сашок, что можно привести хороший пример для сравнения языка с алгоритмом: сделать то же описание похода на кухню по-русски, по-английски и, скажем, по-японски. Алгоритм один и тот же, языки – разные. Выучил новый язык – можешь описать и на нем. Но если не в силах просто членораздельно описать, как пройти на кухню, тогда за программирование лучше и не браться. Даже на самом простом языке.

Каким должен  быть алгоритм?

• Правильным или результативным. То есть, он должен обеспечивать такую последовательность действий, которая позволит вам достичь результата. Если вы, описывая алгоритм утреннего вставания-одевания, опустите операцию “взять одежду в руки”, удастся вам одеться? Сомневаюсь, если только вы не фея. Следовательно, такой алгоритм будет неверным без одной-единственной операции.
• Однозначным. Он должен быть написан так, чтобы не было возможности не единственным образом толковать правила и порядок выполнения действий.
• Эффективным. То есть, он должен достигать результата максимально удобным и коротким способом. Например, если взять тот же алгоритм “как дойти до кухни из комнаты”, то можно сделать это не одним способом. Можно (коротко говоря) выйти из комнаты в коридор, а из него попасть в кухню. А можно вылезти в окно (если вы живете на первом этаже, а если не на первом, то возможностей масса: вылезти по веревке, спуститься, как Тарзан, по балконам соседей, по пожарной лестнице, или придумать что-нибудь покруче в стиле американских экшенов), пробежать/пройти по земле до подъезда, подняться по лестнице или лифтом, открыть свою дверь ключом или позвонить, чтобы кто-то ее открыл и войти на кухню. Итак, цель достигнута в обоих случаях. А про эффективность, думаю, все ясно А про то, что программа, сделанная по неэффективному алгоритму работает во много раз дольше?

Как записать алгоритм.

записывать алгоритмы можно любым удобным способом, лишь бы понятно было.

• Алгоритмический язык. Хорошо, мы уже выяснили, что алгоритм от языка не зависит. А как же его можно записать? А как мы описывали алгоритм, когда делали задание 1? Правильно, на своем собственном языке. Мы просто описывали – что за чем нужно делать. Обычными словами разговорной речи. Но, наверно, вы заметили, что  описания, которые у нас получились – это весьма сдержанный, усеченный вариант речи в котором отсутствуют ненужные красивости и, главное, неоднозначности. Получаем так называемый псевдокод. Это язык описания алгоритмов, искусственный, неформальный (то есть, пишешь так, как тебе удобно, только чтобы другие понимали, если ты работаешь не один).
• Блок-схема. Алгоритм может быть записан графически. Для этого и служит блок-схема. Для изображения операций в ней используются специальные символы. Познакомимся с основными из них.

	Начало или конец. Внутри фигуры пишут начало (или begin – кому как нравится) или конец (end) соответственно. Если вы рисуете не всю схему, а только кусок ее, который нужно расписать подробнее, можете ограничиться маленьким кружочком.
	В прямоугольнике находится операция. Можно написать ее словами (например: умножить х на у), а можно кусочком кода с оператором (х*у)
	Если вы хотите указать, что одно из действий сложное, и его хорошо бы разбить на ряд более простых, и вы выносите его как подзадачу в отдельное место – обозначьте такое действие так.
	Внутри ромба пишутся проверяемые условия (урок С6, урок VB 8). Обычно после проверки условий последовательность операторов перестает быть конструкцией следования и становится конструкцией выбора либо повторения. (следующие уроки будут посвящены именно этим конструкциям)
	Так обозначается введение входных параметров, а также выходных. Допустим, вы вынесли отдельно блок операторов и теперь хотите его расшифровать. Но для его работы нужно ввести определенные данные. Их вы напишете справа от этой скобки. То же относится к данным, которые вам нужно получить по окончании работы программы или части кода.

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

Последовательность операторов изображается стрелочками, соединяющими блоки. Например вот так:

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

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

• Специальные алгоритмические таблицы. Один из примеров таких таблиц является таблица процедур, которая испрользуется для визуальных сред программирования из-за специфики: изначального разделения программы по процедурам обработки событий. Пишутся они следующим образом: в одном столбце пишется название процедуры, во втором столбце – описание этой процедуры как можно более полное, со всеми названиями компонентов, которые участвуют в этой процедуре. Например, если взять ту маленькую программку, которую вам предлагали сделать в курсе VB, где было 2 кнопки – включение звука и выход их программы, то для нее таблица процедур должна выглядеть так:

название процедуры	описание этой процедуры
CmdSound_Click	При щелчке мышью на кнопке cmdSound вызывается звуковой сигнал
CmdEnd_Click	При щелчке мышью на кнопке cmdEnd приложение заканчивает работу.

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

Приложение от Dusk-а.

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

• Поставь машину на ручной тормоз
• Достань домкрат
• Сними колпак
• Ослабь болты на колесе
• Подними машину на домкрате
• Выверни болты
• Сними колесо
• Достань запасное колесо
• Одень запасное колесо на место
• Вверни болты
• Опусти домкрат
• Затяни болты
• Одень колпак
• Положи домкрат и спустившееся колесо в багажник

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

В представленном виде можно отображать линейную структуру (когда действие происходит одно за другим без выбора). А если на колесах вашей машины нет колпаков, тогда вам эта программа не подойдет. Поэтому в реальных программах часто встречаются механизмы принятия решения, и отображать их лучше в виде блок-схем. Для примера представлена блок-схема “Как поджарить яичницу”:

Задание.

• Написать алгоритмы и блок-схемы программ, которые вы делали в курсе раньше. Для VB – сделать таблицу процедур.
• Попробуйте составить блок-схему программы “Как перейти дорогу”.

A Pseudocode is defined as a step-by-step description of an algorithm. Pseudocode does not use any programming language in its representation instead it uses the simple English language text as it is intended for human understanding rather than machine reading.
Pseudocode is the intermediate state between an idea and its implementation(code) in a high-level language.

What is the need for Pseudocode

Pseudocode is an important part of designing an algorithm, it helps the programmer in planning the solution to the problem as well as the reader in understanding the approach to the problem. Pseudocode is an intermediate state between algorithm and program that plays supports the transition of the algorithm into the program.

How to write Pseudocode?

Before writing the pseudocode of any algorithm the following points must be kept in mind. 

• Organize the sequence of tasks and write the pseudocode accordingly.
• At first, establishes the main goal or the aim. 

  Example:

  This program will print first N numbers of Fibonacci series.

• Use standard programming structures such as if-else, for, while, and cases the way we use them in programming. Indent the statements if-else, for, while loops as they are indented in a program, it helps to comprehend the decision control and execution mechanism. It also improves readability to a great extent.

  Example:

  IF “1”
     print response
         “I AM CASE 1”

  IF “2”
     print response
         “I AM CASE 2”

• Use appropriate naming conventions. The human tendency follows the approach of following what we see. If a programmer goes through a pseudo code, his approach will be the same as per that, so the naming must be simple and distinct.
• Reserved commands or keywords must be represented in capital letters.

  Example: if you are writing IF…ELSE statements then make sure IF and ELSE be in capital letters.

• Check whether all the sections of a pseudo code are complete, finite, and clear to understand and comprehend. Also, explain everything that is going to happen in the actual code.
• Don’t write the pseudocode in a programming language. It is necessary that the pseudocode is simple and easy to understand even for a layman or client, minimizing the use of technical terms.

Good vs Bad ways of writing Pseudocode:

Pseudocode Examples:

1. Binary search Pseudocode:

Binary search is a searching algorithm that works only for sorted search space. It repeatedly divides the search space into half by using the fact that the search space is sorted and checking if the desired search result will be found in the left or right half.

Example: Given a sorted array Arr[] and a value X, The task is to find the index at which X is present in Arr[].

Below is the pseudocode for Binary search.

BinarySearch(ARR, X, LOW, HIGH)
       repeat till LOW = HIGH
              MID = (LOW + HIGH)/2
              if (X == ARR[mid])
                  return MID

                      else if (x > ARR[MID]) 
                  LOW = MID + 1

                      else                  
                  HIGH = MID – 1

2. Quick sort Pseudocode:

QuickSort is a Divide and Conquer algorithm. It picks an element as a pivot and partitions the given array around the picked pivot.

Say last element of array is picked as pivot then all elements smaller than pivot element are shifted on the left side of pivot and elements greater than pivot are shifted towards the right of pivot by swapping, the same algorithm is repeatedly followed for the left and right side of pivot until the whole array is sorted.

Below is the pseudocode for Quick sort

QUICKSORT(Arr[], LOW, HIGH) {
   if (LOW < HIGH) {
       PIVOT = PARTITION(Arr, LOW, HIGH);
       QUICKSORT(ARR, LOW, PIVOT – 1);  
       QUICKSORT(ARR, PIVOT + 1, HIGH); 
   }
}

Here, LOW is the starting index and HIGH is the ending index.

Difference between Algorithm and Pseudocode

Algorithm	Pseudocode
An Algorithm is used to provide a solution to a particular problem in form of a well-defined step-based form.	A Pseudocode is a step-by-step description of an algorithm in code-like structure using plain English text.
An algorithm only uses simple English words	Pseudocode also uses reserved keywords like if-else, for, while, etc.
These are a sequence of steps of a solution to a problem	These are fake codes as the word pseudo means fake, using code like structure and plain English text
There are no rules to writing algorithms	There are certain rules for writing pseudocode
Algorithms can be considered pseudocode	Pseudocode cannot be considered an algorithm
It is difficult to understand and interpret	It is easy to understand and interpret

Difference between Flowchart and Pseudocode

Flowchart	Pseudocode
A Flowchart is pictorial representation of flow of an algorithm.	A Pseudocode is a step-by-step description of an algorithm in code like structure using plain English text.
A Flowchart uses standard symbols for input, output decisions and start stop statements. Only uses different shapes like box, circle and arrow.	Pseudocode uses reserved keywords like if-else, for, while, etc.
This is a way of visually representing data, these are nothing but the graphical representation of the algorithm for a better understanding of the code	These are fake codes as the word pseudo means fake, using code like structure but plain English text instead of programming language
Flowcharts are good for documentation	Pseudocode is better suited for the purpose of understanding

1. Infosys Pseudocode Questions:

What will be the output of the following pseudocode?

Question 1) for i=0 to 4 step 1 do
                           If  i==i++ + –i then do
                                  display i
                           end-if
                     end-for
Answer: 0

Question 2)  Set Character c = ‘7’
                                    switch(c)
                                    case ‘1’: display “One”
                                    case ‘7’: display “Seven”
                                    case ‘2’: display “Two”
                                    default: display “Hello”
                                    break
                           end-switch 
Answer: SevenTwoHello

Question 3) Integer a, p
                   Set a = 5
                   a = a + 1
                   a = a * 2
                   a = a / 2
                   p = a / 5 + 6
                   print p 
Answer: 7

Question 4) Integer a, b, c
                    Set b = 40, a = 20, c = 20
                    a = a + c
                    c = c + a
                    a = a + c
                    c = c + a
                    Print a + b + c 
Answer: 300

Question 5) Integer a, b, c
                    Set a = 4, b = 3, c = 1
                    if (a >> (c – 1) && b << (c + 1))
                           a = a + c
                    Else
                          b = a <<< C
                    End if
                    Print a – b + c           
Answer: 3                                                               

2. Accenture Pseudocode Questions:

What will be the output of the following pseudocode?

Questions 1) What will be the output of the following pseudocode for a = 5, b = 1?

                      Integer funn(Integer a, Integer b)
                      if(b + a || a – b) && (b > a) && 1)
                          a = a+b+b-2
                          return 3-a
                      Else
                          return a-b+1
                      End if
                      return a + b
                      End function fun()
Answer: 5

Questions 2) What will be the output of the following pseudocode for a = 5, b = 1?

                       Integer funn(Integer a, Integer b)
                       if((b mod a && a mod b) || (a ^ b > a))
                                a=a ^ b
                       Else
                                return a-b
                       End if
                       return a + b
                       End function funn()
Answer: 5

Questions 3) What will be the output of the following pseudocode?

                      Integer a, b, c
                      Set a = 4, b = 4, c = 4
                      if (a & (b ^ b) & c)
                               a = a >> 1
                      End if
                      Print a + b + c
Answer: 12

Questions 4) What will be the output of the following pseudocode for a = 10, b = 11?

                     Integer funn(Integer a, Integer b)
                     if(0)
                          return a – b – funn(-7, -1)
                     End if
                          a = a + a + a + a
                     return a
                     End function funn()
Answer: 40

Questions 5) What will be the output of the following pseudocode for a = 5, b = 1?

                      Integer funn(Integer a, Integer b)
                      if(b + a || a – b) && (b > a) && 1)
                           a = a + b + b – 2
                           return 3 – a
                      Else
                           return a – b + 1
                      End if
                      return a + b
                      End function fun()
Answer: 5

3. Capgemini Pseudocode Questions

What will be the output of the following pseudocode?

Question 1) What will be the output of the following pseudocode for a=8, b=1?

Integer funn(Integer a, Integer b)
If(a > b && a > 0)
     Return a + b + funn (b-1, a-1)
End if
Return a + b
Answer: 16

Question 2) What will be the output of the following pseudocode for p=7, q=2?

Integer funn(Integer p, Integer q)
           if(p + q < 10)
                 Return 1 + funn(p + 1, q + 1)
              Else
                 Return 2
           End if
Answer: 3

Question 3) What will be the output of the following pseudocode for a=2, b=7, c=7?

      Integer funn(Integer a, Integer b, Integer c)
      if ((b + a) < (a – b))
            a = a + c
            b = (10 + 10) + c
      End if
      Return a + b + c
Answer: 16

Question 4) What will be the output of the following pseudocode? 

String str1 = “err”, str2 = “krr”
Print (count consonant(upper(reverse(str2) + reverse(str1))))
Answer: 5

Question 5) What will be the output of the following pseudo code?

Integer a, b, c
Set a = 2, b = 11, c = 5
if ((4 + 5) < (6 + b))
      b = c & a
End if
Print a + b + c
Answer: 7

PseudoCode Frequently Asked Questions ( FAQ )

1) What are the 5 Rules of pseudocode?

Five important rules for writing pseudocode are:

1. Write one statement per line.
2. Initial keywords should be represented in capital case(READ, WRITE, IF, WHILE, UNTIL).
3. Indentation of pseudocode should be similar to the actual program to show hierarchy.
4. Ending the multiline structure is necessary.
5. Keep statements in simple language(English).

2) How do I start pseudocode?

At first, the purpose of the process should be written to make the aim clear.

3) Is pseudocode easy to learn?

Pseudocode uses plain text mostly written in English language which makes it easy to understand and present.

4) Why do we use pseudocode?

Pseudocode provides easier understanding to people as compared to the conventional programming language code that it is an efficient and platform-independent description of the important principles of an algorithm.

5) Is pseudocode an algorithm?

Pseudocode is used to represent an algorithm but the structure of a pseudocode may not follow the same flow as an algorithm is a well-defined sequence of steps that provides a solution for a given problem.

6) What is the difference between pseudocode and flowchart?

A flowchart is a diagrammatic representation that illustrates a solution model and solution flow to a given problem whereas Pseudocode is an informal high-level description of the operating principle of an algorithm.

7) What is the difference between pseudocode and code?

Pseudocode is just a way to represent the algorithm of the program, it is how the code would look like when if it is actually programmed. Source code is the actual code that can be compiled by the compiler and then be executed by the machine.

8) Which is easier to use algorithm or pseudocode?

Pseudocode is written in English language thus it is easy to understand, construct and simpler to debug on the other hand algorithm is quite complex to construct as it sometimes involves code snippets in it and hence it is a bit difficult when it comes to debugging algorithm.

9) How do you declare a variable in pseudocode?

In pseudocode Assigning a value to a variable is indicated using an arrow symbol (←). The arrow points from the value being assigned towards the variable it is being assigned to. 
Example: String ← “GeeksforGeeks”, would be a valid assignment.

10) What is end if in pseudocode?

To terminate a multiple line if command the endif command is used. The command can either be specified as two separate words, ‘end if’ or as a single word, ‘endif’.

Conclusion:

In the above discussion, we understood the importance of pseudocode in understanding an algorithm. Pseudocode is a lot simpler to construct and debug as compared to an algorithm. 

Основы алгоритмизации и технологии программирования

Понятие алгоритма и его свойства

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

       Алгоритм – описанная на некотором языке точная конечная система правил, определяющая содержание и порядок действий над некоторыми объектами, строгое выполнение которых дает решение, поставленной задачи. Понятие алгоритма, являющееся фундаментальным в математике и информатике, возникло задолго до появления средств вычислительной техники. Слово «алгоритм» появилось в средние века, когда европейцы познакомились со способами выполнения арифметических действий в десятичной системе счисления, описанными узбекским математиком Муххамедом бен Аль-Хорезми («аль-Хорезми» – человек из города Хорезми); в настоящее время город Хива в Хорезмской области Узбекистана). Слово алгоритм – есть результат европейского произношения слов аль-Хорезми. Первоначально под алгоритмом понимали способ выполнения арифметических действий над десятичными числами. В дальнейшем это понятие стали использовать для обозначения любой последовательности действий, приводящей к решению поставленной задачи.

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

        Значение слова «алгоритм» очень схоже со значениями слов «рецепт», «метод», «процесс». Однако, в отличие от рецепта или процесса, алгоритм характеризуется следующими свойствами: дискретностью, массовостью, определенностью, результативностью, формальностью.

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

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

    Определенность (детерминированность, точность) – свойство алгоритма, указывающее на то, что каждый шаг алгоритма должен быть строго определен и не допускать различных толкований; также строго должен быть определен порядок выполнения отдельных шагов. Помните сказку про Ивана-царевича? «Шел Иван-царевич по дороге, дошел до развилки. Видит большой камень, на нем надпись: «Прямо пойдешь – голову потеряешь, направо пойдешь – жену найдешь, налево пойдешь – разбогатеешь. Стоит Иван и думает, что дальше делать». Таких инструкций алгоритм содержать не может.

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

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

Способы описания алгоритмов

        Рассмотрим следующие способы описания алгоритма: словесное описание, псевдокод, блок-схема, программа.

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

        Никаких правил составления словесного описания не существует. Запись алгоритма осуществляется в произвольной форме на естественном, например, русском языке. Этот способ описания не имеет широкого распространения, так как строго не формализуем (под «формальным» понимается то, что описание абсолютно полное и учитывает все возможные ситуации, которые могут возникнуть в ходе решения); допускает неоднозначность толкования при описании некоторых действий; страдает многословностью.

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

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

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

         Рассмотрим некоторые основные конструкции, использующиеся для построения блок-схем (рис. 1).

(1) Блок, характеризующий начало/конец алгоритма (для подпрограмм – вызов/возврат);

(2) Блок – процесс, предназначенный для описания отдельных действий;

(3) Блок – предопределенный процесс, предназначенный для обращения к вспомогательным алгоритмам (подпрограммам);

(4) Блок – ввода/вывода с неопределенного носителя;

(5) Блок – ввод с клавиатуры;

(6) Блок – вывод на монитор;

(7) Блок – вывод на печатающее устройство;

(8) Блок – решение (проверка условия или условный блок);

(9) Блок, описывающий блок с параметром;

(10) Блок – границы цикла, описывающий циклические процессы типа: «цикл с предусловием», «цикл с постусловием»;

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

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

Основные алгоритмические конструкции

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

Линейная алгоритмическая конструкция

          Линейной называют алгоритмическую конструкцию, реализованную в виде последовательности действий (шагов), в которой каждое действие (шаг) алгоритма выполняется ровно один раз, причем после каждого i- гo действия (шага) выполняется (i+ 1)-е действие (шаг), если i-e действие – не конец алгоритма.

         Пример 1.

       Опишем алгоритм сложения двух чисел на псевдокоде в виде блок-схемы (рис. 2).

         Псевдокод:

Ввод двух чисел а, b .

Вычисляем сумму S = а + b .

Вывод S.

Конец.

Разветвляющаяся алгоритмическая конструкция

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

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

             Пример 2.

           Заданы три числа. Найти значение наименьшего из них Заданные числа обозначим: а, b, с; результирующее наименьшее – min. На рис. 5 представлена блок-схема алгоритма решения данной задачи.

Алгоритмическая конструкция «Цикл»

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

        Рассмотрим три типа циклических алгоритмов: ц uкл с параметром (который называют арифметическим циклом), цикл с предусловием и цикл с постусловием (их называют итерационными) .

Арифметический цикл

        В арифметическом цикле число его шагов (повторений) однозначно определяется правилом изменения параметра, которое задается с помощью начального (N) и конечного (К) значений параметра и шагом (h) его изменения. Т.е., на первом шаге цикла значение параметра равно N, на втором – N + h, на третьем – N + 2h и т.д. На последнем шаге цикла значение параметра не больше К, но такое, что дальнейшее его изменение приведет к значению, большему, чем К.

        Пример 3.

      Вывести 10 раз слово «Привет!».

       Параметр цикла обозначим i, он будет отвечать за количество выведенных слов. При i=1 будет выведено первое слово, при i=2 будет выведено второе слова и т. д. Так как требуется вывести 10 слов, то последнее значение параметра i=10. В заданном примере требуется 10 раз повторить одно и то же действие: вывести слово «Привет!». Составим алгоритм, используя арифметический цикл, в котором правило изменения параметра i=1,10, 1. т. е. начальное значение параметра i=1; конечное значение i=10; шаг изменения h=1. На рис. 6 представлена блок-схема алгоритма решения данной задачи.

Цикл с предусловием

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

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

Цикл с постусловием

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

Рекурсивный алгоритм

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

Простые типы данных: переменные и константы

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

        Переменная – есть именованный объект (ячейка памяти), который может изменять свое значение. Имя переменной указывает на зн ачение, а способ ее хранения и адрес остаются скрытыми от программиста. Кроме имени и значения, переменная имеет тип, определяющий, какая информация находится в памяти. Тип переменной задает:

• используемый способ записи информации в ячейки памяти;

• необходимый объем памяти для ее хранения.

         Объем памяти для каждого типа определяется таким образом, чтобы в него можно было поместить любое значение из допустимого диапазона значений данного типа. Например, тип «байт» может принимать значения от О до 255, что в двоичном коде (255₍₁₀₎=11111111₍₂₎) соответствует ячейке памяти длиной в 8 бит (или 1 байт).

          В описанных выше алгоритмах (примеры 1-3) все данные хранятся в виде переменных. Например, инструкция «Ввод двух чисел а, b » означает введение пользователем значений двух переменных, а инструкция «К=К + 1» означает увеличение значения переменной К на единицу.

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

         Все остальные данные в программе, значения которых не изменяются на протяжении ее работы, называют константами или постоянными. Константы, как и переменные, имеют тип. Их можно указывать явно, например, в инструкции «К=К+1» 1 есть константа, или для удобства обозначать идентификаторами: pi=3,1415926536. Только значение pi нельзя изменить, так как это константа, а не переменная.

Структурированные данные и алгоритмы их обработки

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

         Массивом называется упорядоченная совокупность однотипных величин, имеющих общее имя, элементы которой адресуются (различаются) порядковыми номерами (индексами). В качестве иллюстрации можно представить шкаф, содержащий множество пронумерованных ящиков (совокупность – «Ящик № 1», «Ящик № 2», «Ящик № 3» и т.д.; «Ящик» – общее имя всех ее элементов). Доступ к содержимому конкретного ящика (элементу массива) осуществляется после выбора ящика по его номеру (индексу). Элементы массива в памяти компьютера хранятся по соседству, одиночные элементы простого типа такого расположения данных в памяти не предполагают. Массивы различаются количеством индексов, определяющих их элементы.

           Одномерный массив (шкаф ящиков в один ряд) предполагает наличие у каждого элемента только одного индекса. Примерами одномерных массивов служат арифметическая (а_i) и геометрическая (b_i) последовательности, определяющие конечные ряды чисел. Количество элементов массива называют размерностью. При определении одномерного массива его размерность записывается в круглых скобках, рядом с его именем. Например, если сказано: «задан массив A (10)», это означает, что даны элементы: a ₁ , a ₂ , …, a ₁₀ . Рассмотрим алгоритмы обработки элементов одномерных массивов.

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

               Пример 4.

          В заданном числовом массиве A(l0) найти наибольший элемент и его индекс, при условии, что такой элемент в массиве существует, и единственный.

          Обозначим индекс наибольшего элемента т. Будем считать, что первый элемент массива является наибольшим (т = 1). Сравним поочередно наибольший с остальными элементами массива. Если оказывается, что текущий элемент массива а _i (тот, c которым идет сравнение) больше выбранного нами наибольшего а_т, то считаем его наибольшим (т=i) (рис.10).

         Рассмотрим двумерный массив (шкаф с множеством ящиков, положение которых определяется двумя координатами – по горизонтали и по вертикали). В математике двумерный массив (таблица чисел) называется матрицей. Каждый ее элемент имеет два индекса а _ij , первый индекс i определяет номер строки, в которой находится элемент (координата по горизонтали), а второй j – номер столбца (координата по вертикали). Двумерный массив характеризуется двумя размерностями N и М, определяющими число строк и столбцов соответственно (рис. 11).

          Ввод элементов двумерного массива осуществляется построчно, в свою очередь, ввод каждой строки производится поэлементно, тем самым определяется циклическая конструкция, реализующая вложение циклов. Внешний цикл определяет номер вводимой строки ( i ), внутренний – номер элемента по столбцу ( j ). На рис. 12 представлен алгоритм ввода матрицы A(MxN) .

            Пример 5.

        Задана матрица символов (100х100), представляющая собой карту ночного неба; звездам на карте соответствует символы «*». Определить: сколько звезд на карте?

          Алгоритм решения задачи достаточно прост, необходимо перебрать все элементы матрицы и посчитать, сколько среди них символов «*». Обозначим К переменную – счетчик. На рис 13. представлена блок-схема решения этой задачи.

Время выполнения 6 часов Цель работы Усвоить понятия: алгоритм как фундаментальное понятие информатики, способы описания, основные типы алгоритмов, освоить принципы решения задач с использованием основных алгоритмических конструкций. Задачи лабораторной работы После выполнения работы студент должен знать и уметь: знать назначение алгоритма и его определение; знать формы представления алгоритма; уметь работать с основными алгоритмическими конструкциями; уметь представлять алгоритм в виде блок-схемы; уметь приводить примеры алгоритмов и применять их для построения блок-схем; уметь составлять и записывать алгоритм одним из способов. Перечень обеспечивающих средств Для обеспечения выполнения работы необходимо иметь методические указания по выполнению работы.  Общие теоретические сведения Решение любой задачи на ЭВМ можно разбить на следующие этапы: разработка алгоритма решения задачи, составление программы решения задачи на алгоритмическом языке, ввод программы в ЭВМ, отладка программы (исправление ошибок), выполнение программы на ПК, анализ полученных результатов. Первый этап решения задачи состоит в разработке алгоритма. Алгоритм – это точная конечная система правил, определяющая содержание и порядок действий исполнителя над некоторыми объектами (исходными и промежуточными данными) для получения после конечного числа шагов искомого результата. Алгоритм может быть описан одним из трех способов: словесным (пример в начале раздела); графическим (виде специальной блок-схемы); с помощью специальных языков программирования. Блок-схема – распространенный тип схем, описывающий алгоритмы или процессы, изображая шаги в виде блоков различной формы, соединенных между собой стрелками. Линейный алгоритм – это такой алгоритм, в котором все операции выполняются последовательно одна за другой. Алгоритмы разветвленной структуры применяются, когда в зависимости от некоторого условия необходимо выполнить либо одно, либо другое действие. Алгоритмы циклической структуры. Циклом называют повторение одних и тех же действий (шагов). Последовательность действий, которые повторяются в цикле, называют телом цикла.  Циклические алгоритмы подразделяют на алгоритмы с предусловием, постусловием и алгоритмы с конечным числом повторов. В алгоритмах с предусловием сначала выполняется проверка условия окончания цикла и затем, в зависимости от результата проверки, выполняется (или не выполняется) так называемое тело цикла. Задание 1. Определить площадь трапеции по введенным значениям оснований (a и b) и высоты (h). Запись решения задачи на алгоритмическом языке: нач                 s:=((a+b)/2)*h кон  Запись алгоритма в виде блок-схемы (рис. 1): Рисунок 1. Блок-схема линейного алгоритма Задание 2. Определить среднее арифметическое двух чисел, если a положительное и частное (a/b) в противном случае. Запись решения задачи на алгоритмическом языке: нач кон Запись алгоритма в виде блок-схемы (рис. 2): Рисунок 2. Блок-схема алгоритма с ветвлением Задание 3. Составить алгоритм нахождения суммы целых чисел в диапазоне от 1 до 10. Запись решения задачи на алгоритмическом языке: нач     S:=0;     A:=1;         S:=S+a;         A:=a+1; кон Запись алгоритма в виде блок-схемы (рис. 3):  Рисунок 3. Циклический алгоритм с предусловием В алгоритме с постусловием сначала выполняется тело цикла, а затем проверяется условие окончания цикла. Решение задачи нахождения суммы первых десяти целых чисел в данном случае будет выглядеть следующим образом: нач     S:=0;     A:=1;         S:=S+a;         A:=a+1; кон Запись алгоритма в виде блок-схемы (рис. 4):  Рисунок 4. Циклический алгоритм с постусловием Варианты задания Технология выполнения работы В рамках выполнения работы необходимо составить алгоритм решения задачи в виде блок-схемы и с помощью языка псевдокода. Содержание отчета Цель работы и задание. Условие задачи. Алгоритм, написанный с помощью псевдокода и блок- схемы. Вопросы для защиты работы Что такое алгоритм? Свойства алгоритма. Способы записи алгоритма. Основные элементы блок-схемы. Виды алгоритмов. Отличительные особенности алгоритмов с предусловием и постусловием.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #