02.09.17 06:00 Матеріали для підготовки до уроку з програмування в 11 класі тут тут:

20.05.13 06:00 файл Excel тут:

20.05.13 06:00 Конспект урока з комп'ютерних мереж тут:

28.12.10 06:00 Методичка з HTMLтут:

02.11.12 08:00 ПІДГОТОВКА ДО ІІ ТУРУ ОЛІМПІАДИ З ІНФОРМАТИКИ (ПРОГРАМУВАННЯ):
Нагадую, що триває І тур заочної інтернет-олімпіади з програмування (26.10.12-до 15.11.12). Потенційні учасники ІІ туру (міської) олімпіади повинні бути зареєстровані і відіслати розв'язки завдань до серверу своєчасно
     9 КЛАС РОБОТА З МАСИВАМИ. Розв'язати наступні задачі (TOURNAMENT і SORTINGTIME).
   10 КЛАС РОБОТА З ДОВГИМИ ЧИСЛАМИ. Самостійно розробити програму множення і ділення довгих чисел
   11 КЛАС: ОБЧИСЛЮВАЛЬНА ГЕОМЕТРІЯ

31.10.12 08:00 ПІДГОТОВКА ДО ІІ ТУРУ ОЛІМПІАДИ З ІНФОРМАТИКИ (ПРОГРАМУВАННЯ):
     9 КЛАС МАСИВИ. Самостійно зробити програму з пошуку найбільшого та найменшого елементів масиву.
   10 КЛАС РЯДКОВІ ВЕЛИЧИНИ. Самостійно розробити програму, яка зчитує із файла багатозначне число і виводить цифри цього числа у стовпчик в інший файл
   11 КЛАС: ОБЧИСЛЮВАЛЬНА ГЕОМЕТРІЯ

ПІДГОТОВКА ДО ОЛІМПІАДИ З ІНФОРМАТИКИ

TOURNAMENT

У країні Вічних канікул проводиться конкурс на кращого ледаря. Відома кількість днів D[i], яку пробайдикував кожен учасник конкурсу. У вхідному файлі input.txt задається спочатку число претендентів N (від 1 до 100), а далі кількість днів D[i] (від 1 до N), яку пробайдикував кожен учасник, відомо що країна існує лише 1000 днів. Для полегшення роботи журі Вам пропонується вивести масив з N чисел у порядку неубування D[i] у файл output.txt. Максимальна кількість балів буде надана за самий ефективний алгоритм.

Приклад вхідного файлу 5 3 1 2 4 2

Приклад вихідного файлу 1 2 2 3 4

SORTINGTIME

За завданням директора школи необхідно проаналізувати скільки часу кожен з учнів затратив на виконання домашнього завдання з математики. У вхідному файлі input.txt задається спочатку кількість учнів N (від 1 до 100), а далі N відрізків часу. Кажен відрізок часу задается 3 цілими числами - години (від 0 до 23), хвилини (від 0 до 60) і секунди (від 0 до 60). У вихідний файл output.txt виведіть час, впорядкований у порядку неубування (час також необхідно вивести у вигляді трьох чисел)

Приклад вхідного файлу 4 10 20 30 7 30 00 23 59 59 13 30 30

Приклад вихідного файлу 7 30 0 10 20 30 13 30 30 23 59 59

МАСИВИ

МАСИВ - це впорядкована послідовність даних одного типу, об'єднаних під одним ім'ям. Найпростіше уявити собі масив у вигляді таблиці, де кожна величина знаходиться у власній комірці. Положення комірки у таблиці однозначно визначається порядковим номером комірки.

Наприклад:
1. Словник (послідовність слів)
2. Фільм (послідовність кадрів)

Опис типу лінійного масиву:

Type <Ім'я типа>=Array [<Діапазон індексів>] Of <Тип елементів>;
Уведення та виведення масиву

Безпосереднє привласнення значень елементам масиву

var
A : Array [1..20] Of Integer;

Begin
A[1]:=7; {Заповнюємо масив значеннями (окремо кожен компонент)}
A[2]:=32;
A[3]:=-70;
..............
A[20]:=56;
Writeln(A[1],A[2],A[3], ...,A[20]) {Виведення елементів масиву на екран}
End.

Уведення значень елементів з клавіатури

const
n = 20;
var
A : array[1..n] of Real;
     i: integer;

Begin
Writeln('Уведіть элементи масиву:');
for i:=1 to n do Read(A[i]);
for i:=1 to n do Writeln(A[i], ' '); {Виведення елементів масиву на екран}
End.

Генерація і привласнення значень за допомогою функції random

const
maxN = 20;
var
A : array[1..maxN] of Real;
     n,i: integer;

Begin
  randomize;{ініціализує генератор випадкових чисел випадковим значенням (випадкове значення залежить від часу перезапуску, тобто залежить від часу)}
  n:=random(maxN);{генерируємо випадкове значення n з інтервалу від 0 до maxN}
    for i:=1 to n do
      A[i]:=random(100); {генерируємо n елементів масиву, кожен елемент прийме значення з інтервалу 0..99}
    for i:=1 to n do Writeln(A[i], ' '); {Виведення елементів масиву на екран}
End.

РОБОТА З МАСИВАМИ

Будьбашкове сортування (сортування обміном)

Порівняємо перший з другим елементом : якщо А[1] >А[2] , поміняємо їх значення місцями. Потім порівняємо другий з третім і, якщо треба, поміняємо місцями їх значення. Продовжимо ці порівняння та обміни до кінця.


Program PSort;

 Var
  X : Array [1..100] Of Real;
  A : Real;
  n, k, i : Integer;
Begin
 Writeln('Уведіть кількість елементів масиву');
 Readln(n);
 Writeln('Уведіть масив чисел з ',n,' елементів');
 For i := 1 To n Do Read (X[i]);
 { Сортування }
 For k := 1 To n-1 Do
   For i := 1 To n-1 Do
     If X[i] > X[i+1] Then
       Begin
         A:=X[i];
         X[i]:=X[i+1];
         X[i+1]:=A
       End;
 Writeln('впорядкований масив чисел:');
 For i:=1 To n Do
 Write (X[i]);{Виведення масиву}
End.

Сортування вибором

Знаходимо у масиві елемент з мінімальним значенням на інтервалі від 1-го до останнього елементу і міняємо його місцями з першим елементом. На другому кроці знаходимо элемент з мінимальним значенням у інтервалі від 2-го до останнього і міняемо місцями його з другим елементом.
І так далі для усіх елементів до останнього елементу массиву

Program VibSort;
var T:array[1..100] of real;

min: real;
Imin, S, i, n: integer;
begin
Writeln('Уведіть кількість елементів масиву');
Readln(n);
writeln('Уведіть масив чисел з ',n,' елементів');
for i:=1 to n do read(T[i]);
for s:=1 to n-1 do
begin
min:=T[s];
Imin:=s;
for i:=s+1 to n do
if T[i]<min then
begin {Пошук мінімального елементу в діапазоні}
min:=T[i];
Imin:=i;
end;
{Обмін месцями мінімального и s–го елементів}
T[Imin]:=T[s];
T[s]:=min;
end;
writeln('впорядкований масив чисел');
for i:=1 to n do write(T[i]:8:3);
writeln;
end.

Сортування вставками

На j-ому етапі ми "вставляємо" j-ий елемент M[j] у потрібну позицію серед елементів M[1], M[2],. . ., M[j-1], яківже відсортовані. Післе цієї вставки перші j елементів массиву M будуть впорядковані.

Будемо використовувати буферний елемент M[0], значення якого завідомо буде меньше значення будь якого з елементів масиву.

Program VSort;

procedure swap(var x,y:integer);
var t: integer;
begin
t := x;
x := y;
y := t
end;
var i,j,N:integer;
a:array[0..10] of integer;
begin
n:=10;
a[0] := -30000;
randomize;
for i:=1 to n do begin a[i]:=random(10); writeln(a[i]);end;

for j:=2 to N do
begin
i := j;
while a[i] < a[i-1] do
begin
swap(a[i],a[i-1]);
i := i-1
end
end;
writeln;
for i:=0 to n do writeln(a[i])

