Школа С++ для не совсем начинающих

@ct0r · Регистрация: 19.08.2012

Author24 — интернет-сервис помощи студентам

http://cpp-school.unigine.com/

Мне так-то наверное поздновато, но некоторым будет самый раз, ящитаю

@GbaLog- · 05.03.2017, 17:51

Ну что ж, отправил им тестовое задание, правда они требуют компиляции в VS, а у меня VS нет и качать лень, чтобы проверить, компилируется там мой вариант или нет.
Сейчас вспомнил про онлайн-компиляторы и проверил на vc++, там не заработало, пишет типа tolower не пренадлежит пространству имен std.

Похоже, не прошел я.

Добавлено через 6 минут
А, ну понятно, вместо cctype cstdlib подключил.

@ct0r · 05.03.2017, 17:53 **[ТС]**

GbaLog-, какая сложность алгоритма получилась?

@GbaLog- · 05.03.2017, 17:56

Сообщение от ct0r

какая сложность алгоритма получилась?

Ну, достаточно сложная, сейчас подумал и понял, что можно вообще все действия на 1/3 сократить, ну да ладно, уже всё отправлено, gist не изменить, насколько я понял.

@ct0r · 05.03.2017, 18:01 **[ТС]**

Сообщение от GbaLog-

достаточно сложная

Что значит достаточно сложная?)) Асимптотически сколько получилось? big-O от ???

Сообщение от GbaLog-

gist не изменить

Вообще-то легко.

Добавлено через 48 секунд

Сообщение от GbaLog-

сейчас подумал и понял, что можно вообще все действия на 1/3 сократить

Откуда привычка вначале делать, потом думать? Ужас какой

@GbaLog- · 05.03.2017, 18:11

Сообщение от ct0r

Асимптотически сколько получилось?

А, понятия не имею. Не считал, если честно. Да и как посчитать, кроме тупых проверок на время и кол-во слов в файле не знаю.

Сообщение от ct0r

Вообще-то легко.

Да, уже нашёл кнопочку.

Сообщение от ct0r

Откуда привычка вначале делать, потом думать? Ужас какой

С детства.

Croessmah · 05.03.2017, 22:27

Тоже написюкал. Проверю еще на винде завтра.
Под линуксом работает (вроде бы).
Русские символы, utf-8, все дела.

Добавлено через 21 минуту
upd: блин, забыл вывод в файл тоже в utf-8 перекатать. Шпарит в широких символах.

@ct0r · 05.03.2017, 23:35 **[ТС]**

Croessmah, как ты только такие задачки без контекста решаешь? Я вижу несколько реализаций (больше двух), каждая из которых хороша при одних условиях и плоха при других

MrGluck · 05.03.2017, 23:46

Сообщение от ct0r

Откуда привычка вначале делать, потом думать? Ужас какой

production

Добавлено через 1 минуту
Тут кстати не сказано что им важнее - скорость/размер потребляемой памяти, возможно по тестовым данным какие-нибудь ограничения есть.

Добавлено через 3 минуты

Сообщение от GbaLog-

А, понятия не имею. Не считал, если честно. Да и как посчитать, кроме тупых проверок на время и кол-во слов в файле не знаю.

Ну например берём N элементов, прикидываем что для сортировки нужно log N сравнений в среднем, итого сложность алгоритма будет N * log N (каждый элемент (всего N) сравнили log N раз).
Умение оценить асимптотическую сложность достаточно важно. И не только потому, что это спрашивают на каждом втором собеседовании.

Новичок · 06.03.2017, 00:12

Сообщение от MrGluck

прикидываем что для сортировки нужно log N сравнений в среднем,

Интересно, как так можно легко прикинуть?

Добавлено через 44 секунды
Тем более сортировки разные бывают...

Добавлено через 5 минут

Сообщение от ct0r

какая сложность алгоритма получилась?

У меня вышло что-то около len + NK log N, N - количество слов, К - максимальная длина слова, len - длина строки. Хотя мне кажется как-то бредово вышло. NK наверно на len можно заменить...

