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

прекалк - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.84
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.06.2011, 15:37     прекалк #1
Доброго времени суток
Знаю, что есть задачи, которые можно решить только с помощью этого прекалка.
Но что это такое - найти не могу =(
Просьба дать линки на какую-нибудь литературу по этой теме, либо объяснить на примере.
Что он делает, примерно представляю - на олимпиадные задачи отводится определенное время, обычно 1 секунда. Иногда этого недостаточно, и в таких случаях, как я понял, пишут прекалк, т.е. на этапе компиляции вычисляют все возможные значения и затем тупо находят среди них нужный. А вот как это делают - без понятия, и нагуглить ничего толкового не получается.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
18.06.2011, 16:00     прекалк #2
Вместо а = 5 + 7 пишешь а = 12. Это элементарный вариант прекалка.)
А вообще, скорее всего имеется ввиду замена "длительных" функций на предвычесленное значение. Например, создаётся таблица синусов угла и вместо вызова функции sin используется индексный доступ к массиву.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.06.2011, 16:06  [ТС]     прекалк #3
Хм... А как ее сделать на этапе компиляции
Насколько я понял, прекалком вы называете например такой код
C++
1
2
int x=sqrt(y);
for (int i=0; i < x; ++i);
Но я нашел немного другое объяснение
имеется задача - найти факториал числа N... ограничения 0<N<100. Время 0.005 сек. Короче говоря, если делать в лоб, то по времени не пройдет. НО можно заранее подсчитать все факториалы чисел до 100, проициализировать массивчик этими значениями и уже выводить готовый ответ без подсчетов. Вот такой подход называется прекалк.. может у него есть другие названия, но я их не встречал
Сомневаюсь, что можно за 0.005 сек вычислить все факториалы до 100. Значит, вычисляются они на этапе компиляции. Как такое сделать?
Или это невозможно и я ошибаюсь?
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
18.06.2011, 16:15     прекалк #4
Цитата Сообщение от diagon Посмотреть сообщение
Насколько я понял
Не правильно понял.

Например, массив синусов, о котором я сказал выше:
C++
1
2
3
float sinus[360] = { 0, 0.017452406, 0.034899496, ... /*остальные синусы до 359 градусов*/};
//В коде, вместо sin(45) пишеш
float result = sinus[45];
Добавлено через 1 минуту
Цитата Сообщение от diagon Посмотреть сообщение
омневаюсь, что можно за 0.005 сек вычислить все факториалы до 100.
Сомневаюсь, что ты сможешь вычислить !100 не используя длинную арифметику.)
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.06.2011, 16:15  [ТС]     прекалк #5
Да, спасибо, теперь дошло...
Сомневаюсь, что ты сможешь вычислить !100 не используя длинную арифметику.)
А почему бы ее не использовать?)
Есть готовый код для факториала даже.
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
18.06.2011, 16:17     прекалк #6
Цитата Сообщение от diagon Посмотреть сообщение
Сомневаюсь, что можно за 0.005 сек вычислить все факториалы до 100. Значит, вычисляются они на этапе компиляции.
метапрограммно
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.06.2011, 16:18  [ТС]     прекалк #7
Цитата Сообщение от Maxwe11 Посмотреть сообщение
метапрограммно
Хм... а поподробнее?
Где об этом можно почитать?
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
18.06.2011, 16:22     прекалк #8
примерчик в 3-м посте)
факториал в с++
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.06.2011, 16:35  [ТС]     прекалк #9
Хм... Если бы я еще ООП в с++ знал...
Отложу пока до лучших времен, на олимпиадах за прекалк, который компилятор на час загрузит, и кастрировать могут =)
Всем спасибо.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
18.06.2011, 16:37     прекалк #10
Чем тебя не устраивает прекалк в виде массива набитого ручками с калькулятором? Где в массиве ООП?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.06.2011, 16:40  [ТС]     прекалк #11
Цитата Сообщение от Deviaphan Посмотреть сообщение
Чем тебя не устраивает прекалк в виде массива набитого ручками с калькулятором? Где в массиве ООП?
Хм... тоже вариант.
Про массив я намотал на ус, не пользовался таким раньше, но нужно было именно вычисление на этапе компиляции.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
18.06.2011, 16:44     прекалк #12
diagon, а в факториале ООП причём? Шаблоны - обобщенное, а не объектно-ориентированное программирование.
Вот вам вариант без классов (если именно они вас смущают, хотя он абсолютно ничем не отличается от классов с публичными членами):

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
 
template< int N >
struct Factorial
{
    static const long long n = N * Factorial< N - 1 >::n;
};
 
template< >
struct Factorial< 0 >
{
    static const long long n = 1;
};
 
int main()
{
    long long fact5 = Factorial< 5 >::n;
    long long fact8 = Factorial< 8 >::n;
 
    std::cout << fact5 << std::endl << fact8 << std::endl;;
        
    return 0;
}
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
18.06.2011, 16:44     прекалк #13
На этапе компиляции вычисления сильно ограничены. Я не уверен, что даблы можно считать (скорее всего нельзя). С интами практически любые манипуляции делать можно, но благодаря шаблонам в основном.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.06.2011, 16:47  [ТС]     прекалк #14
Цитата Сообщение от silent_1991 Посмотреть сообщение
diagon, а в факториале ООП причём? Шаблоны - обобщенное, а не объектно-ориентированное программирование.
Шаблоны в общих чертах знаю, а классы даже не начинал(там класс Factorial используется). Ну принципы ООП немного из java знаю, но оно там намного проще, чем в с++.
На этапе компиляции вычисления сильно ограничены. Я не уверен, что даблы можно считать (скорее всего нельзя). С интами практически любые манипуляции делать можно, но благодаря шаблонам в основном.
Хм... А с вектором интов(в основном для длинной арифметики надо) как дело обстоит?
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
18.06.2011, 16:49     прекалк #15
Цитата Сообщение от diagon Посмотреть сообщение
но оно там намного проще, чем в с++
о_О. Как принципы ООП в одном языке могут быть проще, чем в другом? Само ООП от языка не зависит ни коим образом. А Java и C++ в этом плане практически близнецы.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.06.2011, 16:52  [ТС]     прекалк #16
Цитата Сообщение от silent_1991 Посмотреть сообщение
о_О. Как принципы ООП в одном языке могут быть проще, чем в другом? Само ООП от языка не зависит ни коим образом. А Java и C++ в этом плане практически близнецы.
Я про само ООП(тавтология получилась, ну да ладно)
Например, в java нету виртуальных функций, нету указателей и еще много всего, чего я не знаю=)
Просто в книге по java, которую я читаю, идет сравнение с++ с java, очень много возможностей с++ там просто вырезано.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
18.06.2011, 16:52     прекалк #17
Цитата Сообщение от diagon Посмотреть сообщение
А с вектором интов
Точно помню, что задавался этим вопросом, искал, нашёл ответ. Но т.к. это было просто любопытство, то уже не помню ответа.)
Есть подозрение, что нельзя.)
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
18.06.2011, 16:54     прекалк #18
diagon, виртуальные функции в Java есть, просто они там все виртуальные по умолчанию. Указатели с ООП ничего общего не имеют.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.06.2011, 17:04  [ТС]     прекалк #19

Не по теме:

Такое ощущение, что меня переманивают на темную сторону с++
Но в ближайшее время мне ничего, кроме процедурного программирования не понадобится, собственно и java я начал учить только из-за родной длинной арифметики=)
Лучше потрачу время на алгоритмы


Ок, спасибо, поковыряюсь с шаблонами.
silent_1991
18.06.2011, 20:16     прекалк
  #20

Не по теме:

diagon, да нет, зачем своими руками клепать конкурентов?
На самом деле я просто уточнил некоторые моменты, о которых у вас сложилось несколько неверное представление))

Yandex
Объявления
18.06.2011, 20:16     прекалк
Ответ Создать тему

Метки
прекалк
Опции темы

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