end.

Швидке сортування Хоара

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

program Quick_Sort;
var A:array[1..100] of integer;
N,i : integer;
{До процедури передаются ліва та права границі фрагменту, що буде впорядкований }

procedure QSort(L,R:integer);
var X,y,i,j:integer;
begin
X:=A[(L+R) div 2];
i:=L; j:=R;
while i<=j do
begin
while A[i]<X do i:=i+1;
while A[j]>X do j:=j-1;
if i<=j then
begin
y:=A[i]; A[i]:=A[j]; A[j]:=y;
i:=i+1; j:=j-1;
end;
end;
if L<j then QSort(L,j);
if i<R then QSort(i,R);
end;

begin
write('кількість елементів масиву');
read(N);
for i:=1 to n do read(A[i]);
QSort(1,n); {впорядкувати елементи з першого до n-го}
for i:=1 to n do write(A[i],' '); {впорядкований масив}
end.

РЯДКОВІ ВЕЛИЧИНИ

Рядок – це послідовність символів. Данні типа рядок зберігаються у вигляді послідовності байт, що містять коди ASCII символів, нульовий байт містить фактичну довжину рядка.
Довжина рядка - кількість символів у рядку. Довжина рядка лежить у діапазоні від 0 до 255.

 
Опис рядка:
var imja_zminnoj: string[довжина рядка];
якщо довжину рядка не вказувати, то буде за замовчуванням встановлена максимальна довжина рядка – 255

var n: string[40];
var m: string;

До кожного символу можна звертатися через індекс(порядковий номер символу в рядку
N:='DNIPRO'
N[1]= 'D'; N[2]='N'; N[3]= 'I'; N[4]= 'P'; N[5]= 'R'; N[6]='O'

Операції над рядками:

 
Операція зчеплення рядків
+

n:='DNIPRO'; m:='PETROVSK';
n+m= 'DNIPROPETROVSK'

Операція відношення (порівняння)

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

=,<, >
'pascal'<'Pascal' {ord('P')>ord('p')}
'pascal'>'pas' {довжина рядка 'pascal'> довжини рядка 'pas'}
'pascal'='pascal'

Стандартні функції і процедури

   
CONCAT(s1,....sN:string):string; - виконує конкатенацію(об'єднання) рядків;
        де si - список рядків чи виразів типу рядок; загальна довжина результату не більше 255 символів.
S1:=’turbo’; S2:=' ';S3:='pascal';
concat(S1,S2,S3) = 'turbo pascal'

POS(S1,S2: string):byte
        Функція, що розшукує підрядок S1 у рядку S2 та повертвє номер позиції першого знайденого входження. Якщо в результаті буде 0, то рядок не містить підрядка S1. S1, S2 - вирази типу рядок.

k:=pos('PETROVSK', 'DNIPROPETROVSK') k=7
m:=pos('for', 'informatics') m=3
l:=pos('math', 'informatics') l=0

LENGTH(S: string):integer
        Функція, що повертає довжину рядка (значення першого байту)

l:=lLENGTH('word') l=4

COPY (var S:string; Pos, N:integer)
        Функція, що повертає із рядка S, починаючи з позиції Pos, підрядок довжиною N символів.

S:='DNIPROPETROVSK';
copy(S, 7, 4);  S='PETR'
DELETE(var s:string, n1,n2:integer) -
        Процедура, дозволяє вилучити підрядок із рядка S, причому сам рядок S змінюється; тут n1 - перший символ, що вилучається; n2 - кількість символів, що вилучаються.
S:='DNIPROPETROVSK';
delete(S, 7, 8);  S='DNIPRO'

INSERT(S1:string;var S2:string;n:integer)
        Процедура, яка додає підрядок S1 у рядок S2 починаючи з позиції n; S1, S2 та n - вирази відповідного типу.

S:='matics';
insert('infor', S, 1);
S='informatics';
STR(x:integer(real)], var s:string);  де x - вираз цілого(integer) або дійсного(real) типу.
        Процедура що перетворює надане у формі x:l1 (ціле) чи x:l1:l2 (дійсне) число у рядок та зберігає його у змінній s.

V1:=12345; V2:=5678;
str(V1,S1); str(V2,S2);
S:= S1+S2; S='123455678';

VAL(s:string; var v:integer/real; var c:integer);
        Процедура, що перетворює рядок s у числову форму (зворотна до str) та зберігає його у змінній v. Якщо рядок містить неприпустимий символ (який не може бути вживано у записі числа), то його позиція зберігається у змінній c, у іншому випадку c=0.

S1:='12345'; S2:='5678';
val(S1,V1,Err); val(S2,V2,Err);
t:=V1+V2; t=18023

РОБОТА З ДОВГИМИ ЧИСЛАМИ

Додавання

Віднімання

var a,b:string;
i,j,k,m:integer;
c,d,x:array[1..253] of integer;
f,f1:text;
begin
assign(f,'input.txt');
assign(f1,'output.txt');
reset(f);
rewrite(f1);
readln(f,a);
readln(f,b);
j:=length(a); {довжина рядка a}
{зверніть увагу, що в результаті наступних дій цифри числа нумеруються у зворотньому порядку}
for i:=1 to length(a) do
begin
{перетворення i-го символу рядка a у j-ту цифру першого числа}
val(a[i],c[j],m); j:=j-1;
end;
j:=length(b);{довжина рядка b}
for i:=1 to length(b) do
begin
{перетворення i-го символу рядка b у j-ту цифру другого числа}
val(b[i],d[j],m);j:=j-1;
end;
if length(a)<length(b) then k:=length(b) else k:=length(a);
k:=k+1;
{обнулення масиву}
for i:=1 to k do x[i]:=0;

{порозрядне додавання (як ми додаємо у стовпчик)}
for i:=1 to k do
begin
x[i]:=c[i]+d[i]+x[i];
if x[i]>=10 then
begin
x[i+1]:=x[i+1]+1;
x[i]:=x[i] mod 10;
end;
end;
if x[k]=0 then k:=k-1;

{порозрядне віднімання ( у стовпчик)}
for i:=1 to k do
begin
x[i]:=x[i]+c[i]-d[i];
if x[i]<0 then
begin
x[i+1]:=x[i+1]-1;
x[i]:=x[i]+10;
end;
end;
while x[k]=0 do k:=k-1; {прибираємо зайві 0}
if a=b then write(f1,'0');{випадок, коли числа однакові}

for i:=k downto 1 do write(f1,x[i]);{виведення результату у зворотньому порядку}
close(f);
close(f1);
end.

ПРОЦЕДУРИ І ФУНКЦІЇ КОРИСТУВАЧА

Процедура
Функція

Процедура (функція) користувача – це незалежна пойменована частина програми, призначена для виконання певних дій.
Процедура (функція) користувача організовується самим програмістом відповідно до синтаксису мови і являє собою локальний блок. Попередній опис процедур і функцій користувача є обов’язковим.
Процедура (функція) складається з заголовка і тіла. Після однократного опису процедуру (функцію) можна викликати з наступних частин програми.
Процедури і функції користувача організовується самим програмістом відповідно до синтаксису мови і являє собою локальні блоки. Попередній опис процедур і функцій користувача є обов’язковим.

Процедура Використання імені процедури в програмі називається викликом процедури. Функція передає в точку виклику скалярне значення (результат своєї роботи),
Ім'я процедури в операторній частині програми є окре-мий оператор, тому виклик процедури не може міститись у виразах як операнд.

Ім’я функції може входити до виразів, як операнд.

Опис:

Procedure<ім’я>[(формальні параметри)];

Заголовок містить зарезервоване слово Procedure , ідентифікатор (ім’я) процедури і необов’язкового списку параметрів із вказівкою типу

Function <ім’я>[(формальні параметри)]:<тип результату>;

Заголовок містить зарезервоване слово Function, ідентифікатор (ім’я) функції та необов’язковий список формальних параметрів і тип результату, що повертається функцією.

Ім’я процедури – ідентифікатор, унікальний в межах програми. Ім’я функції –унікальний у межах блоку ідентифікатор.
Тіло процедури (функції) являє собою локальний блок, за структурою аналогічний програмі:

Procedure<ім’я>[(формальні параметри)];
<розділи описів>;
begin
<розділ операторів>
end;

Як формальні параметри, так і розділ описів у процедурі може бути відсутній.

Function <ім’я>[(формальні параметри)]:<тип результату>;
<розділи описів>;
begin
<розділ операторів>
end;

У розділі операторів повинен бути хоча б один оператор, що присвоює ідентифікатору функції значення. Якщо таких операторів декілька, то результатом виконання функції буде значення останнього оператора присвоювання.

Звернення:

Звернення до процедури, здійснюється за допомогою оператору виклику процедури. Він складається з ідентифікатора (імені) процедури і списку фактичних параметрів, що відділені один від одного комами і знаходяться в круглих дужках. Якщо процедурі не передається ніяких параметрів, то фактичні параметри не вказуються.

<ідентифікатор процедури> [(фактичні параметри)];

Звертання до функції здійснюється за ім’ям з необов’язковою вказівкою списку аргументів.

<ідентифікатор функції> [(фактичні параметри)];

Функції можуть повертати значення цілих, дійсних, булівських, літерних і рядкових типів.

Фактичні параметри за кількістю і типами повинні дорівнювати кількості і типам формальних параметрів
<список параметрів> включає:
1) параметр-значення:
<ідентифікатор>:<тип> - обробляється як локальна змінна по відношенню до даної підпрограми, тобто змінене в тілі підпрограми значення цього параметру не повертається до блоку, що викликав функцію;
2) параметр-змінна:
var <ідентифікатор>:<тип> - змінене в середині програми значення цього параметру повертається до блоку, що викликає підпрограму.
3) нетипізовані параметри-змінні
var <ідентифікатор> - таке описування формального параметру дозволяє виконати посилання на змінну будьякого типу. При цьому тип змінної відсутній, тобто не співпадає з жодним із типів до операції приведення типів.
<тип> - у заголовку безпосередньо може бути визначений тільки простий тип. Будьякий стуктурований тип визначається тільки через ідентифікатор типу.
Область дії ідентифікаторів:
Кожен ідентифікатор повинен бути описаний перед тим, як він буде використаний. Ідентифікатор діє в межах блоку, в якому він описаний. Всі ідентифікатори в одному блоці повинні бути унікальними. Однакові ідентифікатори можуть бути по-різному визначені у кожному окремому блоці, але це вважається поганим стилем програмування і тому не рекомендується в різних блоках програми використовувати змінні з однаковими іменами. Якщо ідентифікатор підпрограми користувача збігається з ім’ям стандартної процедури або функції, то вони стають недоступними в межах дії підпрограми, оголошеної користувачем, тобто стандартна функція ігнорується, а виконується програма користувача.
Приклади:

За допомогою процедури знайти розв'язок квадратного рівняння

y2+2y-3=0

Знаходження рішеня оформити за допомогою процедури.

Program S;
  var Y1,Y2: real;

    Procedure SQ(A,B,C : real; VAR X1,X2 : real);
      var D: real;
    begin
      D:=B*B-4*A*C;
      X1:= (-B+SQRT(D))/(2*A);
      X2:= (-B-SQRT(D))/(2*A);
    end;

  begin
    SQ(1,2,-3,Y1,Y2);
    writeln('Y1=',Y1,'Y2=',Y2);
  end.


Знайти значення числа комбінацій n.


Знаходження факторіалу оформити за допомогою функції.

Program Kombinacij;
  var N,M,C:integer;

    Function Fact(K:integer):integer;
      var i,F:integer;
    begin F:=1;
      for i:= 1 to K do F:=F*i;
      Fact:=F;
    end;

  begin
    Write('n=');
    readln(N);
    write('m=');
    readln(M);
    C:=Fact(N)div(fact(M)*Fact(N-M));
    Writeln('Kilkist kombinacij z ',n, ' po ',m,'=',c);
  end.

Алгоритм Прима-Краскала

На площині розміщено N пунктів. Необхідно з'єднати всі пункти телефонним кабелем так, щоб загальна довжина кабелю була мінімальною.
У термінах теорії графів цю задачу можна сформолювати наступним чином (задача Краскала):
Дано ГРАФ з N вершинами, довжина ребер задається матрицею {di,j}, i,j=1,...,N. Знайти остовне дерево мінімальної довжини.
Вирішити цю задачу можна за допомогою алгоритма ПРИМА-КРАСКАЛА:

