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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 12, средняя оценка - 4.83
wwmwwm
0 / 0 / 0
Регистрация: 05.06.2012
Сообщений: 75
#1

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

02.08.2013, 18:28. Просмотров 1841. Ответов 29
Метки нет (Все метки)

Я собираюсь участвовать в олимпиаде по информатике(Украина). Я использую 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, и других компиляторах?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.08.2013, 18:28
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Библиотеки на олимпиадах (C++):

Какой компилятор используется на олимпиадах - C++
Возможно это очень глупый вопрос ,но мне надо знать какой компилятор используется на олимпиадах Во-первых для тестирования задач(а именно...

про библиотеки в VS C++ (какие библиотеки нужны для функций 'cout' и 'cin') - C++
какие библиотеки нужны для функций 'cout' и 'cin' ???

Как включить библиотеки в исполняемый файл, чтобы не приходилось ставить библиотеки (Eclipse) - C++
Как включить библиотеки в конечный EXE как это сделано в bilder, чтобы не приходилось ставить библиотеки.

Вызов функции одной динамической библиотеки из другой динамической библиотеки - C++
Добрый день! Помогите пожалуйста разобраться со следующим вопросом. Возможно ли из одной библиотеки передать параметры для...

Четверо студентов на олимпиадах - Prolog
выручите, сделайте пожалуйста две простые программки на Visual Prolog'e: 1) Четверо студентов : Иван, Петр, Михаил и Сергей,...

Как посмотреть какие библиотеки тянут другие библиотеки процесса - Системный софт
Привет, есть процесс, у него подтянуты dll'ки список которых я могу просматривать прогой Process Explorer. НО вопрос как посмотреть...

29
wwmwwm
0 / 0 / 0
Регистрация: 05.06.2012
Сообщений: 75
03.08.2013, 00:52  [ТС] #16
Цитата Сообщение от rrrFer Посмотреть сообщение
Это опасная функция сравнения и абсолютно беспонтовая, хочу знать откуда ТС ее откопал ).
Почему. Это же qsort, который упорядычивает массив по возрастанию. Потом в компататоре мы указываем название массива, количество элементов в нем, тип массива, и в конце название функции которую я написал на форуме. Вот так:
C++
1
qsort(arr, arr+n, sizeof(int), comp)
0
gray_fox
What a waste!
1521 / 1226 / 70
Регистрация: 21.04.2012
Сообщений: 2,565
Завершенные тесты: 3
03.08.2013, 02:48 #17
Цитата Сообщение от wwmwwm Посмотреть сообщение
Почему. Это же qsort, который упорядычивает массив по возрастанию.
И зачем он нужен в С++, если есть sort?
0
Somebody
2789 / 1600 / 145
Регистрация: 03.12.2007
Сообщений: 4,193
Завершенные тесты: 1
03.08.2013, 11:45 #18
Цитата Сообщение от wwmwwm Посмотреть сообщение
Почему. Это же qsort, который упорядычивает массив по возрастанию.
Потому что при вычитании может быть переполнение.

Добавлено через 3 минуты
Ещё, думаю, если const void*, то по-хорошему надо const int*.
А такой код с вычитанием и на cppreference.com, и на cplusplus.com.
0
Nameless One
Эксперт С++
5774 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
03.08.2013, 11:56 #19
Цитата Сообщение от rrrFer Посмотреть сообщение
Это опасная функция сравнения и абсолютно беспонтовая, хочу знать откуда ТС ее откопал ).
А что в ней «опасного» и «беспонтового»? Кроме того, что const void * приводится не к const int *?

Цитата Сообщение от rrrFer Посмотреть сообщение
хочу знать откуда ТС ее откопал ).
Стандартная функция сравнения чисел для qsort.

Добавлено через 1 минуту
Цитата Сообщение от wwmwwm Посмотреть сообщение
C
1
qsort(arr, arr+n, sizeof(int), comp)
Второй аргумент qsort — это размер массива.

Добавлено через 3 минуты
Цитата Сообщение от Somebody Посмотреть сообщение
Поэтому те, кто начинают олимпиадное программирование с Паскаля, умеют написать хотя бы бинпоиск и хоть какую сортировку. А кто начинает с C++...
Ну, говорить о том, кто лучше знает элементарные алгоритмы — бесполезно, т.к. объективной статистики нет и не может быть, а твоя выборка — нерепрезентативна.