MrGluck · 06.03.2017, 02:15

Сообщение от Новичок

как так можно легко прикинуть?

Так алгоритм знать надо. Если ты являешься автором, то для своего то алгоритма можешь прикинуть. О чём и спрашивали.
Например, у обычной пузырьковой N*N (для каждого элемента линейная сложность сравнений).

Сообщение от Новичок

Тем более сортировки разные бывают...

Очевидно, что и считать надо для каждой по разному.

Croessmah · 06.03.2017, 06:00

Сообщение от ct0r

Я вижу несколько реализаций (больше двух), каждая из которых хороша при одних условиях и плоха при других

Но раз не указано что к чему,
то можем выбрать любой.

Сообщение от ct0r

как ты только такие задачки без контекста решаешь?

Да никак. Наговнокодил, сегодня проверю и отправлю.

@GbaLog- · 06.03.2017, 06:07

Сообщение от MrGluck

Ну например берём N элементов, прикидываем что для сортировки нужно log N сравнений в среднем, итого сложность алгоритма будет N * log N (каждый элемент (всего N) сравнили log N раз).

Тогда где-то N * N * log N.

Но, честно говоря, не уверен.

Сообщение от MrGluck

Умение оценить асимптотическую сложность достаточно важно.

Ну, буду учится, значит.

@_Ivana · 06.03.2017, 07:24

Писал 2 часа. Серьезно

И это безо всяких юникотов и умных выделений слов по критерию задания (последовательность букв, а не любая последовательность символов, разделенная спейсами). А все оттого, что не знаю ни С++, ни STL, ни как аргументы командной строки читать, ни как файлы читать/писать, ни как число в строку нормально переводить, ни вообще нихрена

Но стековерфлоу и сппреференс наши друзья.

ЗЫ с алгоритмом конечно никаких проблем не было. Кроме того, что он был единственный и безальтернативный

На haskell написал бы за минут 10 и в 4 строки.

@mat_for_c · 06.03.2017, 12:33

Меня похоже не должны взять, т.к.:
1. я не стал писать чтение русских букв в utf8 - ибо не знаю, как это делать (такой задачи никогда не стояло), погуглил, попробовал, что-то не получилось.
2. под линуксом я вообще никогда не сидел, поэтому тоже не знаю, как писать кроссплатформенный код под Windows/Linux (хотя онлайн компиляторы gcc съели мой код и даже не подавились).

И я так понял, что многие как раз писали с чтением utf8 и кроссплатформенный код... Ладно, посмотрим, что будет.

@ct0r · 06.03.2017, 12:47 **[ТС]**

Сообщение от Новичок

У меня вышло что-то около len + NK log N, N - количество слов, К - максимальная длина слова, len - длина строки. Хотя мне кажется как-то бредово вышло. NK наверно на len можно заменить...

Можно за O(n), если при определенных условиях памяти не жалко

@0x10 · 06.03.2017, 12:51

Не по теме:

По большому счету все равно как делать. Сойдет любой не слишком бредовый алгоритм. Контактные данные и профиль на гитхабе оставили? Для начала hr-ам и этого достаточно.

@GbaLog- · 06.03.2017, 13:06

Сообщение от mat_for_c

Меня похоже не должны взять, т.к.:
1. я не стал писать чтение русских букв в utf8 - ибо не знаю, как это делать (такой задачи никогда не стояло), погуглил, попробовал, что-то не получилось.
2. под линуксом я вообще никогда не сидел, поэтому тоже не знаю, как писать кроссплатформенный код под Windows/Linux (хотя онлайн компиляторы gcc съели мой код и даже не подавились).

Но там сказано:

Бонусные очки за поддержку русских букв в кодировке UTF-8.
Бонусные очки за портабельность Windows/Linux.

Это не обязательное условие.

@mat_for_c · 06.03.2017, 13:29

Сообщение от 0x10

Контактные данные и профиль на гитхабе оставили

Ага, причём отправлял 2 раза

- в первый раз был профиль anonimus1 (без регистрации), потом подумал, что так не солидно, решил сделать профиль и переотправил им решение.

Добавлено через 4 минуты

Сообщение от GbaLog-

Это не обязательное условие

Да, не обязательное. Но если смотреть на пост в группе вк, то желающих было очень много, и скорее всего конкуренция всё же будет и эти бонусные баллы станут решающими (имхо)

@_Ivana · 06.03.2017, 16:02

Сообщение от _Ivana

На haskell написал бы за минут 10 и в 4 строки

Дабы не быть голословным - http://rextester.com/HVYB25368 Содержательных все-таки 4 строки (если не считать импорты библиотек и тривиальную вспомогательную функцию компаратора) - но работают и русские и английские буквы, и юникот и скорее всего на Линуксе. Да здравствуют абстракции высокого порядка

@_Ivana 4817 / 2278 / 287 Регистрация: 01.03.2013 Сообщений: 5,947 Записей в блоге: 28
	06.03.2017, 07:24	14
	Писал 2 часа. Серьезно И это безо всяких юникотов и умных выделений слов по критерию задания (последовательность букв, а не любая последовательность символов, разделенная спейсами). А все оттого, что не знаю ни С++, ни STL, ни как аргументы командной строки читать, ни как файлы читать/писать, ни как число в строку нормально переводить, ни вообще нихрена Но стековерфлоу и сппреференс наши друзья. ЗЫ с алгоритмом конечно никаких проблем не было. Кроме того, что он был единственный и безальтернативный На haskell написал бы за минут 10 и в 4 строки. 0

@ct0r Игогошка! 1801 / 708 / 44 Регистрация: 19.08.2012 Сообщений: 1,367
		1
	Школа С++ для не совсем начинающих 05.03.2017, 15:51. Показов 9983. Ответов 168 Метки нет (Все метки) http://cpp-school.unigine.com/ Мне так-то наверное поздновато, но некоторым будет самый раз, ящитаю 17

@GbaLog- Любитель чаепитий 3742 / 1798 / 566 Регистрация: 24.08.2014 Сообщений: 6,016 Записей в блоге: 1
	05.03.2017, 17:51	2
	Ну что ж, отправил им тестовое задание, правда они требуют компиляции в VS, а у меня VS нет и качать лень, чтобы проверить, компилируется там мой вариант или нет. Сейчас вспомнил про онлайн-компиляторы и проверил на vc++, там не заработало, пишет типа `tolower` не пренадлежит пространству имен `std`. Похоже, не прошел я. Добавлено через 6 минут А, ну понятно, вместо `cctype` `cstdlib` подключил. 0

@ct0r Игогошка! 1801 / 708 / 44 Регистрация: 19.08.2012 Сообщений: 1,367
	05.03.2017, 17:53 [ТС]	3
	GbaLog-, какая сложность алгоритма получилась? 0

@GbaLog- Любитель чаепитий 3742 / 1798 / 566 Регистрация: 24.08.2014 Сообщений: 6,016 Записей в блоге: 1
	05.03.2017, 17:56	4
	Сообщение от ct0r какая сложность алгоритма получилась? Ну, достаточно сложная, сейчас подумал и понял, что можно вообще все действия на 1/3 сократить, ну да ладно, уже всё отправлено, gist не изменить, насколько я понял. 0

@ct0r Игогошка! 1801 / 708 / 44 Регистрация: 19.08.2012 Сообщений: 1,367
	05.03.2017, 18:01 [ТС]	5
	Сообщение от GbaLog- достаточно сложная Что значит достаточно сложная?)) Асимптотически сколько получилось? big-O от ??? Сообщение от GbaLog- gist не изменить Вообще-то легко. Добавлено через 48 секунд Сообщение от GbaLog- сейчас подумал и понял, что можно вообще все действия на 1/3 сократить Откуда привычка вначале делать, потом думать? Ужас какой 0

@GbaLog- Любитель чаепитий 3742 / 1798 / 566 Регистрация: 24.08.2014 Сообщений: 6,016 Записей в блоге: 1
	05.03.2017, 18:11	6
	Сообщение от ct0r Асимптотически сколько получилось? А, понятия не имею. Не считал, если честно. Да и как посчитать, кроме тупых проверок на время и кол-во слов в файле не знаю. Сообщение от ct0r Вообще-то легко. Да, уже нашёл кнопочку. Сообщение от ct0r Откуда привычка вначале делать, потом думать? Ужас какой С детства. 0

Croessmah Неэпический 17870 / 10635 / 2054 Регистрация: 27.09.2012 Сообщений: 26,736 Записей в блоге: 1
	05.03.2017, 22:27	7
	Тоже написюкал. Проверю еще на винде завтра. Под линуксом работает (вроде бы). Русские символы, utf-8, все дела. Добавлено через 21 минуту upd: блин, забыл вывод в файл тоже в utf-8 перекатать. Шпарит в широких символах. 0

@ct0r Игогошка! 1801 / 708 / 44 Регистрация: 19.08.2012 Сообщений: 1,367
	05.03.2017, 23:35 [ТС]	8
	Croessmah, как ты только такие задачки без контекста решаешь? Я вижу несколько реализаций (больше двух), каждая из которых хороша при одних условиях и плоха при других 0

MrGluck Форумчанин 8215 / 5045 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	05.03.2017, 23:46	9
	Сообщение от ct0r Откуда привычка вначале делать, потом думать? Ужас какой production Добавлено через 1 минуту Тут кстати не сказано что им важнее - скорость/размер потребляемой памяти, возможно по тестовым данным какие-нибудь ограничения есть. Добавлено через 3 минуты Сообщение от GbaLog- А, понятия не имею. Не считал, если честно. Да и как посчитать, кроме тупых проверок на время и кол-во слов в файле не знаю. Ну например берём N элементов, прикидываем что для сортировки нужно log N сравнений в среднем, итого сложность алгоритма будет N * log N (каждый элемент (всего N) сравнили log N раз). Умение оценить асимптотическую сложность достаточно важно. И не только потому, что это спрашивают на каждом втором собеседовании. 0

Новичок 1642 / 1091 / 487 Регистрация: 17.07.2012 Сообщений: 5,345
	06.03.2017, 00:12	10
	Сообщение от MrGluck прикидываем что для сортировки нужно log N сравнений в среднем, Интересно, как так можно легко прикинуть? Добавлено через 44 секунды Тем более сортировки разные бывают... Добавлено через 5 минут Сообщение от ct0r какая сложность алгоритма получилась? У меня вышло что-то около len + NK log N, N - количество слов, К - максимальная длина слова, len - длина строки. Хотя мне кажется как-то бредово вышло. NK наверно на len можно заменить... 0

	06.03.2017, 16:02

MrGluck Форумчанин 8215 / 5045 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	06.03.2017, 02:15	11
	Сообщение от Новичок как так можно легко прикинуть? Так алгоритм знать надо. Если ты являешься автором, то для своего то алгоритма можешь прикинуть. О чём и спрашивали. Например, у обычной пузырьковой NN (для каждого элемента линейная сложность сравнений). Сообщение от Новичок* Тем более сортировки разные бывают... Очевидно, что и считать надо для каждой по разному. 0

Croessmah Неэпический 17870 / 10635 / 2054 Регистрация: 27.09.2012 Сообщений: 26,736 Записей в блоге: 1
	06.03.2017, 06:00	12
	Сообщение от ct0r Я вижу несколько реализаций (больше двух), каждая из которых хороша при одних условиях и плоха при других Но раз не указано что к чему, то можем выбрать любой. Сообщение от ct0r как ты только такие задачки без контекста решаешь? Да никак. Наговнокодил, сегодня проверю и отправлю. 0

@GbaLog- Любитель чаепитий 3742 / 1798 / 566 Регистрация: 24.08.2014 Сообщений: 6,016 Записей в блоге: 1
	06.03.2017, 06:07	13
	Сообщение от MrGluck Ну например берём N элементов, прикидываем что для сортировки нужно log N сравнений в среднем, итого сложность алгоритма будет N * log N (каждый элемент (всего N) сравнили log N раз). Тогда где-то N * N * log N. Но, честно говоря, не уверен. Сообщение от MrGluck Умение оценить асимптотическую сложность достаточно важно. Ну, буду учится, значит. 0

@mat_for_c 223 / 213 / 80 Регистрация: 26.04.2013 Сообщений: 972
	06.03.2017, 12:33	15
	Меня похоже не должны взять, т.к.: 1. я не стал писать чтение русских букв в utf8 - ибо не знаю, как это делать (такой задачи никогда не стояло), погуглил, попробовал, что-то не получилось. 2. под линуксом я вообще никогда не сидел, поэтому тоже не знаю, как писать кроссплатформенный код под Windows/Linux (хотя онлайн компиляторы gcc съели мой код и даже не подавились). И я так понял, что многие как раз писали с чтением utf8 и кроссплатформенный код... Ладно, посмотрим, что будет. 0

@ct0r Игогошка! 1801 / 708 / 44 Регистрация: 19.08.2012 Сообщений: 1,367
	06.03.2017, 12:47 [ТС]	16
	Сообщение от Новичок У меня вышло что-то около len + NK log N, N - количество слов, К - максимальная длина слова, len - длина строки. Хотя мне кажется как-то бредово вышло. NK наверно на len можно заменить... Можно за O(n), если при определенных условиях памяти не жалко 0

@0x10
	06.03.2017, 12:51 #17
	Не по теме: По большому счету все равно как делать. Сойдет любой не слишком бредовый алгоритм. Контактные данные и профиль на гитхабе оставили? Для начала hr-ам и этого достаточно. 0

@GbaLog- Любитель чаепитий 3742 / 1798 / 566 Регистрация: 24.08.2014 Сообщений: 6,016 Записей в блоге: 1
	06.03.2017, 13:06	18
	Сообщение от mat_for_c Меня похоже не должны взять, т.к.: 1. я не стал писать чтение русских букв в utf8 - ибо не знаю, как это делать (такой задачи никогда не стояло), погуглил, попробовал, что-то не получилось. 2. под линуксом я вообще никогда не сидел, поэтому тоже не знаю, как писать кроссплатформенный код под Windows/Linux (хотя онлайн компиляторы gcc съели мой код и даже не подавились). Но там сказано: Бонусные очки за поддержку русских букв в кодировке UTF-8. Бонусные очки за портабельность Windows/Linux. Это не обязательное условие. 0

@mat_for_c 223 / 213 / 80 Регистрация: 26.04.2013 Сообщений: 972
	06.03.2017, 13:29	19
	Сообщение от 0x10 Контактные данные и профиль на гитхабе оставили Ага, причём отправлял 2 раза - в первый раз был профиль anonimus1 (без регистрации), потом подумал, что так не солидно, решил сделать профиль и переотправил им решение. Добавлено через 4 минуты Сообщение от GbaLog- Это не обязательное условие Да, не обязательное. Но если смотреть на пост в группе вк, то желающих было очень много, и скорее всего конкуренция всё же будет и эти бонусные баллы станут решающими (имхо) 0

@_Ivana 4817 / 2278 / 287 Регистрация: 01.03.2013 Сообщений: 5,947 Записей в блоге: 28
	06.03.2017, 16:02	20
	Сообщение от _Ivana На haskell написал бы за минут 10 и в 4 строки Дабы не быть голословным - http://rextester.com/HVYB25368 Содержательных все-таки 4 строки (если не считать импорты библиотек и тривиальную вспомогательную функцию компаратора) - но работают и русские и английские буквы, и юникот и скорее всего на Линуксе. Да здравствуют абстракции высокого порядка 0