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

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

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

прекалк - C++

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

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

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