Форум программистов, компьютерный форум CyberForum.ru

Библиотеки на олимпиадах - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.83
wwmwwm
 Аватар для wwmwwm
0 / 0 / 0
Регистрация: 05.06.2012
Сообщений: 75
02.08.2013, 18:28     Библиотеки на олимпиадах #1
Я собираюсь участвовать в олимпиаде по информатике(Украина). Я использую Microsoft Visual C++ 2010 Express. На олимпиадах, как я знаю часто используюn намного ранние версии этой программы. Скажите пожалуйста, есть ли запрещенные библиотеки на олимпиадах, такие как #include<getch>. Есть ли все библиотеки Microsoft Visual C++ 2010 Express например Microsoft Visual C++ 6.0 и более ранних. Мне это нужно знать, так как я использую такие библиотеки:
C++
1
2
3
4
5
6
7
#include<iostream>
#include<iomanip>
#include<string>
#include<vector>
#include<algorithm>
#include<fstream>
// другие
И если там не будет библиотеки #include<algorithm>, я просто некоторые вещи не сделаю. Есть ли отличия в библиотеках более ранних Microsoft Visual, и других компиляторах?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.08.2013, 18:28     Библиотеки на олимпиадах
Посмотрите здесь:

C++ Библиотеки
C++ Библиотеки
Библиотеки C++
библиотеки в си++ C++
Библиотеки C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
03.08.2013, 12:24     Библиотеки на олимпиадах #21
Цитата Сообщение от Somebody Посмотреть сообщение
Если задача такая, что со временем находится более хорошее решение и в какой-то момент оно становится окончательным, то вместо математической границы поиска можно использовать временную
Не понял, можно пример?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
03.08.2013, 12:41     Библиотеки на олимпиадах #22
В случае, где при прохождении половины тестов даётся половина баллов, так можно с любым перебором. Например, надо найти кратчайший путь в графе, а алгоритмов человек не знает. Тогда делается полный перебор (который вообще-то по времени не проходит), а когда время заканчивается, тогда выдаётся лучший из найденных вариантов.
С перебором до какой-то границы, которую можно найти, так сразу и не вспомню... Это было давно, и таких задач немного. Но в общем там правильное решение - это какая-то разновидность перебора, только когда этот перебор заканчивать, можно как-то рассчитать по исходным данным.
wwmwwm
 Аватар для wwmwwm
0 / 0 / 0
Регистрация: 05.06.2012
Сообщений: 75
03.08.2013, 12:48  [ТС]     Библиотеки на олимпиадах #23
Цитата Сообщение от gray_fox Посмотреть сообщение
И зачем он нужен в С++, если есть sort?
sort упорядочивает массив по возрастанию, а qsort можно изменять, что бы сортировка производиласт по убыванию. Например было по возрастанию:
C++
1
2
3
4
int comp(const void *i, const void *j)
{
  return *(int *)i - *(int *)j;
}
А стало по убыванию:
C++
1
2
3
4
int comp(const void *i, const void *j)
{
  return *(int *)j - *(int *)i;
}
Dani
1263 / 621 / 50
Регистрация: 11.08.2011
Сообщений: 2,236
Записей в блоге: 2
Завершенные тесты: 1
03.08.2013, 13:07     Библиотеки на олимпиадах #24
wwmwwm, лучше подучить язык до олимпиады, т.к. тратить время на распознавание ошибки с пониманием языка, не очень нужно. Либо писать на языке, который ты 100% знаешь. Потому что, лучше понаступать на грабли до олимпиады, а на ней уже пройти мимо них. Особенно, то что нельзя изменить порядок в сортировки в алгоритме sort, и #include<getch>, говорит о том, что C++ пока юзать не стоит.

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

По поводу стандартных алгоритмов я скажу вот что: чтобы юзать алгоритмы из стандартной библиотеки, нужно знать, как они устроены. Если знаешь, как устроен sort, можно этот алгоритм переписать, изменить, можно вычислить сложность алгоритма и т.д. Бинпоиск всегда круто делать по ответу, а если ответ - число не целое, то нужно предусмотреть некую погрешность, число которой нужно установить самому. А без знания стандартного алгоритма бинпоиска это не провернешь. То, что действительно стоит юзать, так это, например, set, map. Это действительно дает преимущество, перед тем же паскалем. Но, и тут, лучше знать, как устроены эти структуры данных, дабы знать сложность операций, которые с ними можно производить.
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
03.08.2013, 15:19     Библиотеки на олимпиадах #25
Цитата Сообщение от wwmwwm Посмотреть сообщение
sort упорядочивает массив по возрастанию, а qsort можно изменять, что бы сортировка производиласт по убыванию. Например было по возрастанию:
У функции sort есть перегрузка, которая принимает функцию или функтор сравнения, что позволяет реализовать сортировку по любому критерию, так что твоё утверждение некорректно.
wwmwwm
 Аватар для wwmwwm
0 / 0 / 0
Регистрация: 05.06.2012
Сообщений: 75
03.08.2013, 15:34  [ТС]     Библиотеки на олимпиадах #26
Цитата Сообщение от Nameless One Посмотреть сообщение
У функции sort есть перегрузка, которая принимает функцию или функтор сравнения, что позволяет реализовать сортировку по любому критерию, так что твоё утверждение некорректно.
Например
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
03.08.2013, 15:50     Библиотеки на олимпиадах #27
wwmwwm, та же сортировка по убыванию:
C++
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
31
32
33
#include <iostream>
#include <algorithm>
#include <iterator>
 