Кстати, на региональных (как минимум) турах ACM ICPC тот же qsort и bsearch разрешены. А вот time почему-то нет.
1
Somebody
2789 / 1600 / 145
Регистрация: 03.12.2007
Сообщений: 4,193
Завершенные тесты: 1
03.08.2013, 12:17 #20
Цитата Сообщение от Nameless One Посмотреть сообщение
А вот time почему-то нет.
Если задача такая, что со временем находится более хорошее решение и в какой-то момент оно становится окончательным, то вместо математической границы поиска можно использовать временную. Помню, в Turbo Pascal'е использовали longint absolute 0:$46c. Видимо, посчитали, что это слишком халявно...
0
Nameless One
Эксперт С++
5774 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
03.08.2013, 12:24 #21
Цитата Сообщение от Somebody Посмотреть сообщение
Если задача такая, что со временем находится более хорошее решение и в какой-то момент оно становится окончательным, то вместо математической границы поиска можно использовать временную
Не понял, можно пример?
0
Somebody
2789 / 1600 / 145
Регистрация: 03.12.2007
Сообщений: 4,193
Завершенные тесты: 1
03.08.2013, 12:41 #22
В случае, где при прохождении половины тестов даётся половина баллов, так можно с любым перебором. Например, надо найти кратчайший путь в графе, а алгоритмов человек не знает. Тогда делается полный перебор (который вообще-то по времени не проходит), а когда время заканчивается, тогда выдаётся лучший из найденных вариантов.
С перебором до какой-то границы, которую можно найти, так сразу и не вспомню... Это было давно, и таких задач немного. Но в общем там правильное решение - это какая-то разновидность перебора, только когда этот перебор заканчивать, можно как-то рассчитать по исходным данным.
0
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;
}
0
Dani
1393 / 637 / 57
Регистрация: 11.08.2011
Сообщений: 2,282
Записей в блоге: 2
Завершенные тесты: 1
03.08.2013, 13:07 #24
wwmwwm, лучше подучить язык до олимпиады, т.к. тратить время на распознавание ошибки с пониманием языка, не очень нужно. Либо писать на языке, который ты 100% знаешь. Потому что, лучше понаступать на грабли до олимпиады, а на ней уже пройти мимо них. Особенно, то что нельзя изменить порядок в сортировки в алгоритме sort, и #include<getch>, говорит о том, что C++ пока юзать не стоит.

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

По поводу стандартных алгоритмов я скажу вот что: чтобы юзать алгоритмы из стандартной библиотеки, нужно знать, как они устроены. Если знаешь, как устроен sort, можно этот алгоритм переписать, изменить, можно вычислить сложность алгоритма и т.д. Бинпоиск всегда круто делать по ответу, а если ответ - число не целое, то нужно предусмотреть некую погрешность, число которой нужно установить самому. А без знания стандартного алгоритма бинпоиска это не провернешь. То, что действительно стоит юзать, так это, например, set, map. Это действительно дает преимущество, перед тем же паскалем. Но, и тут, лучше знать, как устроены эти структуры данных, дабы знать сложность операций, которые с ними можно производить.
2
Nameless One
Эксперт С++
5774 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
03.08.2013, 15:19 #25
Цитата Сообщение от wwmwwm Посмотреть сообщение
sort упорядочивает массив по возрастанию, а qsort можно изменять, что бы сортировка производиласт по убыванию. Например было по возрастанию:
У функции sort есть перегрузка, которая принимает функцию или функтор сравнения, что позволяет реализовать сортировку по любому критерию, так что твоё утверждение некорректно.
0
wwmwwm
0 / 0 / 0
Регистрация: 05.06.2012
Сообщений: 75
03.08.2013, 15:34  [ТС] #26
Цитата Сообщение от Nameless One Посмотреть сообщение
У функции sort есть перегрузка, которая принимает функцию или функтор сравнения, что позволяет реализовать сортировку по любому критерию, так что твоё утверждение некорректно.
Например
0
Nameless One
Эксперт С++
5774 / 3424 / 255
Регистрация: 08.02.2010
Сообщений: 7,447
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"));
}
0
iRomul
159 / 100 / 11
Регистрация: 17.10.2012
Сообщений: 480
Завершенные тесты: 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 минуту
Ну вот, опоздал
0
Somebody
2789 / 1600 / 145
Регистрация: 03.12.2007
Сообщений: 4,193
Завершенные тесты: 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);
0
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);
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.08.2013, 17:51
Привет! Вот еще темы с ответами:

Подключение библиотеки Crypto. Если возможно, нужна ссылка на скачивание данной библиотеки - Python
Возникли сложности с подключением библиотеки Crypto: import Crypto.Cipher.AES Выдает следующую ошибку: &gt;&gt;&gt;Traceback...

Приложения не видят библиотеки библиотеки Visual C++ - Системный софт
Здравия желаю! Недавно переустанавливал винду с полным форматированием жесткого диска и теперь некоторые программы просят библиотеки visual...

CDialogEx + dll, После завершения модального диалога (CDialogEx) из длл-библиотеки работа длл-библиотеки прерывается - Visual C++
Добрый день, подскажите, пожалуйста, новичку с++/mfc. Работаю в VS 2010. Есть необходимость разработки длл-библиотеки, которая в своём...

Библиотеки - C++
Я начал изучать C++ и сразу столкнулся с проблемой, скачать компилято wxDev-c++ написал #include &lt;iostream.h&gt;int main() { ...


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

Или воспользуйтесь поиском по форуму:
30
Yandex
Объявления
03.08.2013, 17:51
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru