11д

Неделя информатики

Придумать задачу для проведения олимпиады по программированию для 8-10 классов по одной из тем:

1. Целые числа
2. Строки
3. Комбинаторика
4. Длинная арифметика
5. Поиск пути в лабиринте, графе
6. Имитация команд, исполнители
7. Геометрические задачи
8. Игры и стратегии

Составить 5 тестов и написать программу для проверки.

Домашнее задание: придумать и решить задачу в день для недели информатики по одной из тем:

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

Алгоритмы с двумерными массивами

22.02.16 На сайте дистанционной подготовки - №112437(L), №112438(M), №112439(N).
25.01.16 На сайте дистанционной подготовки - №1596 (Седловые точки), 1597 (Слон и ладья)

11.01.16 На блоге "Алгоритмы с массивами" решить все задания в Части 4.

Алгоритмы сортировки

Сортировка по возрастанию или убыванию числовых данных аналогична сортировке в алфавитном порядке строк. Если массив строк типа char, то сравниваем с помощью функции strcmp() библиотеки string.h:

strcmp(str1,str2)<0 <=> str1<str2
strcmp(str1,str2)>0 <=> str1>str2
strcmp(str1,str2)==0 <=> str1=str2

Чтобы заполнить массив по условию из заданного набора данных используем счетчик k:

int a, n, k=0, A[1000];
cin >> n;
for (int i=0; i<n; i++)
{
   cin>>a; if (a%2==0) {A[k]=a; k++;}
} 
for  (int i=0; i<k; i++)cout<<A[i]<<" ";

Для считывания строки, состоящей из слов и чисел, можно их прочитать в разные переменные:

string s1,s2; int a,b,c;
cin>>s1>>s2>>a>>b>>c;

Сортировка обменом (пузырек)

for (int j=0; j<n-1; j++)
 for (int i=0; i<n-1-j; i++)
  if (A[i]>A[i+1]) swap(A[i],A[i+1]);

Сортировка обменом (челнок)  

for (int j=0; j<n/2; j++)
{

 for (int i=j; i<n-1-j; i++)

  if (A[i]>A[i+1])swap(A[i],A[i+1]); 

 for (int i=n-(j+1); i>=j+1; i--)

  if (A[i]<A[i-1]) swap(A[i],A[i-1]); 

}

Сортировка выбором

for (int j=0; j<n-1; j++)

{

 k=j;

 for (int i=j+1; i<n; i++)

  if (A[i]<A[k]) k=i;

  if (k!=j) swap(A[k],A[j]);

}

Сортировка вставками

for (int j=1; j<n; j++)

   for (int i=j-1; i>=0; i--)

      if (A[i+1]<A[i]) 
    swap (A[i+1],A[i]); 
  else break;

Если нужно сделать сортировку по нескольким параметрам, например, в начале по номеру школу S[i], затем по номеру класса K[i], а далее по фамилии ученика F[i], то в условии при проверки нужно добавить еще несколько неравенств: 

if (S[i]<S[i+1] or //проверяем номера школ

//если номер школы одинаков, то проверяем номер класса

   (S[i]==S[i+1] and (K[i]>K[i+1] or

//если и номер класса одинаков, то сравниваем фамилии учеников

                     (K[i]==K[i+1] and F[i]>F[i+1]))))

{

   swap(S[i],S[i+1]);

   swap(K[i],K[i+1]);

   swap(F[i],F[i+1]);

}

Домашнее задание от 5.10.2015: решить оставшиеся задания и отправить код программы по почте. Можете проверить свои программы с входными данными для задач 1, 2, 3, 4.

Подсчёт. Сортировка подсчетом. Цифровая (поразрядная) сортировка
Домашнее задание от 21.09.15: написать программы  для 2 заданий (не считая классных) из раздела "Подсчёт. Сортировка подсчетом. Цифровая (поразрядная) сортировка" на сайте informatics.mccme.ru.

Алгоритмы поиска и сортировки. Бинарный поиск.
Домашнее задание от 07.09.15: написать программы для  5 заданий (не считая классных) из раздела "Бинарный поиск" на сайте informatics.mccme.ru.