bool cmp(const int& a, const int& b)
{
    return a > b;
}
 
struct CmpFunctor
{
    bool operator() (const int& a, const int& b)
    {
        return a > b;
    }
};
 
int main()
{
    int arr[4] = { 0, 2, 1, 3};
 
    // Все эти три варианта равнозначны:
    // 1.
    std::sort(arr, arr + 4, cmp);
 
    // 2.
    std::sort(arr, arr + 4, CmpFunctor());
 
    // 3.
    std::sort(arr, arr + 4, [](const int& a, const int& b) { return a > b; });
 
    std::copy(arr, arr + 4, std::ostream_iterator<int>(std::cout, "\n"));
}
iRomul
 Аватар для iRomul
158 / 99 / 11
Регистрация: 17.10.2012
Сообщений: 474
Завершенные тесты: 1
03.08.2013, 15:54     Библиотеки на олимпиадах #28
[qsort]:
C++
1
void qsort (void* base, size_t num, size_t size, int (*compar)(const void*,const void*));
Последний аргумент - функция-предикат. Его прототип выглядит так:
C++
1
int compar (const void* p1, const void* p2);
Мы можете создавать эту функцию как угодно, тогда сортировка будет по возрастанию, убыванию, да как угодно.
Вот таблица значений, которая функция-предикат возвращает:


<0 Элемент по указателю p1 идёт раньше p2 (меньше)
=0 Элемент по указателю p1 равен p2
>0 Элемент по указателю p1 идёт позже p2 (болеше)


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Ну и пример оттуда же:
#include <stdio.h>      /* printf */
#include <stdlib.h>     /* qsort */
 
int values[] = { 40, 10, 100, 90, 20, 25 };
 
int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}
 
int main ()
{
  int n;
  qsort (values, 6, sizeof(int), compare);
  for (n=0; n<6; n++)
     printf ("%d ",values[n]);
  return 0;
}
Результат:
10 20 25 40 90 100

Если в предикате поменять местами a и b, то получится обратная сортировка

Добавлено через 1 минуту
Ну вот, опоздал
Somebody
2770 / 1583 / 141
Регистрация: 03.12.2007
Сообщений: 4,139
Завершенные тесты: 1
03.08.2013, 16:22     Библиотеки на олимпиадах #29
C++
1
2
3
4
5
6
#include <functional>
...
// ещё до кучи
std::sort(arr, arr + 4, std::greater<int>());
// и в C++11 begin/end для получения итераторов, чтобы размер не прописывать
std::sort(std::begin(arr), std::end(arr), cmp);
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.08.2013, 17:51     Библиотеки на олимпиадах
Еще ссылки по теме:

про библиотеки в VS C++ (какие библиотеки нужны для функций 'cout' и 'cin') C++
C++ Какой компилятор используется на олимпиадах
Вызов функции одной динамической библиотеки из другой динамической библиотеки C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
wwmwwm
 Аватар для wwmwwm
0 / 0 / 0
Регистрация: 05.06.2012
Сообщений: 75
03.08.2013, 17:51  [ТС]     Библиотеки на олимпиадах #30
Цитата Сообщение от iRomul Посмотреть сообщение
[qsort]:
C++
1
void qsort (void* base, size_t num, size_t size, int (*compar)(const void*,const void*));
Последний аргумент - функция-предикат. Его прототип выглядит так:
C++
1
int compar (const void* p1, const void* p2);
Мы можете создавать эту функцию как угодно, тогда сортировка будет по возрастанию, убыванию, да как угодно.
Вот таблица значений, которая функция-предикат возвращает:


<0 Элемент по указателю p1 идёт раньше p2 (меньше)
=0 Элемент по указателю p1 равен p2
>0 Элемент по указателю p1 идёт позже p2 (болеше)


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Ну и пример оттуда же:
#include <stdio.h>      /* printf */
#include <stdlib.h>     /* qsort */
 
int values[] = { 40, 10, 100, 90, 20, 25 };
 
int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}
 
int main ()
{
  int n;
  qsort (values, 6, sizeof(int), compare);
  for (n=0; n<6; n++)
     printf ("%d ",values[n]);
  return 0;
}
Результат:
10 20 25 40 90 100

Если в предикате поменять местами a и b, то получится обратная сортировка

Добавлено через 1 минуту
Ну вот, опоздал
Спасибо, но я эту реализацию сам показывал в этой теме, и показывал, как сделать что бы сортировка была и по убыванию, и по возрастанию

Добавлено через 2 минуты
Цитата Сообщение от Somebody Посмотреть сообщение
C++
1
2
3
4
5
6
#include <functional>
...
// ещё до кучи
std::sort(arr, arr + 4, std::greater<int>());
// и в C++11 begin/end для получения итераторов, чтобы размер не прописывать
std::sort(std::begin(arr), std::end(arr), cmp);
Тоисть до 11 версии это выглядело бы вот так:
C++
1
sort(arr, arr+4, cmp);
Yandex
Объявления
03.08.2013, 17:51     Библиотеки на олимпиадах
Ответ Создать тему
Опции темы

Текущее время: 21:14. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru