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

C++

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.64
Glacius
Сообщений: n/a
#1

Способы решения тривиальных/не тривиальных задач - C++

13.11.2010, 01:58. Просмотров 1722. Ответов 20
Метки нет (Все метки)

Други! В этой теме я предлагаю выкладывать свои способы решения тривиальных/не тривиальных задач и стремиться к элегантности их решения, то бишь к совершенству кода. Это будет способствовать повышению профессионализма и навыков кодерства. Оптимизация должна быть интересной
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.11.2010, 01:58     Способы решения тривиальных/не тривиальных задач
Посмотрите здесь:

C++ Нужна литература и примеры решения задач
C++ Пригоден ли С++ для решения однотипных задач по механике
Применение симплекс-метода для решения задач C++
C++ Информационная система для решения экономических задач
Сайты для решения задач по программированию C++
C++ Симплекс метод решения задач линейного программирования
Литература по C++ для решения вычислительных и математических задач C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
13.11.2010, 01:59     Способы решения тривиальных/не тривиальных задач #2
Glacius, Оптимизация не всегда есть элегантность и совершенство. Ненужная оптимизация - зло
Glacius
Сообщений: n/a
13.11.2010, 02:01     Способы решения тривиальных/не тривиальных задач #3
Таки давайте стремиться к предельному
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
13.11.2010, 02:19     Способы решения тривиальных/не тривиальных задач #4
Glacius, К предельному идиотизму? Ну начинайте, может кто-то и подтянеться.

Оптимизируйте swap двух чисел без использования третьей.

Задача n-ое кол-во раз была на форуме, но с чего-то ведь надо начинать.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
 
void swap(int& a, int &b)
{
    a+=b;
    b=a-b;
    a-=b;
}
 
int main()
{
    int a=10, b=5;
    swap(a, b);
    std::cout<<a<<' '<<b<<'\n';
    return 0;
}
Glacius
Сообщений: n/a
13.11.2010, 02:34     Способы решения тривиальных/не тривиальных задач #5
Вы не использовали 3-ю переменную.
Но задачу можно решить используя оператор "XOR", т.е. "^=":
C++
1
2
3
a ^= b;
b ^= a;
a ^= b;
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
13.11.2010, 02:42     Способы решения тривиальных/не тривиальных задач #6
Glacius, Верно. А можно и
C++
1
a^=b^=a^=b;
Только оптимизация ли это?
Glacius
Сообщений: n/a
13.11.2010, 02:52     Способы решения тривиальных/не тривиальных задач #7
Это один из вариантов. Но тема не столько для оптимизаций, сколько для мыслей и рассуждений.
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
13.11.2010, 02:53     Способы решения тривиальных/не тривиальных задач #8
Glacius, Намного ли быстрее работает XOR чем сложение и вычитание на современных компьютерах?
silent_1991
Эксперт С++
4956 / 3032 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
13.11.2010, 04:41     Способы решения тривиальных/не тривиальных задач #9
ForEveR, ещё можно вспомнить недавнюю тему про реверс строки - там же уже это обсуждалось - даже ассемблерный код приводился...
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
13.11.2010, 10:44     Способы решения тривиальных/не тривиальных задач #10
silent_1991, Да, я помню. Ненамного быстрее все же, насколько я понимаю.
silent_1991
Эксперт С++
4956 / 3032 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
13.11.2010, 10:47     Способы решения тривиальных/не тривиальных задач #11
Да там вроде сошлись во мнении, что практически всегда по скорости обе реализации один в один совпадают.
Glacius
Сообщений: n/a
13.11.2010, 11:07     Способы решения тривиальных/не тривиальных задач #12
Имеете ввиду что тема исчерпала себя до своего создания?
Напильнег
480 / 120 / 10
Регистрация: 30.09.2010
Сообщений: 473
13.11.2010, 11:42     Способы решения тривиальных/не тривиальных задач #13
Цитата Сообщение от ForEveR Посмотреть сообщение
Намного ли быстрее работает XOR чем сложение и вычитание на современных компьютерах?
Да и на не современных одинаково, только XOR в отличие от сложений и вычитаний переполнений и переходов через ноль не вызывает.
Kastaneda
Форумчанин
Эксперт С++
4469 / 2831 / 224
Регистрация: 12.12.2009
Сообщений: 7,201
Записей в блоге: 1
Завершенные тесты: 1
13.11.2010, 11:43     Способы решения тривиальных/не тривиальных задач #14
Цитата Сообщение от silent_1991 Посмотреть сообщение
Да там вроде сошлись во мнении, что практически всегда по скорости обе реализации один в один совпадают.
Ага, так как это делает компилятор C++.
Если бы на ассемблере писал человек, то можно было бы несколко тактов выиграть( в случае с XOR), просто компилятор гененрирует более общий вариант поставленной задачи, а человек будет подходить к этому как к частному случаю.
CheshireCat
Эксперт С++
2891 / 1240 / 78
Регистрация: 27.05.2008
Сообщений: 3,345
13.11.2010, 14:53     Способы решения тривиальных/не тривиальных задач #15
Цитата Сообщение от ForEveR Посмотреть сообщение
Код C++
1
a^=b^=a^=b;
К сожалению, это не оптимизация, а с точностью до наоборот. Хотя этот код стотыщпицот раз уже приводили как "правильный пример". Так вот, это - пример того, как не надо писать. В соответствии с точным смыслом Стандарта языка, этот код приводит к неопределенному поведению программы. А неопределенное поведение, оно такое - может, ничего не произойдет, а может и "бабахнуть".....
А по скорости в сравнении с кодом Glacius - выигрыша нет. Зато код Glacius не обладает UB.
Glacius
Сообщений: n/a
13.11.2010, 14:56     Способы решения тривиальных/не тривиальных задач #16
Цитата Сообщение от CheshireCat Посмотреть сообщение
К сожалению, это не оптимизация, а с точностью до наоборот. Хотя этот код стотыщпицот раз уже приводили как "правильный пример". Так вот, это - пример того, как не надо писать. В соответствии с точным смыслом Стандарта языка, этот код приводит к неопределенному поведению программы. А неопределенное поведение, оно такое - может, ничего не произойдет, а может и "бабахнуть".....
А по скорости в сравнении с кодом Glacius - выигрыша нет. Зато код Glacius не обладает UB.
Вопросик: что вы имеете ввиду под неопределенным поведением программы?
Kastaneda
Форумчанин
Эксперт С++
4469 / 2831 / 224
Регистрация: 12.12.2009
Сообщений: 7,201
Записей в блоге: 1
Завершенные тесты: 1
13.11.2010, 15:02     Способы решения тривиальных/не тривиальных задач #17
Цитата Сообщение от Glacius Посмотреть сообщение
что вы имеете ввиду под неопределенным поведением программы?
Имелось ввиду undefined behavior. Я вот не помню, является ли "=" точкой следования? Если нет, то это UB.

Добавлено через 1 минуту
Цитата Сообщение от Kastaneda Посмотреть сообщение
является ли "=" точкой следования?
Э, подумал - конечно же нет!
slice
32 / 75 / 4
Регистрация: 04.11.2010
Сообщений: 249
13.11.2010, 16:09     Способы решения тривиальных/не тривиальных задач #18
Где там UB? Я не понимаю.
Kastaneda
Форумчанин
Эксперт С++
4469 / 2831 / 224
Регистрация: 12.12.2009
Сообщений: 7,201
Записей в блоге: 1
Завершенные тесты: 1
13.11.2010, 16:59     Способы решения тривиальных/не тривиальных задач #19
Цитата Сообщение от slice Посмотреть сообщение
Где там UB? Я не понимаю.

Если программа пытается модифицировать одну переменную дважды не пересекая точку следования, то это ведет к undefined behavior. Так говорит Стандарт.
Имеется ввиду стандарт C++.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.11.2010, 23:49     Способы решения тривиальных/не тривиальных задач
Еще ссылки по теме:

Посоветуйте литературу для решения олимпиадных задач по программированию C++
Нужно Описание математического метода решения задач C++
C++ Составить программы для решения задач
Где взять решения задач из книги Дейтелов C++

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

Или воспользуйтесь поиском по форуму:
ForEveR
Модератор
Эксперт С++
7958 / 4720 / 319
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
13.11.2010, 23:49     Способы решения тривиальных/не тривиальных задач #20
Да, и правда. Плохой пример я кинул.
Yandex
Объявления
13.11.2010, 23:49     Способы решения тривиальных/не тривиальных задач
Ответ Создать тему
Опции темы

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