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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.84
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
#1

прекалк - C++

18.06.2011, 15:37. Просмотров 2391. Ответов 19

Доброго времени суток
Знаю, что есть задачи, которые можно решить только с помощью этого прекалка.
Но что это такое - найти не могу =(
Просьба дать линки на какую-нибудь литературу по этой теме, либо объяснить на примере.
Что он делает, примерно представляю - на олимпиадные задачи отводится определенное время, обычно 1 секунда. Иногда этого недостаточно, и в таких случаях, как я понял, пишут прекалк, т.е. на этапе компиляции вычисляют все возможные значения и затем тупо находят среди них нужный. А вот как это делают - без понятия, и нагуглить ничего толкового не получается.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
18.06.2011, 16:00     прекалк #2
Вместо а = 5 + 7 пишешь а = 12. Это элементарный вариант прекалка.)
А вообще, скорее всего имеется ввиду замена "длительных" функций на предвычесленное значение. Например, создаётся таблица синусов угла и вместо вызова функции sin используется индексный доступ к массиву.
diagon
Higher
1928 / 1194 / 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++
1286 / 1220 / 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
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.06.2011, 16:15  [ТС]     прекалк #5
Да, спасибо, теперь дошло...
Сомневаюсь, что ты сможешь вычислить !100 не используя длинную арифметику.)
А почему бы ее не использовать?)
Есть готовый код для факториала даже.
Jupiter
Каратель
Эксперт С++
6553 / 3973 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
18.06.2011, 16:17     прекалк #6
Цитата Сообщение от diagon Посмотреть сообщение
Сомневаюсь, что можно за 0.005 сек вычислить все факториалы до 100. Значит, вычисляются они на этапе компиляции.
метапрограммно
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.06.2011, 16:18  [ТС]     прекалк #7
Цитата Сообщение от Maxwe11 Посмотреть сообщение
метапрограммно
Хм... а поподробнее?
Где об этом можно почитать?
Jupiter
Каратель
Эксперт С++
6553 / 3973 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
18.06.2011, 16:22     прекалк #8
примерчик в 3-м посте)
факториал в с++
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.06.2011, 16:35  [ТС]     прекалк #9
Хм... Если бы я еще ООП в с++ знал...
Отложу пока до лучших времен, на олимпиадах за прекалк, который компилятор на час загрузит, и кастрировать могут =)
Всем спасибо.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
18.06.2011, 16:37     прекалк #10
Чем тебя не устраивает прекалк в виде массива набитого ручками с калькулятором? Где в массиве ООП?
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.06.2011, 16:40  [ТС]     прекалк #11
Цитата Сообщение от Deviaphan Посмотреть сообщение
Чем тебя не устраивает прекалк в виде массива набитого ручками с калькулятором? Где в массиве ООП?
Хм... тоже вариант.
Про массив я намотал на ус, не пользовался таким раньше, но нужно было именно вычисление на этапе компиляции.
silent_1991
Эксперт С++
4960 / 3036 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 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++
1286 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
18.06.2011, 16:44     прекалк #13
На этапе компиляции вычисления сильно ограничены. Я не уверен, что даблы можно считать (скорее всего нельзя). С интами практически любые манипуляции делать можно, но благодаря шаблонам в основном.
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
18.06.2011, 16:47  [ТС]     прекалк #14
Цитата Сообщение от silent_1991 Посмотреть сообщение
diagon, а в факториале ООП причём? Шаблоны - обобщенное, а не объектно-ориентированное программирование.
Шаблоны в общих чертах знаю, а классы даже не начинал(там класс Factorial используется). Ну принципы ООП немного из java знаю, но оно там намного проще, чем в с++.
На этапе компиляции вычисления сильно ограничены. Я не уверен, что даблы можно считать (скорее всего нельзя). С интами практически любые манипуляции делать можно, но благодаря шаблонам в основном.
Хм... А с вектором интов(в основном для длинной арифметики надо) как дело обстоит?
silent_1991
Эксперт С++
4960 / 3036 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
18.06.2011, 16:49     прекалк #15
Цитата Сообщение от diagon Посмотреть сообщение
но оно там намного проще, чем в с++
о_О. Как принципы ООП в одном языке могут быть проще, чем в другом? Само ООП от языка не зависит ни коим образом. А Java и C++ в этом плане практически близнецы.
Yandex
Объявления
18.06.2011, 16:49     прекалк
Ответ Создать тему
Опции темы

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