У циклі N-1 раз зробити наступне:

  • обрати саме коротке (з тих, що залишилися) ребер при умові, якщо вони не утворюють цикла з вже обраними вершинами.

У результаті виконання алгоритма будуть обрани ребра графА, які утворять остовне дерево мінімальної довжини.

Розглянемо приклад виконання алгоритма:

Побудуємо неорієнтований граф

 
Уведемо матрицю відстаней:
0 1 2 3 4 5 6 7
1 0 9,5 8,6 10,8 8,9 7,1 14
2 9,5 0 14,6 8,6 17 8,9 6,4
3 8,6 14,6 0 9,5 15 15,6 20,6
4 10,8 8,6 9,5 0 19,7 15 14,9
5 8,9 17 15 19,7 0 9,5 19,3
6 7,1 8,9 15,6 15 9,5 0 9,8
7 14 6,4 20,6 14,9 19,3 9,8 0
 

Розкрасимо кожну вершину у різні кольори

for i:=1 to 7
  do
  col[i]:=i;

У циклі від 1 до N-1 знайдемо ребро мінімальної довжини між вершинами різного кольору. Запам'ятати результат Res1[k]:=i;Res2[k]:=j;
Довжину остовного дерева будемо накоплювати у L.

k:=0; L:=0;
while k<6 do
  begin
    dmin:=30000;
      for i1:=1 to 6 do
        for j1:=i1+1 to 7 do
           if (D[i1,j1]<dmin) and             (col[i1]<>col[j1])
            then begin
              dmin:=D[i1,j1];
               i:=i1;j:=j1;
            end;
  k:=k+1;   L:=L+dmin;
  writeln('L=',l,' dmin=',dmin);
  Res[k,1]:=i; Res[k,2]:=j;
(дивись нижче {*})

  end;

Перекрасимо вершини, які мають колір вершини j (col[j]) у колір вершини i (col[i])


{*}  i1:=col[i]; j1:=col[j];
      for m:=1 to 7 do
        if col[m]=j1 then
          col[m]:=col[i];

Виведемо перелік вершин та величіну остовного дерева (L).

Приклад виведення на екран:

  for j:=1 to 2 do
      begin writeln;
      for i:=1 to 7
        do write(res[i,j]:4);
      end;
  writeln;
  writeln(L);
end.

Приклад програмного коду, запропонований Данилом Скрипльовим

type Ribs=record
a:integer;
b:integer;
end;
var
i,j,k,n,min,col,len:integer;
fi:text;
Matrix:array[1..10,1..10]of integer;
Color:array[1..10]of integer;
Rebra:array[1..10]of Ribs;
begin
assign(fi,'input.txt');
reset(fi);
Readln(fi,n);
For i:=1 to n do begin
Color[i]:=i;
For j:=1 to n do begin
Read(fi,Matrix[i,j]);
Write(Matrix[i,j],' ');
end;
Writeln(' ');
end;
close(fi);
k:=1; While k min:=30000;
For i:=2 to n do
For j:=1 to i-1 do
If (Matrix[i,j]<min)and(color[i]<>color[j]) then begin
min:=Matrix[i,j];
Rebra[k].a:=i;
Rebra[k].b:=j;
end;
len:=len+min;
col:=color[Rebra[k].b];
For i:=1 to n do
If color[i]=col then color[i]:=color[Rebra[k].a];
k:=k+1;
end;
For i:=1 to n-1 do Writeln(Rebra[i].a , '-' , Rebra[i].b);
Writeln('Length is: ',Len);
Readln;
end.