Отправляет email-рассылки с помощью сервиса Sendsay

Олимпиадные задачи и алгоритмы на C++

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "Обзор инструментов SEO-оптимизатора и методов продвижения" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

  Апрель 2004   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Автор
Виктор Журавлев

Статистика

1.725 подписчиков
-1 за неделю
←   Все выпуски   →

Олимпиадные задачи и алгоритмы на C++


Информационный Канал Subscribe.Ru

Олимпиадные задачи и алгоритмы на C++

    Здравствуйте, уважаемые подписчики.

    К сожалению, размер аудитории нашей рассылки пока еще очень невелик. Свои решения к задачам №1 и №2 прислал лишь один наш подписчик. Оба решения верные, с чем можно его поздравить!

Решение задачи №1 "Сумма чисел" (3 балла).

    Задача на знание языка C. Единственный подводный камень - возможное переполнение переменной, в которой хранится сумма, если она имеет тип short.

    Текст программы: 


#include <stdio.h>
#include <stdlib.h>

int main()
{
  short n, i;
  long sum;
  
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  
  sum = 0;
  scanf("%i", &n);
  for (i = 0; i < n; i++)
  {
    short e;
    scanf("%i", &e);
    sum += e;
  }
  printf("%li\n", sum);

  exit(0);
}

Результаты по задаче №1 "Сумма чисел" (3 балла).

НикРезультат
artiaccepted

Решение задачи №2 "Скобочное выражение" (4 балла).

    При решении задачи используется структура данных стек. Стек - это хранилище данных, которое действует по принципу LIFO (last in - first out), по-русски - "Последний пришел - первый ушел". Для стека обычно определены две основные операции: вставка элемента (PUSH) и удаление элемента (POP). Стек можно представить как стопку элементов. Добавляемый элемент всегда кладется на верх стопки. Удаляется всегда самый верхний элемент стопки. Стек легко реализуется с помощью одного линейного массива и целочисленной переменной для хранения размера стека. Размер массива должен быть равен максимальному допустимому размеру стека.

    В данной задаче используется стек из символов. Символы скобочного выражения сканируются слева направо. Если текущий символ - открывающая скобка ('(', '['), то он добавляется в стек и переходим к следующему символу. Если текущий символ - закрывающая скобка (')', ']'), то проверяем: если стек не пуст и элемент на верхушке стека равен соответствующей открывающей скобке, то удаляем этот элемент из стека и переходим к следующему символу; иначе скобочное выражение некорректно. Если после обработки последнего символа стек не пуст, то скобочное выражение некорректно. Доказать корректность данного алгоритма можно, например, методом математической индукции.

    Текст программы: 


#include <stdio.h>
#include <stdlib.h>

const maxsize = 60000;

void main()
{
  long ok, i, size;
  char c;
  char stack[maxsize];

  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  
  ok = 1;
  size=0;
  while (ok && (c = getchar()) != EOF)
    switch (c)
    {
    case '[': 
      stack[size++] = '[';
      break;
    case '(': 
      stack[size++] = '(';
      break;
    case ']':
      if (size == 0 || stack[--size] != '[') ok = 0;
      break;
    case ')':
      if (size == 0 || stack[--size] != '(') ok = 0;
      break;
    }
  if (size) ok = 0;
  
  if (ok)
    printf("YES\n");
  else
    printf("NO\n");
  
  exit(0);
}

Результаты по задаче №2 "Скобочное выражение" (4 балла).

НикРезультат
artiaccepted

    Условия задач, тесты и решения вы всегда можете найти на сайте accepted.narod.ru.

Ведущий рассылкой: Виктор Журавлев
Вопросы, пожелания, предложения пишите на мой e-mail.

http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу

В избранное