• Уважаемые гости и новички, приветствуем Вас на нашем форуме
    Здесь вы можете найти ответы практически на все свои вопросы о серии игр «Готика» (в том числе различных модах на нее), «Ведьмак», «Ризен», «Древние свитки», «Эра дракона» и о многих других играх. Можете также узнать свежие новости о разработке новых проектов, восхититься творчеством наших форумчан, либо самим показать, что вы умеете. Ну и наконец, можете обсудить общие увлечения или просто весело пообщаться с посетителями «Таверны».

    Чтобы получить возможность писать на форуме, оставьте сообщение в этой теме.
    Удачи!

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

Xpycm

Участник форума
Регистрация
6 Янв 2008
Сообщения
2.257
Благодарности
25
Баллы
245
Что-то никто до сих пор ни одной теме в разделе не создал. Непорядок.
Т.к. я закончил первый курс обучения на программиста и у меня остались лекции, я решил выложить их в общее пользование. Мало ли кому понадобятся. Да и сам, если потеряю тетрадь, буду знать, где можно освежить навыки.

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

Xpycm

Участник форума
Регистрация
6 Янв 2008
Сообщения
2.257
Благодарности
25
Баллы
245
Лектор: Федосова Ольга Анатольевна.

[size=10pt]Основы алгоритмизации и программирования.[/size]
Лекция 1.
Алгоритмы
Алгоритм – это заранее заданное понятное и точное предписание возможному исполнителю совершить определенную последовательность действий для получения решения задачи за конечное число шагов.

Свойства алгоритмов:
1. Понятность. Алгоритм должен быть понятным для возможного исполнителя.
2. Дискретность (раздельность, прерывность). Алгоритм должен представлять процесс решения задачи как последовательность выполнения простых шагов.
3. Определенность. Каждое правило алгоритма должно быть четким и однозначным.
4. Результативность (конечность). Алгоритм должен приводить к решению задачи за конечное число шагов.
5. Массовость. Алгоритм разрабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся только исходными данными.

Способы представления алгоритмов:
1. Словесный. Алгоритм представляется на естественном языке.
2. Графический. Алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.
3. Программный. Алгоритм представляется в виде конструкций языка программирования.
4. Структурограммный.

Базовые алгоритмические конструкции.
Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур:
1. Следование.
2. Ветвление.
3. Цикл.

1. Следование. Действия алгоритма строго выполняются друг за другом. Такой алгоритм – линейный.

<img src="http://worldofgothic.ru/forum/index.php?action=dlattach;topic=4977.0;attach=1516">

Последовательность действий никогда не меняется.

2. Ветвление. Обеспечивает, в зависимости от результата проверки условия, выбор одного из альтернативных путей работы. Каждый из путей ведет к общему выходу.
Алгоритм будет продолжаться вне зависимости от того, какой путь будет выбран.

<img src="http://worldofgothic.ru/forum/index.php?action=dlattach;topic=4977.0;attach=1518">

Обход:


<img src="http://worldofgothic.ru/forum/index.php?action=dlattach;topic=4977.0;attach=1520>


3. Цикл. Обеспечивает много кратное выполнение некоторой совокупности действий, называемой телом цикла.


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


<img src="http://worldofgothic.ru/forum/index.php?action=dlattach;topic=4977.0;attach=1522">

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


<img src="http://worldofgothic.ru/forum/index.php?action=dlattach;topic=4977.0;attach=1524">


в) Цикл с параметром.


<img src="http://worldofgothic.ru/forum/index.php?action=dlattach;topic=4977.0;attach=1526">


Этапы решения задачи на РС
1. Постановка задачи.
2. Математическая постановка задачи.
3. Выбор метода решения.
4. Разработка алгоритма решения задачи. (Основной этап)
5. Кодирование программы. (Запись алгоритма на языке программирования)
6. Тестирование и отладка программного продукта.
7. Использование готового программного продукта.

Структура программы на языке Pascal.
Program <имя программы>;
Uses
<список библиотек>;
Label
<список меток в программе>;
Const
<определение констант>;
Type
<описание типов>;
Var
<описание переменных>;
<описание процедур>;
<описание функций>;
Begin
<операторы программы>;
End.

После точки любой текст игнорируется. Конструкции программы компилируются последовательно, поэтому все, что в программе используется должно быть объявлено и определено.
Программу следует сопровождать комментариями. При записи можно использовать только символы, которые определены алфавитом
a..z
A..Z
0..9 и другие специальные символы.

Специальные символы:

+ - / *Знаки арифметических операций. Бинарные знаки.
; Разделители операторов.
( )Скобки арифметических и логических операций.
:=Оператор присваивания.
: Разделитель в описаниях переменных и в формате операторов вывода.
..Многоточие для задания диапазона. (2 точки!)
=Логическое равенство, а также элементы описания констант и типов.
< >Логическое неравенство.
< ><= >=Операции отношения (сравнения)
. Признак окончания программы, а также десятичная точка.
{ } или (* *)Ограничители комментариев
, Разделитель элементов в списке
Ограничитель символьных и строковых констант
[ ]Скобки для обращения к элементам массивов и другие.

Имена (идентификаторы) служат для обозначения объектов. Имя может состоять из букв и цифр, а также знаков подчеркивания (_), но первым символом может быть только буква. Используется только английский алфавит. Нельзя ставить пробелы в имени. Запрещается использовать в качестве имен зарезервированные слова.

Стандартные типы данных в языке Pascal
Целочисленные типы.

Тип
Описание
Диапазон
Объем памяти
Короткое целое без знака
byte​
0..255​
1​
Короткое целое со знаком
shortint​
-127..127​
1​
Целое без знака
word​
0..65536​
2​
Короткое целое со знаком
integer​
-32k..32k​
2​
Длинное целое со знаком
Longint​
-2147483648.. 2147483647​
4​

Обилие целочисленных типов позволяет эффективно использовать память РС и гибко вводит переменные в программу.

Целочисленные данные можно складывать (+), вычитать (-), перемножать (*).
Для выполнения деления используются 2 операции.
div – получения целой части частного
mod – получение остатка от деления

a:=26 div 7; {Ответ: а=3}
b:=26 mod 7; {b=5}
c:=26 mod 13; {c=0}

Пример:
Найти сумму цифр трехзначного числа а.
Пусть а = 256. Каждую цифру отдельно обозначим буквой.
с3=2, с2=5, с1=6

Блок-схема:


<img src="http://worldofgothic.ru/forum/index.php?action=dlattach;topic=4977.0;attach=1528">


Программа:

{Вычисление суммы цифр трехзначного числа}
Program ex_1;
Var
a:word; {исходное трехзначное число}
c1,c2,c3: byte; {количество единиц, десятков, сотен, соответственно}
S: 1..27; {сумма цифр}
Begin
write(‘Введите трехзначное число ’);
readln(a);
c1:=a mod 10;
c2:= a div 10 mod 10; {= a mod 100}
c3:=a div 100;
S:=c1+c2+c3;
writeln(‘ Сумма цифр трехзначного числа ‘,a,’ равна ‘,S);
End.

Конец Лекции 1.
 

Вложения

  • Blok-shema_v_primere.JPG
    Blok-shema_v_primere.JPG
    16,7 KB · Просмотры: 397
  • Lection1.doc
    69 KB · Просмотры: 378
  • Sledovanie.JPG
    Sledovanie.JPG
    4,1 KB · Просмотры: 430
  • Cikl_s_parametrom.JPG
    Cikl_s_parametrom.JPG
    9,6 KB · Просмотры: 407
  • Cikl_s_postusloviem.JPG
    Cikl_s_postusloviem.JPG
    7,1 KB · Просмотры: 549
  • Cikl_s_predusloviem.JPG
    Cikl_s_predusloviem.JPG
    8,9 KB · Просмотры: 417
  • Vetvlenie.JPG
    Vetvlenie.JPG
    7,1 KB · Просмотры: 521
  • Sledovanie.JPG
    Sledovanie.JPG
    4,1 KB · Просмотры: 577
  • Lection1.doc
    69 KB · Просмотры: 395
  • Blok-shema_v_primere.JPG
    Blok-shema_v_primere.JPG
    16,7 KB · Просмотры: 404
  • Cikl_s_parametrom.JPG
    Cikl_s_parametrom.JPG
    9,6 KB · Просмотры: 518
  • Cikl_s_postusloviem.JPG
    Cikl_s_postusloviem.JPG
    7,1 KB · Просмотры: 553
  • Cikl_s_predusloviem.JPG
    Cikl_s_predusloviem.JPG
    8,9 KB · Просмотры: 599
  • Vetvlenie.JPG
    Vetvlenie.JPG
    7,1 KB · Просмотры: 572
Последнее редактирование модератором:

Xpycm

Участник форума
Регистрация
6 Янв 2008
Сообщения
2.257
Благодарности
25
Баллы
245
Лекция 2.
Стандартные процедуры и функции для работы с целочисленными аргументами.

Inc(x,y) Инкременент(увеличение) аргумента х на величину y.
Dec(x,y) Декремент (уменьшение) аргумента х на величину у.
Inc(x) Увеличение на 1: х=х+1.
Dec(x) Уменьшение на 1: х=х-1.
abs(x) Модуль аргумента. |x|
sqr(x) Возведение аргумента в квадрат.
odd(x) Функция возвращает значение истина (true), если число x
нечетное и ложь (false) в противном случае.

Вещественные типы данных.
Данные вещественного типа имеют своими значениями подмножества действительных чисел, допустимых в конкретной ЭВМ.
Real (comp, double, extended, single):
2e², -0,14e² и т.п.

Стандартные процедуры и функции.
abs(x) |x|
sin(x) sin X
cos(x) cos X
arctg(x) arctg X
sqr(x) x²
sqrt(x) √x
exp(x) Е (экспонента) в степени х
ln(x) ln X
Trunc(x) выделение целой части значения (результат –длинное число)
Fruc(x) Выделение дробной части аргумента х.
int(x) целая часть аргумента.
round(x) округление до ближайшего целого (результат – длинное
число).
random случайное число из диапазона [0,1]

Пример:

1)
<img src="http://worldofgothic.ru/forum/index.php?action=dlattach;topic=4977.0;attach=1531">

y:=sqrt(abs(10.2-sqr(x)))/2*exp(3*x);

2)
<img src="http://worldofgothic.ru/forum/index.php?action=dlattach;topic=4977.0;attach=1533">

y:=abs((exp(x*ln(sqr(x)))-sin(3*x)/cos(3*x))/(exp(1/5*ln(cos(x/3)))))



Логический тип данных
Переменные логического типа могут принимать 2 значения: истина и ложь. Для их описания используется ключевое слово boolcan. И памяти РС они занимают 1 байт. Свои значения логические переменные получают в результате выполнения операции отношения (сравнения). Результат отношения равен истине, если отношение удовлетворяется для значений, входящих в него операндов.

Var
c:boolcan;

c:=a>7
a mod 2=1 число а – нечетное.
a mod 7=0 кратно 7
a mod 5 <>0 не кратно 5
a div 10=a mod 10 цифры совпадают (11, 22 и т.д)
abs(x)<=7 диапозон от -7 до 7

Символьный тип данных
char
Величины символьного типа занимают 1 байт.
Значением типа char может быть любой символ из расширенного набора ASCII

Стандартные функции для работы с символьными данными
ORD(x) определяет порядковый номер аргумента х. Результат –
целое число.
CHR(x) определяет символ, код которого равен х.

Пример:
Var
a,b,ch,c1:char;
Begin
a:=’q’; {c1:=’de’ – нельзя. Обязательно, чтобы один знак)
b:=’8’ {символ 8, а не число}
ch:=’;’;
c1>=ch;
c1:=b;

Строковый тип данных
string
Значения переменных строкового типа – это последовательность допустимых символов.
Пример:
Var
s, s1, str2:string;]

s:=’МЭСИ’; {4 байта}
str2:=’Университет’; {11 байт}
s1:=’123’ {не число 123, а строка из 3 символов}




Program Name;
Var
name:string;
Begin
write(‘Введите ваше имя ‘);
readln(name);
writeln(‘Превед, ‘,name)
end.


Дальше куска лекции нет, обойдемся без нее :)


Ветвление алгоритма

<img src="http://worldofgothic.ru/forum/index.php?action=dlattach;topic=4977.0;attach=1535">


Условный оператор
If <условие> then
<оператор1>{; - не ставится}
else
<оператор2>;
Выполнение условного оператора назначается с вычисления значения логического выражения, записанного в условии.
Простые условия записываются в виде равенств и неравенств. Сложные условия составляют из простых операций. Если <условие>истинно, то выполняется <оператор1>, в противном случае – <оператор2>. Если в качестве оператора должна быть выполнена последовательность операторов, то они объединяются операторными скобками: Begin и End;
Пример:

у=√x - если x>0)
у=|x| - в противном случае

If x>0
Then
y:=sqrt(x)
Else
y:=abs(x);



Формат неполного условного оператора

<img src="http://worldofgothic.ru/forum/index.php?action=dlattach;topic=4977.0;attach=1537">

Ветвь else может отсутствовать. В этом случае, если условие ложное, никакие действия не выполняются.
Например:
Если число а кратно 8, увеличить его в 5 раз. (если нет – ничего не делать)
If a mod 8=0
then a:=a*5;

Пример:
Условие: Даны 2 числа. Большее из них увеличить в 3 раза, меньшее – уменьшить на 1.

Блок-схема:

<img src="http://worldofgothic.ru/forum/index.php?action=dlattach;topic=4977.0;attach=1539">

Программа:
Program ex;
Var
x,y:real; {исходные данные, результат}
Begin
write(‘Введите два числа ‘);
readln(x,y);
If x>y
then
begin
x:=3*x;
Dec(y)
End
else
begin
Dec(x);
y:=3*y;
end;
writeln(‘Новые значения ‘);
writeln(‘x= ‘,x:7:2,’ y= ‘,y:7:2);
end.

Тест:
Исходные данные Результат
х=5, y=2. x=15, y=1
x=-10, y=15 x=-11, y=45

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

Вложения

  • Blok-shema_v_primere2.JPG
    Blok-shema_v_primere2.JPG
    17,4 KB · Просмотры: 424
  • nepolniy_operator.JPG
    nepolniy_operator.JPG
    6 KB · Просмотры: 523
  • vetvlenie2.JPG
    vetvlenie2.JPG
    6,6 KB · Просмотры: 392
  • pr2.JPG
    pr2.JPG
    3,7 KB · Просмотры: 388
  • pr1.JPG
    pr1.JPG
    2,5 KB · Просмотры: 534
  • Blok-shema_v_primere2.JPG
    Blok-shema_v_primere2.JPG
    17,4 KB · Просмотры: 565
  • nepolniy_operator.JPG
    nepolniy_operator.JPG
    6 KB · Просмотры: 529
  • vetvlenie2.JPG
    vetvlenie2.JPG
    6,6 KB · Просмотры: 540
  • pr2.JPG
    pr2.JPG
    3,7 KB · Просмотры: 436
  • pr1.JPG
    pr1.JPG
    2,5 KB · Просмотры: 533
Последнее редактирование модератором:

MaGoth

★★★★★★★★★★★
Администратор
Регистрация
7 Янв 2003
Сообщения
19.371
Благодарности
7.801
Баллы
995
Re: Основы алгоритмизации и программирован

2Xpycm:
Молодец что написал, хороший курс лекций для начинающих скриптологов, им будет понятно как правильно составлять схемы и алгоритмы ветвления реализации квестов и их построение. Для понимания работы циклов условий, хорошая вещь. Хотя есть и отличия, но они не значительные и в целом относятся к синтаксису скриптов Готы.. ;)

Да и еще, для написания некоторых элементов текста используй Тег - таблица.
Например этот текст очень не удобен при чтении:
Тип Описание Диапазон Объем памяти
Короткое целое без знака byte 0..255 1
Короткое целое со знаком shortint -127..127 1
Целое без знака word 0..65536 2
Целое со знаком integer -32k..32k 2
Длинное целое со знаком Longint -2147483648.. 2147483647 4

Так бы он смотрелся лучше и понятнее:
Тип
Описание
Диапазон
Объем памяти
Короткое целое без знака
byte​
0..255​
1​
Короткое целое со знаком
shortint​
-127..127​
1​
Целое без знака
word​
0..65536​
2​
Короткое целое со знаком
integer​
-32k..32k​
2​
Длинное целое со знаком
Longint​
-2147483648.. 2147483647​
4​

Пример использования Тега таблица:
Код:
[table][tr][td][center][b]Тип[/b][/center][/td] [td][center][b]Описание[/b][/center][/td] [td][center][b]Диапазон[/b][/center][/td] [td][center][b]Объем памяти[/b][/center][/td][/tr]
[tr][td]Короткое целое без знака[/td] [td][center]byte[/center][/td] [td][center]0..255[/center][/td] [td][center]1[/center][/td][/tr]
[tr][td]Короткое целое со знаком[/td] [td][center]shortint[/center][/td] [td][center]-127..127[/center][/td] [td][center]1[/center][/td][/tr]
[tr][td]Целое без знака[/td] [td][center]word[/center][/td] [td][center]0..65536[/center][/td] [td][center]2[/center][/td][/tr]
[tr][td]Короткое целое со знаком[/td] [td][center]integer[/center][/td] [td][center]-32k..32k[/center][/td] [td][center]2[/center][/td][/tr]
[tr][td]Длинное целое со знаком[/td] [td][center]Longint[/center][/td] [td][center]-2147483648.. 2147483647[/center][/td] [td][center]4[/center][/td][/tr][/table]
 

Xpycm

Участник форума
Регистрация
6 Янв 2008
Сообщения
2.257
Благодарности
25
Баллы
245
2MaGoth:
Сам заметил, что плохо смотрится без таблиц. В Ворде-то все с таблицами, а здесь тэгами надо прописывать, а я не знаю как. "Проектирование интернет-портала" только на 3 курсе :).
Сейчас сделаю красиво.
 

MIXIR94

Участник форума
Регистрация
12 Авг 2008
Сообщения
70
Благодарности
0
Баллы
155
А где эти алгоритмы писать ? Как запускать прогу ?
ЗЫ :
первую лекцию нам читали в 3 классе ! Клянусь !
 

Neкromant

Участник форума
Регистрация
12 Авг 2008
Сообщения
772
Благодарности
2
Баллы
185
А где эти алгоритмы писать ? Как запускать прогу ?

алгоритм это принцип построения всех программ, не зависимо от языка программирования,
а пишутся они в компиляторе любого языка.
 

MIXIR94

Участник форума
Регистрация
12 Авг 2008
Сообщения
70
Благодарности
0
Баллы
155
А не дадите ссылочку на компилятор языка ?
 

Neкromant

Участник форума
Регистрация
12 Авг 2008
Сообщения
772
Благодарности
2
Баллы
185
блин, это для любого языка программирования. Бейсик, паскаль, С++, 1це, асемблер... и т.д и т.п какой ты себе язык поставишь на том и будешь компилить.
 

s@m


Модостроитель
Регистрация
2 Мар 2007
Сообщения
315
Благодарности
56
Баллы
195
2MIXIR94
Для начала я думаю тибе почитать любую книгу по основам программирования, то есть определись с каким языком ты будешь работать, C++ ,Delphi. А уже после этого можешь скачать компилятор + пару исходников с коментариями и сделать свою первую прогу))
От Себя посоветую отличный портал о игровом программирование:
http://gamedev.ru Тут много статей как для начинающего так и для профессионала.
http://www.interestprograms.ru - Есть исходники, с описанием
 

Xpycm

Участник форума
Регистрация
6 Янв 2008
Сообщения
2.257
Благодарности
25
Баллы
245
2No_name: Я учусь в МЭСИ, если это что-то тебе говорит. Московский государственный университет экономики, статистики и информатики. Точнее, в его рязанском филиале. Он маленький, но вроде неплохо учат. По программированию у нас правда хорошие преподы, гоняют нормально так :)
Я вот в этом году закончу 3-й курс а в следующем получю диплом бакалавра, но ровным счетом ничего не знаю
Соболезную. Нужно учиться не ради диплома, а ради знаний.
 

vmazz

Участник форума
Регистрация
18 Дек 2008
Сообщения
218
Благодарности
1
Баллы
165
2Xpycm: Очень полезные лекции для новичков, продолжай в том же духе!
Были бы тут спасибки - я бы влепил. В общем молодец.
 

Марго

Новичок
Регистрация
23 Ноя 2010
Сообщения
1
Благодарности
0
Баллы
145
Семантическая теория программ

Помогите, пожалуйста, выполнить задание.

Формальные языки Е и Т определены над алфавитом {а, *, &, <, >} с помощью денотационной семантики равенствами
Е = Т U * Т U Е & Т и Т= а U а* U <Е>.
Какие из следующих строк *а&*а*&а*; *а&<а&а*>; *<*а*&а>&<*а*>* принадлежат языку Е и какие не принадлежат?
 

siryksv

Участник форума
Регистрация
5 Окт 2009
Сообщения
567
Благодарности
1
Баллы
225
Re: Семантическая теория программ

Помогите, пожалуйста, выполнить задание.
Формальные языки Е и Т определены над алфавитом {а, *, &, <, >} с помощью денотационной семантики равенствами
Е = Т U * Т U Е & Т и Т= а U а* U <Е>.
Какие из следующих строк *а&*а*&а*; *а&<а&а*>; *<*а*&а>&<*а*>* принадлежат языку Е и какие не принадлежат?

Марго! Вы неправильно сформулировали задачу! Е и Т никакие не языки, это нетерминальные символы Вашей грамматики. Далее, Вы не указали начальный нетерминал. Как я понимаю, оно у Вас в задаче E ? Далее, что такое символ U ? Это что, сепаратор альтернатив правил, как я понимаю? Тогда лучше используйте нормальные формы Бэкуса-Наура (НФБ), а то не понятно ведь!

В Вашей задаче строки *а&*а*&а* и *<*а*&а>&<*а*>* невыводимы, вторая строка: *а&<а&а*> - выводима, следовательно, она принадлежит языку, порожденному грамматикой.

Для строки 1 вывод может быть таким:
E -> E&T -> E&T&T -> *T&T&T -> *a&T&T но дальше видно, что *а* невыводимо из T, и мы не можем осуществить возврат к E, ибо тогда появляются угловые скобки. Другие способы вывода также не получатся (в силу указанной причины) Значит, не принадлежит языку.

Для строки 2 вывод:
E -> E&T -> *T&T -> *a&T -> *a&<E> -> *a&<E&T> -> *a&<T&T> -> *a&<a&T> -> *a&<a&a*>
Принадлежит языку.

Для строки 3 вывод:
сразу видно, что сочетание >* невыводимо в грамматике, значит, цепочка невыводима. Итог: строка 3 не принадлежит языку.

З.Ы. Просмотрел бегло, вроде бы, я нигде не ошибся. Это КС-грамматика, можно по ней еще построить автомат, и посмотреть его переходы, распознает ли он цепочки или нет. А Вам, Марго, двойка на зачет :D, ибо задачи очень простые, сами бы могли посмотреть *flowers*!
 

BorisP

Участник форума
Регистрация
7 Июн 2011
Сообщения
1
Благодарности
0
Баллы
145
Нужна помощь - требуется составить схему программы в виде сети Петри и осуществить анализ ее свойств на основе дерева достижимости. Блок-схему программы представлю. Работу оплачу. Жду Ваших сообщений.
 
Сверху Снизу